Поиск по шаблону

   Моя обработка "поиск по шаблону"

Обработка содержит набор процедур, которые реализуют сопоставление строки и шаблона. Шаблон может содержать метасимволы ? и *. Полная постановка задачи дается здесь.

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

Обработка появилась после ответа Ильдара Каюмова о поиске по шаблону в конференции Территория 1С. Ильдар дал согласие на публикацию его обработки, которую вы можете найти здесь.

Спасибо Ильдару за вдохновение, которое позволило завершить эти страницы и мой вариант обработки, за тестирование и ценные советы.

Автор будет благодарен за замечания и предложения по алгоритму и описанию. Пишите: mazzy@mazzy.ru, Мазуркин Сергей

Загрузить обработку (12 Кб)

Обработка "поиск по шаблону"

Обработка содержит визуальные элементы, необходимые для отладки и изучения (таблица "План выполнения"). В реальной программе визуальные элементы не обязательны. При установке в реальную программу необходимо раскомментировать одну строчку в процедуре Поиск_РазборШаблона. Эта строчка должна создавать таблицу в реальной программе.

  Описание алгоритма

Принципы реализации поиска

Поиск по маске на самом деле состоит из двух действий: разбор шаблона и сравнение строки с шаблоном.

Метасимволы в шаблоне обладают определенным значением - семантикой. На первом шаге программа должна разобрать (понять), что от нее требуется. Например шаблон "?" означает, что в строке должен быть только один символ, а "*?" означает, что в строке должно быть не менее одного символа. Надо отметить, что шаблоны "*?" и "?*" имеют одинаковый смысл.

На втором этапе программа должна посмотреть на искомую строку и решить - подходит ли данная строка указанному шаблону.

Заметим, что шаблон может быть достаточно сложным. Поэтому время, необходимое для разбора может быть значительным. Заметим также, что если поиск выполняется в цикле (например, найти всех контрагентов, в названии которого есть буквы "1С"), то искомые строки каждый раз разные, а шаблон - один и тот же.

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

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

Прикинем:

Составим таблицу. По вертикали укажем фазы сравнения. Причем укажем два варианта - без оптимизации и с оптимизацией. По горизонтали укажем количество выполнений поиска. Посчитаем для одноразового выполнения и для цикла, который выполняет поиск 1000 раз. Причем, отдельно посчитаем для монолитного выполнения (разбор и сравнение не разделены) и отдельно для раздельного выполнения (разбор выполняется за циклом, сравнение в цикле).

Таблица 1.
Фазы 1 раз 1000 раз
  монолит разделено монолит разделено
разбор 1 1 1 * 1000 1
сравнение 1 1 * 1 1 * 1000 1 * 1000
Итого 2 сек 2 сек 2000 сек 1001 сек
         
разбор 1 1 1 * 1000 1
оптимизация 2 2 2 * 1000 2
сравнение 0.5 0.5 * 1 0.5 * 1000 0.5*1000
Итого 3.5 сек 3.5 сек 3500 сек 503 сек

Такую же таблицу составим позже на основе реальных данных и сравним с этой прикидочной.

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

Таким образом:

Осталось сделать алгоритм удобным для программиста. Что это значит в среде разработки 1С:

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

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

  1. Скорость работы. Скорость как в одиночных запросах, так и в цикле
  2. Удобство использования
  3. Модульность алгоритма
  4. Возможность повторного использования

Общие сведения

Сейчас поиск обрабатывает метасимволы * и ?, а также неявно, начало и конец строки. Поиск выполняется в одной однострочной строке (извините, за каламбур. у 1С есть понятие "многострочная строка". На английском звучит лучше - SingleLine и MultiLine Strings). Поиск не различает регистр букв (как следствие, поиск будет неправильно работать в кодировке, отличной от 1251).

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

Поиск выполняется в три фазы:

Фазы - сравнительно независимы. Результаты первой фазы (планы выполнения) можно запоминать в разных переменных и использовать функцию ПоискПоПлану с разными планами. Первые фазы можно выполнить до цикла, а третью фазу вызывать в цикле.

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

Первая фаза: разбор

