Как стать автором
Обновить

Комментарии 7

Прекрасно, но надо сделать следующие шаги — вычислить вероятности замены, вставки, удаления и перестановки для каждой из букв с учётом её окружения. Есть типовые опечатки (замены гласных, соседние кнопки на клавиатуре) и их шансы намного выше всех остальных возможных типов.
В fuzzywuzzy есть похожая функциональность — partial_ratio, которое, в отличие от ration, ищет соответствие наилучшего вхождения в строку.
Большое спасибо, действительно похожая функция. Правда немного не подходит для моей конечной цели — находить место, где встретилось похожее слово.
Во-первых, Дамерау тут и не пахнет.
Во-вторых, алгоритм не Левенштейна, а Вагнера-Фишера. Левенштейн и Дамерау-Левенштейн — это расстояния.

Скопировать из интернета и слегка подредактировать код, толком не разобравшись в том, что он делает, и как это всё вообще называется — серьёзная тема для статьи, да.
Мне не нравится ваш тон, но это не отменяет того факта, что вы правы. Подредактировал статью
Какая жалость, я рассчитывал назвать алгоритм своим именем… </:-)>
Определенно здорово, что алгоритмы над строками находят своё применение в биоинформатике и в других областях. Я не увдел статей на русском языке, описывающих этот алгоритм, потому ориентировался на приведенную вами ссылку. По ней алгоритм больше схож с исходным алгоритмом Вагнера-Фишера с инвертированными операциями. Т.е. путь будет искаться не по минимальному значению в ячейке, а по максимальному. Совпадение символов даст не 0 прирост, а максимальный 2. И "технические" первые строка и столбец заполняются не индексом строки/столбца, а нулём.
<:-)> Исходя из вышесказанного, у меня еще есть шанс попасть в историю!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории