Задача нахождения наибольшей общей подпоследовательности, легко решается динамическим программированием:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Но у меня немного другая задача — даже наверное начну с контекста:

Даны две строки: Haystack и Needle
Needle — это точное написание труднопроизносимого слова (это номенклатурные коды, иногда похожие на слова, а иногда нет). Вобщем операторы часто ошибаются вводя их, и на операторов возможности повлиять нету.
Собственно Haystack — это то что набрал оператор. Возможно с ошибками. Но проблема в том, что от оператора приходит не сам код (иначе можно было бы считать расстояние по Дамеро-Левенштейну), а фраза, СОДЕРЖАЩАЯ код где-то посерёдке. Причём окружение кода может быть произвольным, например

Needle = "RX153-alfa";
Haystack = "Client complains about RX153afla, status is red";

Задача распознать что за код пытался ввести оператор.

Для этого у меня созрел план:

1) Найти длиннейшую общую подпоследовательность в строках Haystack и Needle: Common = "RX153aa"
2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
3) Посчитать расстояние Демеро-Левенштейна между Needle и Chunk: damlev("RX153afla","RX153-alfa") = 2; (один инсершн, и одна транспозиция) ну и соотнести с длинной Needle, вычтя полученное соотношение из 1.

Ну и отсортировать коды, по этому критерию. В каждый конкретный момент кодов не много, около 1000. Но они добавляются и удаляются.

Типа FUZZYCONTAINS(Haystack,Needle) = 1-DamLev(Chunk(Haystack,Common(Haystack,Needle)))/LEN(Needle)

И вот всё у меня вроде есть, кроме второго шага.
Как найти кратчайшую подстроку содержащую заданную подпоследовательность.
Что моё динамически-прогрммное мышление сломалось на этой задаче.
Я не вижу чего-то?
Решение за n*m*n*m — элементарное,
за n*n*m — возможно сейчас добью, но это плохо,
Товарищи, как это распилить за O(n*m) ?

Здравствуйте, Artazor, Вы писали:


A>2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
A>Товарищи, как это распилить за O(n*m) ?

Делай как в классическом алгоритме с подсчётом расстояния Левенштейна. Отличия:

• Нельзя добавлять символы;
• Нельзя заменять символы (но по прежнему есть сдвиг по совпадению);
• Можно начинать с любого символа из haystack — на соответсвующей стороне матрицы будут нули (а не 0,1,2,3,… как в Левенштейне);
• Можно закончить на любом символе из haystack (а не только в углу матрицы).

Пример модификации:

#include <vector>
#include <string>
#include <limits>
#include <iostream>

struct Cell {
    size_t cost;
    bool accept;
};

typedef std::vector<Cell> CellVector;
typedef std::vector<CellVector> CellMatrix;

size_t ld(const std::string& haystack, const std::string& common) {
    const size_t len_haystack = haystack.size();
    const size_t len_common = common.size();
    CellMatrix m(len_common + 1, CellVector(len_haystack + 1));
    const size_t inf = std::numeric_limits<size_t>::max();

    // вычисление расстояния
    for (size_t j = 0; j <= len_haystack; ++j)
        m[0][j] = Cell({0, false});
    for (size_t nc = 1; nc <= len_common; ++nc) {
        m[nc][0] = Cell({inf, false});
        char char_common = common[nc - 1];
        for (size_t j = 1; j <= len_haystack; ++j) {
            char char_haystack = haystack[j - 1];
            const Cell& skip = m[nc][j - 1];
            const Cell& shift = m[nc - 1][j - 1];
            size_t skip_cost = (skip.cost == inf) ? inf : skip.cost + 1;
            size_t shift_cost = (char_common == char_haystack) ? shift.cost : inf;
            size_t cost = std::min(inf, std::min(skip_cost, shift_cost));
            m[nc][j].cost = cost;
            m[nc][j].accept = (cost == shift_cost);
        }
    }

    // восстановление пути
    size_t hpos = 0;
    for (size_t h = 0; h <= len_haystack; ++h)
        if (m[len_common][h].cost < m[len_common][hpos].cost)
            hpos = h;
    size_t cost = m[len_common][hpos].cost;
    if (cost == inf)
        return cost;
    std::vector<size_t> indices;
    for (size_t nc = len_common; nc > 0; --nc) {
        while (1) {
            const Cell& c = m[nc][hpos--];
            if (c.accept) {
                indices.push_back(hpos);
                break;
            }
        }
    }

    // визуализация
    std::cout << haystack << std::endl;
    std::string v(len_haystack, '_');
    for (size_t i : indices)
        v[i] = haystack[i];
    std::cout << v << std::endl;
    return cost;
}

