Как найти самую длинную повторяющуюся фразу в нескольких текстах в 1С?

← На главную

При работе с текстовой информацией в 1С:Предприятии регулярно возникают задачи анализа содержимого: поиск дубликатов в договорах, выявление схожих номенклатурных позиций или сопоставление описаний товаров от разных поставщиков. Одной из наиболее сложных задач в этой области является поиск самой длинной общей подстроки (Longest Common Substring - LCS) для нескольких текстов.

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

Разбор терминологии: LCS, LRS и LCSeq

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

Наибольшая общая подстрока (Longest Common Substring, LCS) — это непрерывная цепочка символов, которая присутствует во всех сравниваемых текстах. Это именно то, что мы ищем, когда говорим о «повторяющейся фразе».
Наибольшая общая подпоследовательность (Longest Common Subsequence, LCSeq) — здесь общие символы могут идти не подряд, а с разрывами. Например, для строк «мама мыла раму» и «малина» подпоследовательностью будет «ма», но для поиска точных фраз этот алгоритм бесполезен.
Самая длинная повторяющаяся подстрока (Longest Repeated Substring, LRS) — поиск дублирующихся фрагментов внутри одного и того же текста. Ссылки на этот алгоритм часто дают ошибочно, хотя для сопоставления разных текстов требуется обобщенная задача LCS.

Подход 1: Токенизация по предложениям и сравнение списков

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

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

Для начала создадим функцию, которая разбивает входящий текст на фрагменты:


&НаКлиенте
Функция РазложитьТекстВМассив(мТекст)
    Результат = Новый СписокЗначений;
    
    ДлинаТекста = СтрДлина(СокрЛП(мТекст));
    ПозицияКонец = 0;
    перемТекст = мТекст;
    
    Пока ПозицияКонец <= ДлинаТекста Цикл
        ПозицияКонец = НайтиБлижайшуюПозициюСимвола(перемТекст, ПолучитьСимволыКонцаПредложения());
        
        Если ПозицияКонец = 0 Тогда
            Прервать;
        КонецЕсли;
        
        Подстрока = Сред(перемТекст, 1, ПозицияКонец);
        перемТекст = СокрЛП(Сред(перемТекст, ПозицияКонец + 1));
        
        // Сохраняем длину подстроки в качестве значения для последующей сортировки
        Результат.Добавить(СтрДлина(Подстрока), Подстрока);
    КонецЦикла;
    
    // Сортируем список по убыванию длины предложений
    Результат.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
    Возврат Результат;
КонецФункции

Для корректного разбиения нам понадобятся вспомогательные функции, определяющие границы предложений:


&НаКлиенте
Функция НайтиБлижайшуюПозициюСимвола(сТекст, сСимвол)
    спПозиций = Новый СписокЗначений;
    
    Для каждого мСмв Из сСимвол Цикл
        ЧислоПозиции = СтрНайти(сТекст, мСмв);
        Если ЧислоПозиции > 0 Тогда
            спПозиций.Добавить(ЧислоПозиции);
        КонецЕсли;
    КонецЦикла;
    
    спПозиций.СортироватьПоЗначению(НаправлениеСортировки.Возр);
    
    Если спПозиций.Количество() > 0 Тогда
         Возврат (спПозиций[0].Значение);
    КонецЕсли;    
        
    Возврат 0;
КонецФункции

&НаКлиенте
Функция ПолучитьСимволыКонцаПредложения()
    мСимволы = Новый Массив;
    мСимволы.Добавить(". ");
    мСимволы.Добавить("! ");
    мСимволы.Добавить("? ");
    мСимволы.Добавить("... ");
    Возврат мСимволы;
КонецФункции

Теперь напишем управляющую процедуру, которая сравнивает полученные списки и находит наиболее длинное совпадающее предложение:


&НаКлиенте
Процедура кмСравнить(Команда)
    мТекст1 = "Это первый пример текста. Нам нужно найти общую фразу. Программа должна работать быстро.";
    мТекст2 = "Второй пример содержит другие данные. Нам нужно найти общую фразу. Это важно для анализа.";
    
    мРезультат1 = РазложитьТекстВМассив(мТекст1);
    мРезультат2 = РазложитьТекстВМассив(мТекст2);
    
    Если мРезультат1.Количество() = 0 Или мРезультат2.Количество() = 0 Тогда
        Сообщить("Один из текстов пуст. Ничего не найдено.");
        Возврат;
    КонецЕсли;
    
    СовпадениеНайдено = Ложь;
    Для Каждого СтрокаТекста1 Из мРезультат1 Цикл
        // Ищем точное совпадение предложения во втором тексте
        НайденныйЭлемент = мРезультат2.НайтиПоЗначению(СтрокаТекста1.Значение);
        Если НайденныйЭлемент <> Неопределено Тогда
            Сообщить("Самая длинная общая фраза (предложение): " + СтрокаТекста1.Представление);
            СовпадениеНайдено = Истина;
            Прервать; // Так как список отсортирован по убыванию, первое совпадение — самое длинное
        КонецЕсли;
    КонецЦикла;
    
    Если Не СовпадениеНайдено Тогда
        Сообщить("Общих предложений не обнаружено.");
    КонецЕсли;
КонецПроцедуры

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

Недостатки метода: Алгоритм полностью бессилен, если общая фраза не ограничена классическими символами конца предложения (например, если совпадает кусок фразы внутри сложного предложения) или если в текстах различается пунктуация.

Подход 2: Алгоритм Рабина-Карпа (полиномиальный хеш) и бинарный поиск

