gifts2017

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

Опубликовал o2005 (o2005) в раздел Программирование - Инструментарий

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

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

В 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С можно посмотреть здесь: http://infostart.ru/public/442670/.

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Николай Больсунов (boln) 11.01.16 13:03
Как насчет "тождества визуальных двойников" (русская В = латинская B, русская Р = латинская P, и т.п.)?
Некоторые юзеры грубо вводят наименования, допуская "визуальные двойники". Они также используются для создания ников-клонов в интернете. Лет 10 назад столкнулся с этим, намучился, пришлось специальную dll писать.
2. Сергей Старых (tormozit) 11.01.16 13:56
Жду реализацию на встроенном языке 1С и в виде внешней компоненты. Планирую внедрять этот алгоритм в инструмент "Поиск дублей и замена ссылок (ИР)". Может и исходники приложения опубликуешь?

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

и похожесть строк лучше в % показывать - народу привычнее.
Evil Beaver; +1 Ответить 1
9. Сергей (Che) Коцюра (CheBurator) 11.01.16 22:58
По опыту "идентификации" достаточно больших неформализованных прайсов - опыт показывает, что если похожей позиции нет в первых 20 позициях - то скорее всего дальше смотреть не надо...
10. Николай Больсунов (boln) 11.01.16 22:59
(6) CheBurator, здесь фонетика как раз не всегда совпадает. Латинская P - это "п", латинская H - это "х"...
11. o2005 (o2005) 12.01.16 09:20
(8) CheBurator, в ВК strmatch.dll , как пишет автор: "Важное замечание 1. Значения, выдаваемые компонентой, это НЕ ПРОЦЕНТЫ (!!!)."
В случае моей программы, как вариант, можно использовать альтернативный алгоритм, тогда разница будет в %. Другое дело что при этом падает в 3 раза производительность.
12. o2005 (o2005) 12.01.16 09:32
(10) boln, в программе FuzzyStringComparison есть фонетический алгоритм Metaphone. И при установке флага "Использовать алгоритм Metaphone" получите результат с учетом фонетического звучания.
Следует понимать, что алгоритм Metaphone изначально создавался под английский язык. В сети существует адаптация его к русскому, но на мой взгляд (опытным путем), его работа не очень хороша. Поэтому использовал идею произвести транслитерацию и применить к полученному результату алгоритм Metaphone.
JohnyDeath; boln; +2 Ответить
13. Вадим Никонов (V.Nikonov) 14.01.16 14:43
Остался вопрос: Анализируются отдельные слова? Как обработка относится к перестановке слов в фразе? Учитывается перестановка отдельных букв? Например, [Вкусный Чай] и [Чай Вкусный] сильно похожи?
14. o2005 (o2005) 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 (o2005) 10.02.16 21:16
(15) Zet1313, на мой взгляд сложно сходу определить какой из алгоритмов транслитерации будет себя лучше показывать. Как вариант, можно внедрить в программу несколько ГОСТов транслитерации, чтобы пользователь выбирал на свое усмотрение.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа