Как найти общие части 2 строк при вычислении их расстояния Левенштейна

Question

Я должен выполнить нечеткое сопоставление между исходной строкой и набором шаблонных строк.Это соответствие дается формулой 1 - D (I, P) / max (длина (I), длина (P))
, где

• I - строка ввода
• P - строка шаблона
• D (I, P) - расстояние Левенштейна между I и P.

Один разЯ нашел P, который максимизирует эту оценку, я хотел бы иметь отображение между общими частями I и P

Например: если I = "воскресенье" и P = "суббота", отображение будеткак список следующих пар:
{{0, 0}, {1, 3}, {3, 5}, {4, 6}, {5, 7}}
в качестве общих символовare 's', 'u', 'd', 'a' и 'y'

В этой статье Википедии можно легко найти реализацию для вычисления расстояния Левенштейна, но этоМне не совсем понятно, как я мог получить отображение из матрицы, построенной в процессе, который он описал.Кто-нибудь может просветить меня?

спасибо

Answer 1

Отображение, которое вы приводите в качестве примера, вообще не включает в себя расстояние редактирования, как я вижу, поскольку оно просто ищет общие символы.Возможно, я вас неправильно понимаю, но вам не нужна матрица расстояний редактирования для отображения общих символов;единственный раз, когда вы будете смотреть на расстояние редактирования, будет ваш расчет D (I, P), чтобы определить самую высокую строку шаблона оценки.Чтобы сгенерировать сопоставление, которое вы дали в качестве примера, было бы просто выполнить итерацию по обеим строкам для определения индексов символов для идентификации пар.

Answer 2

Начните с двух копий одного и того же массива с именами «источник» и «пункт назначения», которые являются позициями в исходной строке, перечисленной.Удаления удаляют соответствующий элемент из обоих массивов и уменьшают следующие значения в целевом массиве.Вставки увеличивают следующие значения в массиве назначения.Затем просто заархивируйте оба массива и создайте карту.