В процессе интеграции различных информационных систем, загрузки прайс-листов или очистки справочников от дублей мы регулярно сталкиваемся с проблемой нетождественного написания одних и тех же данных. Например, в одной базе контрагент записан как "TOO AlumConstruction", во второй — просто "AlumConstruction", в третьей — "ООО САНТАЛ", а в четвертой — "САНТАЛ, ООО". Обычное строковое сравнение через оператор равенства тут бессильно.
В этой статье мы подробно разберем, как реализовать нечеткое сравнение строк в среде «1С:Предприятие 8». Мы проанализируем различные подходы — от самых простых алгоритмов на чистом языке 1С до использования встроенного полнотекстового поиска и современных кроссплатформенных Native-компонент.
Прежде чем применять любой математический алгоритм нечеткого сравнения, исходные строки необходимо подготовить. Без нормализации точность любого поиска будет крайне низкой. Проанализируем типичные "шумы" в наименованиях контрагентов:
Рассмотрим пример функции, которая приводит строку к нормализованному виду для последующего сравнения:
Функция НормализоватьСтроку(Знач ИсходнаяСтрока) Экспорт
// Приводим к верхнему регистру
Результат = ВРег(ИсходнаяСтрока);
// Удаляем знаки препинания и кавычки
СимволыДляУдаления = "\"", "'", "«", "»", ",", ".", "-", "(", ")", "/";
Для Индекс = 1 По СтрДлина(СимволыДляУдаления) Цикл
Символ = Сред(СимволыДляУдаления, Индекс, 1);
Результат = СтрЗаменить(Результат, Символ, " ");
КонецЦикла;
// Удаляем стандартные мусорные слова (стоп-слова)
СтопСлова = Новый Массив;
СтопСлова.Добавить("ООО");
СтопСлова.Добавить("ИП");
СтопСлова.Добавить("ТОО");
СтопСлова.Добавить("ЗАО");
СтопСлова.Добавить("АО");
Для Каждого Слово Из СтопСлова Цикл
// Ищем слова с границами, чтобы случайно не вырезать часть названия
Результат = СтрЗаменить(Результат, " " + Слово + " ", " ");
Если Лев(Результат, СтрДлина(Слово) + 1) = (Слово + " ") Тогда
Результат = Сред(Результат, СтрДлина(Слово) + 2);
КонецЕсли;
Если Прав(Результат, СтрДлина(Слово) + 1) = (" " + Слово) Тогда
Результат = Лев(Результат, СтрДлина(Результат) - СтрДлина(Слово) - 1);
КонецЕсли;
КонецЦикла;
// Схлопываем двойные пробелы и убираем крайние
Результат = СокрЛП(Результат);
Пока Найти(Результат, " ") > 0 Цикл
Результат = СтрЗаменить(Результат, " ", " ");
КонецЦикла;
Возврат Результат;
КонецФункции
Для решения проблемы разного порядка слов (например, "Шуст Игорь Александрович" и "Игорь Александрович Шуст") очищенную строку рекомендуется разбить на массив слов, отсортировать этот массив по алфавиту и собрать строку обратно через пробел.
Это один из самых надежных, быстрых и простых в реализации алгоритмов, который можно написать на чистом коде 1С без внешних компонент. Суть метода заключается в разделении сравниваемых строк на пересекающиеся последовательности из N символов (обычно используются биграммы — по 2 символа, либо триграммы — по 3 символа).
Проанализируем пример сопоставления слов "САНТАЛ" и "САНТЕЛ" с использованием биграмм:
(2 * ЧислоСовпадений) / (ВсегоБиграмм1 + ВсегоБиграмм2). В нашем случае: (2 * 3) / (5 + 5) = 0.6 (или 60% похожести).Разберем по шагам реализацию этого алгоритма в коде 1С:
Функция ПолучитьБиграммыСтроки(Знач ВходнаяСтрока)
Биграммы = Новый Массив;
СтрокаОчищенная = СтрЗаменить(ВходнаяСтрока, " ", ""); // убираем пробелы внутри слова
Длина = СтрДлина(СтрокаОчищенная);
Для СимволИндекс = 1 По Длина - 1 Цикл
Биграмма = Сред(СтрокаОчищенная, СимволИндекс, 2);
Биграммы.Добавить(Биграмма);
КонецЦикла;
Возврат Биграммы;
КонецФункции
Функция РассчитатьКоэффициентСхожести(Знач Строка1, Знач Строка2) Экспорт
// Предварительно нормализуем строки
С1 = НормализоватьСтроку(Строка1);
С2 = НормализоватьСтроку(Строка2);
Если С1 = С2 Тогда
Возврат 100; // Полное совпадение
КонецЕсли;
Если ПустаяСтрока(С1) Или ПустаяСтрока(С2) Тогда
Возврат 0;
КонецЕсли;
Биграммы1 = ПолучитьБиграммыСтроки(С1);
Биграммы2 = ПолучитьБиграммыСтроки(С2);
Количество1 = Биграммы1.Количество();
Количество2 = Биграммы2.Количество();
Если Количество1 = 0 Или Количество2 = 0 Тогда
Возврат 0;
КонецЕсли;
// Ищем количество пересечений
Совпадений = 0;
Для Каждого Биграмма Из Биграммы1 Цикл
Индекс = Биграммы2.Найти(Биграмма);
Если Индекс <> Неопределено Тогда
Совпадений = Совпадений + 1;
Биграммы2.Удалить(Индекс); // исключаем повторный учет одного и того же символа
КонецЕсли;
КонецЦикла;
// Формула Сёренсена-Диса
Коэффициент = (2 * Совпадений) / (Количество1 + Количество2) * 100;
Возврат Окр(Коэффициент, 2);
КонецФункции
Если вам необходимо искать похожие строки в рамках базы данных (например, искать дубли контрагентов среди сотен тысяч записей справочника), посимвольное сравнение каждой строки в цикле будет работать слишком медленно. В этом случае на помощь приходит встроенный полнотекстовый поиск платформы 1С.
Платформа поддерживает операторы нечеткого поиска. Спецификатор нечеткости задается символом # (решетка). Выясним, как это работает на практике:
#АлюмКонстракшн найдет слова, отличающиеся от исходного на одну букву (опечатку).АлюмКонстракшн#2 найдет слова с расстоянием редактирования (количеством опечаток) не более двух.Рассмотрим пример кода, выполняющего нечеткий поиск контрагентов по наименованию:
Функция НайтиПохожихКонтрагентовЧерезППП(Знач НаименованиеДляПоиска) Экспорт
СписокНайденныхСсылок = Новый Массив;
// Формируем поисковый запрос с нечеткостью (допускаем 2 опечатки)
ТекстЗапросаППП = НаименованиеДляПоиска + "#2";
ВыборкаППП = ПолнотекстовыйПоиск.СоздатьСписок(ТекстЗапросаППП, 20); // Ограничимся первыми 20 результатами
ВыборкаППП.ОбластьПоиска.Добавить(Метаданные.Справочники.Контрагенты);
ВыборкаППП.ПерваяЧасть();
Для Каждого СтрокаРезультата Из ВыборкаППП Цикл
Если ТипЗнч(СтрокаРезультата.Значение) = Тип("СправочникСсылка.Контрагенты") Тогда
СписокНайденныхСсылок.Добавить(СтрокаРезультата.Значение);
КонецЕсли;
КонецЦикла;
Возврат СписокНайденныхСсылок;
КонецФункции
Важный нюанс: Полнотекстовый поиск не возвращает точный процент совпадения (например, "84.5%"). Он лишь возвращает список подходящих объектов. Рекомендуется использовать ППП как первоначальное быстрое сито для отсева заведомо неподходящих записей, а полученную выборку из 10-20 элементов уже детально дорабатывать и ранжировать программным методом N-грамм.
В современных конфигурациях, использующих "Библиотеку стандартных подсистем" (БСП), разработчики 1С отказались от старых COM-компонент (таких как StrMatch.dll) из-за проблем совместимости с 64-битными серверами и операционными системами Linux. Вместо этого в состав БСП включена производительная Native-компонента поиска строк.
Разберем, как подключить эту компоненту программно и задействовать ее мощный функционал:
// Подключаем компоненту из общего макета БСП
Если ПодключитьВнешнююКомпоненту("ОбщийМакет.КомпонентаПоискаСтрок", "FuzzySearch", ТипВнешнейКомпоненты.Native) Тогда
ПоисковыйДвижок = Новый("AddIn.FuzzySearch.FuzzyStringMatchExtension");
Иначе
ЗаписьЖурналаРегистрации("ПоискДублей", УровеньЖурналаРегистрации.Ошибка, , , "Не удалось загрузить компоненту поиска строк!");
Возврат;
КонецЕсли;
// Параметры метода StringSearch:
// 1. Искомая строка
// 2. Массив строк-кандидатов для сравнения
// 3. Разделитель слов (например, пробел)
// 4. Порог длины коротких строк
// 5. Минимальный процент совпадения для коротких строк
// 6. Минимальный процент совпадения для длинных строк
МассивКандидатов = Новый Массив;
МассивКандидатов.Добавить("ООО САНТАЛ ГРУПП");
МассивКандидатов.Добавить("САНТАЛ-М");
МассивКандидатов.Добавить("КОМПАНИЯ САНТАЛ");
СтрокаПоиска = "САНТАЛ ООО";
// Ищем совпадения с порогом схожести от 70%
ИндексыСовпадений = ПоисковыйДвижок.StringSearch(СтрокаПоиска, МассивКандидатов, " ", 5, 70, 70);
Для Каждого Индекс Из ИндексыСовпадений Цикл
Сообщить("Найден похожий контрагент: " + МассивКандидатов[Индекс]);
КонецЦикла;
Этот способ является наиболее производительным для высоконагруженных систем, так как вычисления выполняются на уровне скомпилированного C++ кода компоненты, минуя интерпретатор виртуальной машины 1С.
Для достижения наилучшего результата мы рекомендуем комбинировать рассмотренные подходы:
#. Это позволит мгновенно ограничить выборку.