Алгоритм поиска строк

В информатике , алгоритмы поиска строк иногда называемые алгоритмами сопоставления строк , представляют собой важный класс строковых алгоритмов , которые пытаются найти место, где одна или несколько строк (также называемых шаблонами) находятся внутри более крупной строки или текста.

Базовый пример поиска строк — это когда шаблон и искомый текст представляют собой массивы элементов алфавита ( конечного множества ) Σ. Σ может быть алфавитом человеческого языка, например, буквы от A до Z , а другие приложения могут использовать двоичный алфавит (Σ = {0,1}) или алфавит ДНК (Σ = {A,C,G,T}). в биоинформатике .

На практике на метод допустимого алгоритма поиска строк может влиять кодирование строки. В частности, если кодирование переменной ширины используется , то поиск N -го символа может быть медленнее, возможно, потребуется время, пропорциональное N . Это может значительно замедлить работу некоторых алгоритмов поиска. Одним из многих возможных решений является поиск последовательности кодовых единиц, но это может привести к ложным совпадениям, если кодирование специально не предназначено для предотвращения этого. ^{[ нужна ссылка ]}

Обзор

Самый простой случай поиска строк включает в себя одну (часто очень длинную) строку, иногда называемую haystack , и одну (часто очень короткую) строку, иногда называемую иголкой . Цель состоит в том, чтобы найти одно или несколько вхождений иглы в стоге сена. Например, можно выполнить поиск с точностью до :

Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.

Можно запросить первое вхождение слова «to», которое является четвертым словом; или все вхождения, которых 3; или последнее, то есть пятое слово с конца.

Однако очень часто добавляются различные ограничения. Например, можно захотеть сопоставить «иглу» только в том случае, если она состоит из одного (или нескольких) полных слов - возможно, определяемых как отсутствие других букв, непосредственно прилегающих с обеих сторон. В этом случае поиск по словам «hew» или «low» для приведенного выше примера предложения не будет успешным, даже если эти литеральные строки действительно встречаются.

Другой распространенный пример включает «нормализацию». Во многих случаях поиск такой фразы, как «быть», должен быть успешным даже в тех местах, где между «быть» и «быть» есть что-то еще:

Более одного места
Другие символы «пробела», такие как табуляция, неразрывные пробелы, разрывы строк и т. д.
Реже дефис или мягкий дефис.
В структурированных текстах, тегах или даже произвольно больших, но «круглых» вещах, таких как сноски, номера списков или другие маркеры, встроенные изображения и т. д.

Многие системы символов включают символы, которые являются синонимами (по крайней мере, для некоторых целей):

Алфавиты на основе латиницы различают строчные и прописные буквы, но для многих целей ожидается, что строковый поиск будет игнорировать это различие.
Многие языки включают лигатуры , где один составной символ эквивалентен двум или более другим символам.
Многие системы письма включают диакритические знаки , такие как ударения или гласные , которые могут различаться по своему использованию или иметь различную важность при сопоставлении.
Последовательности ДНК могут включать некодирующие сегменты, которые для некоторых целей можно игнорировать, или полиморфизмы, которые не приводят к изменению кодируемых белков, что может не считаться истинным различием для некоторых других целей.
В некоторых языках есть правила, согласно которым в начале, середине или конце слов должен использоваться другой символ или форма символа.

Наконец, для строк, представляющих естественный язык, задействуются аспекты самого языка. Например, можно захотеть найти все вхождения «слова», несмотря на то, что оно имеет альтернативные варианты написания, префиксы или суффиксы и т. д.

Другой, более сложный тип поиска — это поиск по регулярным выражениям , при котором пользователь создает шаблон символов или других символов, и любое совпадение с шаблоном должно выполнять поиск. Например, чтобы уловить как американское английское слово «color», так и его британский эквивалент «color», вместо поиска двух разных литеральных строк можно использовать регулярное выражение, например:

colou?r

где "?" обычно делает предыдущий символ («u») необязательным.

В этой статье в основном обсуждаются алгоритмы для более простых видов поиска строк.

Аналогичная проблема, возникшая в области биоинформатики и геномики, — максимально точное сопоставление (MEM). ^[1] Учитывая две строки, MEM представляют собой общие подстроки, которые нельзя расширить влево или вправо, не вызывая несоответствия. ^[2]

Примеры алгоритмов поиска

Наивный поиск строк

Простой и неэффективный способ увидеть, где одна строка находится внутри другой, — это проверять каждый индекс один за другим. Сначала мы видим, существует ли копия иглы, начинающаяся с первого символа стога сена; если нет, мы смотрим, есть ли копия иглы, начинающаяся со второго символа стога сена, и так далее. В обычном случае нам нужно посмотреть только на один или два символа для каждой неправильной позиции, чтобы увидеть, что это неправильная позиция, поэтому в среднем случае это занимает O ( n + m ) шагов, где n — длина стог сена и m – длина иглы; но в худшем случае поиск строки типа «aaaab» в строке типа «aaaaaaaaab» занимает O ( nm )

