Как реализовать нечеткий поиск строк в 1С:Предприятии для нахождения похожих значений?

← К списку

В работе с данными часто возникает необходимость найти записи, которые похожи друг на друга, но не являются идентичными. Это может быть связано с опечатками, разными вариантами написания, синонимами или особенностями ввода информации. Традиционный поиск по точному совпадению в таких случаях неэффективен. Именно здесь на помощь приходит нечеткий поиск (или fuzzy search) — метод, позволяющий определить степень схожести между строками, даже если они содержат незначительные различия.

Мы вместе рассмотрим различные подходы к реализации нечеткого поиска в 1С:Предприятии, начиная от простых и часто достаточных, и заканчивая более сложными алгоритмами. Выясним, какие инструменты и методы платформы 1С помогут нам решить эту задачу эффективно, и проанализируем преимущества и недостатки каждого из них.

Метод 1: Простой поиск с оператором "ПОДОБНО" и предварительной обработкой строк

Этот подход является одним из самых простых в реализации и часто оказывается достаточным для большинства случаев нечеткого поиска. Он основан на идее предварительной подготовки (нормализации) строк и использовании встроенного в 1С оператора ПОДОБНО в запросах.

Шаг 1: Подготовка и нормализация строк

Прежде чем сравнивать строки, мы рекомендуем их нормализовать. Это поможет уменьшить количество различий, не связанных с сутью искомой информации, и повысит точность поиска. Давайте рассмотрим основные этапы нормализации:

Приведение регистра: Преобразуем все символы строки к одному регистру (например, к нижнему), чтобы избежать различий из-за прописных и строчных букв. Для этого используем функцию НРег().
Замена схожих символов: Заменим букву "ё" на "е", так как они часто взаимозаменяемы в русском языке и могут быть причиной несовпадений при поиске. Используем функцию СтрЗаменить().
Удаление пунктуации и лишних пробелов: Заменим все знаки препинания на пробелы, а затем удалим повторяющиеся пробелы и пробелы по краям строки. Это поможет избежать различий из-за лишних символов и форматирования.
Разбиение на подстроки: Разобьем нормализованную строку на отдельные слова или части по пробелам. Это позволит нам искать совпадения по отдельным компонентам строки, а не по всей строке целиком, что значительно увеличивает гибкость поиска.

Посмотрим на пример кода для функции нормализации строки:


