Моя обработка "поиск по шаблону"
- Описание алгоритма
- Методика использования
- Разбор алгоритма: плюсы и минусы
- Возможные расширения алгоритма
Обработка содержит набор процедур, которые реализуют сопоставление строки и шаблона. Шаблон может содержать метасимволы ? и *. Полная постановка задачи дается здесь.
Обработка является внешней обработкой для программы 1С:Предприятие 7.7. Набор процедур данной обработки может использоваться с любой основной компонентой 1С:Предприятия. Для того, чтобы использовать набор процедур достаточно скопировать в свою конфигурацию этот набор процедур и раскомментировать одну строчку.
Обработка появилась после ответа Ильдара Каюмова о поиске по шаблону в конференции Территория 1С. Ильдар дал согласие на публикацию его обработки, которую вы можете найти здесь.
Спасибо Ильдару за вдохновение, которое позволило завершить эти страницы и мой вариант обработки, за тестирование и ценные советы.
Автор будет благодарен за замечания и предложения по алгоритму и описанию. Пишите: mazzy@mazzy.ru, Мазуркин Сергей
Загрузить обработку (12
Кб)
Обработка содержит визуальные элементы, необходимые для отладки и изучения (таблица "План выполнения"). В реальной программе визуальные элементы не обязательны. При установке в реальную программу необходимо раскомментировать одну строчку в процедуре Поиск_РазборШаблона. Эта строчка должна создавать таблицу в реальной программе.
Описание алгоритма
Принципы реализации поиска
Поиск по маске на самом деле состоит из двух действий: разбор шаблона и сравнение строки с шаблоном.
Метасимволы в шаблоне обладают определенным значением - семантикой. На первом шаге программа должна разобрать (понять), что от нее требуется. Например шаблон "?" означает, что в строке должен быть только один символ, а "*?" означает, что в строке должно быть не менее одного символа. Надо отметить, что шаблоны "*?" и "?*" имеют одинаковый смысл.
На втором этапе программа должна посмотреть на искомую строку и решить - подходит ли данная строка указанному шаблону.
Заметим, что шаблон может быть достаточно сложным. Поэтому время, необходимое для разбора может быть значительным. Заметим также, что если поиск выполняется в цикле (например, найти всех контрагентов, в названии которого есть буквы "1С"), то искомые строки каждый раз разные, а шаблон - один и тот же.
На самом деле, поиск в цикле по одному шаблону - это наиболее частый случай. Поэтому вряд ли рационально тратить внутри цикла существенное время на разбор одного и того же шаблона. Возникает мысль сделать поиск двухэтапным - разбор шаблона и сравнение строки по шаблону. Очевидно, что чем быстрее выполняется сравнение, тем лучше. Очевидно, что для оптимизации сравнения придется попыхтеть на этапе разбора.
С другой стороны, не так уж и редко случается ситуация, когда надо один раз проверить строчку на соответствие шаблону и... забыть о строчке и шаблоне. В этом случае надо как можно быстрее завершить обе стадии. Если разбор выполняется за секунду, поиск выполняется за секунду и оптимизация ускорит вдвое сравнение, то вряд ли выполнять оптимизацию, которая займет две секунды.
Прикинем:
- разбор шаблона выполняется за 1 сек
- оптимизация шаблона - 2 сек
- сравнение по неоптизированному разбору шаблону 1 сек
- оптимизация в среднем улучшает сравнение вдвое
Составим таблицу. По вертикали укажем фазы сравнения. Причем укажем два варианта - без оптимизации и с оптимизацией. По горизонтали укажем количество выполнений поиска. Посчитаем для одноразового выполнения и для цикла, который выполняет поиск 1000 раз. Причем, отдельно посчитаем для монолитного выполнения (разбор и сравнение не разделены) и отдельно для раздельного выполнения (разбор выполняется за циклом, сравнение в цикле).
Фазы | 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
, либо напрямую обращаться к разбору, оптимизации, сравнению) - Пользователь не обязан знать детали алгоритма. Хотя, если он захочет, то он должен иметь возможность
влезть в алгоритм.
С одной стороны, алгоритм скрывает (инкапсулирует) сложную структуру в таблице значений, хотя таблица значений очень медленный объект в 1С (здесь противоречие с принципом 1 о скорости, но здесь удобство важнее). С другой стороны, описание содержит документацию о формате таблицы, и, если пользователь захочет, то он может создавать не строковый шаблон, а сразу таблицу с планом выполнения сравнения. - Алгоритм не должен использовать недокументированных возможностей 1С. И не должен требовать от пользователя значений недокументированных возможностей.
Было бы хорошо сделать алгоритм поиска модульным (чтобы модули слабо зависели друг от друга), легко расширяемым.
Сформулирую принципы, которые учитывались при разработке. Принципы перечислены в порядке важности:
- Скорость работы. Скорость как в одиночных запросах, так и в цикле
- Удобство использования
- Модульность алгоритма
- Возможность повторного использования
Общие сведения
Сейчас поиск обрабатывает метасимволы * и ?, а также неявно, начало и конец строки. Поиск выполняется в одной однострочной строке (извините, за каламбур. у 1С есть понятие "многострочная строка". На английском звучит лучше - SingleLine и MultiLine Strings). Поиск не различает регистр букв (как следствие, поиск будет неправильно работать в кодировке, отличной от 1251).
Параметры поиска можно легко расширить. Например, сейчас легко добавляется параметр - учитывать регистр, параметр поиска начала и конца строки. Легко добавляется возможность указывать допустимые и недопустимые символы.
Поиск выполняется в три фазы:
- разбор маски-шаблона и построение плана выполнения
- оптимизация плана выполнения (можно пропустить)
- сравнение строки по плану выполнения
Фазы - сравнительно независимы. Результаты первой фазы (планы выполнения) можно запоминать в разных переменных и использовать функцию ПоискПоПлану с разными планами. Первые фазы можно выполнить до цикла, а третью фазу вызывать в цикле.
Алгоритм разрабатывался для быстрой работы и с одиночными запросами, и в цикле. Предполагается, что в одиночных запросах алгоритм должен быстро сделать разбор и сравнение, а в цикле алгоритм может потратить некоторое время на оптимизацию, чтобы фаза сравнения выполнялась быстрее.
Задача первой фазы - преобразовать шаблон из текстовой формы в структурированный план выполнения. Первая фаза должна отработать быстро. Поэтому первая фаза - просмотр строки шаблона и фиксация задания. Разбор имеет дело только с текущей позицией шаблона и с текущей командой плана выполнения. (исключение составляют преобразование последовательности команд "*","?" в последовательность "*","?","*" и обработка конца строки. Более поздняя обработка этих комбинаций приводит к очень сложным алгоритмам).
План выполнения после выполнения первой фазы не обязательно будет оптимальным. Можно даже утверждать, что на этом этапе он скорее всего будет неоптимальным. Однако можно утверждать, что план выполнения будет получен с наименьшей возможной (в данных условиях) задержкой.
Вторая фаза: оптимизация
Вторая фаза не является обязательной. Оптимизация может занять достаточно большое время (по сравнению с первой и третьей фазами). Задача оптимизации - минимизировать число команд в плане выполнения.
Сейчас оптимизация выполняет несколько шагов:
- замена последовательности *? на эквивалентную ?*
- поиск и оптимизация дублей
- (несколько подряд идущих ** заменяется на *
- последовательность вопросительных знаков на одну команду ? с длинной строкой из ?, что позволяет сделать сравнение за одну команду
- последовательность из СС на одну команду
- и т.д.
- удаление * в начале и конце и замена этих команд на более короткие эквиваленты
- замена последовательности *,СЛ на СС (сравнение слева после звездочки заменяется на сравнение с середины без звездочки)
- сравнение строки в конце заменяется на проверку строки справа
- единственная строка в шаблоне заменяется на СР (вместо трех команд ПН,СЛ,ПК получаем одну СР)
- удаление команды ПН
- для каждой команды выполняется подсчет символов, которые обязательно должны остаться в искомой строке перед сравнением.
Третья фаза: сравнение
Задача третьей фазы - быстро сравнить сроку, используя заданный план выполнения. Третья фаза может принять оптимизированный и неоптимизированный план выполнения.
План не обязательно должен готовится на первой фазе. Пользователь алгоритма может составить план выполнения самостоятельно. Третья фаза написана таким образом, чтобы она принимала и корректно отрабатывала любой план. Для выполнения этого требования пришлось слегка усложнить эту фазу. Но я постарался сильно не усложнять. Самое главное выполнить сравнение быстро!
Параметр Команда в плане выполнения
* | любая подстрока |
? | любой символ |
СЛ | Сравнить сЛева |
СП | Сравнить сПрава |
СС | Сравнить с Середины |
СР | Сравнить на полное Равенство |
ПН | Позиция Начала строки |
ПК | Позиция Конца строки |
Параметр Строка в плане выполнения
Символы шаблона, которые обязательно должны присутствовать в искомой строке. Для команды "?" длина этой строки показывает количество произвольных символов должно быть в текущей позиции.
Должно быть справа (число символов)
Показывает число символов, которые обязательно должны остаться в проверяемой строке перед выполнением команды. Этот параметр вычисляется только при оптимизации. Перед выполнением команды, алгоритм поиска проверяет, чтобы в проверяемой строке осталось символов не меньше, чем указано. Этот реквизит может сильно ускорить поиск на коротких строках и длинных шаблонах.
Например, строка "АБВ", Шаблон "*????*". После оптимизации, перед выполнением команды, сравнение "знает" о том, что в строке должно быть не меньше 4 символов. Перед первой командой алгоритм может проверить длину (это достаточно быстрая операция) и возвратить неудачу достаточно быстро.
Методика использования
Алгоритм поиска содержит набор процедур, которые можно поместить в глобальный модуль любой конфигурации.
Внимание! После копирования в глобальный модуль надо расскоментировать первую строку в функции
Поиск_РазборШаблона
.
Эта строка создает таблицу. В обработке таблица - визуальный элемент, а в глобальном модуле таблицу надо создать.
Список функций и процедур, которые надо перенести:
Функция
Поиск_РазборШаблона
(Знач
Шаб
=
""
) Экспорт Процедура
Поиск_ОптимизацияПланаВыполнения
(
План
) Экспорт Функция
ПоискПоПлану
(Знач
Стр
,
План
,
Шаг
=
1
) Экспорт Функция
Поиск1
(
Стр
,
Шаб
=
""
,
Оптимизация
=
0
) Экспорт Функция
Поиск
(
Стр
,
Шаб
=
""
) Экспорт
План выполнения хранится в таблице значений. Если поиск по одному шаблону выполняется большое число раз
в цикле, то
разбор маски и оптимизацию можно выполнить один раз до поиска (Поиск_РазборШаблона
, Поиск_ОптимизацияПланаВыполнения
).
Внутри цикла можно выполнять сравнение по построенному и оптимизированному плану выполнения
Например:
План = Поиск_РазборШаблона
(
"*1С*"
);
// искать всех контрагентов, у которых в названии есть 1С
Поиск_ОптимизацияПланаВыполнения
(
План
);
// можно пропустить, но с этим шагом // сравнение будет выполняться быстрее
Контрагент = СоздатьОбъект
(
"Справочник.Контрагенты"
);
Контрагент.ВыбратьЭлементы
(
0
)
;
Пока
Контрагент.ВыбратьЭлемент
()
=1
Цикл Если
ПоискПоПлану
(
Контрагент.Наименование
,
План
)=
1
Тогда Сообщить(
"Найден контрагент:"
+Контрагент
);
КонецЕсли; КонецЦикла;
В дальнейшем, если поиск будет повторятся план из переменной План можно использовать еще раз. Если
поиск выполняется
однократно, или шаблоны каждый раз разные, то лучше использовать функцию Поиск
или Поиск1
.
Поиск выполняет
сравнение по шаблону с оптимизацией плана выполнения Поиск1
позволяет указывать, нужна ли оптимизация
в параметре. По
умолчанию, фнукиця Поиск1
не оптимизирует план.
Возможные расширения алгоритма
- Параметр различения регистра букв (сейчас используется ВРЕГ)
- Параметр поиска начала и конца строки (сейчас есть неявно)
- Параметр, указывающий допустимые или недопустимые символы в искомой строке
- только цифры
- только буквы
- только большие буквы
- только маленькие буквы
- только пробелы (isalpha)
- только разделители
- комбинации предыдущих
- Параметр поиска в многострочных строках
- Оптимизация для поиска в длинных строках/текстах
- Работа с кодировками (по крайней мере, на уровне ANSI, OEM)
- Логические выражения И(AND), ИЛИ(OR), БЛИЗКО (NEAR)
- Работа со списком стоп-слов
- Морфологический анализ
Пока все. По мере возможности буду дописывать.
Буду рад получить ваши замечания и предложения.
Мазуркин Сергей
mazzy@mazzy.ru