Совпадение двух строк, но допускает степень ошибки

Как я могу сопоставить две строки, но в то же время учесть неправильное количество символов X в совпадении. Количество ошибок должно быть управляемой переменной.

Хотя количество символов X в строке может не совпадать, должно быть ограничение на количество запусков в последовательности. Учитывая две строки, я могу допустить, чтобы 5 символов были разными, но не более 2-х подряд.

Я ищу рекомендуемый алгоритм для сравнения этих двух строк, или, возможно, уже есть известное решение для этого.

Примерная начальная точка поиска строки - это расстояние Левенштейна . Этот алгоритм подсчитывает количество односимвольных правок (вставка, удаление и подстановка), чтобы изменить одно слово на другое.

Примером этого является kitten-> sittingкоторый имеет расстояние редактирования три

1. k itten -> s itten (заменить 's' на 'k')
2. sitt e n -> sitt i n (заменить «i» на «e»)
3. сижу -> сижу г (добавить «г» в конце)

Существуют вариации этого алгоритма, в частности расстояние Дамерау – Левенштейна, которое позволяет транспонировать два соседних символа («hte» в «the» имеет расстояние DL 1 и расстояние Левенштейна 2) и, таким образом, часто более подходит для проверка орфографии. Другие варианты существуют для приложений, где важны пробелы (последовательности ДНК).

Расстояние Левенштейна хорошо известно, и его не так уж сложно найти (у меня когда-то была причина найти его реализацию в виде функции в oracle - это было намного быстрее, чем срывать все данные и затем запускать часть кода запроса). Rosettacode имеет множество (54) реализаций расстояния Левенштейна (обратите внимание, что некоторые языки имеют это как часть строковой библиотеки - если вы делаете Java, посмотрите на язык Apache Commons Lang ). В Wikibooks есть 31 реализация, и беглый взгляд на них не показывает один и тот же код для одного и того же языка.

То, как это работает, создает матрицу, соответствующую отношениям между двумя строками:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

.Строк и столбцов представляют , что вы можете получить в целевой строке по «просто» вставить каждую букву из пустой строки. Это не идеальный случай, но он есть, чтобы заполнить алгоритм.

Если значение совпадает с этим местом ('i' == 'i'), это значение совпадает со значением по диагонали слева. Если два пятна различаются ('s'! = 'K'), значение является минимумом:

• диагональ вверх и влево + 1 (замена)
• прямо над + 1 (вставка)
• прямо налево + 1 (удаление)

Возвращаемое значение расстояния редактирования - это значение в правом нижнем углу матрицы.

Если вы следите от нижнего правого до верхнего левого с минимальным значением, вы можете увидеть сделанные изменения:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Обратите внимание, что это довольно интенсивный подход к памяти. Он может быть уменьшен в объеме памяти, если не построить полную матрицу - все, о чем заботится алгоритм - это подмножество данных, и его можно уменьшить из N*Mпространства в 2*max(N,M)пространство, просто сохранив предыдущую строку (и то, что было рассчитано для текущей строка). Code Project показывает, как это можно сделать (с помощью кода C # для загрузки).