Как реализовать поиск схожести двух строк (названия продуктов)?

Question

[rumasterov]

Добрый день.

Раздумываю над следующей задачей: есть продукты в базе и есть прайс листы, хочу реализовать хоть какой-нибудь автомаппинг продукта из базы данных к продукту из прайс листа.

Например, в базе данных есть продукт: "Apple Macbook Pro 15" и в прайсе "Apple Macbook Pro 15", "Apple Macbook Pro 14", нужно Apple Macbook Pro 15 из базы и Apple Macbook Pro 15 из прайса связать между собой.

Что я пробовал:
1. Полнотекстовый поиск MySQL, но оно с одинаковой релевантностью выдает и Apple Macbook Pro 15 и Apple Macbook Pro 14.

2. Расстояние Джаро-Винклера. Здесь сделал следующее:
Беру продукт из базы данных и разбиваю его название на слова, получаю массив. Тоже самое делаю с названием из прайса. Начинаю проходить массив из слов продукта из базы и ищу для него расстояние по алгоритму Джаро-Винклера в массиве слов продукта из прайса, если нашел расстояние больше 0.95, отмечаю что для данного слова было найдено соответствующее слово из продукта что в прайсе. Потом смотрю что для каждого слова продукта из базы было найдено соответствующее слово из продукта в прайсе и считаю их одинаковыми.

Но приемлемого результата из этого не получилось. Если например у меня продукт "Apple Macbook Pro 15", а в прайсе "Apple Macbook Pro 15 сумка синяя", то по второму пункту что я выше описал сходство будет 100%, но это абсолютно разные продукты.

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

Comments

[d'Ivan]

> "Apple Macbook Pro 15", "Apple Macbook Pro 14", вот желательно их связать между собой.
И это должен сделать поисковик без участия человека?

[d'Ivan]

Человек может искать также аксессуары по связанной тематике.

[sim3x]

не надо развибивать на слова

[d'Ivan]

Андрей Аксенов - Выбираем поисковик умом головы : https://www.youtube.com/watch?v=wcKt2eE8POM

Answer 1

[aol-nnov]

есть еще Расстояние Левенштейна .
Может, оно лучше подойдет?

Comments

[aol-nnov]

эй, кто отредактировал мой ответ??

[d'Ivan]

aol-nnov: это не я!

[xmoonlight]

aol-nnov: не, левенштейн тут - будет много меньше, чем слабоват....
посмотрите на демо по линку в моём ответе: там выводится сравнение с Левенштейном как раз есть.

Answer 2

[d'Ivan]

1. Полнотекстовый поиск MySQL, но оно с одинаковой релевантностью выдает и Apple Macbook Pro 15 и Apple Macbook Pro 14.

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

Вопрос больше по части интеллектуального поиска и обработки естественного языка, а не просто какой-то банальный SELECT.
Исходя из описания задачи я понимаю, что речь идёт о смысловом разборе текста для последующей кластеризации наименований продуктов.

Имеет смысл обратить сначала внимание на поисковой движок Sphynx со встроенным стеммингом для русского и английского языков, а также просмотреть по теме слайды докладчиков из Яндекса и других компаний.

Добавлено
Для анализа текста можно взять на вооружение Томита-парсер от Яндекса.

Томита-парсер создан для извлечения структурированных данных из текста на естественном языке. Вычленение фактов происходит при помощи контекстно-свободных грамматик и словарей ключевых слов. Парсер позволяет писать свои грамматики и добавлять словари для нужного языка. Исходный код проекта открыт и выложен на GitHub.

Answer 3

[xmoonlight]

Fuzzy Search

Answer 4

[al_gon]

Это тема называется "нечёткий поиск" или "толерантный к ошибкам поиск"или как сказали раннее Fuzzy Search.

Здесь два аспекта: чем искать (технология) и как именно искать (подход, методика).

1) Если у вас мало данных, и они легко помещаются в память то делайте поиск по инвертированному индексу в памяти.
Иначе используйте посковый индекс, напрашивается solr, elasticsearch или чистая lucene .

2) Тюнинг через один из коеффециентов похожести. Я бы посоветовал коэффициент Сёренсена (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%8D%D... ) или обратная ему мера Дайса. Расстояние Левенштейна, т.к. это редакционное расстояние решает намного медленее.

Основные шаги:

1) Очистка данных и индексация.
2) Поискоивый запрос и ранжирование по релевантности.

Answer 5

[ingerbird]

Можете еще такой вариант добавить:
https://www.postgresql.org/docs/9.1/static/pgtrgm.html
F.35.1. Trigram (or Trigraph) Concepts

A trigram is a group of three consecutive characters taken from a string. We can measure the similarity of two strings by counting the number of trigrams they share. This simple idea turns out to be very effective for measuring the similarity of words in many natural languages.

Answer 6

[Юрий]

Честное сопоставление со 100% гарантией сможет сделать только человек. тк одного анализа букв/слов не достаточно, нужен анализ по смыслу.

Сомневаюсь что вы готовы там ИИ писать. попробуйте в дополнение к названию учитывать еще и совпадение цены в неких пределах(или других аттрибутов), тогда макбук и сумка будет отдельно хотя бы.

также могу предложить захардкодить названия аксессуаров ("сумка", "чехол" и тд), если тематика товаров более менее конечная. большую часть проблем это решит.

Comments

[xmoonlight]

"захардкодить названия..." - это называется "словарная синонимизация". и это действительно решает много проблем, даже при ИИ-анализе.