Ты когда-нибудь пробовал резать складным ножом с кучей лезвий, штопором, вилкой, пилкой и т.д? Намного неудобней чем обычный нож.
Универсальный алгоритм не может учесть правила синтаксиса конкретного вида наименований. Можно его использовать как базу для предварительного сравнения, но не как требуемый конечный алгоритм.

Как один из вариантов - предобработка наименования до сравнения (перевод в один регистр, удаление не цифробуквенных символов, приведение общепринятых сокращений к единому написанию)
Например в случае с названиями организаций (только слова с сортировкой по алфавиту):
ооо "Кристал" => КРИСТАЛ;ООО;
ООО Христалл => ООО;ХРИСТАЛ;
ООО Кристалл => КРИСТАЛ;ООО;
ООО "Пиво-Водка" => ВОДКА;ООО;ПИВО
ООО "Водка-Пиво" => ВОДКА;ООО;ПИВО
В случае с ООО Кристалл будет отловлено совпадение, а в случае ООО "Пиво-Водка" и ООО "Водка-Пиво" будет ложное совпадение

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

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

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

korsak...
Найденное решение:
http://lit999.narod.ru/soft/string.html

И как? Устраивает?

Я решал подобную проблему для наименований медикаментов, переделывал алгоритм несколько раз (начинал с чего-то похожего), и в конечном варианте родился алгоритм примерно следующий:
1. Все сопоставления делаются с эталонным базовым справочником, который должен содержать все множество наименований, причем каждое в одном экземпляре (без дублей). Все найденные совпадения сохраняются в справочнике аналогов.

2. Выполняется предобработка - наименование разбирается на слова и цифры, выискиваются все дозировки мг, мл и т.п. выбираются общепринятые сокращения и приводятся к одному виду (например таб, тбл, табл) в итого получается что-то типа:
ИсходноеПредобработанноеНафтизин капли 0.1% фл. 10млN1;Fнафтизин;V10;P0.1;Tкапли;Нафтизин капли в нос 0.1% 10млN1;Fнафтизин;V10;P0.1;Tкапли;Tназал; НАФТИЗИН 0.1% капли назал. фл. 10 млN1;Fнафтизин;V10;P0.1;Tкапли;Tназал;НАФТИЗИН капли наз. 0.05% фл. 10 млN1;Fнафтизин;V10;P0.05;Tкапли;Tназал;Суть предобработки в том, что после нее никакая полезная информация не теряется, а просто название приводится к единому написанию. Поэтому по итогам сравнения 2 и 3 написаний можно однозначно утверждать что найдено полное совпадение .

3. На основе сравнения предобработанных делается таблица возможных совпадений (например 1 вариант это не полный второй), но это одно и то же наименование или два разных может решить только оператор. Но никак не алгоритм. Соответственно эта таблица дается оператору который определяет правильно найдено совпадение или нет. Вот тут можно использовать степень похожести, например 3 и 4 отличаются дозировкой, поэтому вероятность того что это одно и то же почти нулевая. Тут просто подбирается граница похожесть ниже которой не включать в таблицу.

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

korsak...
Аналогичный случай :) Только для наименований изготовителей.


Ну тогда тот алгоритм очень кстати :) Лучше чем ничего.
А разноязычное написание: Lek, Lek d.d., Лек, Лек (Словения), Лек Д.Д.?

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

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

korsakА в таком случае как поступал? :
Настойка боярышника
Боярышник наст.100мл

ИсходноеПредобработанноеНастойка боярышника 100 млN1;Fбоярышника;V100;Tнаст;Боярышник н-ка 100млN1;Fбоярышник;V100;Tнаст;

Полного совпадения нет, обработается на этапе 3 оператором

В данном случае настойка (мазь, раствор, бальзам и т.д.) это форма выпуска (в распарсеном виде обозначается Т), сначала происходит поиск известных слов и если они найдены - из названия они убираются, так же обработка чисел и их единиц измерения. А все что осталось - нераспознанные слова, из нераспознанных берется первое как название препарата

Была еще такая мысль по поводу изготовителей (реально не реализовывал): убрать все символы кроме цифр и букв, отсортировать оставшиеся символы по алфавиту (предобработка) и сравнивать две строки по результату сравнения присваивать вес примерно так:
а. 1 польностью входит во 2 - схожесть = кол-во оставшихся символов во 2
b. остались несовпавшие и в 1 и во 2 - схожесть = (кол ост. 1 + кол ост 2) * 2
Множитель 2 это без проверки, тут надо пробовать, смотреть что получается, подбирать.

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

