Алгоритм для выделения ошибок?

Question

[windoctor]

Подскажите алгоритм для выделения ошибок.


На вводе есть два слова, одно правильное, а другое не совсем, необходимо в правильном слове подсветить буквы, которых недостает, ну и еще учесть много вещей, к примеру одна может быть пропущена.


К примеру

jahn => j^o^hn

однклассники => одн^о^классники

одноклaнсники => однокла^с^сники


Яндекс так делает yandex.ru/yandsearch?text=sphix&lr=2


За ссылки и описания буду признателен.

Answer 1

[Nicolette]

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

Answer 2

[mixermsk]

А заранее известно, что «jahn» — кривонаписанный «john»? Или известно, только то, что пара — это какое-то слово из словаря? Если первое — проще всего тупо посимвольно.
Если второе — можно попробовать поиск по маске. Например ищем аналог «reccursion»:

r*n — слишком дохрена вариантов?(+1 символ)
re*n — все еще?
re*on… и т.п.

соответственно, если не добились успеха и ошибка в крайних буквах — действовать от обратного(tecursion):
*ecursion -> *ecursio* -> *cursi* (для примера — правильный вариант найдётся в первой итерации)

Такой вариант юзабелен и для SQL-ного LIKE и для grep`a