int main() {
    const char* a = "Client complains about RX153afla, status is red";
    const char* b = "RX153aa";
    size_t r = ld(a, b);
    std::cout << r << std::endl;
    return 0;
}

Зело спасибствую.
То, что нужно нести в ячейке не одно число — я сообразил, но не по-левенштейновски.
А тут всего лишь bool. Закопаю ка я его в бит чётности, и использую уже выделенную память под таблицы предыдущих шагов.
Здорово, cпасибо!

Здравствуйте, Artazor, Вы писали:

A>Зело спасибствую.
A>То, что нужно нести в ячейке не одно число — я сообразил, но не по-левенштейновски.
Достаточно одного числа. Это просто признак какое действие было совершено. Его можно вычислить на обратном проходе. Просто кода будет чуть больше. А хранить его не обязательно.
A>А тут всего лишь bool.
Ну по смыслу это не bool, конечно, а enum (или что-то другое перечислимое). Просто тут действий всего два: вставка и замена. Так например у расстояния Дамерау—Левенштейна действий четыре, поэтому если хранить, то потребуется уже два бита.

A>Для этого у меня созрел план:

A>1) Найти длиннейшую общую подпоследовательность в строках Haystack и Needle: Common = "RX153aa"
A>2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
A>3) Посчитать расстояние Демеро-Левенштейна между Needle и Chunk: damlev("RX153afla","RX153-alfa") = 2; (один инсершн, и одна транспозиция) ну и соотнести с длинной Needle, вычтя полученное соотношение из 1.
Вообще, такой подход мне не нравится. Например, он может очень плохо работать в случае появления лишних символов в needle, которые с чем-нибудь там совпадут в тексте.

A>Собственно Haystack — это то что набрал оператор. Возможно с ошибками. Но проблема в том, что от оператора приходит не сам код (иначе можно было бы считать расстояние по Дамеро-Левенштейну), а фраза, СОДЕРЖАЩАЯ код где-то посерёдке. Причём окружение кода может быть произвольным, например
Всё же лучше считай сразу расстояние Дамеро-Левенштейна между полным образцом и полным текстом. Просто возьми эти граничные условия:
WM>

• Можно начинать с любого символа из haystack — на соответсвующей стороне матрицы будут нули (а не 0,1,2,3,… как в Левенштейне);
• Можно закончить на любом символе из haystack (а не только в углу матрицы).

Эта простые модификации позволят тебе сразу найти кусок в тексте, который наиболее похож на образец.
Такой способ будет более устойчив к ошибкам в выборе общей части, чем в твоём варианте. К тому же он ещё и работать будет быстрее.

Здравствуйте, watch-maker, Вы писали:

WM>Вообще, такой подход мне не нравится. Например, он может очень плохо работать в случае появления лишних символов в needle, которые с чем-нибудь там совпадут в тексте.

Поэтому я и рассказал контекст, т.к. было весьма похоже, что всю задачу можно решить одним проходом, но я как в анекдоте про "выливаем воду из чайника, и приводим задачу к известной".

WM>Всё же лучше считай сразу расстояние Дамеро-Левенштейна между полным образцом и полным текстом. Просто возьми эти граничные условия:
WM>Можно начинать с любого символа из haystack — на соответсвующей стороне матрицы будут нули (а не 0,1,2,3,… как в Левенштейне);

Это легко.

WM>> Можно закончить на любом символе из haystack (а не только в углу матрицы)

Я правильно понимаю, что при поиске окончания, я отбрасываю начальную квадратную матрицу размера Needle (типа Needle должен быть прочитан весь)
А потом ищу минимум по последней строчке, расположенной вдоль Haystack.
Если матрицу нельзя отбросить, то результат (расстояние) — это угловой элемент.

