Программа для нечеткого сравнения строк FuzzyStringComparison

05.02.16

Разработка - Инструментарий разработчика

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

Скачать файлы

Наименование Файл Версия Размер
FuzzyStringComparison.exe
.exe 520,00Kb
22
.exe 1.0 520,00Kb 22 Скачать

Что такое расстояние (метрика) Левенштейна?

В 1965 году советский математик Владимир Иосифович Левенштейн разработал алгоритм, который позволяет оценить, насколько похожа одна строка на другую. Алгоритм Левенштейна позволяет получить именно численную оценку похожести строк. Основная идея алгоритма состоит в том, чтобы посчитать минимальное количество операций удаления, вставки и замены, которые нужно сделать над одной из строк, чтобы получить вторую. Допустим, у нас есть слова Машка и Миша. Попробуем преобразовать одно слово в другое, используя только удаление, добавление и замену.

Машка Миша — исходное состояние

Мишка Миша — шаг 1 (замена)

Миша Миша — шаг 2 (удаление)

Нам потребовалось два шага, значит, расстояние Левенштейна от строки Машка до строки Миша равно 2.

Фонетический алгоритм Metaphone

Фонетические алгоритмы сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Для английского языка давно существуют и активно используются алгоритмы Soundex и Metaphone, которые создают для слова ключ, причём похожим словам или неверным написаниям одного слова будет соответствовать один ключ. Если кассир в банке наберёт вашу фамилию неверно, она всё равно получит доступ к вашей записи в базе данных, так как поиск ведётся по ключам. Например, ключ MetaPhone для Gustavson и Gustafson - KSTFS. Ключ SoundEx для тех же фамилий - G312. Уже отсюда можно видеть, что MetaPhone убирает гласные, преобразует строку в верхний регистр и пишет одну букву F вместо двух одинаково читающихся F и V. Более простой алгоритм SoundEx записывает первую букву, затем номера групп последующих согласных (B, F, P, V - первая группа; C, G, J, K, Q, S, X, Z - вторая; D, T - третья; L - четвёртая; M, N - пятая и R - шестая). Из повторяющихся номеров остаётся только один; всего записывается не более четырёх номеров.

Транслитерация кириллицы в латынь по правилам ГОСТа

RArrayL = 'абвгдеёжзийклмнопрстуфхцчшщьыъэюя';

RArrayU = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ';

