Меня зовут Дмитрий Ольшанский, я ведущий инженер Т-Банка. Расскажу о новом (насколько мне известно) алгоритме поиска текста по шаблону. Такая задача возникла в рамках проекта 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, доступный и для других языков программирования. Открытой задачей является поиск таких гибридов традиционных алгоритмов и побитового параллелизма.
Комментарии (44)
Zara6502
12.05.2025 10:20было интересно но непонятно ) но это моя особенность, отсюда вопрос первый: у вас есть шаблон например "Hello *rld" и есть 100 петабайт данных, которые начинаются на "Hello ", а потом у вас 100 петабайт повторов строки например "qrld". Что случится с вашей реализацией?
вопрос второй: как вы битами кодируете разные команды?
третий: вы упоминаете всегда 1 бит, но одним битом можно закодировать два состояния, а вы кодируете и петли и пропуски и совпадения.
четвертый: что такое маска у вас и как вы маску создадите для 100 петабайт данных?
DmitryOlshansky Автор
12.05.2025 10:20Насчет петабайт, как раз проблем не будет тк это данные а не шаблон. Просто пожужжит вашим SSD и выдаст что ничего не найдено. Биты кодируют состояние автомата, автомат по размеру пропорционален длине шаблона. 1 кодирует неактивное состояние, 0 активное. Про маску опять же маска это слово, и делается один раз для каждого символа алфавита. Советую посмотреть и может даже попробывать псевдокод для ShiftOr. Он может только строки, но петабайты данных ему не страшны)
Zara6502
12.05.2025 10:20Биты кодируют состояние автомата
я делал реализацию автомата для кодирования слов, там всё так же - 0 сдвинуть, 10 - поменять местами, 11 - еще что-то, в любом случае команда это сколько то бит.
1 кодирует неактивное состояние, 0 активное
непонятно
Про маску опять же маска это слово, и делается один раз для каждого символа алфавита
непонятно, маска чего? всех вариантов ASCII? Если судить по статье то у вас конечная маска это 0001, но она одна, а символов много.
Советую посмотреть и может даже попробывать псевдокод для ShiftOr
Поизучаю, если пойму.
DmitryOlshansky Автор
12.05.2025 10:20Про команды, нет биты здесь не кодируют операции. Автомат поисковый и каждый бит соответствует тому сколько подходящих символов мы увидели. Это конечно до звездочек, там немного сложнее, я про ShiftOr.
Про 0/1 надеюсь теперь понятно. Грубо говоря мы поддерживает много вариантов сматченной строки. С каждым символом мы сдвигаем все биты вперед и с помощью маски для текущего символа отсекаем не корректные варианты.
Маски да для всех вариантов ASCII, но не стоит путать эти маски с финальной, она просто нужна чтобы проверить дошли ли мы до финального состояния
Zara6502
12.05.2025 10:20пардон, но ничего не понимаю все равно. спасибо за попытку объяснить.
wataru
12.05.2025 10:20Вам надо почитать теорию: https://ru.wikipedia.org/wiki/Конечный_автомат
Zara6502
12.05.2025 10:20я знаю что такое автомат и как он работает, я не могу связать написанное в статье с этим. автомат всегда получает алфавит, если у вас биты, то алфавит 0 и 1, если вы хотите несколько больше чем два состояния, то вы или задаёте алфавит с фиксированным размером слова или с переменным размером, например код Элиаса/Голомба.
Если в статье например указан поиск, то я имея алфавит на основе ASCII могу для 64 бит указать только 8 команд/данных/масок. Но в статье вообще ничего не сказано про алфавит.
Маска - про неё так же нет информации.
нет информации и о том почему в статье всё показано как 1010101 словно не бывает состояний 11111 или 110011
вероятнее всего в статье остались за скобками какие-то понятные вам и автору вещи, а мне их не хватает чтобы понять рассказанное.
---
допустим алфавит никак не связан со строкой поиска и 0 и 1 применяются чтобы указать на совпало или нет, тогда не ясно как эти биты формируются. Например я хочу найти строку "abcde" в "abcabcde", то откуда берутся 64 бита команд? Ведь если бит указывает на совпадение, то сначала мы это совпадение должны получить путём сравнения, но если мы уже сравнили, то зачем нам данные о том что было раньше? мы просто переходим к следующему символу. Если это маска "ab*e", то найдя "ab" просто ждём появления "e". Как тут применить биты?
wataru
12.05.2025 10:20В статье есть картинки автоматов, принмающих шаблон.
В недетерменированном конечном автомате вы не находитесь в одном состоянии, а находитесь в каком-то их множестве. При применении символа это множество меняется: из каждого состояния во множестве делается переход по этому символу.
Так вот, 0 и 1 обозначаются состояния. 0 - те, которые активны, 1 - те, которые не активны.
Алгоритм скармливает автомату по одному символу текста, отслеживая текущие активные состояния.
Простая реализация проходилась бы циклом по всем состояниям, смотрела, активно ли оно, и есть ли оттуда переход по символу. Хитрая реализация в статье выполняет вместо цикла битовые операции сразу со всеми состояниями параллельно. Вот те состояния, из которых есть переход по этому символу - их позиции и формируют маску. Есть сделать побитовое или с маской актвиных состояний, то получим 0 только там, где есть и состояние активно, и из него можно сделать переход. Поскольку в этом автомате все переходы вперед, то сдвинув маску на 1 бит мы получим новую маску активных состояний.
Zara6502
12.05.2025 10:20Процесс симуляции автомата прост: мы считываем очередной символ и для всех активных состояний смотрим на стрелочки переходов. Если есть допустимый переход, мы передвигаем активное состояние вперед. В противном случае активное состояние исчезает.
Например мы считали символ М, смотрим на картинку, там символ А и стрелочка на 0, что с этим делать? Пусть М не равно А, тогда что?
На следующем рисунке будем считать, что автомат уже прошел через abab и активными остались состояния 1 и 3.
Если автомат сравнивал входные значения с
abab, то мы пришли вc, это состояние между последними 0 и 1, откуда взялись эти 10101? Почему автор пишет что "активными остались состояния 1 и 3" если мы их оставили позади? Если биты сдвигаются при совпадении, то почему красным закрашены нули в середине кода?wataru
12.05.2025 10:20Пусть М не равно А, тогда что?
Тогда никуда не переходим. Ни одно состояние не становится активным. Автомат строку с М не принимает вообще, ведь ее нет в шаблоне. Суть в том, чтобы проверить, активно ли последнее состояние - значит строка нашлась. Если из состояния нет перехода то активных состояний быть не может. Можете считать, что в автомате есть состояние "тупик", из которого нет выхода (все переходы в него же) и куда ведут все переходы, которых на графике нет. Но для простоты его не рисуют и не считают.
Если автомат сравнивал входные значения с
abab, то мы пришли вcНет. Мы пришли в 3 и 1. Потому что в конце строки abab есть ab. Автомат недетерменированный же. Помните, что состояние s всегда активно, потому что можно начать прикладывать строку с любой позиции. Поэтому 2 символа назад мы по a перешли одновременно из S и 1. Получили 0 и 2. На следующем символе b мы перешли одновременно из 0 и 2. Получили 1 и 3.
, откуда взялись эти 10101
У автора 0 - это активное состояние. На картинке красные состояния 1 и 3. Биты равны 0 в этих позициях. S в битах не хранится, ведь оно всегда активно.
При наложении маски мы получаем, из каких состояний будет переход. Потом это сдвигаем на 1 бит и получаем новые активные состояния.
Zara6502
12.05.2025 10:20Тогда никуда не переходим
а биты тогда зачем?
Ни одно состояние не становится активным
Если М не равно А то мы знаем только о неравенстве, о каких состояниях речь?
Автомат строку с М не принимает вообще, ведь ее нет в шаблоне
В каком шаблоне?
Суть в том, чтобы проверить, активно ли последнее состояние - значит строка нашлась. Если из состояния нет перехода то активных состояний быть не может.
Можете считать, что в автомате есть состояние "тупик", из которого нет выхода (все переходы в него же) и куда ведут все переходы, которых на графике нет. Но для простоты его не рисуют и не считают.
За этими фразами скрывается какой-то механизм, который я и не понимаю.
Нет. Мы пришли в 3 и 1. Потому что в конце строки abab есть ab. Автомат недетерменированный же. Помните, что состояние s всегда активно, потому что можно начать прикладывать строку с любой позиции. Поэтому 2 символа назад мы по a перешли одновременно из S и 1. Получили 0 и 2. На следующем символе b мы перешли одновременно из 0 и 2. Получили 1 и 3.
Тут описывается что-то с чем я не знаком, я не понимаю как это устроено и как сразу и 3 и 1.
У автора 0 - это активное состояние. На картинке красные состояния 1 и 3. Биты равны 0 в этих позициях. S в битах не хранится, ведь оно всегда активно.
При наложении маски мы получаем, из каких состояний будет переход. Потом это сдвигаем на 1 бит и получаем новые активные состояния.
мне кажется бесполезно ) не тратьте время, пардон что беспокоил.
wataru
12.05.2025 10:20а биты тогда зачем?
Множество активных состояний хранится в битовой маске
Если М не равно А то мы знаем только о неравенстве, о каких состояниях речь?
По букве М мы должны взять все состояния, которые активны и из которых есть переход по М. И сделать оттуда переход. Активные состояния, из которых нет перехода из М никуда не переходят.
В каком шаблоне?
Строка, которую мы ищем
За этими фразами скрывается какой-то механизм, который я и не понимаю.
Перечитайте википедию про конечные автоматы. Особенно про недетерменированные.
Zara6502
12.05.2025 10:20Множество активных состояний хранится в битовой маске
там же два состояния можно хранить для одного символа, как именно появится множество для всех возможных вариантов строки?
По букве М мы должны взять все состояния
откуда их взять и как они там изначально появились?
Строка, которую мы ищем
Получается всё равно сравнивается строка и подстрока?
Перечитайте википедию про конечные автоматы. Особенно про недетерменированные.
не в этом дело. я не понимаю как именно это реализовано. я практик, перекладывать теорию на код я практически не умею. а тут я даже не понимаю что происходит.
wataru
12.05.2025 10:20У нас K состояний в автомате. По длине строки шаблона (что ищем). Каждое может быть активно или нет. Каждому состоянию соотвествует один бит.
Каждое состояние означает, что сейчас вот в этом месте текста можно приложить шаблон до вот этого символа. Вот на картинке выше активны состояния 1 и 3. Состояние 1 означает, что к тексу сейчас можно приложить "ab". Состояние 3 - "abab". Если актвно последнее состояние - вы можете приложить всю искомую строку и нашли совпадение.
Когда обрабатываем следующий символ текста, надо взять активные состояния, из которых следующий символ как в тексте, и сделать активными следующие состояния. Потому что в них происходит переход.
Простая реализация: циклом по всем состояниям прошлись, проверили. что оно активно и посмотрели, какой там символ нужен. Но раз состояний не более 64, можно это все заменить битовыми операциями.
Zara6502
12.05.2025 10:20я пытаюсь сопоставить теорию с практическим применением.
У нас K состояний в автомате. По длине строки шаблона (что ищем).
Это абстракция не привязанная к программированию. Я могу её воспринимать как факт, что у нас есть эти состояния, но что это такое, как работает и как этим пользоваться я не знаю.
Каждое может быть активно или нет
Опять же это просто теория, а на практике это что?
Каждому состоянию соотвествует один бит
Например строка abc, это что? 000, 001, 010, 011, 100, 101, 110, 111? Получается символов в строке три, но ascii кодов например 128, получается 128 в третьей степени вариантов, а битов у нас всего 8 вариантов. Не совпадает что-то.
Каждое состояние означает, что сейчас вот в этом месте текста можно приложить шаблон до вот этого символа
как и в предыдущем примере, вариантов с ascii очень много, как это реализуется?
Вот на картинке выше активны состояния 1 и 3. Состояние 1 означает, что к тексу сейчас можно приложить "ab". Состояние 3 - "abab"
Это какая-то теоретическая выкладка, а как мы это проверяем с помощью кода? почему 1 и 3?
Когда обрабатываем следующий символ текста, надо взять активные состояния, из которых следующий символ как в тексте, и сделать активными следующие состояния
как это происходит на практике?
циклом по всем состояниям прошлись
откуда нам их взять? кто эти состояния создал, как они хранятся?
проверили. что оно активно и посмотрели, какой там символ нужен
если активны 1 и 3 (что бы это не значило), то как осуществляется проверка? как сопоставляем символу?
wataru
12.05.2025 10:20Например строка abc, это что? 000, 001, 010, 011, 100, 101, 110, 111?
000 означает, что мы ничего не нашли. 001 - нашли c, 010 - b, 011 - нашли b и c (это невозможно для этой строки, ибо текст не может одновременно оканчиваться на b и c)...
Давайте с другой стороны: вы знакомы с динамическим программированием?
Zara6502
12.05.2025 10:20я знаю что DP это использование предыдущих вычислений, как например в моей статье про поиск квадрата из единиц.
000 означает, что мы ничего не нашли
и как это что-то упрощает если вместо того чтобы вернуть false мы вернули 000 который где-то сначала кодировали, а потом еще нужно декодировать.
001 - нашли c
то есть для строки abc и для строки def число 001 в одном случае будет означать что мы нашли c а в другом f? а как это различать? Например есть переменная string и есть substring, мы их передали функции find(string, substring) и она вернула 001, как мы узнаем там c или f? или тут просто важна информация что мы нашли букву на позиции 3? Ну, допустим, но зачем нам это промежуточное состояние с битами?
wataru
12.05.2025 10:20Вот вам ДП для этой задачи (найти вхождения шаблона в тексте):
dp[i][j] - находятся ли в конце первых i символов текста первые j символа шаблона (можно ли приложить шаблон так, что в позиции i+1 текста окажется j-ый символ шаблона).
Например, если текст "abacaba" а шаблон "aba", то dp будет:
{{1,0,0,0}, // ноль символвов в тексте. можно приложить только 0 из шаблона {1,1,0,0}, // текст - "a". Можно приложить "" и "a" {1,0,1,0}, // текст "ab". Можно пиложить "" и "ab" {1,1,0,1}, // к "aba" можно приложить "a" и "aba" {1,0,0,0}, // текст "abac" - ни "a", "ab", "aba" приложить нельзя. ... }Обратите внимание dp - это мы прикладываем кусок шаблона к куску текста в конце текста.
Ясно, что если dp[i][len(pattern)] == 1 - то мы нашли вхождение. К какому-то куску текста приложили весь шаблон.
База: dp[i][0] = 1, dp[0][j] = 0
Переход: dp[i][j] = (text[i-1] == pattern[j-1]) & dp[i-1][j-1]. Можем приложить, только если последние символы совпали и левее можно приложить оставшуюся часть.
Вот одна строка этого ДП - это и есть биты с которыми работает алгоритм. Длина строки матрицы = длине шаблона+1 = количеству состояний в автомате.
Можно пересчитывать ДП двумя циклами, а можно заметить, что все операции
(text[i-1] == pattern[j-1]) & dp[i-1][j-1]можно подсчитать одной битовой операцией, если кажду строку матрицы хранить в битовой маске. Берем строку для dp[i-1], сдвигаем и зануляем все биты, где(text[i-1] != pattern[j-1]).Далее, вот эти зануляемые биты, там от i зависит только text[i-1]. Т.е. если в разных позициях i в тексте один и тот же символ, то мы занулим одни и те же биты в строке матрицы. Поэтому можно предподсчитать все позиции j, для которых для данного символа алфавита условие выполняется. Это и есть маски для символов. В итоге, вместо цикла по j надо лишь сделать
dp[i] = (dp[i-1] << 1) & mask[text[i-1]];Ну и, храним только последнюю строку в dp.
Но это без зведочек в шаблоне, со зведочками чуть-чуть сложнее вычисления. Будет
dp[i][j] = ((text[i-1] == pattern[j-1]) & dp[i-1][j-1]) || (pattern[i-1] == '*' & (dp[i-1][j-1] | dp[i-1][j]))Тут также все можно вычислить за несколько битовых операций.
Вот это ДП эквивалентно автомату. Тут в каждой строке 1 означает активное состояние автомата после i символов. Пересчет ДП - это изменение активных состояний.
wataru
Тольео если длина шаблона менее 64 символов (на самом деле строже - ибо '*' пораждают несколько состояний, и ограничние на количество состояний).
На самом деле ваш алгоритм все те же O(n*m), только там еще константа 1/64 из-за битовых операций, и при ограничении на m это выглядит как O(n).
Но это так, придирки. Статья хорошая и написано все понятно и доступно.
Есть еще вариант ввести это не через NFA, а фактически через DP: может ли в i-ой позиции текста заканчиваться строка, удовлетворяющая первым j символам шаблона. База - для j=0 всегда true. Переходы по последнему символу шаблона: если это не *, то должно совпасть с текстом, иначе можно звездочку съесть текущим символом или не есть. Опять же, это хорошо оптимизируется с помощью битовых операций. В итоге получится очень похожий код и тоже с битовым сдвигом, если не такой же в точности.
DmitryOlshansky Автор
Про m - как и ShiftOr алогритм не зависит от длины m, так что это никак не O(mn). То есть если шаблон уложится, то нет разницы в скорости было ли m равно 4 или скажем 60. Поэтому все же O(n), да это с ограничениями. Про DP все же отмечу что для представления в уме, оно все же будет посложнее, чем похоже и вызвана такая непривычная сложность описания того же ShiftOR. Когда таблицы не ложатся на простую для восприятия основу алгоритмы кажутся сложнее, и как следствие меньше людей ими интересуются.
wataru
Это особенность реализации. Вы могли бы вместо int64 использовать int8 для m=4. И там уже и в кеш сильно больше чего влезет, и сами операции меньше тактов могут занять. Просто вы для простоты кода и для маленьких m используете большой тип данных, даже если это теоретически может быть медленнее.
Но вообще, если мы говорим про O(), то надо устремлять m в бесконечность. И ваш алгоритм отлично работает и для сколь угодно большого m, если его чуть-чуть допилить: вместо одной маски у вас будут массив из ceil(m/64) чисел.
DmitryOlshansky Автор
Про размер слова верно, тут главное уместиться в L1 кеш, дальше большой выгоды получить будет трудно. 8*256 = 2кб при этом для чистого ASCII можно смело брать вдвое меньше. Скорость работы непосредственно битовых операций от размера не зависит. Так что при прочих равных брать меньше 64 на 64-битном процессоре смысла нет.
Про допилить до произвольного m, да можно, но нужно быть аккуратным чтобы не деградировать основной случай m < 64. По сути самое простое решение выбирать алгоритм по размеру паттерна и сделать отдельные реализации под 1 машинное слово, под 2 ну и под k штук.