Нахождение двух одинаковых строк

Question

Я ищу алгоритм, который принимает 2 строки и возвращает мне «коэффициент сходства».

По сути, у меня будет ввод с ошибками, транспонирование букв и т. Д., И я должен найти наиболее близкие совпадения в списке возможных значений.

Это не для поиска в базе данных. У меня будет в памяти список из 500 или около того строк для сравнения, все до 30 символов, поэтому он может быть относительно медленным.

Я знаю, что это существует, я видел это раньше, но я не могу вспомнить его имя.

---

Редактировать: Спасибо, что указали на Левенштейна и Хэмминга. Теперь, что я должен реализовать? Они в основном измеряют разные вещи, обе из которых могут быть использованы для того, что я хочу, но я не уверен, какая из них более подходит.

Я перечитал алгоритмы, Хэмминг, кажется, быстрее. Поскольку ни один из них не обнаружит два транспонируемых символа (т. Е. Джордан и Йодран), что, я считаю, будет распространенной ошибкой, которая будет более точной для того, что я хочу? Может кто-нибудь рассказать мне немного о компромиссах?

Answer 1

Хорошо, поэтому стандартные алгоритмы:

1) Расстояние Хэмминга Подходит только для струн одинаковой длины, но очень эффективных. В основном это просто подсчет количества различных символов. Бесполезно для нечеткого поиска текста на естественном языке.

2) Расстояние Левенштейна . Расстояние Левенштейна измеряет расстояние в терминах количества «операций», необходимых для преобразования одной строки в другую. Эти операции включают вставку, удаление и замену. Стандартный подход к вычислению расстояния Левенштейна заключается в использовании динамического программирования.

3) Обобщенный Левенштейн / (расстояние Дамерау – Левенштейна) Это расстояние также учитывает транспонирование символов в слове и, вероятно, является расстоянием редактирования, наиболее подходящим для нечеткого сопоставления введенного вручную текста. Алгоритм вычисления расстояния немного сложнее, чем расстояние Левенштейна (обнаружение транспозиции не легко). Наиболее распространенные реализации - это модификация алгоритма bitap (например, grep).

В общем, вы, вероятно, захотите рассмотреть реализацию третьего варианта, реализованного в каком-то виде поиска ближайшего соседа на основе дерева k-d

Answer 2

расстояние Дамерау-Левенштейна аналогично расстоянию Левенштейна, но также включает в себя двухсимвольную транспозицию. страница википедии (по ссылке) содержит псевдокод, который должен быть довольно простым для реализации.

Answer 3

• Расстояние Левенштейна
• Расстояние Хэмминга
• Саундэкс
• метафон

Answer 4

Вы ищете расстояние Левенштейна