Определение похожести строк или фраз (алгоритм нахождения расстояния Дамерау Левенштейна)

22.12.17

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

Реализация алгоритма поиска расстояния Дамерау Левенштейна (Damerau–Levenshtein distance) для определения похожести слов или фраз.

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

Наименование Файл Версия Размер
Обработка без БСП
.epf 7,87Kb
58
.epf 7,87Kb 58 Скачать
Обработка с БСП
.epf 11,64Kb
27
.epf 11,64Kb 27 Скачать

Объясню свой интерес к алгоритму с предыстории.

Шло начало миллениума. В домашних локальных сетях популярным было общаться в IRC чатах. Чтобы как-то с интересом и пользой провести время существовали каналы с названием "BuKToPuHa", где крутился tcl бот "Знайка".

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

Бот играл за меня и делал случайные задержки между появлением вопроса и вводом ответа. Делал определенный процент ошибок, чтобы не засветиться сразу. Через какое-то время я выбился в первые позиции рейтинга. Администратор канала заподозрил неладное и начал дорабатывать алгоритм выдачи вопросов подменяя русские буквы "о,а,е,р,у,с.." на их английские аналоги, а кавычки заменяя двойными/одинарными. На простых вопросах бот работал, но на более длинных и сложных перестал находить ответы в базе. Встала задача о том как сравнить два текста вопроса на похожесть, чтобы выбрать ответ для наиболее похожего вопроса. Тогда мне эту задачу в полной мере решить не удалось, кроме того, меня перманентно забанили...

Спустя 17 лет я решил восполнить упущение и изучить тему повнимательней.

В 1С есть механизм Полнотекстового Поиска, в нем можно осуществлять "Нечеткий поиск". Тем не менее, это закрытая коробка.

Кроме того было интересно реализовать алгоритм именно на языке 1С. Надеюсь, кому-нибудь пригодится.

Тестировалось на 8.3.7.2027 и 8.3.11.2867.

UPDATE:

22.12.2017 - Добавлен вариант обработки без требования БСП

См. также

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

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

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

1 стартмани

30.01.2024    1756    stopa85    12    

33

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

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

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

19.10.2023    4427    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7466    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

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

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

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

16.12.2021    4448    fishca    13    

36

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

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

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

12.10.2021    8846    John_d    73    

46

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

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

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

31.08.2021    7813    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Dnki 4 14.12.17 23:37 Сейчас в теме
В Вашей статье совсем не прозвучала тема о полезности задачи. А между тем, я такую решал в след. проблеме:
- импортировал товары их файла. Поиск велся по коду/ артикулу / штрих-коду и т.д.
А наименования в файле только похожи на наши в базе.
- потом нужно показать результат пользователю оба наименования этими двумя колонками.
- т.к. строк много, вот тут и нужно сравнить оба наименования и цветом/ значком показать степень различия.

Мой алгоритм был простым: по количеству совпадающих слов. Так что накоплю денег и скачаю для спортивного интереса.
2. PerlAmutor 129 15.12.17 06:09 Сейчас в теме
(1) Спасибо за комментарий. Действительно, функцию можно использовать для таких вещей как автоматическое сопоставление номенклатуры предприятия и номенклатуры поставщика в той же ERP.
4. pallid 270 22.12.17 10:59 Сейчас в теме
(2)
(3)

В данном решении используется StrMatch.dll?

я помню что StrMatch.dll не работает на 64x
5. PerlAmutor 129 22.12.17 14:05 Сейчас в теме
(4) Нет, я не использовал внешние компоненты.
3. CheBurator 3119 16.12.17 00:43 Сейчас в теме
(1) успешно решается применением StrMatch.dll (работает и в 8-ке)
https://infostart.ru/public/14255/ - работает

(1),(2) обработки с такими возможностями уже есть на ИС для 8-ки, поищите.
6. echo77 1868 22.12.17 14:41 Сейчас в теме
Данная обработка написана с учетом того, что в конфигурации есть БСП, управляемые формы.
Скачал. В УПП не открывается, т.к. БСП нет
Ziggurat; +1 Ответить
7. PerlAmutor 129 22.12.17 15:54 Сейчас в теме
(6) Спасибо за замечание. Добавил вариант обработки без использования БСП.
8. Поручик 4670 24.12.17 01:11 Сейчас в теме
Алгоритм Левенштейна на 1С давно сделан
https://forum.infostart.ru/forum9/topic27268/#message369426
9. PerlAmutor 129 24.12.17 08:14 Сейчас в теме
(8) Этот пост не видел, видимо плохо искал. Тем лучше, что теперь у нас есть 2 алгоритма и "Расстояние Левенштейна" и "Расстояние Дамерау-Левенштейна" (дополненный Дамерау операцией перестановки букв).
10. AnryMc 849 22.07.19 09:12 Сейчас в теме
11. PerlAmutor 129 22.07.19 18:42 Сейчас в теме
(10) В данном случае оформление внешней обработки для возможности встраивания в справочник "Дополнительные Отчеты и Обработки", который принадлежит Библиотеке Стандартных Подсистем.
12. ikbokov 22 30.09.19 09:40 Сейчас в теме
А есть ли алгоритмы учитывающие перестановку слов?
13. PerlAmutor 129 30.09.19 20:25 Сейчас в теме
(12) На самом деле этот алгоритм можно доработать и под перестановку слов. Его суть заключается в том, что изначально создается "словарь" (каталог), уникальных символов из двух наборов данных - строка, которую надо сравнить и строка с которой идет сравнение. Раньше коды символов были в кодировке ASCII (досовской IBM866), что наталкивало программистов на простое решение - создать массив из 256 элементов, где индекс будет равен коду символа. С появлением unicode, utf-8 и utf-16 (которую использует 1С) алгоритм потребовалось немного видоизменить, т.к. возможных символов стало несколько десятков тысяч. Соответственно один символ уже не занимает фиксированное количество байт и может иметь вариативный размер. Но весь их набор на самом деле не нужно держать в памяти. Достаточно, чтобы в словаре были перечислены все уникальные значения из двух строк. Таким образом можно сделать 2 словаря и 2 проверки. Первый словарь - набор уникальных символов, второй словарь - набор уникальных слов. Таким образом первая проверка даст процент похожести двух строк в разрезе символов и их перестановок, а вторая проверка в разрезе слов и их перестановок. Два значения результата можно привести к какому-то общему.
14. ROM_1C 691 22.09.20 22:34 Сейчас в теме
Оставьте свое сообщение