Сопоставление наименований в справочниках

#c_sharp #парсер

Не знаю с какой стороны подступиться. В учетной системе есть справочник товаров,
примерно 500тыс. есть поставщики, у каждого в прайсе в среднем 20тыс товаров. необходимо
идентифицировать в терминах нашего справочника что же там у поставщика в прайсе, т.е.
сопоставить строку в прайсе и в справочнике. понятно что руками такое не осилить. проблема
в том что у всех названия написаны по разному, к примеру ряженка 200мл и ряженка 0,2л
- это самый безобидный пример.

какие есть методики или подходы для решения таких задач ?

Перефразируя: есть большой классификатор 500тыс+ категорий и нужно определить к какой
из категорий принадлежит входящая строка.
    

Ответы

Ответ 1

Тут нужна система  которая по определённой функции подбирает наиболее похожие варианты
с коэффициентом похожести.

У этой функции может быть несколько модулей.


Модуль штрих кода. Выдаёт вариант по штрих коду, если таковой есть.
Модуль сравнения названия. Выдаёт похожие варианты по названию.
Другие модули (например анализ цветов картинки, цена в диапазоне, производитель итп.).


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

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

Про систему паттернов:

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

И то что сразу готовая система заработает речи не идёт, это постепенно доделывание
и выверение системы.

Добавлено:
Так же я рекомендую не торопиться писать код, а выверять каждый миллиметр кода. Система
которая анализирует базу из 500000 наименований тоже будет большая. Система паттернов
сравнения и модулей должна быть максимально ясной, простой, понятной, логичной и так
далее, что бы её можно было легко развивать, улучшать и так далее, так как работать
она будет долгое время.

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

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


Ответ 2

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

Для начала необходимо провести лексический анализ всех справочников - тупо выделить
лексемы по знакам препинания и пробельным символам.

После этого можно сформулировать правила формирования синтаксических конструкций,
некоторым из которых можно сопоставить одинаковую семантику. Например, после числового
литерала (который слагается либо из одиночного набора цифр, либо из двух наборов цифр,
разделённых точкой или запятой) должны идти единицы измерения, и мы все единицы приводим
к единой системе, например, к литрам. В результате 0,2 л, 0.2 л и 200 мл в результате
синтаксического анализа дадут один и тот же результат.

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


Ответ 3

данный ответ разделён на две части


"многА умных букАф" - выборка из англоязычного СО
ответ на вопрос


  какие есть методики или подходы для решения таких задач ?


структура:
Q: перевод вопроса
оригинальное название - ссылка на вопрос
A: ответ
"рассуждения"
на тему


  Сопоставление наименований в справочниках



многА умных букАф

Q: нахождение наилучшего совпадения строки

Getting the closest string match

A: реально много букАф там

а это уже ближе к простым смертным


  Вы можете найти для себя полезной данную библиотеку! http://code.google.com/p/google-diff-match-patch/
  Список поддерживаемых языков программирования Java, JavaScript, Dart, C++, C#,
Objective C, Lua и Python
  Я использую её в свих Lua проектах.  


Q: какие использовать алгоритмы для определения насколько схожи две строки

What are some algorithms for comparing how similar two strings are?

A: оригинал тут Вольный перевод:

То, что вы ищите называется String Metric algorithms. Вот ссылка на en.wikipedia.
Содержит большой список алгоритмов, однако многие со сходными характеристиками. Среди
наиболее популярных:

(->далее автор приводит список с краткой расшифровкой, которая заменена мной цитатами
из википедии<-)

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

Расстояние Хэмминга: число позиций, в которых соответствующие символы двух слов одинаковой
длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой
длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние
в метрическом пространстве) объектов одинаковой размерности.

Алгоритм Смита — Ватермана : предназначен для получения локального выравнивания последовательностей.

Коэффициент Сёренсена: бинарная мера сходства (безразмерный показатель сходства сравниваемых
объектов. Также известен под названиями «мера ассоциации», «мера подобия» и др.)

UPD:

https://ru.wikipedia.org/wiki/Список_алгоритмов#Алгоритмы_на_строках

например работа утилиты diff, предназначенной для сравнения файлов,
основана на нахождении 
наибольшей общей подпоследовательности

Diff Algorithm stackoverflow.com/q/805626

Q: лучшая библиотека для проверки орфографии C#

What is the best spell checking library for C#?

A: ответ:


NHunspell
Aspell.net




Hunspell


ru.wikipedia
stackoverflow




PostgreSQL


ru.wikipedia
ru.stackoverflow
stackoverflow





F.17. Модули словарей Hunspell
Введение в полнотекстовый поиск в PostgreSQL
Пишем расширение для PostgreSQL на примере полнотекстового поиска


рассуждения

я считаю, что алгоритм, необходимый для решения задачи, требуется всего один:
разделение исходного вопроса/проблемы на несколько "маленьких"

далее идёт поиск средства/библиотеки для решения каждого из "маленьких" вопроса

данные от поставщиков - лево -> ( средство ) <- право - наша база, справочник
                                     ^
                                     |
                 программный комплекс,библиотека, модуль


например:  


  как вариант можно попробовать нечеткий поиск, но проблему с тем что в наименование
товара входят его характеристики придется решать так или иначе


Q: строка содержит мусор, как?
A: производить поиск с право на лево

Q: как искать?
A: берём "средство" которое умеет склонять, проверять на ошибки и ищем по ключевым
словам (одно поле в "справочнике" может иметь несколько ключевых слов)
просто ищем "капусту" не делите "капусту" на "квашенную" "тушенную" "свежую" - пусть
этим занимается пользователь

Q: как пользователь будет искать по такой базе
A: для "клиента" пишется такая же программа как на "сервере", только проще!
согласитесь, ведь легче написать поисковик, чем парсер

Q: ок, а если "средство" не нашло ни "капусту" ни "капусточку" ни "капустой"
A: к ключевым словам добавляем второй критерий - имена собственные
находим словарь, в процессе пополняем своими названиями

продолжаем "разделение исходного вопроса"

a: есть поставщики
b: меняем условие на есть поставщик и решаем задачу 

категории: 

категории могут использоваться при анализе они могут быть дополнительным критерияем,
да просто сократить перебор

a: поставщик поставляет товары одной категории (только стройматериалы только продукты)
b: всё ок 

a: поставщик поставляет товары разных категории
b: просим, чтобы разделил по файлам / таблицам по категориям


Ответ 4

Я бы начал писать инструментарий для "Мепирования". Идея простая, для начала, каждая
категория из справочника имеет только своё название. Далее, по какому либо алгоритму,
строится соответствие и вычисляется вероятность импортированного наименования к категории,
и, например, показываются 5 вариантов для каждой номенклатуры. Далее человек уже решает
- а что действительно подходит. Его выбор запоминается, и для последующих импортов
учитывается. Ну а далее, если вероятность совпадения > 90% то и не спрашивает, и при
импорте выводит только те номенклатуры которые < 80% например.