Алгоритм Кнута-Морриса-Пратта: Быстрый поиск в тексте
Задача поиска слова (паттерна) внутри большого текста (строки) — одна из самых частых в компьютерных науках. Наивный алгоритм, который мы бы написали интуитивно, прикладывает паттерн к началу текста, сравнивает символы, и при несовпадении сдвигает паттерн ровно на одну позицию вправо, начиная проверку с нуля. В худшем случае (например, поиск паттерна "ААААВ" в строке "АААААААААВ") этот метод работает за время O(N*M), что неприемлемо. Алгоритм КМП решает эту проблему за строго линейное время O(N+M).
Алгоритм Кнута-Морриса-Пратта (KMP), опубликованный в 1977 году Дональдом Кнутом, Джеймсом Моррисом и Воаном Праттом, базируется на глубоком математическом свойстве строк: информация, полученная при частичном совпадении паттерна с текстом, не должна пропадать зря.
Представьте, что вы ищете паттерн "АБРАКАДАБРА". Вы успешно совпали на буквах "АБРАКАД", но на следующей букве споткнулись. Наивный алгоритм сдвинется на одну букву и начнет искать всё заново с буквы "Б". Но алгоритм КМП "знает" структуру самого паттерна. Он понимает, что внутри прочитанного куска "АБРАКАД" нет начала слова "АБРАКАДАБРА", кроме самой первой буквы "А", которая может быть началом нового совпадения. Поэтому КМП сдвинет паттерн сразу на несколько позиций вправо, пропуская заведомо провальные проверки.
Секрет КМП кроется в предварительной обработке самого паттерна. Перед началом поиска алгоритм строит специальный массив π (Пи) — массив префикс-функции (или LPS: Longest Proper Prefix which is also Suffix). Размер этого массива равен длине паттерна. Для каждого символа паттерна массив хранит длину самого длинного собственного префикса, который одновременно является и суффиксом текущей подстроки паттерна.
Вычисление префикс-функции — это магия дискретной математики. Оно выполняется динамическим программированием за время O(M) (длина паттерна). Как только массив LPS готов, алгоритм запускает конечный автомат по большому тексту. Если символы совпадают, мы идем вперед. Если происходит несовпадение, мы не откатываем указатель в большом тексте назад! Мы просто смотрим в массив LPS и откатываем указатель внутри паттерна на ту позицию, которая позволяет сохранить максимальное уже найденное перекрытие.
Благодаря тому, что указатель по основному тексту (длины N) всегда движется только вперед и никогда не возвращается назад, алгоритм идеально подходит для потоковой обработки данных. Вы можете искать вирусные сигнатуры в бесконечном входящем сетевом трафике (сокете), не буферизуя весь трафик в оперативную память.
Последнее от Александр
- Английский сленг: фразы и выражения на английском с переводом
- Промышленная безопасность - как теория вероятностей помогает прогнозировать аварии на ОПО
- Финансовая математика печати: как рассчитать реальную стоимость владения принтером
- Лучшие нейросети для написания текстов
- Гнеденко Борис Владимирович