Ну а потом уже оттуда и разматываю.
?

Здравствуйте, Artazor, Вы писали:


WM>>> Можно закончить на любом символе из haystack (а не только в углу матрицы)

A>Я правильно понимаю, что при поиске окончания, я отбрасываю начальную квадратную матрицу размера Needle (типа Needle должен быть прочитан весь)
A>А потом ищу минимум по последней строчке, расположенной вдоль Haystack.
A>Если матрицу нельзя отбросить, то результат (расстояние) — это угловой элемент.

A>Ну а потом уже оттуда и разматываю.
A>?
Не вижу необходимости в явном отбрасывании квадратной подматрицы.
Если h = |haystack|, n = |needle|. И есть матрица с расстояниями M размера (n+1)×(h+1), то задаёшь условия
m[0][j] = 0, j ∈ [0..h];
m[i][0] = i, i ∈ [0..n].
Далее, как обычно заполняешь все остальные элементы матрицы.
В последней строке m[n][1..h] будут оценки. Разумеется, из чисел m[n][1..h] нужно взять минимум. Число m[n][j] показывает расстояние от needle до подстроки haystack, которая заканчивается в позиции j. Раскручивая обратно можно узнать и начало подстроки. Хотя для задачи оценки соответствия раскручивать что-либо вообще не обязательно — значение метрики-то уже есть.

При этом рассматривать числа m[n][1..n-1] каким-либо особым образом не нужно. Хоть туда needle целиком никогда и не влезет, но значения метрики в них в любом случае будут сравнимы с длиной needle, а значит они и так не пройдут фильтрацию или ранжирование. У тебя ведь есть проверка, что расстояние Левенштейна должно быть не больше 50% (условно говоря) от n? Вот эта проверка тебе и скажет, что нет соответствия.

Здравствуйте, watch-maker, Вы писали:

Посыпаю голову пеплом: вместо m[i][0] = i, i ∈ [0..n] забил их нулями.
Вот и получил неадекват в первых ячейках результата.
И да, разматывать не нужно, метрика сразу получается.
Собственно классная функция получилась.
Оформил в виде UDF для mysql.
Что написать в авторских комментах? Как тебя упомянуть?
Потом сюда приататтчу. Пусть народ пользуется.

Здравствуйте, Artazor, Вы писали:

A>Что написать в авторских комментах?

Этой идее уже больше 30 лет. Например, это носит название semi global alignment в статье Recognition of patterns in genetic sequences. Но сам подход встречается в литературе значительно раньше. Сложно сказать кто это первым придумал.

Здравствуйте, Artazor, Вы писали:

A>Задача нахождения наибольшей общей подпоследовательности, легко решается динамическим программированием:
A>http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

A>Но у меня немного другая задача — даже наверное начну с контекста:

A>Даны две строки: Haystack и Needle
A>Needle — это точное написание труднопроизносимого слова (это номенклатурные коды, иногда похожие на слова, а иногда нет). Вобщем операторы часто ошибаются вводя их, и на операторов возможности повлиять нету.
A>Собственно Haystack — это то что набрал оператор. Возможно с ошибками. Но проблема в том, что от оператора приходит не сам код (иначе можно было бы считать расстояние по Дамеро-Левенштейну), а фраза, СОДЕРЖАЩАЯ код где-то посерёдке. Причём окружение кода может быть произвольным, например

A>Needle = "RX153-alfa";
A>Haystack = "Client complains about RX153afla, status is red";

A>Задача распознать что за код пытался ввести оператор.
...
A>Решение за n*m*n*m — элементарное,
A>за n*n*m — возможно сейчас добью, но это плохо,
A>Товарищи, как это распилить за O(n*m) ?

Все решается проще, не надо никаких матриц ДП и подпоследовательностей.
Haystack индексируешь суффиксным деревом — это O(N) по времени и памяти. Затем прогоняешь автоматон Левенштейна, сделанный из Needle и мах расстояния k, по дереву — там более хитрая временная асимптотика, но она зависит в основном от k. Таким образом получишь все похожие вхождения иглы в стоге. Для всего этого можно воспользоваться моей библиотекой.