korsak1. как после сортировки оценивать неск. одинаковых знаков - "aa" и "aaa"?
2. имхо на фоксе будет работать очень медленно
3. как быть с разными по смыслу словами - напр. "колос от" и "соло кот"?
Повторюсь, что это только одна из нереализованных задумок, если бы начал делать вероятно алгоритм немного усложнился бы.

1 и 3 по мере накопления базы (базовый справочник и синонимы или альтернативные написания) точность поиска будет повышаться, т.к. будет увеличиваться вероятность того что наиболее похожие наименования будут иметь наибольшую схожесть.
А слов со смыслом в названиях изготовителей искать не стоит, это просто наборы букв с приятным звучанием. А так же сокращениями и опечатками операторов
Пара "aa" и "aaa" ни чем не отличается от пары "aa" и "aaб"

2. Тяжелая операция сортировка - ее достаточно проводить один раз, а затем хранить отсортированную строку вместе с исходным наименованием. А сравнение двух отсортированных наборов данных делается в один проход. Сравнение можно написать на C++ для ускорения, но думаю, фокс не намного медленнее все сделает при грамотно поставленном алгоритме.
У меня на сегодня разновидностей написания изготовителей чуть меньше 20 тыс.шт (примерно за 2 года накопилось) Думаю вполне реально делать сначала поиск полного совпадения, затем поиск полного совпадения после предобработки, а уж если не помогло, то полный перебор для поиска наиболее схожего. Думаю сравнение 1-2 тыс.шт/сек потянет любой P4, а может и еще быстрее, т.е. максимум 20 сек, а количество таких наименований, для которых будет нужен полный поиск будет резко уменьшаться с наполнением базы.

verigaИзвините, что врываюсь в разговор. У меня те же проблемы, а потому вопросы:

А как у тебя система поняла, что словосочетание "в нос" это "Тназал"? Было уже забито в справочнике общепринятых сокращений?
Как она сравнит такое:
"Таблетки от кашля 0,5г. №10"
и
"Фервекс №10шипуч.таб (от сухого кашля)"
Самые распространенные слова (словосочетания) забиты ( типа 'в нос', 'назал', 'назальный'), я ж об этом уже написал:
Dima T2. Выполняется предобработка - наименование разбирается на слова и цифры, выискиваются все дозировки мг, мл и т.п. выбираются общепринятые сокращения и приводятся к одному виду (например таб, тбл, табл) Тут только важно не перестараться, а то я сначала понаделал автозамен, а потом часть убрать пришлось.

korsakМне кажется проще все-таки вести таблицу соответствия кодов товара своего справочника и кодов поставщиков, чем каждый раз разбирать наименования.
Во всяком случае у меня такая система работает реально (в моем справочнике 15000 наименований , в таблице кодов - 100000 записей). Проще, только нет гарантии что код вообще будет, или у отправителя какой-нибудь умник решит что это наименование больше не надо и исправит на другое похожее, чтобы заново не заводить, а код останется.

korsakОтправитель с такой учетной системой недолго в бизнесе продержится :)
Это его проблемы, главное, чтобы деньги платил :)

korsakЕсли у отправителя нет кодов - можно его наименование минимально "причесывать" (напр. "тб." в "таб." и проч.) и присваивать код - напр. хэш MD5 этого наименования.

Однозначного распознавания на автомате никогда не добиться - все равно будет операторская работа (добавление вариантов в распознавалку).
Абсолютной увереннности нет, что от всех будет получены коды, а заранее вводить такие ограничения - себе проблемы создавать.
Если у тебя ситуация обстоит по-другому, то может тебе коды сподручнее использовать

Redrikhttp://www.pharmbase.com.ua/
Очень многие фирмы отказываются работать с контрагентами, которые не пользуются этой базой!
Бумажные документы сопровождаются електронными - приход товара делается моментально!

Жаль что мы не на украине У нас каждый крупный поставщик кричит "у меня справочник самый правильный" привязывайтесь ко мне. Отдельная песня сертификация, лаборатория говорит "почему название в списке сдаваемых на проверку не как в сертификате написано", а сертификат из Москвы привезли. Проблема общероссийская, подобные справочники есть, только официально узаконить их никто не хочет. Посему каждый желающий изобратает свой велосипед.

korsakМда ...
Кстати - а парафармация в этом справочнике есть?
ИМХО - Минздрав здесь ни при чем. Не надо изобретать велосипед. Для этого штрихкодирование и придумано. Ввели бы обязаловку - например чтобы в счете-фактуре обязательно стоял EAN13 товара - и все проблемы решены.

