Добрый день,
Кто-либо знает о "out-of-the-box" реализации Levenshtein DFA (детерминированные конечные автоматы) в.NET (или легко переводимый к нему)? У меня есть очень большой словарь больше чем с 160 000 различных слов, и я хочу, учитывая inicial Word w, найти все известные слова в расстоянии Левенштейна самое большее 2 из w эффективным способом.
Конечно, наличие функции, которая вычисляет все возможные редактирования при редактировании, дистанцирует один из пообещанного, и применение его снова к каждому из этих редактирований решает проблему (и симпатичным straightforwad способом). Проблемой является effiency---пообещанный 7 букв, это может уже принять 1 секунду для завершения, и мне нужно что-то намного более эффективный---, если это возможно, как это с Levenshtein DFAs, решение, которое берет O (|w |) шаги.
Править: Я знаю, что могу создать свой собственный подход к проблеме с определенным изучением, но в данный момент я не могу позволить себе читающего Schulz и статьи Mihov 60 страниц длиной.
Большое спасибо.