Алгоритм сопоставления строк

Question

Скажите, у меня есть 3 строки.А затем еще 1 строка.
Существует ли алгоритм, который позволил бы мне определить, какая из первых 3 строк соответствует 4-й строке наиболее?
просто пытаюсь найти самое близкое соответствие.
И если алгоритм уже существует в STL, это было бы неплохо.

Заранее спасибо.

Answer 1

Вы не указываете, что именно вы подразумеваете под «наиболее соответствует», поэтому я предполагаю, что у вас нет точных требований. В этом случае расстояние Левенштейна в разумной метрике. Просто вычислите расстояние Левенштейна между каждой из трех струн и четвертой и выберите ту, которая дает наименьшее расстояние.

Answer 2

Вы можете реализовать алгоритм Расстояние Левенштейна , это очень хорошая мера того, насколько близко совпадение между двумя строками у вас есть.Он измеряет, сколько нажатий клавиш нужно сделать, чтобы превратить одну строку в другую.Вы можете найти реализацию C ++ здесь .

Вычислить расстояние Левенштейна между строкой # 4 и тремя имеющимися у вас строками.Выберите строку с наименьшим расстоянием.

Answer 3

У вас есть приблизительная проблема соответствия строк.В зависимости от того, какой тип соответствия вы хотите выполнить, вы будете использовать другой алгоритм.Их много .. SOUNDEX , Яро-Винклер , Расстояние Левенштейна , метафора ... и т.д. Что касается STL, я не знаю каких-либо функций, которые реализуютэти алгоритмы, но вы можете посмотреть здесь для некоторого источника с использованием C ++.Кроме того, обратите внимание, что если вы получаете свои строки из базы данных, очень вероятно, что ваш движок базы данных реализует некоторые из этих алгоритмов (скорее всего, SOUNDEX).

Answer 4

В STL ничего не готово, но вам нужна какая-то строковая метрика.

• Используйте Расстояние Левенштейна , если строки похожи на некоторые опечатки, например, Hello против Helol.
• Используйте Расстояние Джакарта / Коэффициент Кости на множестве n-грамм, если строки могут измениться более резко, например hello world против world hello.