В информатике, алгоритмы струнно-поиска, иногда называемые алгоритмы сравнения строк, представляют собой важный класс алгоритмов строк, которые пытаются найти место, где один или несколько строк (также называемые шаблоны) находятся в пределах большей строки или текста.
Базовый пример строкового поиска - это когда шаблон и искомый текст являются массивами элементов алфавита ( конечного множества ) Σ. Σ может быть алфавитом человеческого языка, например, буквы от A до Z и другие приложения могут использовать двоичный алфавит (Σ = {0,1}) или алфавит ДНК (Σ = {A, C, G, T}) в биоинформатике.
На практике на метод возможного алгоритма поиска строки может влиять кодировка строки. В частности, если в переменной ширины кодирование используется, то это может быть медленнее, чтобы найти г N - й символ, возможно, требует времени, пропорционального N. Это может значительно замедлить работу некоторых поисковых алгоритмов. Одно из многих возможных решений состоит в том, чтобы вместо этого искать последовательность кодовых единиц, но это может привести к ложным совпадениям, если только кодирование специально не предназначено для того, чтобы этого избежать.
Самый простой случай поиска строки включает одну (часто очень длинную) строку, иногда называемую стогом сена, и одну (часто очень короткую) строку, иногда называемую иглой. Цель состоит в том, чтобы найти одно или несколько вхождений иголки в стоге сена. Например, можно искать с точностью до:
Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.
Можно запросить первое появление «to», которое является четвертым словом; или все вхождения, из которых 3; или последнее, пятое с конца слово.
Однако очень часто добавляются различные ограничения. Например, кто-то может захотеть сопоставить «иглу» только в том случае, если она состоит из одного (или нескольких) полных слов - возможно, определяется как отсутствие других букв, непосредственно смежных с обеих сторон. В этом случае поиск «hew» или «low» должен завершиться неудачно для приведенного выше примера предложения, даже если эти буквальные строки действительно встречаются.
Другой распространенный пример включает «нормализацию». Для многих целей поиск такой фразы, как «быть», должен быть успешным даже в тех местах, где есть что-то еще, промежуточное между «to» и «be»:
Многие системы символов включают символы, которые являются синонимами (по крайней мере, для некоторых целей):
Наконец, для строк, представляющих естественный язык, задействуются аспекты самого языка. Например, кто-то может захотеть найти все вхождения слова, несмотря на то, что оно имеет альтернативное написание, префиксы или суффиксы и т. Д.
Другой более сложный тип поиска - это поиск по регулярному выражению, когда пользователь создает шаблон из символов или других символов, и любое совпадение с шаблоном должно выполнять поиск. Например, чтобы поймать и американское английское слово «цвет», и британский эквивалент «цвет», вместо поиска двух разных буквальных строк можно использовать такое регулярное выражение, как:
colou?r
где "?" обычно делает предыдущий символ («u») необязательным.
В этой статье в основном обсуждаются алгоритмы для более простых видов поиска по строкам.
Похожая проблема, возникающая в области биоинформатики и геномики, - это максимальное точное соответствие (MEM). Учитывая две строки, MEM являются общими подстроками, которые нельзя расширить влево или вправо, не вызывая несоответствия.
Простой и неэффективный способ увидеть, где одна строка встречается внутри другой, - это проверять каждое место, где она может быть, одно за другим, чтобы увидеть, есть ли оно там. Итак, сначала мы видим, есть ли копия иголки у первого символа стога сена; если нет, мы смотрим, есть ли копия иглы, начинающаяся со второго символа стога сена; в противном случае мы смотрим, начиная с третьего символа и так далее. В обычном случае нам нужно только посмотреть на один или два символа для каждой неправильной позиции, чтобы увидеть, что это неправильная позиция, поэтому в среднем случае это занимает O ( n + m) шагов, где n - длина стог сена и m - длина иголки; но в худшем случае поиск строки типа «aaaab» в строке типа «aaaaaaaaab» занимает O ( нм)
В этом подходе мы избегаем поиска с возвратом, создавая детерминированный конечный автомат (DFA), который распознает сохраненную строку поиска. Их создание дорого - обычно они создаются с использованием конструкции powerset, - но очень быстро в использовании. Например, DFA, показанный справа, распознает слово «МАМА». Этот подход часто обобщается на практике для поиска произвольных регулярных выражений.
Кнут – Моррис – Пратт вычисляет DFA, который распознает входные данные со строкой для поиска как суффикс, Бойер – Мур начинает поиск с конца иглы, поэтому обычно на каждом шаге он может продвигаться вперед на целую длину иглы. Баеза – Йейтс отслеживает, были ли предыдущие символы j префиксом строки поиска, и, следовательно, может быть адаптирован для поиска по нечеткой строке. Алгоритм bitap является применение подхода Баеза-Йейтс.
Более быстрые поисковые алгоритмы предварительно обрабатывают текст. После построения индекса подстроки, например дерева суффиксов или массива суффиксов, можно быстро найти вхождения шаблона. Например, суффиксное дерево может быть построено во времени, и все вхождения шаблона могут быть найдены во времени при условии, что алфавит имеет постоянный размер и все внутренние узлы в суффиксном дереве знают, какие листья находятся под ними. Последнее может быть выполнено путем запуска алгоритма DFS из корня дерева суффиксов.
Некоторые методы поиска, например поиск по триграмме, предназначены для поиска оценки «близости» между строкой поиска и текстом, а не «совпадение / несоответствие». Иногда это называют «нечетким» поиском.
Различные алгоритмы можно классифицировать по количеству используемых ими шаблонов.
В следующей компиляции m - длина шаблона, n - длина текста, доступного для поиска, k = | Σ | - размер алфавита, а f - константа, вводимая операциями SIMD.
Алгоритм | Время предварительной обработки | Время совпадения | Космос |
---|---|---|---|
Наивный алгоритм поиска по строке | никто | Θ (млн) | никто |
Оптимизированный алгоритм простого поиска по строкам (libc ++ и libstdc ++ string:: find) | никто | Θ (мн / ж) | никто |
Алгоритм Рабина – Карпа | Θ (м) | среднее Θ (n + m), худшее Θ ((n − m) m) | О (1) |
Алгоритм Кнута – Морриса – Пратта | Θ (м) | Θ (п) | Θ (м) |
Алгоритм поиска строки Бойера – Мура | Θ (м + к) | лучшее Ω (n / m), худшее O (mn) | Θ (к) |
Битовый алгоритм ( shift-or, shift-and, Baeza – Yates – Gonnet ; нечеткий; согласованный) | Θ (м + к) | O (мин) | |
Двусторонний алгоритм сопоставления строк (glibc memmem / strstr) | Θ (м) | О (п + м) | О (1) |
BNDM (обратное недетерминированное сопоставление DAWG) (нечеткое + регулярное выражение; nrgrep) | O (м) | На) | |
BOM (обратное сопоставление Oracle) | O (м) | O (мин) | |
FM-индекс | На) | O (м) | На) |
Алгоритм строк поиска Бойер-Мур был стандартным эталоном для практической строкового поиска литературы.
Естественно, что в этом случае образцы не могут быть перечислены до бесконечности. Обычно они представлены регулярной грамматикой или регулярным выражением.
Возможны другие подходы к классификации. Один из наиболее распространенных критериев - предварительная обработка.
Текст не предварительно обработан | Текст предварительно обработан | |
---|---|---|
Шаблоны не обрабатываются предварительно | Элементарные алгоритмы | Индексные методы |
Шаблоны предварительно обработаны | Сконструированные поисковые системы | Методы подписи: |
Другой классифицирует алгоритмы по их стратегии сопоставления:
|journal=
( помощь )|journal=
( помощь )