Полнотекстовый нечеткий поиск с использованием алгоритма Вагнера-Фишера

[ServPonomarev]

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

[Nepherhotep]

В fuzzywuzzy есть похожая функциональность — partial_ratio, которое, в отличие от ration, ищет соответствие наилучшего вхождения в строку.

[kotbajan]

Большое спасибо, действительно похожая функция. Правда немного не подходит для моей конечной цели — находить место, где встретилось похожее слово.

[izvolov]

Во-первых, Дамерау тут и не пахнет.
Во-вторых, алгоритм не Левенштейна, а Вагнера-Фишера. Левенштейн и Дамерау-Левенштейн — это расстояния.

Скопировать из интернета и слегка подредактировать код, толком не разобравшись в том, что он делает, и как это всё вообще называется — серьёзная тема для статьи, да.

[kotbajan]

Мне не нравится ваш тон, но это не отменяет того факта, что вы правы. Подредактировал статью

[mbait]

За исключением одной детали — это алгоритм Smith-Waterman, а задача называется Local sequence alignment.

[kotbajan]

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