В свое время мне пришлось решать следующую задачу: загрузить отчет комиссионера, состоящий из порядка 10 000 строк, предоставленный в электронном виде, в базу данных комитента (УТ 10.2). Проблема была в сопоставлении номенклатуры, так как кодов не было, а наименования не совпадали — вводились различными людьми в разных местах независимо, иногда с ошибками и по разным принципам.
Для хранения соответствий номенклатуры я добавил регистр сведений и решил заполнить его наиболее похожими позициями из справочника номенклатуры базы данных. Далее оператор должен только утвердить найденный автоматически вариант или выбрать другой, ориентируясь при этом по коэффициенту "похожести", сформированному при автоматическом подоборе номенклатуры.
Для решения этой задачи мне нужна была функция, которая позволит вычислить для заданного наименования товара из отчета коэффициенты "похожести" по всем позициям справочника номенклатуры, чтобы в качестве соответствия выбрать номенклатуру с наибольшим коэффициентом. Для возможности такого сравнения необходимо, чтобы функция выдавала результат сравнения из одинакового для любых входных строк диапазона (то есть оценка должна быть нормированной). Подходящей функции я тогда не нашел (одна из них не давала нормированной оценки, другая не понравилась мне алгоритмом — нужно было вводить количество символов в анализируемых комбинациях непонятно исходя из чего), но это меня даже обрадовало, так как задача показалась мне интересной и я решил написать собственную функцию на языке 1С. В скором времени функция была написана и с ее помощью задача была успешно решена.
Результат представляю вашему вниманию — во вложении обработка с двумя полями ввода — Строка1 и Строка2 и кнопкой "Сравнить", результат — коэффициент похожести в диапазоне от 0 до 1 выводится в окно сообщений. Алгоритм чувствителен порядку следования символов в строках — 2 разных набора одних и тех же символов дадут в общем случае различные результаты сравнения.
Немного об особенностях реализации — сначала вычисляются автокорреляционные функции для каждой из строк, после чего бОльшая из вычисленных величин выбирается в качестве нормирующей. Далее вычисляется взаимная корреляция строк и нормируется вычисленной на предыдущем этапе величиной (путем деления результата на нее), что гарантирует нахождение определенного таким образом коэффициента в диапазоне от 0 до 1.
При вычислении исходные строки преобразуются в массивы, что позволит, если будет необходимо, легко перевести этот алгоритм на другие языки программирования. Недостатком данного алгоритма является относительно низкая скорость работы — за все приходится платить. Надеюсь, кому нибудь пригодится!
P.S.
Модуль СКБ Контур говорит автору спасибо — пожалуйста.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Какой из алгоритмов используется?
(1) Altair777,
Боюсь, что не самый и интересный.
(2) AlexO, самопал? 🙂
А как же «полнотекстовый поиск» 1с не пробовали?
(3) Altair777,
что-то вроде «сравннеия в лоб», без применения алгоритмов сортировок и оптимизаций 🙂
(5) AlexO, а зачем? 🙂
сто лет в обед 😉 давно и с успехом данную задачу решает ВК strmatch (можно использовать в снеговике) — — к достоинствам (для большого класа задач) данной ВК следует отнести: нечувствительность не «незвуковым» символам, поддержка фонетической похожести (отзыв и otzyv будут весьма близки). Так что на этой хрения в agfvfwbb у меня был накручен основной мегафункционал — разработки на основе этой ВК успешно работают н аавтозапчастях, игрушках, электробытовых приборах итд (как пример: . чем длиннее сравниваемая строка — тем работает лучше. В приведенном примере — по радиодеталям, где почти все зависит от цифробуквенной маркировки — где многоцифр и маркировка короткая — работало затруднительно — все на все похоже с большоим подобием 😉 пришлось ввести парочку эмпирических правил, которые существенно улучшили ситуацию. Лекарственные прайсы по 10 тыс позиций у меня автоиндентифицировались (примерно на 60-80% — как чувсвтительность выставишь) минут за 40 в далеком 2004-2006гг.
.
а во время моих длительных скитаний по стране 1С — такой алгоритм как у автора давным давно на 7.7 был написан еще на встроенном языке. Так что — как обычно — мы впереди планеты всей в изобретении велосипедов 😉
.
так что разработка автора представляет весьма ограниченный интерес. ибо колесо — оно и есть колесо. но вот если бы автор привел сравнение своего алгоритма, strmatch. полнотекствого поиска снеговика итд — вот это было бы интересно.. сразу бы стало понятно — на что претендует автолр — на колесо для волокуши из цельного куска дерева или на высокотоехнологичное колесо гоночного велосипеда.
(7) CheBurator, ваша информация интересна. Я представил конкретный алгоритм с ОТКРЫТЫМ кодом (в отличие от strmatch и пр.). Ваш восторг по поводу «нечувствительность не «незвуковым» символам» вполне объясним — довольствоваться приходится тем что есть.
Приведите ссылки на его описание — интересно насколько он «такой» и когда был написан и где (может на заборе?).
По поводу сравнения — мне самому было бы интересно сравнить работу моего алгоритма с другими, будет время, напишу об этом отдельно. НО, еще раз (для самых одаренных) — я предоставил алгоритм, он перед вами — сравнивайте!
Спасибо, нужная вещь!
С практической точки зрения больший интерес представляет применение полнотекстового поиска. Например, для поиска похожих контрагентов при вводе нового контрагента. Каждый раз вычислять похожесть двух строк при количестве контрагентов несколько тысяч будет достаточно медленно. Когда в 1С еще не было полнотекстового поиска для получения приемлемого быстродействия приходилось извращаться с монструозным запросом использующим анализ вхождения подстрок искомой строки в поле базы данных. Теперь с полнотекстовым поиском все проще.
(10) 1с-программы.com, спасибо за интерес к моим работам. Придется вас огорчить — полнотекстовый поиск и сравнение строк это несколько разные все таки вещи, хотя издалека действительно похожи. Задачи, которые можно решить с помощью полнотекстового поиска не стоит решать с помощью сравнения строк.
(11) Не нужно меня огорчать 🙂 Конечно это разные вещи. Просто мне так сразу в голову не приходит практическое применение в рамках эксплуатации продуктов 1С алгоритма сравнения двух строк на похожесть.
Если не секрет — с какой целью Вы его писали ? Просто интересно.
Инфостарт выдает список других разработок автора, поэтому я еще заинтересовался и другими вашими разработками. Не подумайте — ничего личного 🙂
+(7) CheBurator,
strmatch == рулёз
Вот пример практического применения фукнции сравнения строк:
Модуль обработки СКБ-Контур говорит автору спасибо, а я передаю.
(15) fishca, Спасибо! Приятно получить такой отзыв 🙂