Еще в январе 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]

В результате мы получим набор отрезков суффиксного массива, элементы которых указывают на подстроки, соответствующие /[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