Задача первой фазы - преобразовать шаблон из текстовой формы в структурированный план выполнения. Первая фаза должна отработать быстро. Поэтому первая фаза - просмотр строки шаблона и фиксация задания. Разбор имеет дело только с текущей позицией шаблона и с текущей командой плана выполнения. (исключение составляют преобразование последовательности команд "*","?" в последовательность "*","?","*" и обработка конца строки. Более поздняя обработка этих комбинаций приводит к очень сложным алгоритмам).

План выполнения после выполнения первой фазы не обязательно будет оптимальным. Можно даже утверждать, что на этом этапе он скорее всего будет неоптимальным. Однако можно утверждать, что план выполнения будет получен с наименьшей возможной (в данных условиях) задержкой.

Вторая фаза: оптимизация

Вторая фаза не является обязательной. Оптимизация может занять достаточно большое время (по сравнению с первой и третьей фазами). Задача оптимизации - минимизировать число команд в плане выполнения.

Сейчас оптимизация выполняет несколько шагов:

Третья фаза: сравнение

Задача третьей фазы - быстро сравнить сроку, используя заданный план выполнения. Третья фаза может принять оптимизированный и неоптимизированный план выполнения.

План не обязательно должен готовится на первой фазе. Пользователь алгоритма может составить план выполнения самостоятельно. Третья фаза написана таким образом, чтобы она принимала и корректно отрабатывала любой план. Для выполнения этого требования пришлось слегка усложнить эту фазу. Но я постарался сильно не усложнять. Самое главное выполнить сравнение быстро!

Параметр Команда в плане выполнения

* любая подстрока
? любой символ
СЛ Сравнить сЛева
СП Сравнить сПрава
СС Сравнить с Середины
СР Сравнить на полное Равенство
ПН Позиция Начала строки
ПК Позиция Конца строки

Параметр Строка в плане выполнения

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

Должно быть справа (число символов)

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

Например, строка "АБВ", Шаблон "*????*". После оптимизации, перед выполнением команды, сравнение "знает" о том, что в строке должно быть не меньше 4 символов. Перед первой командой алгоритм может проверить длину (это достаточно быстрая операция) и возвратить неудачу достаточно быстро.

  Методика использования

Алгоритм поиска содержит набор процедур, которые можно поместить в глобальный модуль любой конфигурации.

Внимание! После копирования в глобальный модуль надо расскоментировать первую строку в функции Поиск_РазборШаблона. Эта строка создает таблицу. В обработке таблица - визуальный элемент, а в глобальном модуле таблицу надо создать.

Список функций и процедур, которые надо перенести:

Функция Поиск_РазборШаблона(Знач Шаб="") Экспорт
Процедура Поиск_ОптимизацияПланаВыполнения(План) Экспорт
Функция ПоискПоПлану(Знач Стр,План,Шаг=1) Экспорт
Функция Поиск1(Стр,Шаб="",Оптимизация=0) Экспорт
Функция Поиск(Стр,Шаб="") Экспорт

План выполнения хранится в таблице значений. Если поиск по одному шаблону выполняется большое число раз в цикле, то разбор маски и оптимизацию можно выполнить один раз до поиска (Поиск_РазборШаблона, Поиск_ОптимизацияПланаВыполнения). Внутри цикла можно выполнять сравнение по построенному и оптимизированному плану выполнения

Например:

План = Поиск_РазборШаблона("*1С*");
// искать всех контрагентов, у которых в названии есть 1С
Поиск_ОптимизацияПланаВыполнения(План);
// можно пропустить, но с этим шагом
// сравнение будет выполняться быстрее

Контрагент = СоздатьОбъект("Справочник.Контрагенты");
Контрагент.ВыбратьЭлементы(0);
Пока Контрагент.ВыбратьЭлемент()=1 Цикл
    Если ПоискПоПлану(Контрагент.Наименование,План)=1 Тогда
        Сообщить("Найден контрагент:"+Контрагент);
    КонецЕсли;
КонецЦикла;

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

  Возможные расширения алгоритма

Пока все. По мере возможности буду дописывать.
Буду рад получить ваши замечания и предложения.

Мазуркин Сергей
mazzy@mazzy.ru