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

17.05.21

Разработка - Математика и алгоритмы

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

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

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

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

Описание взято на сайте: 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.

 

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

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1757    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4432    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7474    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7859    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4451    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8849    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7814    dusha0020    8    

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

И, по-моему, даже Jek D@nielz тоже могла находить.
DrAku1a; sbcode; +2 Ответить
6. Serg1701 151 23.04.18 11:31 Сейчас в теме
(5)При желании транслитерацию в данную обработку не сложно будет добавить.
9. JohnyDeath 301 23.04.18 19:54 Сейчас в теме
(6) тут не в транслитерации дело, а именно в фонетике. Т.е. в похожести звучания двух слов/выражений
15. DrAku1a 1679 26.04.18 05:21 Сейчас в теме
(9) Кстати, хорошая идея для разработки.
21. for_sale 971 23.07.19 10:25 Сейчас в теме
(15)
Фонетика - это скользкая тропа, разработки будет очень много. Например, water, произнесённое англичанином, американцем, индусом и русским (с нашим фирменным русским акцентом) будут четыре разных слова. И это только первый уровень абстракции. Внутри самой Британии акцентов несколько десятков, разных, в Америке северозападные иногда и сами тяжело понимаю, что говорят на юговостоке и т.п.
7. onec.developer 181 23.04.18 12:34 Сейчас в теме
Хорошо бы конечно более однозначный результат выводить.. например вычислить максимальный результат и выводить %
8. Serg1701 151 23.04.18 12:52 Сейчас в теме
(7)Согласен, можно и так. На досуге попробуем.
22. apic 13 30.11.22 07:38 Сейчас в теме
(7) Разве не достаточно просто умножить результат на 100 в случае отдельного слова, что бы получить процент? В случае фразы, вычислить сначала среднеарифметическое, а потом так же умножить на 100. Это по-моему и без автора можно сделать.
10. CheBurator 3119 24.04.18 02:03 Сейчас в теме
https://infostart.ru/public/14255/ - вот моя семерочная демо на основе strmatch
на основе этой ВК я столько этих нечетких сравнений для разных клиентов и областей написал...
.
было бы, конечно, интересно провести "соревнование" (не 7 с 8 ;-), а того, как ище одно и второе.
принцип простой. на вход двух программ подаем одинаковый список допустим из 1000 наименований, в т.ч. например, наименования книг с ISBN, фармацевтики, электроники и прочее - то есть достаточно смешанный

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

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

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