Pull to refresh

Comments 7

UFO landed and left these words here
Интересно, а почему вообще нужен специальный автомат? Я для правки опечаток в поисковых запросах использовал обычный трай словоформ. Словарь для трая можно использовать любой, например, все тот же словарь Зализняка из АОТ. Для нечеткого поиска в словаре используем алгоритм, схожий с обходом недетерминированного автомата. Расширяем состояние двумя атрибутами: позицией в исходной строке и штрафом за операции редактирования. В каждый момент времени обхода автомата имеется множество таких состояний. Переход для каждого состояния осуществляется соответственно операциям редактирования: для удаления символа меняем только позицию в строке в состоянии и увеличиваем штраф, для замены делаем переход по всем символам, у которых есть переходы из данного состояния, увеличиваем позицию в строке и штраф, если символ перехода не совпадает с символом в строке. Вставка похожа на замену, только позиция в строке не увеличивается.
Например, пусть с трае у нас две словоформы: мама и папа и на вход дана словоформа «ама». В начале имеет состояние { 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 это тоже специальный случай конечного автомата, причем детерминированного.
Ну да, ясное дело, что трай — это автомат. Я спрашиваю, почему просто не ходить по траю с операциями редактирования, как я описал? Зачем заводить какие-то дополнительные структуры?
Зачем заводить какие-то дополнительные структуры?

Во втором абзаце вы тоже ввели дополнительную структуру. И с точки зрения теории автоматов — это недетерминированный конечный автомат. Чтобы понять в чем его отличия от описанного в посте, нужно смотреть программную реализацию. Возможно их нет. В этом случае попробуйте перейти к детерминированному автомату — реализовать проще и работает быстрее.
Only those users with full accounts are able to leave comments. Log in, please.