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

Публикация № 715698

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

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

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

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

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

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

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

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

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

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

UPDATE:

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

22

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

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

См. также

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

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

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

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

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

(1),(2) обработки с такими возможностями уже есть на ИС для 8-ки, поищите.
6. echo77 1079 22.12.17 14:41 Сейчас в теме
Данная обработка написана с учетом того, что в конфигурации есть БСП, управляемые формы.
Скачал. В УПП не открывается, т.к. БСП нет
Ziggurat; +1 Ответить
7. PerlAmutor 35 22.12.17 15:54 Сейчас в теме
(6) Спасибо за замечание. Добавил вариант обработки без использования БСП.
8. Поручик 4268 24.12.17 01:11 Сейчас в теме
9. PerlAmutor 35 24.12.17 08:14 Сейчас в теме
(8) Этот пост не видел, видимо плохо искал. Тем лучше, что теперь у нас есть 2 алгоритма и "Расстояние Левенштейна" и "Расстояние Дамерау-Левенштейна" (дополненный Дамерау операцией перестановки букв).
Оставьте свое сообщение