Если нам требуется найти абсолютно точное посимвольное совпадение любой фразы произвольной длины, предыдущий метод не подойдет. В этом случае идеальным выбором для платформы 1С будет комбинация бинарного поиска по длине искомого фрагмента и полиномиального хеширования (rolling hash).

Проанализируем логику этого алгоритма подробнее:

Мы определяем границы поиска длины фразы: от 1 до длины самого короткого текста.
Используя бинарный поиск, мы выбираем среднее значение длины L.
Для выбранной длины L мы вычисляем скользящие хеши всех подстрок этой длины во всех текстах. Благодаря свойствам полиномиального хеша, вычисление хеша для каждого последующего символа со сдвигом происходит за константное время O(1).
Если мы находим пересечение хешей во всех текстах — значит, общая фраза длины L гарантированно существует. Мы запоминаем этот результат и сдвигаем левую границу бинарного поиска вправо (пытаемся найти еще более длинную фразу).
Если пересечений нет — сдвигаем правую границу влево.

Этот подход работает за время O(N log(min_len)), где N — суммарная длина текстов, и пишется на чистом встроенном языке 1С без использования тяжелых динамических структур.

Подход 3: Суффиксные массивы и LCP

Для максимально производительного поиска на больших объемах данных в теории алгоритмов применяются суффиксные структуры. Суффиксные деревья строить на 1С крайне не рекомендуется из-за колоссального расхода памяти (в 20-30 раз больше объема исходных текстов) и сложности отладки алгоритма Укконена.

Вместо этого мы можем использовать Суффиксный массив (Suffix Array) в сочетании с массивом LCP (Longest Common Prefix):

Мы объединяем все сравниваемые тексты в одну гигантскую строку через уникальные символы-разделители (например: Строка1 + "#" + Строка2 + "$" + Строка3).
Строим суффиксный массив (список начальных позиций всех суффиксов, отсортированных в алфавитном порядке).
Вычисляем значения LCP для всех соседних суффиксов в массиве.
Используем алгоритм "скользящего окна" шириной, равной количеству исходных текстов. Если окно содержит хотя бы по одному суффиксу из каждого исходного текста, минимум LCP в этом окне является кандидатом на звание самой длинной общей подстроки.

Штатные механизмы платформы 1С и их ограничения

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

Этот объект предназначен для интеллектуального анализа данных (Data Mining) и выявления последовательностей событий во времени (например, "после покупки принтера в 80% случаев покупают картридж"). Попытка использовать этот механизм для посимвольного или пословного анализа сырого текста технически неэффективна. Он работает с табличными источниками данных и транзакциями, а не со строками.

Однако в платформе есть другой мощный инструмент. Начиная с версии 8.3.23, разработчикам доступна нативная поддержка регулярных выражений. Функции СтрНайтиПоРегулярномуВыражению и СтрЗаменитьПоРегулярномуВыражению неоценимы для предварительной нормализации текстов перед сравнением:


// Пример предварительной очистки текста на 1С 8.3.23+
&НаСервере
Функция ПодготовитьТекст(ИсходныйТекст)
    // Удаляем все знаки препинания и приводим к нижнему регистру
    ШаблонОчистки = "[^\w\s\s]";
    Результат = СтрЗаменитьПоРегулярномуВыражению(НРег(ИсходныйТекст), ШаблонОчистки, "");
    // Заменяем множественные пробелы на одиночные
    Результат = СтрЗаменитьПоРегулярномуВыражению(Результат, "\s+", " ");
    Возврат СокрЛП(Результат);
КонецФункции

Подход 4: Интеграция с внешними Python-скриптами

Поскольку встроенный язык 1С является однопоточным, обработка текстов объемом в десятки мегабайт может вызвать существенные задержки сеанса пользователя. На практике часто применяется "офлоад" вычислений во внешнюю среду (например, Python), где подобные задачи решаются за миллисекунды встроенными Си-библиотеками.

Рассмотрим, как организовать такое взаимодействие по шагам:

Записываем сравниваемые тексты во временные файлы на диске.
Вызываем Python-скрипт через метод ЗапуститьПриложение, передавая пути к файлам в качестве аргументов.
Python-скрипт считывает файлы, находит LCS с помощью библиотеки difflib или аналогичных и записывает результат в выходной JSON-файл.
1С считывает JSON-файл и выводит пользователю результат.

Посмотрим на пример кода 1С, реализующего этот процесс:


&НаСервере
Процедура СравнитьЧерезPython(ПутьКФайлу1, ПутьКФайлу2)
    ПутьКВыходу = КаталогВременныхФайлов() + "result.json";
    ПутьКСкрипту = "C:\Scripts\find_lcs.py";
    
    // Формируем команду запуска
    СтрокаЗапуска = "python """ + ПутьКСкрипту + """ """ + ПутьКФайлу1 + """ """ + ПутьКФайлу2 + """ """ + ПутьКВыходу + """";
    
    // Запускаем приложение в синхронном режиме (ожидаем завершения)
    КодВозврата = Неопределено;
    ЗапуститьПриложение(СтрокаЗапуска, , Истина, КодВозврата);
    
    Если КодВозврата = 0 Тогда
        // Читаем результат из JSON
        Чтение = Новый ЧтениеJSON;
        Чтение.ОткрытьФайл(ПутьКВыходу);
        РезультатСравнения = ПрочитатьJSON(Чтение);
        Чтение.Закрыть();
        
        Сообщить("Найдена общая фраза: " + РезультатСравнения.НаибольшаяПодстрока);
    Иначе
        ВызватьИсключение "Ошибка работы внешнего скрипта сравнения текстов.";
    КонецЕсли;
КонецПроцедуры

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