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

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

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

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

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

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 этого наименования.

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