сравнение строк с наиболее похожей строкой

Question

знает ли кто-нибудь, существует ли алгоритм, который дает одну строку A и массив строк B, сравнивает строку A со всеми строками в B, давая на выходе наиболее похожую.

Для "наиболееаналогично «Я имею в виду, например,

, если строка« А »:« Привет, мир, как дела? »

, тогда

« asdf asdewr Привет, мир, как вы? »

больше похоже на:

"h2ll4 w1111 h11 111 111"

Answer 1

Обычным измерением для этого является расстояние Левенштейна .Вычислите расстояние Левенштейна от оригинала до каждого кандидата и выберите наименьшее расстояние в качестве наиболее вероятного кандидата.

Answer 2

Определить сходство. Алгоритмы, которые могут сделать это, включают:

1. Расстояние Левенштейна / LCS / n-грамма (сравните строку с каждой из строк в вашем наборе, возьмите строку с самым низким расстоянием)
2. индексирование tf-idf
3. Автоматы Левенштейна
4. Сети Хопфилда
5. BK-деревья

Все это может быть реализовано на C или C ++. Google "сходство строк", "поиск дубликатов" или "связывание записей" для доступных метрик и алгоритмов.

Answer 3

Обычно это делается с проверкой множества вариантов имеющейся у вас строки ... взгляните на алгоритмы исправления орфографии - например, здесь