Нечеткий поиск в словаре с универсальным автоматом Левенштейна. Часть 1

Реализация на Java/Scala bit.ly/1QBYn79 в дополнение к списку ссылок.

Интересно, а почему вообще нужен специальный автомат? Я для правки опечаток в поисковых запросах использовал обычный трай словоформ. Словарь для трая можно использовать любой, например, все тот же словарь Зализняка из АОТ. Для нечеткого поиска в словаре используем алгоритм, схожий с обходом недетерминированного автомата. Расширяем состояние двумя атрибутами: позицией в исходной строке и штрафом за операции редактирования. В каждый момент времени обхода автомата имеется множество таких состояний. Переход для каждого состояния осуществляется соответственно операциям редактирования: для удаления символа меняем только позицию в строке в состоянии и увеличиваем штраф, для замены делаем переход по всем символам, у которых есть переходы из данного состояния, увеличиваем позицию в строке и штраф, если символ перехода не совпадает с символом в строке. Вставка похожа на замену, только позиция в строке не увеличивается.
Например, пусть с трае у нас две словоформы: мама и папа и на вход дана словоформа «ама». В начале имеет состояние { 0, 0, 0 }, с начальным номером, нулевой позицией в строке и нулевым штрафом. Переходы из начального состояния: { 0, 0, 1 } (удаление а), { 1, 0, 1 } (вставка м), { 2, 0, 1 } (вставка п), { 1, 1, 1 } (замена а на м) и { 2, 1, 1 } (замена а на п). Для каждого из этих состояний также генерируются переходы. Если мы допускаем не более одной операции редактирования, то переходы из всех состояний, кроме { 1, 0, 1 } и { 2, 0, 1 }, увеличат штрафы, а для этих состояний будет произведен переход по символу «а»: { 1, 0, 1 } --> { 3, 1, 1 } и { 2, 0, 1 } --> { 4, 1, 1 }. Это без штрафа, со штрафом также будут сгенерированы переходы с редактированием, но они не будут добавлены по порогу. В результате мы дойдем с этими двумя состояниями до символа «м». Там перехода для пути по «папа» не будет, будет произведена замена «м» на «п» со штрафом и дальше не пойдем по порогу штрафа. А вот по пути «мама» дойдем до допускающего состояния и распознаем это слово с одной операцией редактирования.
Для поисковых запросов, который состоят из множества слов, можно также делать переходы по пробелам (между словами) из допускающих состояний и переходы со вставкой пробела из допускающего состояния (когда пробел между словами в запросе пропущен).
В литературе я этого способа вычисления дистанции Левенштейна по словарю не нашел. Может, Вы подскажете, что-то такое встречалось?

Интересно, а почему вообще нужен специальный автомат?

mefrill, во втором абзаце вы тоже описали автомат. Trie это тоже специальный случай конечного автомата, причем детерминированного.