stringtranslate.com

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

цвет

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

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

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

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

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

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

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

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

Заглушки

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

Методы индексации

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

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

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

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

Классификация по ряду признаков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ Курц, Стефан; Филлиппи, Адам; Делчер, Артур Л; Смут, Майкл; Шамвей, Мартин; Антонеску, Корина; Зальцберг, Стивен Л (2004). «Универсальное и открытое программное обеспечение для сравнения больших геномов». Genome Biology . 5 (2): R12. doi : 10.1186/gb-2004-5-2-r12 . ISSN  1465-6906. PMC 395750.  PMID 14759262  .
  2. ^ Хан, Зия; Блум, Джошуа С.; Кругляк, Леонид; Сингх, Мона (2009-07-01). «Практический алгоритм поиска максимальных точных совпадений в больших наборах данных последовательностей с использованием разреженных массивов суффиксов». Биоинформатика . 25 (13): 1609–1616. doi :10.1093/bioinformatics/btp275. PMC 2732316. PMID  19389736 . 
  3. ^ Crochemore, Maxime; Perrin, Dominique (1 июля 1991 г.). "Two-way string-matching" (PDF) . Journal of the ACM . 38 (3): 650–674. doi :10.1145/116825.116845. S2CID  15055316. Архивировано (PDF) из оригинала 24 ноября 2021 г. . Получено 5 апреля 2019 г. .
  4. ^ Наварро, Гонсало; Раффино, Матье (1998). "Битово-параллельный подход к суффиксным автоматам: быстрое расширенное сопоставление строк" (PDF) . Комбинаторное сопоставление с образцом . Lecture Notes in Computer Science. Vol. 1448. Springer Berlin Heidelberg. pp. 14–33. doi :10.1007/bfb0030778. ISBN 978-3-540-64739-3. Архивировано (PDF) из оригинала 2019-01-05 . Получено 2019-11-22 .
  5. ^ Фань, Х.; Яо, Н.; Ма, Х. (декабрь 2009 г.). «Быстрые варианты алгоритма обратного оракула» (PDF) . 2009 Четвертая международная конференция по интернет-вычислениям для науки и техники . стр. 56–59. doi :10.1109/ICICSE.2009.53. ISBN 978-1-4244-6754-9. S2CID  6073627. Архивировано из оригинала 2022-05-10 . Получено 2019-11-22 .
  6. ^ "glibc/string/str-two-way.h". Архивировано из оригинала 2020-09-20 . Получено 2022-03-22 .
  7. ^ "musl/src/string/memmem.c". Архивировано из оригинала 1 октября 2020 г. Получено 23 ноября 2019 г.
  8. ^ Хьюм; воскресенье (1991). «Быстрый поиск строк». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. doi :10.1002/spe.4380211105. S2CID  5902579.
  9. ^ Комментц-Вальтер, Беате (1979). Алгоритм сопоставления строк, быстрый в среднем (PDF) . Международный коллоквиум по автоматам, языкам и программированию . LNCS . Т. 71. Грац, Австрия: Springer. С. 118–132. doi :10.1007/3-540-09510-1_10. ISBN 3-540-09510-1. Архивировано из оригинала (PDF) 2017-10-10.
  10. ^ Меличар, Боривой, Ян Голуб и Дж. Полкар. Алгоритмы поиска текста. Том I: Прямое сопоставление строк. Том 1. 2 тома, 2005. http://stringology.org/athens/TextSearchingAlgorithms/ Архивировано 04.03.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

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

На Викискладе есть медиафайлы по теме Алгоритм поиска строк .