Поиск на основе конечного автомата

В этом подходе возврата назад можно избежать за счет построения детерминированного конечного автомата (DFA), который распознает сохраненную строку поиска. Их создание дорого (обычно они создаются с использованием конструкции powerset ), но их очень быстро использовать. Например, DFA , показанный справа, распознает слово «МАМА». На практике этот подход часто обобщается для поиска произвольных регулярных выражений .

Незавершённые версии

Кнут-Моррис-Пратт вычисляет DFA , который распознает входные данные со строкой для поиска в качестве суффикса, Бойер-Мур начинает поиск с конца иглы, поэтому обычно на каждом шаге он может перепрыгивать на всю длину иглы. Баеза-Йейтс отслеживает, были ли предыдущие символы j префиксом строки поиска, и поэтому может быть адаптирован для поиска нечеткой строки . Алгоритм битового ввода представляет собой применение подхода Баеза-Йейтса.

Индексные методы

Алгоритмы более быстрого поиска предварительно обрабатывают текст. После построения индекса подстроки , например суффиксного дерева или суффиксного массива , можно быстро найти вхождения шаблона. Например, можно построить суффиксное дерево. $\Theta (n)$ время и все $z$ случаи появления шаблона можно найти в $O(m)$ время при условии, что алфавит имеет постоянный размер и все внутренние узлы суффиксного дерева знают, какие листья находятся под ними. Последнее можно выполнить, запустив алгоритм DFS из корня суффиксного дерева.

Другие варианты

Некоторые методы поиска, например триграммный поиск , предназначены для поиска показателя «близости» между строкой поиска и текстом, а не «совпадения/несовпадения». Иногда их называют «нечеткими» поисками .

Классификация алгоритмов поиска

Классификация по ряду закономерностей

Различные алгоритмы можно классифицировать по количеству используемых шаблонов.

Одношаблонные алгоритмы

В следующей компиляции m — длина шаблона, n — длина текста, доступного для поиска, а k = |Σ| размер алфавита.

Алгоритм	Время предварительной обработки	Время сопоставления ^[1]	Космос
Наивный алгоритм	никто	Θ(n+m) в среднем, Θ(мн)	никто
Рабин–Карп	Θ(м)	Θ(n) в среднем, О(мин) в худшем случае	О(1)
Кнут-Моррис-Пратт	Θ(м)	Θ(п)	Θ(м)
Бойер-Мур	Θ(м + к)	Ом(н/м) в лучшем случае, О(мин) в худшем случае	Θ(к)
Двусторонний алгоритм ^[3]^[2]	Θ(м)	На)	О (журнал (м))
Обратное недетерминированное сопоставление DAWG (BNDM) ^[4]^[3]	О (м)	Ом(н/м) в лучшем случае, О(мин) в худшем случае
Обратное сопоставление Oracle (BOM) ^[5]	О (м)	О(мин)

1. ^ Асимптотические времена выражаются с использованием обозначений O, Ω и Θ .

2. ^ Используется для реализации функций поиска memmem и strstr в glibc. ^[6] и мусл ^[7] Стандартные библиотеки C.

3. ^ Может быть расширен для обработки приблизительного сопоставления строк и (потенциально бесконечных) наборов шаблонов, представленных в обычных языках . ^{[ нужна ссылка ]}

был Алгоритм поиска строк Бойера-Мура стандартным эталоном в практической литературе по поиску строк. ^[8]

Алгоритмы, использующие конечный набор шаблонов

В следующей компиляции M — длина самого длинного шаблона, m — их общая длина, n — длина текста, доступного для поиска, o — количество вхождений.

Алгоритм	Продление	Время предварительной обработки	Время сопоставления ^[4]	Космос
Ахо – Корасик	Кнут-Моррис-Пратт	Θ(м)	Θ(п + о)	Θ(м)
Комментц-Вальтер	Бойер-Мур	Θ(м)	Θ(M * n) худший случай сублинейный в среднем ^[9]	Θ(м)
Set-BOM	Обратное сопоставление Oracle

Алгоритмы, использующие бесконечное количество шаблонов

Естественно, что в этом случае закономерности невозможно перечислить конечно. Обычно они представлены регулярной грамматикой или регулярным выражением .

Классификация по использованию программ предварительной обработки

Возможны и другие подходы к классификации. Один из наиболее распространенных использует предварительную обработку в качестве основного критерия.

Классы алгоритмов поиска строк ^[10]
	Текст без предварительной обработки	Текст предварительно обработан
Шаблоны без предварительной обработки	Элементарные алгоритмы	Индексные методы
Предварительно обработанные шаблоны	Созданные поисковые системы	Методы подписи: ^[11]

