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

0. PerlAmutor 106 14.12.17 09:33 Сейчас в теме
Реализация алгоритма поиска расстояния Дамерау Левенштейна (Damerau–Levenshtein distance) для определения похожести слов или фраз.

Перейти к публикации

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

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

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

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

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