Нечеткий поиск в справочнике. Версия 1.02

Опубликовал - - (sleeping07) в раздел Администрирование - Поиск данных

Для целей автоматического сопоставления справочников из разных баз данных при загрузке табличных частей документов была написана эта функция,  к которой в итоге был прикручен визуальный интерфейс. На практике вполне оправдала себя и позволила за разумное время автоматически заполнять большие документы.

В основе лежит функция нечеткого сравнения, разбивающая искомую строку на части, последовательно уменьшающиеся в длине, начиная с полной длины искомого, и ищущая совпадение в строке сравнения. Если совпадение найдено, совпадающие части удаляются из обеих строк, и происходит рекурсивное обращение к самой себе с накоплением результатов совпадения вплоть до размера искомых строк в 2 символа.

Результатом является рейтинг совпадения, который потом переводится в %. Параметрами же самой функции поиска является в том числе значение требуемой достоверности, а также временной таймаут, а возвращает она в случае успеха ссылку на элемент справочника.

Процедура написана на языке 1С, потому не является оптимизированной по скорости, но со своими задачами вполне справляется на справочнике порядка 7000 элементов.

Для интерактивного ее варианта (и отладки) было добавлено отображение списка 20 лучших результатов с рейтингами и подстроками совпадения.

История версий:

1.02

  • Отбор без групп удален из запроса, выведен в цикл перебора результатов (вызывал ошибку в справочниках без групп)
  • Достоверность по умолчанию установлена в 80% (при 0% - была ошибка)
  • Убрано прерывание поиска в случае 100% совпадения

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

Наименование Файл Версия Размер
Нечеткий поиск в справочнике 1.02
.erf 10,76Kb
19.02.16
26
.erf 10,76Kb 26 Скачать

См. также

Добавить вознаграждение
Комментарии
1. Андрей Карпов (karpik666) 334 20.01.16 07:48 Сейчас в теме
А замер времени такой операции производился?
2. - - (sleeping07) 21 20.01.16 08:00 Сейчас в теме
Ну, по факту - конечно. Зависит от размера справочника линейно и в большей степени от длины строки сравнения. Запрос оптимизирован для ускоренного поиска по подобию началу строки поиска, в реальных условиях это помогает в большинстве случаев, тогда скорость поиска в пределах единиц секунд, если же случай сложный, то перебираются все остальные варианты, время в таком случае может достигать десятков секунд. Запрос выглядит так:
Запрос=Новый Запрос("ВЫБРАТЬ
| Справочник.Наименование КАК Наименование,
| Справочник.Ссылка,
| Выбор Когда (Справочник.Наименование Подобно &Начало)
| Тогда 0 Иначе 1 Конец КАК Подобие
| ИЗ Справочник."+Справочник+" КАК Справочник
| ГДЕ
| НЕ Справочник.ПометкаУдаления
| И НЕ Справочник.ЭтоГруппа
|УПОРЯДОЧИТЬ ПО
| Подобие, Наименование");
Запрос.УстановитьПараметр("Начало","%"+Сред(Искомое,1,5)+"%");
3. Андрей Карпов (karpik666) 334 20.01.16 08:11 Сейчас в теме
(2) sleeping07, ааа, то есть просто запрос на подобно, а если в фразе несколько слов, то вначале разбиваете строку на слова, и каждое слово ищете на подобно, а затем получаете результат, который соответствует обоим вариантам?
4. - - (sleeping07) 21 20.01.16 08:19 Сейчас в теме
Нет, процедура сравнения всегда одинаковая - с разбиением на части (не на слова, перед сравнением все пробелы, спецсимволы убираются), просто из предположения, что совпадающие с началом строки поиска более вероятны, позволяет поиск ускорить в большинстве случаев.
5. Вадим Никонов (V.Nikonov) 113 22.01.16 12:40 Сейчас в теме
Что то при поиске Номенклатуры выглядит неубедительно...
Хочется получить статистику сравнительного анализа способов поиска...
6. - - (sleeping07) 21 22.01.16 13:03 Сейчас в теме
V.Nikonov, какую достоверность ставите? У меня все находило на автомате при значении порядка 60% при загрузке табличной части из другой базы с похожей, но все же местами отличающейся наименованиями номенлатурой.
UPD: вот попробовал с номенклатурой
Прикрепленные файлы:
7. Сергей (Che) Коцюра (CheBurator) 3367 24.01.16 20:19 Сейчас в теме
А почему бы не было сделать с использованием проверенной и зарекомендовавшей себя strmatch.dll..?
8. - - (sleeping07) 21 24.01.16 20:57 Сейчас в теме
(7) CheBurator, а зачем, собственно? Интересно было реализовать именно на языке 1С. Сама функция сравнения небольшая, симпатичная, рекурсивная. Не черный ящик, все можно подстроить. Это приложение конечно малоприменимо на практике, только для демонстрации, но и в реале функция уже поработала, и сейчас на ее основе закончил обработку сравнения-сопоставления таблиц - весьма работоспособна.
9. Ольга Немешева (kn) 22 19.02.16 11:32 Сейчас в теме
Добрый день.
1. При поиске в демо базе Ботинки женские обработка находит только в справочнике Номенклатура Ботинки женские демисезонные, хотя в справочнике есть и Ботинки женские натуральная кожа, т.е не совсем рабочий алгоритм.
2. При вводе в поле Ищем данных пишет Ошибка деления на ноль.
10. - - (sleeping07) 21 19.02.16 12:52 Сейчас в теме
(9) kn, спасибо за замечание! Устранил, сейчас выложу изменения. Дело в том, что изначально поиск предназначался для поиска одного подходящего значения, поэтому при 100% совпадении с поисковой строкой поиск прерывается. Для данной демонстрации это неверно, потому следует в процедуре "НечеткийПоиск" закомментировать строчку
Если Рез=100 Тогда Прервать КонецЕсли;
Ошибка деления на 0 - очевидно при 0 достоверности, также поправил - по умолчанию устанавливается значение 80%.