Классификация по стратегиям сопоставления

Другой классифицирует алгоритмы по их стратегии сопоставления: ^[12]

Сначала сопоставьте префикс (Кнут-Моррис-Пратт, Shift-И, Ахо-Корасик)
Сначала сопоставьте суффикс (Бойер-Мур и варианты, Комментц-Вальтер)
Сначала сопоставьте лучший фактор (BNDM, BOM, Set-BOM)
Другая стратегия (Наивная, Рабина-Карпа, Векторизованная)

См. также

Ссылки

^ Курц, Стефан; Филиппи, Адам; Делчер, Артур Л; Смут, Майкл; Шамуэй, Мартин; Антонеску, Корина; Зальцберг, Стивен Л. (2004). «Универсальное и открытое программное обеспечение для сравнения больших геномов» . Геномная биология . 5 (2): Р12. дои : 10.1186/gb-2004-5-2-r12 . ISSN 1465-6906 . ПМК 395750 . ПМИД 14759262 .
^ Хан, Зия; Блум, Джошуа С.; Кругляк Леонид; Сингх, Мона (1 июля 2009 г.). «Практический алгоритм поиска максимальных точных совпадений в больших наборах данных последовательностей с использованием разреженных массивов суффиксов» . Биоинформатика . 25 (13): 1609–1616. doi : 10.1093/биоинформатика/btp275 . ПМЦ 2732316 . ПМИД 19389736 .
^ Крошмор, Максим; Перрен, Доминик (1 июля 1991 г.). «Двустороннее сопоставление строк» (PDF) . Журнал АКМ . 38 (3): 650–674. дои : 10.1145/116825.116845 . S2CID 15055316 . Архивировано (PDF) из оригинала 24 ноября 2021 года . Проверено 5 апреля 2019 г.
^ Наварро, Гонсало; Раффино, Матье (1998). «Бит-параллельный подход к суффиксным автоматам: быстрое сопоставление расширенных строк» (PDF) . Комбинаторное сопоставление с образцом . Конспекты лекций по информатике. Том. 1448. Шпрингер Берлин Гейдельберг. стр. 14–33. дои : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3 . Архивировано (PDF) из оригинала 5 января 2019 г. Проверено 22 ноября 2019 г.
^ Фан, Х.; Яо, Н.; Ма, Х. (декабрь 2009 г.). «Быстрые варианты алгоритма обратного марша Oracle» (PDF) . 2009 Четвертая Международная конференция по Интернет-вычислениям в науке и технике . стр. 56–59. дои : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9 . S2CID 6073627 . Архивировано из оригинала 10 мая 2022 г. Проверено 22 ноября 2019 г.
^ "glibc/string/str-two-way.h" . Архивировано из оригинала 20 сентября 2020 г. Проверено 22 марта 2022 г.
^ "musl/src/string/memmem.c" . Архивировано из оригинала 1 октября 2020 года . Проверено 23 ноября 2019 г.
^ Хьюм; Воскресенье (1991). «Быстрый поиск строки». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. дои : 10.1002/спе.4380211105 . S2CID 5902579 .
^ Комментц-Вальтер, Беате (1979). Алгоритм сопоставления строк, быстрый в среднем (PDF) . Международный коллоквиум по автоматам, языкам и программированию . ЛНКС . Том. 71. Грац, Австрия: Шпрингер. стр. 118–132. дои : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1 . Архивировано из оригинала (PDF) 10 октября 2017 г.
^ Меличар, Боривой, Ян Голуб и Дж. Полкар. Алгоритмы поиска текста. Том I: Прямое сопоставление строк. Том. 1. 2 тома, 2005 г. http://stringology.org/athens/TextSearchingAlgorithms/. Архивировано 4 марта 2016 г. в Wayback Machine .
^ Риад Мокадем; Витольд Литвин http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Быстрый строковый поиск на основе nGramBased по данным, закодированным с использованием алгебраических сигнатур , 33-я Международная конференция по очень большим базам данных (VLDB) {{citation}}: Внешняя ссылка в |surname2= ( помощь ) CS1 maint: числовые имена: список авторов ( ссылка )
^ Гонсало Наварро; Матье Раффино (2008), Гибкие строки сопоставления с образцом: практические алгоритмы онлайн-поиска текстов и биологических последовательностей , Cambridge University Press, ISBN 978-0-521-03993-2

Р. С. Бойер и Дж. С. Мур, Алгоритм быстрого поиска строк , Carom. ACM 20, (10), 262–272 (1977).
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , третье издание. MIT Press и McGraw-Hill, 2009. ISBN 0-262-03293-7 . Глава 32: Сопоставление строк, стр. 985–1013.

Внешние ссылки

Огромный список ссылок на соответствие шаблону Последнее обновление: 27.12.2008 20:18:38
Большой (поддерживаемый) список алгоритмов сопоставления строк
Список алгоритмов сопоставления строк NIST
StringSearch — высокопроизводительные алгоритмы сопоставления с образцом на Java — Реализации многих алгоритмов сопоставления строк на Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
StringsAndChars — реализации многих алгоритмов сопоставления строк (для одного и нескольких шаблонов) в Java.
Алгоритмы точного сопоставления строк — анимация на Java, подробное описание и реализация многих алгоритмов на языке C.
(PDF) Улучшенное приблизительное сопоставление одиночных и множественных строк. Архивировано 11 марта 2017 г. на Wayback Machine.
Kalign2: высокопроизводительное множественное выравнивание белковых и нуклеотидных последовательностей, позволяющее использовать внешние функции
NyoTengu — высокопроизводительный алгоритм сопоставления с образцом на C — Реализация векторных и скалярных алгоритмов сопоставления строк на C

[1] Курц, Стефан; Филиппи, Адам; Делчер, Артур Л; Смут, Майкл; Шамуэй, Мартин; Антонеску, Корина; Зальцберг, Стивен Л. (2004). «Универсальное и открытое программное обеспечение для сравнения больших геномов» . Геномная биология . 5 (2): Р12. дои : 10.1186/gb-2004-5-2-r12 . ISSN 1465-6906 . ПМК 395750 . ПМИД 14759262 .

[2] Хан, Зия; Блум, Джошуа С.; Кругляк Леонид; Сингх, Мона (1 июля 2009 г.). «Практический алгоритм поиска максимальных точных совпадений в больших наборах данных последовательностей с использованием разреженных массивов суффиксов» . Биоинформатика . 25 (13): 1609–1616. doi : 10.1093/биоинформатика/btp275 . ПМЦ 2732316 . ПМИД 19389736 .

[3] Крошмор, Максим; Перрен, Доминик (1 июля 1991 г.). «Двустороннее сопоставление строк» (PDF) . Журнал АКМ . 38 (3): 650–674. дои : 10.1145/116825.116845 . S2CID 15055316 . Архивировано (PDF) из оригинала 24 ноября 2021 года . Проверено 5 апреля 2019 г.

[4] Наварро, Гонсало; Раффино, Матье (1998). «Бит-параллельный подход к суффиксным автоматам: быстрое сопоставление расширенных строк» (PDF) . Комбинаторное сопоставление с образцом . Конспекты лекций по информатике. Том. 1448. Шпрингер Берлин Гейдельберг. стр. 14–33. дои : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3 . Архивировано (PDF) из оригинала 5 января 2019 г. Проверено 22 ноября 2019 г.

[5] Фан, Х.; Яо, Н.; Ма, Х. (декабрь 2009 г.). «Быстрые варианты алгоритма обратного марша Oracle» (PDF) . 2009 Четвертая Международная конференция по Интернет-вычислениям в науке и технике . стр. 56–59. дои : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9 . S2CID 6073627 . Архивировано из оригинала 10 мая 2022 г. Проверено 22 ноября 2019 г.

[6] "glibc/string/str-two-way.h" . Архивировано из оригинала 20 сентября 2020 г. Проверено 22 марта 2022 г.

[7] "musl/src/string/memmem.c" . Архивировано из оригинала 1 октября 2020 года . Проверено 23 ноября 2019 г.

[:0-8] Хьюм; Воскресенье (1991). «Быстрый поиск строки». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. дои : 10.1002/спе.4380211105 . S2CID 5902579 .

[Commentz-Walter-9] Комментц-Вальтер, Беате (1979). Алгоритм сопоставления строк, быстрый в среднем (PDF) . Международный коллоквиум по автоматам, языкам и программированию . ЛНКС . Том. 71. Грац, Австрия: Шпрингер. стр. 118–132. дои : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1 . Архивировано из оригинала (PDF) 10 октября 2017 г.

[10] Меличар, Боривой, Ян Голуб и Дж. Полкар. Алгоритмы поиска текста. Том I: Прямое сопоставление строк. Том. 1. 2 тома, 2005 г. http://stringology.org/athens/TextSearchingAlgorithms/. Архивировано 4 марта 2016 г. в Wayback Machine .

[11] Риад Мокадем; Витольд Литвин http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Быстрый строковый поиск на основе nGramBased по данным, закодированным с использованием алгебраических сигнатур , 33-я Международная конференция по очень большим базам данных (VLDB) {{citation}}: Внешняя ссылка в |surname2= ( помощь ) CS1 maint: числовые имена: список авторов ( ссылка )

[12] Гонсало Наварро; Матье Раффино (2008), Гибкие строки сопоставления с образцом: практические алгоритмы онлайн-поиска текстов и биологических последовательностей , Cambridge University Press, ISBN 978-0-521-03993-2

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Трие
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции