Нечеткое сравнение строк. Метод Джаро-Винклера на 1С

Программирование - Теория программирования

схожесть аналоги номенклатуры похожие похожесть нечеткое сравнение метод сходство Джаро Винклер расстояние джаро строки примерный поиск рейтинг анализ алгоритм

87
Схожесть строк. Метод Джаро-Винклера. В обработке реализован алгоритм нечеткого сравнения строк.

Коротко о методе:

Описание взято на сайте: wikipedia.org.

Сходство Джаро — Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. Это вариант, который в 1999 году предложил Уильям Э. Винклер (William E. Winkler) на основе расстояния Джаро (1989, Мэтью А. Джаро, Matthew A. Jaro).

Каждый символ строки сравнивается со всеми соответствующими ему символами в . Количество совпадающих (но отличающихся порядковыми номерами) символов, которое делится на 2, определяет число транспозиций. Например, при сравнении слова CRATE со словом TRACE, только 'R' 'A' и 'Е' являются совпадающими символами, то есть m=3. Хотя 'C' и 'T' появляются в обоих строках, они дальше, чем на 1, то есть floor(5/2)-1=1. Следовательно, t=0 . В сравнении DwAyNE с DuANE соответствующие буквы находятся уже в том же самом порядке D-A-N-E, так что никаких перестановок не требуется.

Замечено, что алгоритм превосходит по производительности некоторые другие алгоритмы (например.: алгоритм "Расстояние Левенштейна").

Также присутствует функция сравнения текста по словам. Сначала обе строки разбиваются по словам. Затем поочередно сравниваются и максимальный результат сравнения идет к общему зачету. Максимально возможный результат сравнения равен 1. Соответственно общий максимальный результат может быть равен числу сравнений слов в строках. Пример: сравниваем "зеленая трава" и "трава зеленая" результат будет 2. (1+1).

 

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

Тестировалась: 1С:Предприятие 8.3 (8.3.10.2580) УТ11.3.4.93.

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

87

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

Наименование Файл Версия Размер
Метод Джаро-Винклера. Нечеткое сравнение строк.:
.epf 8,28Kb
20.04.18
50
.epf 8,28Kb 50 Скачать

См. также

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
3. onec.developer 116 23.04.18 09:45 Сейчас в теме
Можешь простыми словами объяснить, что означает результат?
4. Serg1701 94 23.04.18 10:00 Сейчас в теме
(3) Если речь идет о сравнении по словам, то результат - это сумма попарного сравнения слов в двух строках. Допустим мы сравниваем две строки: "ааа ббб ввв" и "ббб ггг ааа". Сначала из первой строки берется слово "ааа" и поочередно сравнивается со всеми словами из второй строки: "ббб"-результат =0, "ггг"-результат =0 и "ааа"-результат максимальный 1, т.к. слово идентично. К ЗАЧЕТУ в первой итерации принимается максимальный результат 1. Далее сравнение "ббб" из первой строки, результат тоже будет 1. Прибавляем с общему результату. И наконец "ввв" с результатом 0. Итого общий результат будет 2. Можно его назвать своего рода рейтингом сравнения.
А для сравнения слов между собой применяется алгоритм Джаро-Винклера, функция которого и возвращает результат от 0 до 1.
5. Evil Beaver 5377 23.04.18 10:52 Сейчас в теме
Тут старожили с "семерки" могут вспомнить внешнюю компоненту, которая делала фонетическое сравнение. Т.е. "Джек Дэниелс" и "Jack Daniels" могла сопоставить.

И, по-моему, даже Jek D@nielz тоже могла находить.
DrAku1a; sbcode; +2 Ответить
6. Serg1701 94 23.04.18 11:31 Сейчас в теме
(5)При желании транслитерацию в данную обработку не сложно будет добавить.
9. JohnyDeath 290 23.04.18 19:54 Сейчас в теме
(6) тут не в транслитерации дело, а именно в фонетике. Т.е. в похожести звучания двух слов/выражений
15. DrAku1a 1293 26.04.18 05:21 Сейчас в теме
(9) Кстати, хорошая идея для разработки.
7. onec.developer 116 23.04.18 12:34 Сейчас в теме
Хорошо бы конечно более однозначный результат выводить.. например вычислить максимальный результат и выводить %
8. Serg1701 94 23.04.18 12:52 Сейчас в теме
(7)Согласен, можно и так. На досуге попробуем.
10. CheBurator 3569 24.04.18 02:03 Сейчас в теме
https://infostart.ru/public/14255/ - вот моя семерочная демо на основе strmatch
на основе этой ВК я столько этих нечетких сравнений для разных клиентов и областей написал...
.
было бы, конечно, интересно провести "соревнование" (не 7 с 8 ;-), а того, как ище одно и второе.
принцип простой. на вход двух программ подаем одинаковый список допустим из 1000 наименований, в т.ч. например, наименования книг с ISBN, фармацевтики, электроники и прочее - то есть достаточно смешанный

далее зрители кидают нам строку. любую. в т.ч. могут и из списка кинуть точное совпадение и с вариациями разными. как захотят.
каждая прога выдает 10 наиболее похожих из списка.
судейское жюри оценивает.
проводим батл из 40-50 раундов.. ;-)
.
прикольно, а че... хоть какой-то оживляж...
(на сайте есть и другие подобные решения - их авторов тоже можно привлечь)
BigB; Serg1701; Ovkay; Gluk_1C; KEV8383; UniversaLL; Altair777; +7 Ответить
12. rpgshnik 912 24.04.18 06:03 Сейчас в теме
(10) интересно будет в рамках инфостарт ивента... не более думаю. Подкиньте идею своему другу :)
11. CheBurator 3569 24.04.18 02:04 Сейчас в теме
если что - пишите в личку.
13. Serg1701 94 24.04.18 08:54 Сейчас в теме
Поддерживаю, интересная идея
14. o2005 59 25.04.18 08:13 Сейчас в теме
Делал такое "Программа для нечеткого сравнения строк FuzzyStringComparison"
infostart.ru/public/442217/
16. DrAku1a 1293 26.04.18 05:30 Сейчас в теме
Как-то очень-очень давно (лет 10 или более назад) - делал такое... ну как делал... нашёл алгоритм то ли на SQL, то ли на C++, разобрал и сделал аналог на 1С, применил в обработках.
Сверка справочников между базами v77
и
Сверка справочников между базами 1С v8.1

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

Кстати, есть ещё нюанс по поводу сравнения - это учёт аналогичных английских букв (С, О, А, Р, В...) особенно "С" - это самая злостная клавиша на клавиатуре: например, оператор набирает не глядя на экран "Cjcbcrb", понимает что имеет место очепятка - стирает всё, кроме первой буквы (она то нормальная "С") и далее пишет "Cосиски". Довольно частое явление.
17. viptextil1 13 26.04.18 11:53 Сейчас в теме
18. Leon75 13.06.18 18:14 Сейчас в теме
19. PerlAmutor 33 16.06.18 07:02 Сейчас в теме
https://infostart.ru/public/715698/ - тоже когда-то делал, но на базе алгоритма нахождения расстояния Дамерау Левенштейна.
20. German_Tagil 6 18.06.18 19:59 Сейчас в теме
надо посмотреть - искал что-то подобное с год назад
надо было номенклатуру для заявок из Экселя подобрать
пришел к выводу что ручками снабженцы быстрее набьют
но мысль осталась
Оставьте свое сообщение