Насколько похожи эти два слова

Question

Есть ли более точный алгоритм, чем алгоритм «Левенштейн расстояния»? http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 1

Существует Damerau–Levenshtein distance, который добавляет поддержку символьных транспозиций и обеспечивает больший охват для общих опечаток.

Чтобы получить процент сходства для Левенштейн или Damerau-Левенштейна сделать что-то вроде этого:

int relative_similarity = 1.0 - 1.0/((len(x) + len(y))/2) * lev(x, y); //untested 

В качестве альтернативы вы можете взглянуть на longest common subsequence как метрики подобия.

Далее есть

• Soundex
• Metaphone
• Double Metaphone

которые являются фонетические алгоритмы согласования.

Хотя Smith и его немецкий коллега Schmidt бы оказаться совершенно иным использованием редактирования расстояния (a.k.a Левенштейн), Саундэкс и Metaphone рассмотрит их фонетически сходные или даже эквивалентны.

---

Но без вас рассказывал нам, что неправильно о чистом расстояния Левенштейна это трудно угадать лучший алгоритм.