Найти наилучший алгоритм приближенного матчинга

[Oleg Sychev]

Originally reported on Google Code with ID 90

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

Лучшие варианты (в порядке возрастания сложности и лучшей реализации):
1) Дамеро-Левенштейна - добавляет к расстоянию Левеншнтейна операцию перестановки двух
соседних букв;
2) на основе CCS (ближайшей общей подпоследовательности) - определяет ближайшую общую
последовательность регулярного выражения и строки, минимизируя сумму "пропущенных"
переходов в строке и автомате для получения такой последовательности - позволяет учитывать
перемещение символов (строк) на большие расстояния;
3) использовать операции добавления, удаления и перемещения символа на произвольное
расстояние и считать их сумму как цену.

Reported by oasychev on 2012-01-04 18:27:17

[Oleg Sychev]

Reported by `oasychev` on 2012-03-25 19:24:42 - Labels added: Component-Preg

[Oleg Sychev]

Есть еще проблемы с приближенным матчингом. Бывают ошибки в один символ, которые вовсе
не опечатки.

Например есть функции strspn и strcspn - их параметры идентичны, а имена отличаются
одной буквой - но смысл меняется на противоположный!

Reported by oasychev on 2013-07-02 15:02:20

[Oleg Sychev]

Релиз с приближенным матчингом сделан