29 марта в 13:28

Поиск по регулярным выражениям с помощью суффиксного массива перевод

image

Еще в январе 2012 Расс Кокс опубликовал замечательный блог-пост, объясняющий работу Google Code Search с помощью триграммного индекса.

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

Суффиксные массивы


Суффиксный массив — это структура данных, используемая для осуществления полнотекстового поиска и для других приложений, в основном в области биоинформатики.

Концепция суффиксного массива довольно проста: это отсортированный массив всех суффиксов строки. Так, для строки “туда и сюда”

0 1 2 3 4 5 6 7 8 9 10
т у д а _ и _ с ю д а

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

Индекс Суффикс
4 _ и сюда
6 _ сюда
10 а
3 а и сюда
9 да
2 да и сюда
5 и сюда
7 сюда
0 туда и сюда
1 уда и сюда
8 юда


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

[4 6 10 3 9 2 5 7 0 1 8]

Существуют алгоритмы, позволяющие быстро строить суффиксные массивы (за время O(n)) или преобразовывать исходный массив в суффиксный (с использованием постоянного объема дополнительной памяти вне самого массива).

Полнотекстовый поиск по подстроке


Одно из основных приложений суффиксного массива — полнотекстовый поиск.

Если мы ищем подстроку в корпусе текстов, то такая подстрока, если она существует, будет префиксом некоторого суффикса корпуса. То есть, если мы построим суффиксный массив, любая подстрока корпуса должна быть началом какого-либо элемента массива. Например, если мы будем искать “да” в строке “туда и сюда”, то мы обнаружим, что оно встречается в этой строке дважды, а также что с него начинаются две строки в массиве, приведенном выше.

Индекс Суффикс
2      да и сюда
9      да

Но так как суффиксный массив отсортирован, мы можем быстро найти эти элементы методом бинарного поиска, а индексы укажут нам место искомой подстроки в исходном тексте.

По направлению к поиску по регулярным выражениям


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

В процессе индексации livegrep считывает все исходники и объединяет их в огромный буфер (livegrep строит суффиксный массив с помощью открытой библиотеки libdivsufsort; более старые версии livegrep использовали поразрядную сортировку (radix sort), которая на некоторых наборах могла иметь квадратичную сложность – с внедрением divsufsort скорость построения индекса значительно увеличилась). Затем в памяти сохраняется так называемая “таблица файл — содержание" (file content map)” — отсортированная таблица вида (начальный индекс, конечный индекс, информация о файле), которая позволяет определить, из какого файла в буфер попали определенные байты.

(Механизм описан упрощенно, на самом деле в livegrep вместо одного гигантского суффиксного массива используется несколько, кроме того, мы сжимаем входные данные с помощью дедупликации одинаковых строк, что усложняет file content map. Возможно, мы рассмотрим эти подробности в одном из будущих постов).

Но как же применить эту структуру для быстрого поиска соответствий регулярным выражениям?

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

Например, возьмем регулярное выражение /hello.*world/. Очевидно, что все искомые подстроки будут содержать слово “hello”, а значит, мы можем найти все строки с этим словом, а затем проверить их с помощью регулярного выражения.

Более сложный поиск


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

  • Поиск по диапазону: с помощью бинарного поиска с обоих концов массива можно быстро найти все вхождения из диапазона символов. Если наш диапазон [A-F], бинарным поиском находим первый суффикс, начинающийся на A, и последний суффикс, начинающийся на F, и, как нам известно, каждый элемент суффиксного массива между ними начинается с буквы из диапазона между A и F.

  • Поиск цепочек: если существует блок суффиксного массива, у всех элементов которого общий префикс, то поиск можно сузить с помощью дополнительных поисков внутри этого блока по следующему символу. Например, если мы ищем /hi(s|m)/, мы можем найти все элементы, начинающиеся с hi, и получим блок из смежных элементов внутри массива. Так как элементы внутри блока отсортированы, мы можем выполнить еще пару бинарных поисков в этом диапазоне, но теперь по третьему символу. Один поиск будет искать s, второй — m, и в конце концов мы получим два более мелких отрезка — для his и для him.

Есть также возможность выполнять поиск сразу нескольких элементов и объединять результаты. Например, для регулярного выражения /hello|world/ мы отдельно найдем совпадения для «hello», отдельно для «world», а потом посмотрим на местоположения обоих слов в тексте.

Кроме того, мы можем применить комбинацию всех этих стратегий. Например, поиск по выражению /[a-f][0-9]/ будет осуществляться следующим образом:

  1. Бинарный поиск для нахождения a-f
  2. Разделение на 6 блоков, по одному для a, b, c, d, e и f
  3. Внутри каждого из блоков выполняем бинарный поиск по второму символу и находим те блоки, где второй символ принадлежит диапазону [0-9]