arr: array[1..2, 1..ColChar] of string = (('a', 'b', 'v', 'g', 'd', 'e', 'yo', 'zh', 'z', 'i', 'y','k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'u', 'f','kh', 'ts', 'ch', 'sh', 'shch', '''', 'y', '''', 'e', 'yu', 'ya'), ('A', 'B', 'V', 'G', 'D', 'E', 'Yo', 'Zh', 'Z', 'I', 'Y','K', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'U', 'F','Kh', 'Ts', 'Ch', 'Sh', 'Shch', '''', 'Y', '''', 'E', 'Yu', 'Ya'));

Адаптация фонетического алгоритма для русского языка

Переводим всё слово в один регистр, например в нижний, и заменяем одни буквы или комбинации букв их «фонетическими соответствиями», т.е., попросту, другими буквами (много реже — комбинациями).
Приблизительная таблица «фонетических соответствий» для русского языка:

Во первых – всевозможные сдвоенные согласные. Убираем, одной вполне достаточно:

bb=b; kk=k; rr=r; cc=c; ll=l; ss=s; dd=d; mm=m; tt=t; ff=v; nn=n; zz=z; hh=h; pp=p

Далее — разнообразные шипяще-свистящие:

sh=s; zch=s ; ck=k ; ch=c ; sch=s ; ks=x; shch=s; csh=s ; ts=c; zhch=s; zh=z ; tc=c

Потом остальные фирменные фишки русского языка, такие как «ю», «я», «ё», «й», «ф» и т.п.:

yu=u; je=e; oy=oi; ju=u; oj=oi; ey=ei; ph=f; ya=a; ej=ei ; yy=i; ja=a; yo=e ; ii=i; ia=a; io=e; iy=i; ye=e; jo=e ; y=i; ie=e

Ну и прочее, оставшееся:

kh=h; gh=g; '=

Метод n-грамм, метод триад

Это семейство методов основано на следующем наблюдении: модифицированное и исходное слова должны обладать общими подстроками. Пусть, к примеру, "полоса" в результате ошибки (скажем при оптическом распознавании) трансформировалась в слово "пороса". Тогда оба слова обладают общей подстрокой: оса. В общем случае, можно использовать следующее свойство: пусть слово и получено из слова V в результате к операций редактирования (типа удаление, замена или вставка), тогда, если представить слово и в виде последовательности (k+1) подстроки, то хотя бы одна из этих подстрок будет также являться подстрокой исходного слова V.

Организация списка ключевых слов в виде инвертированного файла, в котором роль терминов играют подстроки длины n (так называемые "n-граммы"), позволяет вести поиск по сходству и по подстроке, в большинстве случаев - без сканирования словаря. Предположим, нужно найти все термины, отличающиеся от n не более чем на k операций редактирования. Представим и в виде суммы k+1 подстрок, каждая из которых не короче n. Если такое разбиение невозможно - сканируем словарь. Если же возможно - то все подстроки разбиения обладают префиксом длины n. Для каждого префикса (являющегося как раз n-граммой) нужно считать соответствующий инвертированный список (где хранятся ссылки на слова, содержащие эту n-грамму), и для каждого слова из инвертированного списка непосредственно проверить, действительно ли оно отличается от поискового термина и не более чем на к операций редактирования.

Чтобы избежать сканирования словаря в случае коротких поисковых терминов - желательно также инвертировать и "синтетические" n-граммы, то есть подстроки вида $s и i$, где s и i, соответственно, начала и окончания слов длины n-1, а $ - специальный символ, не входящий в алфавит. Модификация метода n-грамм Вилбура-Ховайко, которую сами авторы называют методом триад (используются 3-граммы или "триады"), была разработана для минимизации числа обращений к словарю. Авторы метода предложили строить полное множество терминов, имеющих общие триады с ключевыми словами запроса, но затем - с помощью весового "коэффициента похожести" терминов словаря и запроса - на этапе чтения инвертированных списков "отсекать" малоперспективные варианты (для которых коэффициент похожести будет меньше заданного порогового значения). При этом какие-то термины могут быть пропущены; налицо компромисс между эффективностью поиска и его полнотой.

Про альтернативный метод поиска в программе FuzzyStringComparison

В программе FuzzyStringComparison используется модифицированный метод триад, предложенный в 1998 году Владимиром Кива.

Предположим есть такой текст:

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

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

   Усложним процедуру, добавив проверку на присутствие 2-буквенных подстрок первого слова во втором. Потом 3-х буквенных... не пора ли остановиться? Средняя длина слова в русском языке - 6 букв. Хотите верьте, хотите нет, но перебором 3-х буквенных подстрок (ровно половина от 6) можно ограничиться. Число успешных поисков поделим на общее число подстрок - это и будет показатель сходства.

   Примеры:

   КОЛЕСО, ОКОСЕЛ. По отдельным буквам 6 попаданий из 6. 2-х буквенные: КО, ОЛ, ЛЕ, ЕС, СО - 1 из 5. 3-х буквенные: КОЛ, ОЛЕ, ЛЕС, ЕСО - 0 из 4. Результат: (6+1+0)/(6+5+4) = 0.467.

   АРБУЗ, ТАРАКАН. 2 из 5; 1 из 4; 0 из 3. Результат: 3/12 = 0.250.

   ТАРАКАН, АРБУЗ. 4 из 7; 1 из 6; 0 из 5. Результат: 5/18 = 0.278.

   Видим, что "сходство", вообще говоря, не транзитивно. Поменяв порядок сравнения, можно получить иной результат. Чтобы побороть такой эффект, будем вычислять "коэффициент сходства", усредненный по обоим словам. Общее число совпадающих подстрок разделим на общее число подстрок: (3+5)/(12+18) = 0.267.

Краткое описание программы FuzzyStringComparison

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

На вход программы подаются два файла:

файл из базы-источника (по маске Для_FuzzyStringComparison_Источник*.txt);

файл из базы-приемника (по маске Для_FuzzyStringComparison_Приемник*.txt).

Оба файла содержат строки следующего формата: Код|Наименование|, например:

в базе-источнике:

02463|ящик A-Elita Box|

16115|ящик A-Elita Sport|

31403|ящик A-Elita Sputnik|

в базе-приемнике:

26683|ящик A-Elita Sputnik|

13708|ящик A-Elita малый Sport|

21436|ящик A-Elita малый SportBeg яркий|

На выходе формируется файл: FuzzyStringComparison_Результат.txt.

Файл результата имеет строки следующего формата: Код_Приемник|Наименование_Приемник|Код_Источник;Расстояние_Левенштейна|, например:

26683|ящик A-Elita Sputnik|31403;0|16115;5|24613;6|02463;7|08040;11|21620;11|02243;12|09474;12|10807;12|15352;12|

13708|ящик A-Elita малый Sport|16115;5|02463;9|31403;10|24613;10|06966;13|03118;13|07200;13|06204;14|00447;14|19550;14| 21436|

ящик A-Elita малый SportBeg яркий|16115;13|31403;14|24613;15|02463;17|09744;19|27177;19|21620;19|04494;20|02727;20|14652;20|

Коды из базы-источника выстраиваются по возрастанию расстояния Левенштейна (0 - полное соответствие).

Количество соответствий в настоящей версии программы 10 штук.

Оценка скорости работы программы FuzzyStringComparison

При использовании только флага "Использовать алгоритм Левенштейна" при сопоставлении двух баз по 30000 строк время обработки около 4-х часов.

Качество сопоставления

Traper кормушка фидер "Methody" 25-50гр 2шт. = Traper кормушка Feeder Metody 2шт 25/30/35/40/50gr

кембрик Фламинго силикон.цветной d.1,0-2,0мм 1м. = Flamingo кембрик силикон дл.1м д.1,0-2,0мм

блесна Меппс Аглия Хэви Лонг №2Tiger = блесна Mepps Heavy Aglia Long №2 Tiger

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

Примечание

С остальными сочетаниями флагов можете экспериментировать на свое усмотрение. Но при этом важно отметить, что если снят флаг "Использовать алгорим Левенштейна", тогда используется алтернативный алгоритм (в три раза более медленный) и соответствие строк выражается в процентах (100 - полное соответствие). 

Также обращайте внимание на кодировки сравниваемых текстовых файлов (желательно использовать ANSI).

Примеры обработок 1С можно посмотреть здесь: //infostart.ru/public/442670/.

Программа для нечеткого сравнения строк FuzzyStringComparison

См. также

SALE! 20%

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

Инструментарий разработчика Роли и права Запросы СКД Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

13000 10400 руб.

02.09.2020    121599    670    389    

711

SALE! 25%

Infostart PrintWizard

Пакетная печать Печатные формы Инструментарий разработчика Платформа 1С v8.3 Запросы 1С:Зарплата и кадры бюджетного учреждения 1С:Конвертация данных 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 Платные (руб)

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

18000 15300 руб.

06.10.2023    7260    21    6    

39

SALE! 20%

Infostart УДиФ: Управление данными и формами

Инструменты администратора БД Инструментарий разработчика Роли и права Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

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

10000 8000 руб.

10.11.2023    3499    11    1    

33

SALE! 30%

PowerTools

Инструментарий разработчика Инструменты администратора БД Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Россия Платные (руб)

Универсальный инструмент программиста для администрирования конфигураций. Сборник наиболее часто используемых обработок под единым интерфейсом.

3600 2520 руб.

14.01.2013    177724    1073    0    

849

Многопоточность. Универсальный «Менеджер потоков» 2.1

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Восстановление партий или взаиморасчетов, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

5000 руб.

07.02.2018    99338    239    97    

296

[ЕХТ] Фреймворк для Расширений 1С

Инструментарий разработчика Платформа 1С v8.3 Управляемые формы Платные (руб)

"Фреймворк для Расширений 1С" это универсальное и многофункциональное решение, упрощающее разработку и поддержку создаваемых Расширений. Поставляется в виде комплекта из нескольких Расширений с открытым исходным кодом. Работает в любых Конфигурациях в режиме Управляемого приложения с режимом совместимости 8.3.12 и выше без необходимости внесения изменений в Конфигурацию.

3000 руб.

27.08.2019    18102    6    8    

39

1С HTML Шаблоны / HTML Templates

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Быстрая и удобная обработка для работы с шаблонами HTML. Позволяет легко и быстро формировать код HTML.

2040 руб.

27.12.2017    28091    3    10    

15

Выполнение произвольного кода или запроса с параметрами через Web-сервис (замена COM-подключений)

Инструментарий разработчика Обмен между базами 1C Платформа 1С v8.3 Платные (руб)

В процессе работы в 1С часто возникает потребность получить данные из другой базы.  Обычно это делается через COM-соединение, и время выполнения запроса при этом оставляет желать лучшего. В данной публикации представлено универсальное решение, позволяющее практически моментально выполнить произвольный код или запрос с параметрами в другой информационной базе через Web-сервис.

2400 руб.

24.09.2019    23595    15    15    

32
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. boln 1040 11.01.16 13:03 Сейчас в теме
Как насчет "тождества визуальных двойников" (русская В = латинская B, русская Р = латинская P, и т.п.)?
Некоторые юзеры грубо вводят наименования, допуская "визуальные двойники". Они также используются для создания ников-клонов в интернете. Лет 10 назад столкнулся с этим, намучился, пришлось специальную dll писать.
4. o2005 62 11.01.16 16:36 Сейчас в теме
(1) boln, Если ошиблись с одной буквой расстояние Левенштейна будет 1. Не тождество конечно, но очень близко.
6. CheBurator 3119 11.01.16 22:50 Сейчас в теме
(1) boln, strmatch дает похожесть с учетом фонетики
10. boln 1040 11.01.16 22:59 Сейчас в теме
(6) CheBurator, здесь фонетика как раз не всегда совпадает. Латинская P - это "п", латинская H - это "х"...
12. o2005 62 12.01.16 09:32 Сейчас в теме
(10) boln, в программе FuzzyStringComparison есть фонетический алгоритм Metaphone. И при установке флага "Использовать алгоритм Metaphone" получите результат с учетом фонетического звучания.
Следует понимать, что алгоритм Metaphone изначально создавался под английский язык. В сети существует адаптация его к русскому, но на мой взгляд (опытным путем), его работа не очень хороша. Поэтому использовал идею произвести транслитерацию и применить к полученному результату алгоритм Metaphone.
JohnyDeath; boln; +2 Ответить
2. tormozit 7136 11.01.16 13:56 Сейчас в теме
Жду реализацию на встроенном языке 1С и в виде внешней компоненты. Планирую внедрять этот алгоритм в инструмент "Поиск дублей и замена ссылок (ИР)". Может и исходники приложения опубликуешь?

Еще есть древняя ВК на похожую тему http://infostart.ru/public/237186/
3. cool.vlad4 2 11.01.16 15:49 Сейчас в теме
(2) tormozit, я эту древнюю переписал (исходники же автор выложил) частично в Native (не все методы реализовал, поскольку не нужны были) и юзаю . может дойдут руки, причешу и выложу
5. o2005 62 11.01.16 16:57 Сейчас в теме
(2) tormozit, эту библиотеку я имел в виду: "Поискав то, что есть на эту тематику, нашел библиотеку, но время работы ее абсолютно не годилось для моей задачи."
Как время будет может быть сделаю внешнюю компоненту на Native.
Исходники пока выкладывать не планирую.
Программа делалась под задачу. Пример ее использования можно посмотреть здесь http://infostart.ru/public/442670/.
7. CheBurator 3119 11.01.16 22:53 Сейчас в теме
(2) tormozit, strmatch в виде ВК нормально юзается в восьмерке.
Со strmatch я много работал/работаю - считаю работает отлично!
основное время кушается на заполнение кеша, сам поиск похожих выдает итог достаточно быстро.
8. CheBurator 3119 11.01.16 22:56 Сейчас в теме
таких сравнений я написал уже наверное вагон, простенький пример http://infostart.ru/public/14255/
можно юзать ВК strmatch.dll (выложена на портале автором, даже исходники раздавал).

и похожесть строк лучше в % показывать - народу привычнее.
Evil Beaver; +1 Ответить
11. o2005 62 12.01.16 09:20 Сейчас в теме
(8) CheBurator, в ВК strmatch.dll , как пишет автор: "Важное замечание 1. Значения, выдаваемые компонентой, это НЕ ПРОЦЕНТЫ (!!!)."
В случае моей программы, как вариант, можно использовать альтернативный алгоритм, тогда разница будет в %. Другое дело что при этом падает в 3 раза производительность.
9. CheBurator 3119 11.01.16 22:58 Сейчас в теме
По опыту "идентификации" достаточно больших неформализованных прайсов - опыт показывает, что если похожей позиции нет в первых 20 позициях - то скорее всего дальше смотреть не надо...
13. V.Nikonov 120 14.01.16 14:43 Сейчас в теме
Остался вопрос: Анализируются отдельные слова? Как обработка относится к перестановке слов в фразе? Учитывается перестановка отдельных букв? Например, [Вкусный Чай] и [Чай Вкусный] сильно похожи?
14. o2005 62 14.01.16 23:06 Сейчас в теме
(13) V.Nikonov, Анализируется фраза целиком. При этом проводится транслитерация.
Результаты программы для предложенных Вами фраз [Вкусный Чай] и [Чай Вкусный]:
- расстояние Левенштейна (без Metaphone) = 8
- расстояние Левенштейна (c Metaphone) = 2
- альтернативный алгоритм (без Metaphone) = 86 %
- альтернативный алгоритм (с Metaphone) = 83 %
Но полученные результаты не должны вводить в заблуждение, что какой-то из методов сравнения лучше чем другие. На разных примерах они показывают себя по разному.
15. Zet1313 10.02.16 15:17 Сейчас в теме
Спасибо за идею и прекрасную программу!
Но почему вы взяли старый ГОСТ по транслитерации? Например в ГОСТ Р 52535.1-2006 (который применяется для транслитерации загранпаспортов и кредитных карт) буква Ю выглядит как IU , что в общем логично с точки зрения фонетики...
16. o2005 62 10.02.16 21:16 Сейчас в теме
(15) Zet1313, на мой взгляд сложно сходу определить какой из алгоритмов транслитерации будет себя лучше показывать. Как вариант, можно внедрить в программу несколько ГОСТов транслитерации, чтобы пользователь выбирал на свое усмотрение.
Оставьте свое сообщение