// Функция нормализует строку для нечеткого поиска
// ИсходнаяСтрока: Строка, которую нужно нормализовать
// Возвращает: Нормализованную строку
Функция НормализоватьСтрокуДляПоиска(ИсходнаяСтрока)
    // 1. Приведение к нижнему регистру
    ПеременнаяСтрока = НРег(ИсходнаяСтрока);

    // 2. Замена "ё" на "е"
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "ё", "е");

    // 3. Замена точек и других знаков пунктуации на пробелы
    // Можно расширить список символов для замены
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, ".", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, ",", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "-", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "(", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, ")", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, """", " "); // Замена кавычек
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "/", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "\", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, ":", " ");
    ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, ";", " ");

    // Удаляем повторяющиеся пробелы
    Пока СтрНайти(ПеременнаяСтрока, "  ") > 0 Цикл
        ПеременнаяСтрока = СтрЗаменить(ПеременнаяСтрока, "  ", " ");
    КонецЦикла;

    // Удаляем пробелы по краям
    ПеременнаяСтрока = СокрЛП(ПеременнаяСтрока);

    Возврат ПеременнаяСтрока;
КонецФункции

// Функция разбивает нормализованную строку на таблицу подстрок
// ИсходнаяСтрока: Нормализованная строка
// Возвращает: ТаблицуЗначений с колонками "Подстрока" и "ДлинаСтроки"
Функция ПолучитьТаблицуПодстрокДляПоиска(ИсходнаяСтрока)
    ТаблицаПодстрок = Новый ТаблицаЗначений;
    ТаблицаПодстрок.Колонки.Добавить("Подстрока");
    ТаблицаПодстрок.Колонки.Добавить("ДлинаСтроки", Новый ОписаниеТипов("Число"));

    МассивСлов = СтрРазделить(ИсходнаяСтрока, " ", Ложь); // Разбиваем по пробелам

    Для Каждого Слово Из МассивСлов Цикл
        Если Не ПустаяСтрока(Слово) Тогда
            // Формируем паттерн для ПОДОБНО
            Паттерн = "%" + Слово + "%";
            НоваяСтрока = ТаблицаПодстрок.Добавить();
            НоваяСтрока.Подстрока = Паттерн;
            НоваяСтрока.ДлинаСтроки = СтрДлина(Слово);
        КонецЕсли;
    КонецЦикла;

    // Дополнительно можно добавить паттерн для всей строки целиком
    Если Не ПустаяСтрока(ИсходнаяСтрока) Тогда
        НоваяСтрока = ТаблицаПодстрок.Добавить();
        НоваяСтрока.Подстрока = "%" + ИсходнаяСтрока + "%";
        НоваяСтровая.ДлинаСтроки = СтрДлина(ИсходнаяСтрока);
    КонецЕсли;

    Возврат ТаблицаПодстрок;
КонецФункции

Шаг 2: Построение запроса с оператором "ПОДОБНО"

После того как мы подготовили таблицу подстрок, мы можем использовать ее в запросе 1С с оператором ПОДОБНО. Этот оператор позволяет искать строки, соответствующие определенному шаблону, где символ % означает любую последовательность символов, а _ — любой одиночный символ.

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


// Пример использования в запросе 1С
// Предполагается, что у нас есть ТаблицаПодстрок, полученная ранее
// из искомой строки (например, "Иванов Петр")

Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
    |    ТЗ.Подстрока,
    |    ТЗ.ДлинаСтроки
    |ПОМЕСТИТЬ ВТ_Подстроки
    |ИЗ
    |    &ТаблицаПодстрок КАК ТЗ
    |;
    |
    |////////////////////////////////////////////////////////////////////////////////
    |ВЫБРАТЬ ПЕРВЫЕ 10 // Получим до 10 наиболее похожих
    |    ГдеИщем.Наименование,
    |    МАКСИМУМ(ВТ_Подстроки.ДлинаСтроки) КАК Приоритет
    |ИЗ
    |    Справочник.Контрагенты КАК ГдеИщем // Замените на ваш справочник/документ
    |        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ_Подстроки КАК ВТ_Подстроки
    |        ПО (ГдеИщем.Наименование ПОДОБНО ВТ_Подстроки.Подстрока)
    |ГДЕ
    |    НЕ ГдеИщем.ПометкаУдаления // Исключаем удаленные элементы
    |СГРУППИРОВАТЬ ПО
    |    ГдеИщем.Наименование
    |УПОРЯДОЧИТЬ ПО
    |    Приоритет УБЫВ";

Запрос.УстановитьПараметр("ТаблицаПодстрок", ТаблицаПодстрок); // Передаем нашу ТЗ

РезультатЗапроса = Запрос.Выполнить();
Выборка = РезультатЗапроса.Выбрать();

Пока Выборка.Следующий() Цикл
    Сообщить("Найдено: " + Выборка.Наименование + ", Приоритет: " + Выборка.Приоритет);
КонецЦикла;

Преимущества этого метода: простота реализации, хорошая производительность для умеренных объемов данных, возможность использования стандартных средств запросов 1С.

Недостатки: не учитывает порядок слов (например, "Петр Иванов" будет похож на "Иванов Петр" с тем же приоритетом), нечувствителен к опечаткам внутри слов (например, "Иванов" и "Ивановв" не будут найдены как похожие, если не добавить дополнительные паттерны).

Метод 2: Алгоритм расстояния Левенштейна

Если нам требуется более точный и математически обоснованный подход к определению схожести строк, мы можем использовать алгоритм расстояния Левенштейна. Расстояние Левенштейна (или редакционное расстояние) — это минимальное количество операций вставки, удаления или замены одного символа, необходимых для превращения одной строки в другую. Чем меньше расстояние, тем более похожи строки.

Этот алгоритм широко используется для исправления опечаток, сравнения ДНК, анализа плагиата и других задач, где важна степень различия между текстовыми последовательностями.

Реализация алгоритма Левенштейна на 1С

Давайте рассмотрим подробную реализацию функции для расчета расстояния Левенштейна на встроенном языке 1С. Мы будем использовать динамическое программирование для построения матрицы, в которой каждая ячейка матрица[i][j] будет хранить расстояние между префиксом первой строки длиной i и префиксом второй строки длиной j.


// Функция РасстояниеЛевенштейна
// Строка1: Первая строка для сравнения
// Строка2: Вторая строка для сравнения
// Возвращает: Целое число - расстояние Левенштейна между Строка1 и Строка2
Функция РасстояниеЛевенштейна(Строка1, Строка2)
    // Получаем длины строк
    len1 = СтрДлина(Строка1);
    len2 = СтрДлина(Строка2);

    // Создаем матрицу размером (len1+1) x (len2+1)
    // Матрица будет хранить минимальные расстояния
    матрица = Новый Массив(len1 + 1);
    Для i = 0 По len1 Цикл
        матрица[i] = Новый Массив(len2 + 1);
    КонецЦикла;

    // Инициализация первой строки матрицы
    // Расстояние от пустой строки до префикса длиной j равно j (нужно j вставок)
    Для j = 0 По len2 Цикл
        матрица[0][j] = j;
    КонецЦикла;

    // Инициализация первого столбца матрицы
    // Расстояние от префикса длиной i до пустой строки равно i (нужно i удалений)
    Для i = 0 По len1 Цикл
        матрица[i][0] = i;
    КонецЦикла;

    // Заполнение остальной части матрицы
    Для i = 1 По len1 Цикл
        Для j = 1 По len2 Цикл
            // Получаем текущие символы для сравнения
            символ1 = Сред(Строка1, i, 1);
            символ2 = Сред(Строка2, j, 1);

            // Определяем стоимость замены: 0, если символы совпадают, 1 - если различаются
            cost = ?(символ1 = символ2, 0, 1);

            // Вычисляем значение текущей ячейки матрицы
            // Это минимум из трех операций:
            // 1. Удаление символа из Строка1 (матрица[i-1][j] + 1)
            // 2. Вставка символа в Строка1 (матрица[i][j-1] + 1)
            // 3. Замена символа (матрица[i-1][j-1] + cost)
            матрица[i][j] = Мин(
                матрица[i-1][j] + 1,   // Удаление
                матрица[i][j-1] + 1,   // Вставка
                матрица[i-1][j-1] + cost  // Замена или совпадение
            );
        КонецЦикла;
    КонецЦикла;

    // Результат - значение в правом нижнем углу матрицы
    Возврат матрица[len1][len2];
КонецФункции

Как использовать: Вы можете применить эту функцию, перебирая элементы справочника или документа и сравнивая их наименования с искомой строкой. Если расстояние Левенштейна меньше определенного порога (например, 1, 2 или 3, в зависимости от длины строк), то строки считаются похожими.

Пример использования:


ИскомаяСтрока = "Апельсин";
ПорогСхожести = 2; // Максимальное допустимое расстояние

Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ Наименование ИЗ Справочник.Номенклатура ГДЕ НЕ ПометкаУдаления";
ВыборкаНоменклатуры = Запрос.Выполнить().Выбрать();

Пока ВыборкаНоменклатуры.Следующий() Цикл
    Расстояние = РасстояниеЛевенштейна(ИскомаяСтрока, ВыборкаНоменклатуры.Наименование);
    Если Расстояние <= ПорогСхожести Тогда
        Сообщить("Найдено похожее: " + ВыборкаНоменклатуры.Наименование + ", Расстояние: " + Расстояние);
    КонецЕсли;
КонецЦикла;

Преимущества алгоритма Левенштейна: высокая точность, математическая обоснованность, чувствительность к опечаткам и порядку символов.

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

Метод 3: Другие алгоритмы нечеткого поиска и встроенные механизмы 1С

Помимо рассмотренных выше методов, существуют и другие, более специализированные алгоритмы и встроенные средства 1С, которые могут быть полезны для нечеткого поиска.

1. Другие алгоритмические подходы

Расстояние Джаро-Винклера: Это мера схожести строк, которая является вариантом расстояния Джаро. Она учитывает количество совпадающих символов, количество транспозиций (переставленных символов) и масштабирующий коэффициент для совпадений префиксов. Этот алгоритм особенно полезен при наличии небольших опечаток или фонетических вариаций, так как он придает больший вес совпадениям в начале строки.
N-граммы: Метод нечеткого поиска, основанный на построении индекса из N-грамм (последовательностей из N символов, например, "ап", "пе", "ел" для N=2 из слова "апельсин"). Его можно реализовать с помощью запросов в 1С. Индексирование N-грамм может потребовать значительных ресурсов хранения, но позволяет выполнять очень быстрый поиск.
Расстояние Дамерау-Левенштейна: Расширение расстояния Левенштейна, которое, помимо операций вставки, удаления и замены символов, также учитывает транспозицию (перестановку двух соседних символов). Это делает его еще более точным для обнаружения некоторых видов опечаток.
Фонетические алгоритмы (например, Soundex, Metaphone): Эти алгоритмы устанавливают одинаковый индекс для строк, имеющих схожее звучание. Они полезны, когда поиск ведется по слуховому восприятию слова, а не по его точному написанию. Soundex разработан для английского языка, но существуют адаптации и для других языков.

2. Встроенный полнотекстовый поиск 1С

Платформа 1С:Предприятие имеет встроенный механизм полнотекстового поиска, который может выполнять нечеткий поиск с использованием оператора * (поиск по префиксу). Например, запрос руне* найдет "рунет", "рунета" и так далее.

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

3. Функции Библиотеки стандартных подсистем (БСП)

В составе Библиотеки стандартных подсистем (БСП) для 1С 8.3 могут присутствовать специализированные компоненты для нечеткого поиска, например, FuzzySearch.StringSearch. Если ваша конфигурация использует БСП, рекомендуем изучить ее функциональность, так как она может предложить готовые и оптимизированные решения для поиска строк с определенными параметрами, такими как процент совпадения.

4. Словари синонимов и сопоставление номенклатуры

Для повышения релевантности поиска можно использовать дополнительные словари синонимов. Платформа 1С и некоторые сторонние модули поддерживают такие словари, которые расширяют системные и могут содержать специфические термины.

В стандартных конфигурациях 1С (например, УТ, БП, ERP) часто реализованы механизмы сопоставления и объединения номенклатуры или контрагентов, которые могут использовать различные подходы к нечеткому поиску. Мы можем изучить, как эти механизмы реализованы в типовых решениях, чтобы понять их логику и применить аналогичные подходы в своих задачах.

Производительность и оптимизация

Нечеткий поиск может быть ресурсоемким, особенно при очень больших наборах данных. Мы должны учитывать следующие моменты при оптимизации:

Предварительная индексация: Для алгоритмов, таких как N-граммы, или для полнотекстового поиска, предварительное построение индексов может значительно ускорить поиск, но потребует ресурсов для их создания и обновления.
Ограничение области поиска: Старайтесь всегда максимально сужать область поиска с помощью точных фильтров (например, по дате, типу, группе), прежде чем применять нечеткий поиск.
Пакетная обработка: Если необходимо сравнить большое количество строк, старайтесь выполнять сравнения пакетами, чтобы минимизировать накладные расходы на вызовы функций.
Выбор алгоритма: Для простых случаев используйте метод с ПОДОБНО. Для более точных, но менее производительных — алгоритмы редакционного расстояния.

Выбор конкретного метода или комбинации методов зависит от требований к точности, объему данных и доступным ресурсам. Мы рекомендуем начать с более простых подходов и переходить к сложным алгоритмам только в случае, если первые не дают удовлетворительных результатов.

← К списку