STR Строки и тексты Алгоритм
Наивный поиск подстроки
Также: Naive string search · brute-force string matching · поиск перебором · прямой поиск подстроки · strstr · indexOf
Приложить образец к каждой позиции текста и сравнивать буквы, пока не встретится отличие. В худшем случае это n · m сравнений, а на обычном тексте чуть больше одного на позицию: первая же буква почти всегда не та. Поэтому такой поиск, ускоренный фильтром по одной букве, работает внутри стандартных библиотек, а линейные алгоритмы стоят при нём страховкой.
Где в первой части «Войны и мира» появляется Пьер? Программа ниже умеет отвечать на этот вопрос только одним способом: приложить слово «Пьер» к каждой из 244 497 позиций текста и сравнить буквы. Совпали все четыре — нашли. Нет — сдвинуть слово на одну позицию и начать заново. Нажмите ▶ и посмотрите, как это выглядит вблизи, или выберите другое имя. Полоса сверху — вся часть, от салона Анны Павловны до Лысых Гор, по главам.
Пьер встречается в первой части 243 раза. На это ушло 245 462 сравнения букв, всего на 965 больше, чем позиций. Посмотрите на нижний график. 244 018 сдвигов из 244 497 закончились на первой же букве: там в тексте стояла не «П». Ещё на 236 сдвигах «П» совпала, а вторая буква — нет. Дальше второй буквы поиск заходил только там, где действительно стоял Пьер. Перебор, который в худшем случае стоит n · m, на прозе работает почти за n. Почему так выходит, когда это перестаёт быть правдой и как этим пользуются стандартные библиотеки — об этом статья.
Идея
Приложить образец к началу текста, как линейку, и сравнивать буквы слева направо до первого отличия. Совпали все — вхождение. Нашлось отличие — сдвинуть образец на одну позицию и начать сначала. Ничего не готовить заранее и ничего не помнить о прочитанном.
Пусть текст t длины n, образец p длины m. Положение образца, при котором его первая буква стоит под буквой t[s], называют сдвигом s; сдвигов n − m + 1, от 0 до n − m. Вот все сдвиги образца «кол» в слове «колокол» и образца aaab в восьми буквах a — так их печатает листинг из раздела с кодом. Справа — сколько сравнений стоил сдвиг:
колокол
кол 3 found
к≠о 1
к≠л 1
к≠о 1
кол 3 found
5 shifts, 9 comparisons
aaaaaaaa
aaab≠a 4
aaab≠a 4
aaab≠a 4
aaab≠a 4
aaab≠a 4
5 shifts, 20 comparisons
В «колоколе» три сдвига из пяти отвергнуты первой буквой. В тексте из одних a каждый сдвиг доходит до последней буквы образца и только там узнаёт, что вхождения нет. Следующий сдвиг перечитывает те же три a, которые только что совпали: поиск ничего не помнит. Вся разница между лучшим и худшим случаем — в том, как далеко заходит сравнение на одном сдвиге.
Наивный поиск делает не меньше n − m + 1 и не больше (n − m + 1) · m сравнений букв. Обе границы достигаются. Дополнительной памяти, кроме двух счётчиков, ему не нужно.
На каждом сдвиге сравнивается хотя бы первая буква и не больше m букв. Нижняя граница достигается, когда первая буква образца не встречается в тексте вовсе: каждый сдвиг стоит одно сравнение. Верхняя — на тексте an и образце am−1b: на каждом сдвиге первые m − 1 букв совпадают, а последняя нет. Листинг проверяет это при n = 10 000 и m = 100: 990 100 сравнений, ровно (n − m + 1) · m.
Квадратичный худший случай и делает этот поиск «наивным»: на тексте в миллион букв и образце в тысячу он может сделать миллиард сравнений. Но худший случай требует особенного текста. На первой части романа поиск «Пьера» стоит 1,0039 сравнения на сдвиг при возможных четырёх.
Почему на обычном тексте быстро
Сравнение на сдвиге продолжается, только пока буквы совпадают. Вероятность, что совпадёт первая, равна доле этой буквы в тексте; что совпадут две — примерно произведению долей. Эти вероятности быстро убывают, и средняя цена сдвига складывается из геометрической прогрессии.
Пусть буквы текста независимы и одинаково распределены, и q — вероятность, что две случайные буквы текста совпадают. Тогда для образца, буквы которого тоже случайны с тем же распределением, наивный поиск делает на одном сдвиге в среднем меньше 1/(1 − q) сравнений. Если алфавит из σ букв и все они равновероятны, q = 1/σ, и на сдвиг уходит меньше σ/(σ − 1) сравнений — для любого образца.
Сравнение номер j + 1 на сдвиге происходит, только если совпали первые j пар букв. Пары независимы, каждая совпадает с вероятностью q, поэтому до сравнения номер j + 1 доходят с вероятностью qj. Среднее число сравнений — сумма вероятностей того, что сравнение произойдёт: 1 + q + q² + … + qm−1 < 1/(1 − q). При равновероятных буквах буква текста совпадает с любой заранее выбранной буквой образца с вероятностью 1/σ, и та же сумма не превосходит σ/(σ − 1), каким бы ни был образец.
Число q = Σ pc², где pc — доля буквы c, криптографы называют индексом совпадений. Его ввёл Уильям Фридман в работе, изданной в 1922 году: по нему можно отличить осмысленный текст от шифровки и угадать длину ключа шифра Виженера. У «Войны и мира», если считать все знаки вместе с пробелами, q = 0,0570, и наивный поиск случайного куска текста должен стоить меньше 1,0604 сравнения на сдвиг. У ДНК четыре буквы почти поровну, q около ¼, и граница — около 4/3: поиск сайта GGATCC в геноме фага λ стоит 1,353 сравнения на сдвиг.
Настоящий текст не случаен: после «ска» часто идёт «зал», а не что угодно. Поэтому на частых словах поиск чуть дороже модели: «сказал» по всему роману стоит 1,0488 сравнения на сдвиг. Имена, наоборот, дешевле: они начинаются с заглавной буквы, а заглавные редки. «Бонапарт» — 1,0014 на сдвиг, «Пьер» — 1,0032. «Князь Андрей» дороже, 1,0289: его первая буква, строчная «к», стоит в тексте 72 283 раза.
Где перебор тонет
Худший случай требует, чтобы образец долго совпадал с текстом на многих сдвигах подряд. В прозе так не бывает, но бывает в других данных. Ниже четыре настоящих текста. По горизонтали — все сдвиги образца, по вертикали — сколько сравнений стоил каждый. Красный пунктир на высоте m — потолок: прямоугольник под ним целиком закрашивает только худший случай. Наведите на график, чтобы увидеть самый дорогой сдвиг в этом месте.
На прозе закрашена полоска высотой в одно сравнение, а «князь Андрей» занимает 8,6 % прямоугольника: 1,0318 сравнения на сдвиг из двенадцати возможных. В коде сцены КМП этого каталога образец «двенадцать пробелов и ctx.» стоит уже 2,073 сравнения на сдвиг: в начале каждой строки с отступом поиск проходит сначала пробелы и только потом спотыкается. В ДНК — 1,353: всего четыре буквы, и первая совпадает в каждом четвёртом случае.
Четвёртый текст — файл из байтов 00 и FF, где посередине стоит серия из тысячи байтов FF, а образец на один байт длиннее серии. Каждый сдвиг внутри серии проходит её до конца, натыкается на 00 и отступает на одну позицию. Закрашенный треугольник — это 251,7 сравнения на сдвиг, четверть прямоугольника. Укоротите образец до тысячи байтов: вхождение найдётся, а цена почти не изменится — поиск по-прежнему проходит остаток серии с каждой позиции.
Этот файл — уменьшенная копия настоящего. 7 октября 2020 года пользователь Python сообщил, что bytes.find зависает на файле в 32 мебибайта, где встречаются только байты 00 и FF. Поиск 15 403 807 байтов FF подряд заканчивался мгновенно, а на один байт длиннее — не заканчивался. Тим Питерс повторил это на Python 3.9. Поиск в Python 3.9 — перебор сдвигов, который прыгает дальше, если видит, что вхождение невозможно. Но для образца из одинаковых байтов прыжок равен нулю: поиск двигался на одну позицию и каждый раз заново проходил серию FF длиной в пятнадцать миллионов. По нашей оценке, это десятки триллионов сравнений. Деннис Суини заменил поиск длинных образцов двусторонним алгоритмом Крошмора — Перрена, у которого время линейно в худшем случае; исправление вошло в Python 3.10.
Похожие тексты встречаются чаще, чем кажется: нули в двоичных файлах и образах дисков, отступы и разделители «=====» в логах и коде, повторы в геномах, которые занимают около половины ДНК человека. И главное — текст может прислать противник. Если поиск стоит на сервере и обрабатывает чужие строки, худший случай становится атакой: мегабайт подобранного текста и полмегабайта образца — это сотни миллиардов сравнений.
Код
Две функции с одинаковым результатом. naive — поиск как он есть, по одному сравнению за шаг цикла. naive_skip делает те же сравнения и считает их так же, но сдвиги, на которых первая буква не совпала, пропускает встроенным str.find: он ищет одну букву в цикле на C, а каждый пропущенный сдвиг всё равно добавляет в счётчик одно сравнение. Это тот же приём, что в стандартных библиотеках, — о нём ниже. Программа ищет имена в первой части романа и во всём романе: он лежит на сервере, где исполняется код. В Go текст переводится в срез рун, чтобы позиция была номером буквы, а не байта UTF-8, как в Python.
По всему роману цифры те же, что по первой части: от 1,0014 сравнения на сдвиг у «Бонапарта» до 1,0488 у «сказал». Строки про «Пьера» и «князя Андрея» — то же, что гистограмма первой сцены: сдвиги, остановившиеся после 0, 1, 2… совпавших букв. У «князя Андрея» 5558 сдвигов прошли первую букву и споткнулись на второй: «к» в романе на каждом шагу.
Сколько это стоит
| Текст | Сравнений | Время |
|---|---|---|
| первая буква образца в тексте не встречается | n − m + 1 | O(n) |
| случайный, вероятность совпадения букв q | меньше (n − m + 1) / (1 − q) в среднем | O(n) |
| a…a и образец a…ab | (n − m + 1) · m | O(n · m) |
Память — O(1): два счётчика, и ничего не готовится заранее. Это достоинство: у КМП таблица на m чисел, у Бойера — Мура — таблицы по алфавиту, и для образца из пяти букв их построение может стоить больше самого поиска в короткой строке.
Замер: текст — десять тысяч букв, длина образца растёт от 4 до 256. Проза — кусок романа, образец — кусок из другого места, которого в этом тексте нет. Худший случай — десять тысяч a и образец a…ab.
На прозе наивный поиск не замечает длины образца: линия горизонтальная, потому что почти каждый сдвиг стоит одно сравнение. На a…a линия идёт вверх, наклон близок к единице: в 64 раза длиннее образец — в 30–45 раз дольше и в Python, и в Go. Встроенные поиски на обоих текстах почти не дорожают. В Python 3.13 это перебор с прыжками для коротких образцов и двусторонний алгоритм для длинных, в Go — фильтр по первому байту со страховкой. Одна ступенька на линии Go всё же есть: на русской прозе его поиск длинных образцов в несколько раз медленнее, чем короткий. Почему — в следующем разделе.
Наивный поиск в стандартных библиотеках
Алгоритмы с линейным худшим случаем известны с 1970-х, но перебор сдвигов из стандартных библиотек не ушёл. На коротких образцах и обычных текстах он часто быстрее всех: ему ничего не надо готовить, а процессор умеет сравнивать 16, 32 или 64 байта одной командой. Библиотеки берут перебор и добавляют к нему две вещи — фильтр и страховку.
| Где | Как ищет |
|---|---|
C++, std::search | перебор сдвигов; стандарт разрешает до N₁ · N₂ сравнений. С C++17 можно передать поисковик Бойера — Мура или Бойера — Мура — Хорспула |
Java, String.indexOf | ищет первую букву образца, потом сравнивает остальные. Метод помечен для компилятора HotSpot, и тот может подменить его версией на векторных командах |
Go, strings.Index | короткие строки — векторный перебор; длинные — фильтр по первому байту, а если фильтр ошибается слишком часто, переход на векторный перебор (образец до 32 байт на arm64, до 63 на x86-64 с AVX2) или на Рабина — Карпа |
Python, str.find | для коротких образцов — перебор с прыжками, «смесь Бойера — Мура и Хорспула», как сказано в исходниках; с версии 3.10 для длинных — двусторонний алгоритм Крошмора — Перрена, на который поиск переключается и посреди работы, если перебор часто ошибается |
| Rust, библиотека memchr | фильтр по паре байтов образца, которые по таблице частот считаются редкими, а кандидатов проверяет двусторонний алгоритм; на совсем коротких текстах — Рабин — Карп |
Фильтр. Сдвиг, на котором первая буква не совпала, стоит одно сравнение, и таких сдвигов на прозе больше 99 %. Поэтому библиотеки сначала ищут одну букву образца — функцией вроде memchr, которая проверяет десятки байтов за команду, — и полное сравнение запускают только там, где она нашлась. Выгоднее ждать самую редкую букву образца, а не первую. В «Войне и мире» строчная «к» стоит 72 283 раза, а заглавная «А» — 3377: поиск «князя Андрея» по букве «А» проверяет в 21 раз меньше мест. Так делает memchr в Rust: у неё есть таблица, насколько часто встречается каждый байт, посчитанная по большим текстам и исходникам компилятора Rust.
Страховка. Фильтр не помогает, если нужная буква стоит везде. Тогда библиотека переключается на алгоритм с гарантией: Go — на векторный перебор или Рабина — Карпа, Python — на двусторонний алгоритм. Срабатывает она не только на подобранных текстах. В UTF-8 каждая буква русского алфавита занимает два байта, и первый из них у всех букв — D0 или D1. Для фильтра Go по первому байту русский текст — сплошные ложные тревоги. Мы повторили логику strings.Index из Go 1.27 на куске романа: фильтр сдаётся в первые 20 байт, после четырёх-шести неудач. На сервере сайта, процессоре amd64 с набором команд AVX2, образцы до 63 байт, то есть до 31 русской буквы, дальше ищет векторный перебор, а образцы длиннее — Рабин — Карп. Это и есть ступенька на замере: на длинных образцах поиск Go переходит на хеш и становится в несколько раз медленнее.
Поиск в Python тоже долго был перебором с прыжками и без страховки. Его написал Фредрик Лунд в мае 2006 года на спринте «Need for Speed» в Рейкьявике, и четырнадцать лет он работал так, пока не встретился файл из 00 и FF. Двусторонний алгоритм добавили только после этого.
Перебор хорош и там, где сравнение — не равенство букв. В образце может стоять «любая буква» или класс букв: сайт фермента HinfI записывают как GANTC, где N — любое основание. КМП и Бойер — Мур на таких образцах ломаются, потому что их таблицы выводят из совпадения букв равенство других букв. Перебору делать выводы не нужно, и он работает без изменений. Это первая задача ниже.
Задачи
В первой задаче буквы образца — множества оснований, и пригодится как раз то, что перебор ничего не выводит из совпадений. Во второй нужно предсказать, сколько сравнений сделает перебор, не запуская его: на неудачных текстах прогон занял бы минуты.
Сайты с буквой N Счётчик сравненийДанные: «Война и мир», Л. Н. Толстой, общественное достояние Исходный код сцен каталога legost.in Геномы фагов λ и φX174 и митохондрии человека: NCBI RefSeq NC_001416.1, NC_001422.1, NC_012920.1