С помощью каких алгоритмов реализовывается сравнение строк

[like2dev]

Исходная задача:
Есть много интернет-магазинов у каждого из них один и тот же продукт, может иметь разные названия.
Пример:

Lenovo IdeaPad U260
Ноутбук Lenovo IdeaPad U260 12.5" [59064465]
Lenovo IdeaPad U260 59064465 Intel Core i3 380UM (1.33GHz), 4096MB, 320GB, 12.5" (1366*768), DVD+/-RW, Shared VGA, Windo ws 7 Home Basic, Brown, 1.4 kg (59-064465)
IdeaPad U260 12,5" WXGA, Ci3-380UM(1,33GHz) /4Gb/320Gb/Intel HD/NO DVD/WebCam/WiFi/BT/W7HB/1,38kg, Mocha brown
Ноутбук Lenovo IdeaPad U260 i384G320B (Intel Core i3-380UM / 4096 МБ / 320 ГБ / Intel GMA HD / 12,5" / Win 7 HB)

Необходимо алгоритмы с помощью, которых система сможет определить, что на самом деле это один и тот же товар.

Такой механизм реализован в прайс-агрегаторах:

http://price.ru
http://hotline.ua

Что нашел сам: http://en.wikipedia.org/wiki/String_metric , но не уверен, что этих алгоритмов хватит для сложного анализа

[_Ivana]

Цитата:

Директор цирка: Принцем вы пленились, с ним вы Решили судьбу связать навек. Но ведь принц и Мистер Икс – Один и тот же человек!
Все: Какой позор!

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

[like2dev]

Вы хотите сказать, что все эти прайс-площадки держаться на ручной связке позиций, без никаких алгоритмов обработки?

[mustitz]

Что такое "один и тот же товар"? Даже это понятие неформализовано. Есть товары. Есть атрибуты. Какие атрибуты определяют новый товар? Какие определяют модификацию товара? Даже человек в этом без опыта запутается, а вы хотите автоматизированный общий алгоритм.

[like2dev]

Выше был приведен пример одного и того же товара, он определяется по его наименованию

[mustitz]

Примера явно недостаточно, тем более, без знаний того, как именуется продукция фирмой.

iPad 4
iPad 4 Black
iPad 4 White
Apple iPad4 32GB WiFi + 4G (LTE) black
iPad4 64GB 4G

А тут? Это все один товар или разные?

[longstreet]

like2dev, хороший вопрос! Мне самому интересны подобные алгоритмы. Есть ли у вас хоть какая-либо информация по ним?

-- 15.01.2013, 19:23 --

Может быть, тут есть какие-то варианты с самообучением? Чтобы программа сама искала товар в интернете и сравнивала спецификации...

-- 15.01.2013, 19:25 --

Ктсати, вроде что-то на фразу "нечёткое сравнение строк" гуглится.

-- 15.01.2013, 19:31 --

Нашёл такой список алгоритмов (по фамилиям авторов):

Цитата:

Левенштайн
Укконен
Кнут-Моррис-Пратт
Бойер-Мур-Хорспул
Сандей
Хьюм и Сандей
Харрисон
Карп-Рабин
Вагнер-Фишер
Хиршберг
Хант-Шиманский
Машек-Патерсон

[like2dev]

Перечисленные вами алгоритмы всеголишь облегчат поиск возможных совпадений, но не дают 100% гарантии...

[longstreet]

_Ivana и mustitz уже сказали, что в общем виде задача решения со 100% гарантией не имеет. Так что же вы хотите? Откуда у вас уверенность в том, что оно существует?

-- 16.01.2013, 00:17 --

mustitz в сообщении #671978 писал(а):

iPad 4
iPad 4 Black
iPad 4 White
Apple iPad4 32GB WiFi + 4G (LTE) black
iPad4 64GB 4G

А тут? Это все один товар или разные?

Это зависит от строки поиска. Ведь это что-то вроде несимметричной функции...
Если запрос был "Ipad 4" - то да, это всё одно и тоже.

[_Ivana]

like2dev

Цитата:

Остап Бендер: стопроцентную гарантию дает только страховой полис.

longstreet в сообщении #672142 писал(а):

Если запрос был "Ipad 4" - то да, это всё одно и тоже.

Только если запрос был регистронезависимый и пробелонеучитывающий.

[mustitz]

longstreet в сообщении #672142 писал(а):

Это зависит от строки поиска. Ведь это что-то вроде несимметричной функции...
Если запрос был "Ipad 4" - то да, это всё одно и тоже.

Я вообще в условии не видел "строки поиска". Было только "определить, где на самом деле это один и тот же товар".

[longstreet]

Тогда не хватает данных. И, чтоб вы знали, "iPad 4 Black" ни один магазин не напишет. Будет более подробная информация.

-- 16.01.2013, 22:52 --

Кстати, ЯндексМаркет с поставленной задачей справляется. Он вообще не выдаёт списка товара. Выдаёт товар и список магазинов, где его можно приобрести.

[like2dev]

Интересует, как тогда справляется с этими задачами Yandex Market, price.ru, hotline.ua ?

[longstreet]

Про wikimart я слышал, что там 30 человек в штате, которые категоризуют товар, оО

[like2dev]

Товарищ подсказал, что можно решать задачи такого типа с помощью Экспертных систем (Нечёткая логика).