Меня зовут Дмитрий Ольшанский, я ведущий инженер Т-Банка. Расскажу о новом (насколько мне известно) алгоритме поиска текста по шаблону. Такая задача возникла в рамках проекта Sage — observability-платформы от Т-Банка, для которой мы строим новый бэкэнд для структурированных логов, SageDB.
Какая была задача
Имея, например, запрос hello *orld, нам нужно было найти строки, содержащие как hello world, так и hello, wonderful world, — то есть звездочка подразумевает любое количество символов и мы игнорируем знаки препинания.
Для традиционных подходов с токенизацией это выливается в различные проблемы: нужно собрать все токены, оканчивающиеся на orld, и иметь в виду пропуск произвольного числа токенов между hello и концевым токеном. Больше звездочек — больше проблем.
В SageDB мы сознательно отходим от построения полных inverted index и применяем brute-force-тактику — ищем шаблон по всем отфильтрованным строкам.
Когда у нас возникла проблема поиска текста по шаблонам, первое, что пришло в голову, — регулярные выражения. Шаблон hello orld можно описать как \bhello\s+.orld\b, для простоты будем считать, что слова разделены пробелами.
Поскольку я еще и автор std.regex-модуля языка D, проблемы такого подхода меня не сильно удивили: ожидаемо большие накладные расходы на запуск движка на отдельных строках.
Даже использование Hyperscan не дало желаемой скорости работы и прибавило проблем интеграции с JVM, так как наш движок написан на Java. Плата за универсальность слишком высока и мы решили использовать более простые и быстрые алгоритмы поиска подстрок там, где это возможно.
Так появилась идея взять за основу алгоритм Shift-Or и максимально приблизиться к нашим шаблонам. Это был путь экспериментов, и постепенно мне удалось не только сделать приближенное решение, но и вовсе уложить всю логику наших шаблонов в простой алгоритм, который я называл BitNFA. Покажу наш путь по шагам и расскажу, как из простой идеи появился новый алгоритм.
Начало — Shift-Or
Сначала разберемся с самим алгоритмом Shift-Or. В других статьях по этой теме, как мне кажется, слишком увлекаются двоичными матрицами, упуская главный момент: алгоритм на самом деле частный случай поиска подстроки через симуляцию NFA. Так что лучший способ разобраться в алгоритме — это увидеть, как работает NFA, а затем уже переходить к битам.
Для простоты возьмем подстроку ababc и построим автомат для ее поиска. У нас есть одно стартовое состояние, которое всегда активно, — так мы «прикладываем» подстроку к каждому символу в исходном тексте. Далее следует цепочка состояний, по одному на каждый символ подстроки, переходы будут обозначены символом, который мы ожидаем увидеть, чтобы перейти в следующее состояние. Наконец, есть финальное состояние — если оно стало активным после очередного символа, мы нашли подстроку.
В чем же недетерминированность автомата? Простой ответ — в том, что одновременно могут быть активны несколько состояний. Такая ситуация может возникнуть при поиске в строке abababc. После того как мы прочитали ab, мы снова видим a — и заранее не знаем, будет ли подстрока найдена начиная с первого символа a или со второго. Автомат тоже этого «не знает» и поддерживает два активных состояния, отражающих этот недетерминизм.
Процесс симуляции автомата прост: мы считываем очередной символ и для всех активных состояний смотрим на стрелочки переходов. Если есть допустимый переход, мы передвигаем активное состояние вперед. В противном случае активное состояние исчезает.
Поиск через симуляцию автомата довольно изящен, но требует где-то хранить состояния и в простой реализации будет работать медленно: за O(mn), где m — число состояний в автомате, а n — размер текста.
Существуют разные методики ускорения NFA, но по-настоящему красивое решение для линейных автоматов — это Shift-Or. Посмотрим на состояния нашего автомата и сопоставим каждому состоянию число по порядку следования. Теперь если число состояний меньше 64 (для 64-битных систем, 32 для 32-битных), то мы можем описать любую комбинацию активных состояний как одно машинное слово. Каждому состоянию дается один бит: 0 будет активным, а 1 — неактивным состоянием. На следующем рисунке будем считать, что автомат уже прошел через abab и активными остались состояния 1 и 3.
Когда у нас появилось такое компактное описание всех состояний, остается сделать последний шаг — симуляцию автомата через побитовые операции. Легко заметить, что побитовый сдвиг переведет все состояния разом вперед.
Остается отфильтровать состояния, которые должны остаться активными. Для этого прекрасно подходит операция побитового ИЛИ с некоторой маской — она, конечно, для каждого символа своя. Важно то, что мы обрабатываем все состояния одной операцией, так что построение этих масок учитывает все переходы для одного символа.
В нашем случае для символов a и b есть два перехода, им будет соответствовать два нулевых бита в маске, так мы сохраним нули при наложении маски через ИЛИ.
Рассмотрим финальную стадию: состояние автомата у нас — два нуля в состояниях 1 и 3 после предпоследнего символа b.
Аналогично рассмотрим сдвиг битов, теперь у нас активно последнее состояние.
Фильтрация через маску для символа c.
Финально у нас есть позиция бита, при попадании на которую поиск успешно завершается, такое можно проверить через побитовое И — должен получиться 0 при наложении финальной маски. Для простоты будем называть машинное слово, содержащее наш автомат, просто словом.
Рассмотрим алгоритм в псевдокоде Си-подобного языка — его несложно привести в реальный код на С/С++/Java/C#/Rust. Главное, у нас есть подготовка, которая выполняется один раз для подстроки. Далее с подготовленными таблицей и маской завершения мы можем многократно и в разных строках искать нужную нам подстроку.
Основной цикл максимально прямолинеен и состоит из одного чтения таблицы, одного сдвига влево, побитового ИЛИ и побитового И. Такие плотные циклы замечательно работают на современных процессорах, и при необходимости его можно размотать (unroll), что, скорее всего, и сделает оптимизирующий компилятор (в том числе JIT).
long[256] table;
long finish;
prepare(string substring) {
for (int i=0; i<256;i++) {
table[i] = -1L; // -1 это все единицы во всех разрядах
}
for (int i=0; i<substring.length; i++) {
table[substring[i]] &= ~(1L<<i); //ноль в позиции i
}
finish = 1<<(substring.length-1);
}
search(string input) {
long state = -1L;
for(int i=0; i<input.length;i++) {
state <<= 1;
char c = input[i];
state |= table[c];
if ((state & finish) == 0) return true;
}
return false;
}Расширение
Теперь об интересных особенностях алгоритма: он без изменений в логике поддерживает классы символов, прямо как в регулярных выражениях. Мы можем при подготовке разрешить переход состояния для нескольких символов одновременно. Мы легко реализуем шаблоны с условным ‘\s’ — переход по любому пробельному символу (в том числе для нашей изначальной задачи можем учесть еще и знаки препинания) и даже ‘.’ — переходу по любому символу.
С классами символов разобрались, теперь что там со звездочками из регулярных выражений? Для простоты попробуем внедрить в наш автомат понятие ‘\s+’ из исходного регулярного выражения. Выделим состояние и бит под \s. Теперь во время сдвига нам надо сделать состояние ‘\s’ снова активным, и, поскольку все в битах, нам достаточно сделать битовую маску для всех состояний с плюсом.
Наложим маску на текущее слово через ИЛИ, собирая нули в активных состояниях на этих позициях, сдвинем назад и опять наложим уже через И, тем самым возвращая только эти состояния назад. Так мы добавляем цикличность в наш автомат, немного расширив алгоритм. Мы не теряем преимуществ нашего побитового подхода, одна операция обслуживает все состояния с плюсом.
long[256] table;
long finish;
long plus_mask;
prepare(string pattern) {
plus_mask = -1L; // -1 это все единицы во всех разрядах
for (int i=0; i<256;i++) {
table[i] = -1L; // -1 это все единицы во всех разрядах
}
for (int i=0; i<pattern.length; i++) {
char c = pattern[i];
long mask = (1L<<i); //ноль в позиции i
if (isPaddingSymbol(c)) { // пробельный символ
for (p in PADDING_SYMBOLS) {
table[p] &= ~mask;
}
// фиксируем 0 на позиции пробельного символа
plus_mask &= ~mask;
} else {
table[c] &= ~mask;
}
}
finish = 1<<(pattern.length-1);
}
search(string input) {
long state = -1L;
for(int i=0; i<input.length;i++) {
state <<= 1;
// сдвигаем состояния с плюсом на 1 назад
state &= (state | (plus_mask << 1)) >> 1;
char c = input[i];
state |= table[c];
if ((state & finish) == 0) return true;
}
return false;
}
Состояние с плюсом кажется более простым, чем состояние со звездочкой, так как у нас есть привычное состояние. Отличие звездочки лишь в том, что мы должны передвинуть вперед состояние, чтобы учесть случай нулевого повторения. Так что для . мы используем тот же подход, то есть маска для плюса будет активна и для этого состояния.
Теперь, чтобы превратить .+ в .*, нам нужно учесть случай нулевой длины. На языке автоматов это называется «эпсилон-переход», то есть стрелочка, которая работает даже без символа. Поскольку все у нас в битовом подходе, опять понадобится битовая маска, чтобы выделить эти состояния. Дальше все просто: применив маску, сдвинем вперед и снова наложим на текущее слово.
long[256] table;
long finish;
long plus_mask;
long star_mask;
prepare(string pattern) {
plus_mask = -1L; // -1 это все единицы во всех разрядах
star_mask = -1L; //
for (int i=0; i<256;i++) {
table[i] = -1L; // -1 это все единицы во всех разрядах
}
for (int i=0; i<pattern.length; i++) {
char c = pattern[i];
long mask = (1L<<i); //ноль в позиции i
if (c == '*') {
for (int j=0; j<256; j++) {
c[j] &= ~mask;
}
//start_mask отвечает только за сдвиг вперед
//star_mask за сдвиг назад те повторения
plus_mask &= ~mask;
star_mask &= ~mask;
}
else if (isPaddingSymbol(c)) { // пробельный символ
for (p in PADDING_SYMBOLS) {
table[p] &= ~mask;
}
// фиксируем 0 на позиции пробельного символа
plus_mask &= ~mask;
} else {
table[c] &= ~mask;
}
}
finish = 1<<(pattern.length-1);
}
search(string input) {
long state = -1L;
for(int i=0; i<input.length;i++) {
state <<= 1;
// продвигаем вперед состояния со звездочкой
long state1 = (state | star) << 1;
// сдвигаем состояния с плюсом на 1 назад
long state2 = (state | (plus_mask << 1)) >> 1;
state = state & state1 & state2;
char c = input[i];
state |= table[c];
if ((state & finish) == 0) return true;
}
return false;
}Мы реализовали лишь что-то вроде \s+hello\s+.*orld\s+ в сравнении с искомым \bhello\s+.*orld\b. Здесь все решается просто: для начального перехода мы сделаем два состояния активными сразу — и ‘\s+’, и ‘h’. Концовка также решается дополнительной проверкой после финального сдвига влево.
long[256] table;
long finish;
long plus_mask;
long star_mask;
prepare(string pattern) {
plus_mask = -1L; // -1 это все единицы во всех разрядах
star_mask = -1L; //
long mask = 1
for (int i=0; i<256;i++) {
table[i] = -1L; // -1 это все единицы во всех разрядах
}
for (c in PADDING_SYMBOLS) {
table[c] = ~mask;
}
plus_mask &= ~mask;
for (int i=0; i<pattern.length; i++) {
char c = pattern[i];
mask <<= 1;
if (c == '*') {
for (int j=0; j<256; j++) {
c[j] &= ~mask;
}
//start_mask отвечает только за сдвиг вперед
//star_mask за сдвиг назад те повторения
plus_mask &= ~mask;
star_mask &= ~mask;
}
else if (isPaddingSymbol(c)) { // пробельный символ
for (p in PADDING_SYMBOLS) {
table[p] &= ~mask;
}
// фиксируем 0 на позиции пробельного символа
plus_mask &= ~mask;
} else {
table[c] &= ~mask;
}
if (pattern[pattern.length-1] != '*') {
mask = mask shl 1;
for (p in PADDING_SYMBOLS) {
table[p] &= ~mask;
}
// фиксируем 0 на позиции пробельного символа
plus_mask &= ~mask;
}
}
finish = mask;
}
search(string input) {
long state = -4L; // первые два состояния активны
for(int i=0; i<input.length;i++) {
// продвигаем вперед состояния со звездочкой
long state1 = (state | star) << 1;
// сдвигаем состояния с плюсом на 1 назад
long state2 = (state | (plus_mask << 1)) >> 1;
state = state & state1 & state2;
char c = input[i];
state |= table[c];
if ((state & finish) == 0) return true;
state <<= 1;
}
return (state & finish) == 0;
}Производительность
Стоило ли бороться? Со всеми изменениями мы делаем приличное количество побитовых операций в основном цикле. Здесь имеет смысл заняться бенчмарками.
Главное, что мы сохранили, — это стабильность алгоритма. Вне зависимости от количества звездочек или длины шаблона поиск занимает фиксированное O(n).
Для бенчмарка выберем три паттерна и три строки, получится матрица на девять комбинаций для каждого алгоритма. Строки представляют собой типовые сообщения из реальных логов, при этом third отличается большим размером — около килобайта. В качестве алгоритмов сравниваем regular expressions из JDK, наш предыдущий алгоритм с токенизацией (custom) и, наконец, BitNFA.
Первая пара — BitNFA vs custom, числами указано соотношение скоростей в операциях в секунду (speedup). То есть, например, 2,269 означает, что BitNFA в два с лишним раза быстрее, чем custom.
Pattern/Input | first | second | third |
| 2,269 | 3,134 | 2,286 |
| 3,188 | 6,065 | 14,436 |
| 2,703 | 4,082 | 5,494 |
Видим, что наш предыдущий алгоритм в 2—12 раз медленнее — в зависимости от паттерна и строки. Эта нестабильность нас беспокоила и привела к поиску новых решений. Можно оценить типовую разницу в производительности через геометрическое среднее, по сравнению с custom она составит 4,021 раза.
Вторая пара — BitNFA vs регулярные выражения из JDK, числами показано отношение скоростей.
Pattern/Input | first | second | third |
| 3,000 | 5,715 | 5,785 |
| 5,762 | 5,574 | 5,659 |
| 132,755 | 3,192 | 4,238 |
Сравнивать с регулярными выражениями иногда даже неудобно: с ними случаются катастрофические падения производительности при большом числе звездочек. В отдельном случае регулярки в 132 раза медленнее, чем BitNFA, и это только две звездочки! Такое не подходит для нагруженного движка поиска, где пользователи зачастую составляют довольно сложные запросы. Геометрическое среднее — 6,831.
Ограничения
И вот конкуренты далеко позади, кажется, самое время праздновать победу. Но есть нюанс: BitNFA в представленном виде ограничена ASCII-символами и шаблон не может быть длиннее 62 символов (64 минус 2 символа — стартовый и концевой пробелы). На практике 60 символов более чем достаточно, но приходится делать фоллбэк.
Так, а что там с юникодом? Кратко говоря, для поддержки полного UTF-8 нужно декодировать байты кодировки (codeunit) в абстрактные символы (codepoint). Code point — это числа из диапазона [0, 1114111], и потребуется большая таблица для хранения масок при таком размере алфавита. Эти таблицы, как правило, упаковывают в trie, то есть делают многостадийными таблицами.
Мы для простоты используем только первый plane из всего Unicode, тем самым укладываясь в 64 тысячи записей в таблице, то есть с русским языком, но без поддержки эмодзи. В действительности мы перейдем на folded trie, как только такая необходимость возникнет.
Итоги нашего пути
Взяв за основу довольно гибкий алгоритм поиска подстроки, мы смогли поэтапно расширить его возможности далеко за пределы изначальной функциональности. Каждый шаг по-своему прост, но требует экспериментов, итерации и, главное, нацеленности на результат.
Всегда стоит вопрос: а можно ли сделать больше, не потеряв при этом производительности, ведь она и есть мерило любого алгоритма? Без решения вопроса производительности любой алгоритм — это лишь еще один способ решить задачу, один из многих и, возможно, неактуальный на практике.
Побитовый параллелизм — это кладезь эффективных алгоритмов и структур данных, который, я уверен, еще не раз преподнесет нам новые решения в самых разных областях. Например, для исходной задачи поиска подстрок появился мощный алгоритм BNDM, доступный и для других языков программирования. Открытой задачей является поиск таких гибридов традиционных алгоритмов и побитового параллелизма.