![image](https://habrastorage.org/getpro/habr/post_images/f49/bb2/620/f49bb262046eed26721865e934005e06.png)
Еще в январе 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]/
будет осуществляться следующим образом:- Бинарный поиск для нахождения
a-f
- Разделение на 6 блоков, по одному для
a, b, c, d, e
иf
- Внутри каждого из блоков выполняем бинарный поиск по второму символу и находим те блоки, где второй символ принадлежит диапазону
[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…
…
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