Как сравнивать строки по неполному сходству?

Question

[AlexandrMa]

На сайте есть названия товаров.
В стороннем прайс листе, эти же товары, но с отличиями в названии (запятые, тире, пробелы) и иногда слова местами поменяны.
Можно ли как-то автоматически сопоставить строки?
PS. не знаю какие теги выбрать к вопросу. Поправьте пожалуйста.

Comments

[Александр]

Это называется «нечёткое сравнение», fuzzy compare.

Быстрее будет нанять стороннего исполнителя.

[AlexandrMa]

Александр, спасибо. и не знал :)

[NewDevLab]

да нечёткий поиск, словари синонимов, нормализация.

Answer 1

[d'Ivan]

Расстояние Левенштейна или другие метрики для сравнения.

Answer 2

[Сергей Ильин]

Про расстояние Левенштейна (как базовую метрику, с которой стоит начинать) вам уже написали. Проблема начинается, как по мне, в момент, когда приходит понимание, что "слова могут быть переставлены". И тут вам придется вспомнить комбинаторику и все эти факториалы. Потому как даже для трех слов количество перестановок будет равно 3! = 6. А вы, опять же скорее всего, будете брать и сплитить вашу строку по пробелам и сравнивать каждое слово с каждым. Чувствуете возрастающую сложность?