Наивный... Я тоже так думал, пока в аптеке штрихкодирование не запустил. Оказывается нормально если один изготовитель разные штрихкоды лепит на одно и тоже. Например есть два завода в словении Лек, оба выпускают один препарат, каждый бабахает свой штрихкод, а в документах "Таблетка такая-то Лек, Словения". То же помню с "зубной щеткой" какой-то было. Про наши заводы вообще молчу (корвалол какой-то одного завода 3 или 4 штрихкода). Я сначала сделал один штрихкод на одно наименование, потом переделал - на много. И аптекарям проще - приходуют "Цитрамон, Россия" а там штрихкоды всех заводов, а аптеке все-равно какой у нее цитрамон, главное что есть.

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

Redrik korsak...Ввели бы обязаловку...
+ пластиковые карточки всем! И налоги не на доходы, а на расходы! И никакого нала! Нигде...
А как же "сироты", кричащие о том, что у них нет компа, софта и т.п.?
Отвечу сам: нафик с рынка !!!
Когда я слышу от аптеки, что у них нет компа... А на дворе 2007-ой... Нафик с рынка! Redrik`а в президенты, или в министры здавоохранения накрайняк "Даешь тотальную автоматизацию всей страны! (на фоксе)"

UrriУх ты, сколько народу, оказывается, таблетками торговало! Не удивительно, фармрынок - один из лидеров по уровню автоматизации.

korsakДа, я наивный - видимо 10 лет в фармбизнесе меня ничему не научили :)
Я же не сказал что работа по штрихкодам - это сейчас реально ;-)
То что ты описал - это проблема реализации идеи, а не самой идеи.
Сама идея с EAN13, согласись , хороша.
Можно ведь иногда немножко помечтать... Мои 11 лет в фармбизнесе желание мечтать как-то сильно поубавили
Хорошо хоть вторая глобальная проблема нас не касается (это я про дороги :) )
А про EAN13 соглашусь, сказка хорошая, только, боюсь, ее реализации мы с тобой никогда не увидим

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

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

Ни один игрок на рынке никогда не будет решать проблему всего рынка, зачем улучшать условия конкурентам? Наиболее реально получить это решение от государства, только оно этим врядли займется. Поэтому нам с тобой остается подстраиваться под то что есть

korsak...
А не знаешь - как у буржуев с EAN13 дело обстоит - реально работает или как у нас - "немножко беременна"? Про буржуев не знаю, хотя тоже интересно, у них с порядком в учете получше должны дела обстоять.

Urri...
А если данный проект не ведет министерство здравоохранения, то может, найти другие пути?
Скажем, некая независимая организация могла бы создать такой классификатор. Тогда если основных игроков рынка убедить его использовать, то они бы могли работы по его поддержке и финансировать.
А теперь представь себя на месте "основных игроков рынка", приходит кто-то и говорит "давай я тебе буду говорить как справочники заполнять, а ты мне за это доплачивать", им это зачем? У каждого своя банда ИТ-шников, которые всегда под рукой, в любой момент пнул и они все быстренько сделали (как сделали вопрос другой), а тут создавать себе зависимость от кого-то за свои же деньги. В чем "пряник"? Утрировано конечно, но суть в этом. Слишком много должно быть влияния у этой организации, чтобы не просить, а заставлять на первом этапе. Кроме минздрава я никого на этом месте не вижу, а как наши власти насильно автоматизируют все по ЕГАИСу помнят :)

На самом деле достаточно ввести правила подачи сопроводительной информации (наименований) на местах контроля (таможня, лаборатории по контролю качества) единые по всей стране, и если они дружно будут требовать чтобы поставщик им писал "Цитрамон табл. 10 мг № 6", а "Цитрамон 10 мг таб. N 6" назовут несуществующим наименованием, или код из единого классификатора чтобы указывали заставят, тогда сразу все поставщики от мала до велика единообразно все сделают. Тоже красивая сказка, только кто эти органы автоматизирует? у большинства самодельный доисторический софт крутится, хотя тут можно это выдать за "повышение эффективности контроля качества лексредств", можно, например, обязать всех участников рынка, по первому требованию выдавать отчет о текущих остатках с указанием кодов из классификатора в едином электронном виде для проверки. Политики любят по теме таблеток поглумиться, очки позарабатывать предвыборные, только слишком этот вопрос технологичен, с ним в массы тяжело идти, могут не понять :)
Вот только если кто из крупных софтописателей сделает качественный софт для контролирующих госорганов и пролоббирует его использование в этих самых органах ...

Есть еще одна проблема: в аптеках все больше товаров не фармпрофиля (БАДы, косметика, минералка, салфетки и т.п.), а они идут и от тех же фармпоставщиков и от поставщиков с других рынков. Там с наименованиями вообще все плохо, занимается их контролем СЭС. Хотя с EAN13 там дела наверно получше обстоят, ведь Мега-Гигамаркетовые сети штрихкоды активно используют, а сил поставщиков понагибать у них хватает.