Пример
1.

A…




F…

2.

A…
B…
C…
D…
E…
F…

3.

A…
A[0-9]…
B…
B[0-9]…
C…
C[0-9]…
D…
D[0-9]…
E…
E[0-9]…
F…
F[0-9]…


В результате мы получим набор отрезков суффиксного массива, элементы которых указывают на подстроки, соответствующие /[A-F][0-9]/.

Это по сути означает, что ответы на запросы могут иметь следующую структуру (в синтаксе языка Go):

type IndexKey struct {
  edges []struct {
    min  byte
    max  byte
    next *IndexKey
  }
}

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

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

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

Во многих случаях это просто: класс символов легко преобразуется в набор диапазонов, буквенная строка — это линейная цепочка ключей IndexKey с диапазонами в один символ и т.д. Все усложняется, когда нам встречаются операторы повторения или дизъюнкции (|). Надеюсь написать об этом подробнее в одном из будущих постов, а пока, если вам любопытно, можете почитать indexer.cc или поэкспериментировать с analyze-re, у которого есть режим вывода dot, показывающий результат анализа livegrep.

Применение результатов


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

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

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

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

После того как мы прогоним RE2 по всем позициям, содержащим потенциальные соответствия, мы получим окончательный список соответствий, найденных в корпусе. Для каждого соответствия с помощью упомянутой выше file content map найдем файл, содержащий данные байты. Чтобы определить номер строки, вытащим все содержание файла и посчитаем символы перехода строки.

Если же мы ограничиваем поиск конкретным файлом (например, file:foo\.c), мы проходим по file content map одновременно со списком результатов после прохождения по индексам, и удаляем из него записи, если содержащий их файл не совпадает с файлом из запроса.

Интересная особенность этого подхода в том, что ограничение по имени файла на самом деле сокращает область поиска незначительно — livegrep все равно проходит по всему суффиксному массиву и все равно рассматривает каждое найденное соответствие (хотя он мог бы намного быстрее проверить file content map и не вызывать RE2). Тем не менее, livegrep настолько производителен, что ему не обязательно пользоваться преимуществом ограничения по имени файла, чтобы выдавать результат быстро — таким ему и необходимо быть, чтобы уметь обрабатывать запросы без указания конкретного файла.

Из этого следует, что наиболее медленно livegrep будет обрабатывать те запросы, которые строго ограничивают путь к файлу и при этом неэффективно используют суффиксный массив: . file:zzzz, пожалуй, один из самых медленных на сегдня запросов, которые можно отправить livegrep.

Продолжение следует


Мы рассмотрели работу livegrep только в общих чертах. В следующий раз я более подробно расскажу, как мы строим index query и трансформируем регулярное выражение в index query, а затем я наконец расскажу, как в livegrep на самом деле работают суффиксный массив и структуры file-content по сравнению с упрощенной версией, описанный здесь. В частности, livegrep на самом деле значительно сжимает входные данные, что сокращает потребление памяти и ускоряет поиск, ценой усложнения построения индекса и обработки результатов.

О, а приходите к нам работать? :)
wunderfund.io — молодой фонд, который занимается высокочастотной алготорговлей. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

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

Присоединяйтесь к нашей команде: wunderfund.io
Автор: @wunder_editor Nelson Elhage
Wunder Fund
рейтинг 169,79
Мы занимаемся высокочастотной торговлей на бирже
Похожие публикации

Комментарии (1)

  • +1
    Кажется, что можно весьма универсально прогонять регулярные выражения по всем суффиксам, если использовать их представление в виде детерминированных конечных автоматов.

    Пусть, например, из начального состояния выводят рёбра с буквами a и b (например, регулярка начинается с [ab]). Переходим по каждому из рёбер, находя (двумя бинарными поисками на ребро) диапазоны подходящих суффиксов. Запишем в состояние, в которое мы пришли по ребру a, диапазон суффиксов, начинающихся с a, в состояние, в которое мы пришли по ребру b — диапазон суффиксов, начинающихся с b (если это то же самое состояние, то можно держать в нём список диапазонов). И так идём дальше по рёбрам.

    Итого алгоритм такой: если есть ребро из состояния q1 в состояние q2, то берём все диапазоны, записанные в q1, находим в каждом очередной поддиапазон, записываем список из непустых полученных поддиапазонов в q2 (или дописываем в q2, если мы уже посещали это состояние), опционально объединяем смежные/пересекающиеся диапазоны, идём дальше. Проходим так по всем рёбрам от начальных состояний до конечных. Вуаля, универсальный и, кажется, оптимальный алгоритм.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка