stringtranslate.com

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

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

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

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

Обзор

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

Некоторые книги нужно попробовать, другие — проглотить, а некоторые — пережевать и переварить.

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

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

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

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

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

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

цвет

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы более быстрого поиска предварительно обрабатывают текст. После построения индекса подстроки , например суффиксного дерева или суффиксного массива , можно быстро найти вхождения шаблона. Например, суффиксное дерево может быть построено во времени, и все вхождения шаблона могут быть найдены во времени при условии, что алфавит имеет постоянный размер и все внутренние узлы суффиксного дерева знают, какие листья находятся под ними. Последнее можно выполнить, запустив алгоритм DFS из корня суффиксного дерева.

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

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

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

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

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

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

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

1. ^ Асимптотические времена выражаются с использованием обозначений O, Ω и Θ .
2. ^ Используется для реализации функций поиска memmem и strstr в стандартных библиотеках C glibc [6] и musl [7] .
3. ^ Может быть расширен для обработки приблизительного сопоставления строк и (потенциально бесконечных) наборов шаблонов, представленных в обычных языках . [ нужна цитата ]

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  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 г.
  8. ^ Хьюм; Воскресенье (1991). «Быстрый поиск строки». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. дои : 10.1002/сп.4380211105. S2CID  5902579.
  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: numeric names: authors list (link)
  12. ^ Гонсало Наварро; Матье Раффино (2008), Гибкие строки сопоставления с образцом: практические алгоритмы онлайн-поиска текстов и биологических последовательностей , Cambridge University Press, ISBN 978-0-521-03993-2

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

В Wikimedia Commons есть медиафайлы, связанные с алгоритмом поиска строк .