Алгоритмы. Индексирование регулярных выражений

За что я люблю тему IR — так это только приготовление (и поедание) пищи может сравниться в разнообразности и возможности занять свободное время.

Ещё одна порция ссылок и размышлений, на сей раз по индексированию регулярных выражений.

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

Условно подходов два:

1. Распаковка регулярных выражений в DFA и построение индекса как это описывалось в работе RE-Tree.

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

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

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

Для начала попробую порассуждать что связывает слово (а вернее любую последовательность байтов) с регулярным выражением. В первую очередь, прогоняя слово против регулярных выражений мы рассматриваем ситуацию сравнения объекта являющегося последовательностью значений против совокупности правил описывающих структуру и характер этих значений. А то есть регулярные выражения по своей природе ограничены теми данными против которых они используются. Они формируются на основе значений отдельных элементов слова, группировки этих элементов в подпоследовательности и описания структуры их взаимосвязей. Например, алгоритмы построения n-gram индексов основаны на том что в регулярных выражениях сожержит обязательная статическая часть которая может быть использована для фильтрации тех выражений в которых подобная часть (части) присутствует.

Или же esmre — где используется подход алгоритм Ахо-Карасика не только с проверкой наличия статической части, но и с учётом расстояния между этими частями и возможностью проверки слова по этой статической части для понимания применимо ли данное регулярное выражение к нему или нет.

При этом, на самом деле, индексирование через n-gram’мы от esmre отличается не сильно. И там и там используется принцип «неявных правил», которые обычно игнорируются. Чтобы понять что такое эти «неявные правила» надо посмотреть на последовательность символов, слово несколько иным взглядом.

Например, слово «абв» — помимо собственного значения и в некомпактной записи описывается как (1, а), (2, б), (3, в). Причём позиции букв находятся в отношениях близости (расстояния) и несут в себе значения букв. Так позиция 1 находится на расстоянии 1 от позиции 2, и на расстоянии 2 от позиции 3. И так далее, развёрнутое описание любой статической части, на самом деле окажется набором правил записанных в компактной форме. А учитывая что эта компактная форма — слово является и наиболее приближенной к практическому использованию чтением и речью, то в подавляющем большинстве случаев мы принимаем последовательность символов как некое а-приорное явление. Что, в общем-то, не обязательно таковым является.

Как бы то ни было, оперируя на пространствах: структура последовательности и значения элементов есть ограниченное число средств измерения характеристик последовательности относительно рассматриваемого набора правил которые к нему могут быть применены. В свою очередь, поскольку правила также основаны на этих пространствах, то могут быть сформулированы общие для правил и слов метрики позволяющие перенести часть логики правил из них в упрощённом виде и обеспечить возможность сравнения слова по этим метрикам до прямой проверки на соответствие его данному правилу.

Примеры этих метрик:

1. Длина

Для слова его длина — это фиксированная численная метрика, в то же время для регулярного выражения фиксированное значение длины подпадающих под него слов — это лишь частный случай, а в общем случае регулярному выражению могут соответствовать слова с длиной от 0 до бесконечности. Отсюда любое регулярное выражение обладает двумя обязательными метриками — min_length (минимальной длиной) и max_length (максимальной длиной) при том что если длина слова не входит в промежуток между этими двумя значениями, значит регулярное выражение к нему неприменимо. Тут, конечно, надо оговорится что одно и то же регулярное выражение может иметь различные «ветви» в цепочке правил которым будут соответствовать слова разной минимальной и максимальной длины и min_length и max_length будут соответствовать минимальной длине из всех минимальных и максимальной длине из всех максимальных для данного регулярного выражения.

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

2. Сегментирование значений

Поскольку любое слово состоит из последовательностей элементов — букв каждый из которых обладает своим значением, то любое слово можно проверить на вхождение его элементов в выбранный заранее сегмент или группу значений. При этом выбор этих сегментов может основываться на различных подходах зависящих от стоящих задач, а сами сегменты могут быть как обладать некой смысловой нагрузкой, так и не обладать ей вовсе. К примеру, для слов именно как слов, а не как последовательностей байт, мы можем рассматривать такие сегменты как буквы в пределах от «а» до «я», цифры, спец. символы, буквы латинского алфавита. Кириллические и латинские буквы, в свою очередь, можно делить на гласные и согласные. Можно согласные делить на группы по звонкости. Можно делить буквы по частотным картам, можно и по другим характеристикам. Важнее то что если мы предварительно формируем список сегментов для нарезки пространства значений буквы, то для каждого слова мы можем определить группу сегментов значения из которых присутствуют в данном слове и сегменты значения из которых заведомо отсутствуют в данном слове. При этом, эти сегменты могут быть как непрерывными участками таблицы значений (таблицы кодировки) так и разбросанными по таблице отдельными значениями. В случае непрерывности сегментов, помимо флага наличия у слова букв со значениями в сегмент попадающими, также могут храниться значения минимального и максимального значений букв из данного сегмента присутствующих в данном слове.

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

3. Статические блоки

Большая часть регулярных выражений так или иначе, но обычно содержит блоки являющиеся статическими. Иногда это слова или их части, иногда это участки вплоть до одиночных символов находящихся на фиксированном расстоянии. Например, регулярное выражение ‘[0-3][0-9]{3}/[0-1][0-9]/[0-3][0-9]’ хотя и не обладает непрерывным статическим текстом, но обладает двумя символами «/» находящимися на расстоянии в 2 символа, что позволяет использовать к данному регулярному выражению esmre и существенно ускорять проверки по нему. Схожим образом работает индексирование статических участков с помощью n-gram — это помогает для тех регулярных выражений где они присутствуют. Основным вопросом в данном подходе как и в остальных метриках является предварительный анализ решулярных выражений на предмет наличия статических блоков и доля таких регулярных выражений в общем числе.

4. Правила правил

Регулярные выражения — это по сути набор правил позволяющих определять соответствие слова ряду условий. Причём это правила которые можно описать в виде DFA (или NFA) в виде цепочки их выполнения с последовательностью проверки и так далее. Учитывая что сами эти правила базируются на ограниченном числе операций и значений символов входящих в буквы, то и сами правила могут быть описаны в форме правил более высокого уровня с расчётом метрик на различных участках регулярного выражения.

Например, описывая условно, регулярные выражения «(а|б)» и «(в|где)» можно назвать идентичными по структуре. При этом при оценке идентичности мы учитываем операцию «или» — «|», но игнорируем операцию последовательности, о том что любой последовательный текст — это на самом деле совокупность отношения я писал ранее выше. Нас, также, не волнуют значения которые находятся на данном участке, но волнуются метрики данных значений, а вернее участков регулярных выражений.

Например, если для регулярного выражения «(а|б)» длина слова должна быть всегда равна 1, то для «(в|где)»она может быть в пределах от 1 до 3, а ещё точнее по отдельным метрикам подвыражений, то, либо 1, либо 3.

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

5. Наследование выражений

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

6. Искусственные выражения

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

Конечно, во всех перечисленных метриках есть необходимость в их извлечении, то есть, по любому, необходим парсер выражений позволяющих их извлечь, но может статься что написание такого парсера, а также построение индексов на базе данных метрик может позволить существенно, если не ускорить, то упростить проверку одного слова против базы регулярных выражений без необходимости преобразования их в DFA (NFA).

About This Author

  • Санитар

    Вот что меня всегда радовало в «академически мыслящих», так это способность из простых вещей, достойный максимум двух строк, слепить монографию.

  • http://ivan.begtin.name ivbeg

    В две строки это, увы, никак не уложить. Из всех известных мне тем по поиску и индексированию данных — эта одна из самых сложных.

  • http://www.clockstyle.ru Wayne

    Алгоритмы клевые и хорошие.

Яндекс.Метрика