В информатике , алгоритмы струнно-поиска , иногда называемые алгоритмы сравнения строк , представляют собой важный класс алгоритмов строк , которые пытаются найти место , где один или несколько строк (также называемые шаблоны) находятся в пределах большей строки или текста.
Базовый пример строкового поиска - это когда шаблон и искомый текст представляют собой массивы элементов алфавита ( конечный набор ) Σ. Σ может быть алфавитом человеческого языка, например, буквы от A до Z и другие приложения могут использовать двоичный алфавит (Σ = {0,1}) или алфавит ДНК (Σ = {A, C, G, T}) в биоинформатике .
На практике на метод возможного алгоритма поиска строки может влиять кодировка строки. В частности, если в переменной ширины кодирование используется, то это может быть медленнее , чтобы найти г N - й символ, возможно , требует времени , пропорционального N . Это может значительно замедлить работу некоторых поисковых алгоритмов. Одно из многих возможных решений - вместо этого искать последовательность кодовых единиц, но это может привести к ложным совпадениям, если только кодирование специально не предназначено для предотвращения этого. [ необходима цитата ]
Обзор [ править ]
Самый простой случай поиска строки включает одну (часто очень длинную) строку, иногда называемую стогом сена , и одну (часто очень короткую) строку, иногда называемую иглой . Цель состоит в том, чтобы найти одно или несколько вхождений иголки в стоге сена. Например, можно искать с точностью до :
Некоторые книги нужно пробовать, другие проглатывать, а некоторые - разжевывать и переваривать.
Можно запросить первое вхождение «to», которое является четвертым словом; или все вхождения, из которых 3; или последнее, пятое слово с конца.
Однако очень часто добавляются различные ограничения. Например, кто-то может захотеть сопоставить «иглу» только в том случае, если она состоит из одного (или нескольких) полных слов - возможно, определяется как отсутствие других букв, непосредственно смежных с обеих сторон. В этом случае поиск «hew» или «low» должен завершиться неудачно для приведенного выше примера предложения, даже если эти буквальные строки встречаются.
Другой распространенный пример включает «нормализацию». Во многих случаях поиск такой фразы, как «быть», должен быть успешным даже в тех местах, где есть что-то еще, промежуточное между «to» и «be»:
- Более одного места
- Другие «пробельные» символы, такие как табуляция, неразрывные пробелы, перенос строки и т. Д.
- Реже дефис или мягкий дефис
- В структурированном тексте теги или даже произвольно большие, но «заключенные в скобки» вещи, такие как сноски, номера списков или другие маркеры, встроенные изображения и так далее.
Многие системы символов включают символы, которые являются синонимами (по крайней мере, для некоторых целей):
- Алфавиты на основе латиницы различают строчные и прописные буквы, но для многих целей ожидается, что поиск по строкам будет игнорировать это различие.
- Многие языки включают лигатуры , в которых один составной символ эквивалентен двум или более другим символам.
- Во многих системах письма используются диакритические знаки, такие как акценты или гласные , которые могут различаться в использовании или иметь различное значение при сопоставлении.
- Последовательности ДНК могут включать в себя некодирующие сегменты, которые можно игнорировать для некоторых целей, или полиморфизмы, которые не приводят к изменению кодируемых белков, что может не считаться истинным различием для некоторых других целей.
- В некоторых языках есть правила, согласно которым в начале, середине или конце слова должен использоваться другой символ или форма символа.
Наконец, для строк, представляющих естественный язык, задействуются аспекты самого языка. Например, кто-то может захотеть найти все вхождения слова, несмотря на то, что оно имеет альтернативные варианты написания, префиксы или суффиксы и т. Д.
Еще один более сложный тип поиска - это поиск по регулярному выражению , когда пользователь создает шаблон из символов или других символов, и любое совпадение с шаблоном должно выполнять поиск. Например, чтобы поймать и американское английское слово «цвет», и британский эквивалент «цвет», вместо поиска двух разных буквальных строк можно использовать регулярное выражение, такое как:
цвет
где "?" обычно делает предыдущий символ («u») необязательным.
В этой статье в основном обсуждаются алгоритмы для более простых видов поиска по строкам.
Похожая проблема, возникающая в области биоинформатики и геномики, - это максимальное точное соответствие (MEM). [1] Для двух строк MEM являются обычными подстроками, которые нельзя расширить влево или вправо, не вызывая несоответствия. [2]
Примеры алгоритмов поиска [ править ]
Наивный поиск по строке [ править ]
Простой и неэффективный способ увидеть, где одна строка встречается внутри другой, - это проверять каждое место, где она может быть, одно за другим, чтобы увидеть, есть ли оно там. Итак, сначала мы видим, есть ли копия иголки в первом символе стога сена; если нет, мы смотрим, есть ли копия иглы, начинающаяся со второго символа стога сена; если нет, мы смотрим, начиная с третьего символа и так далее. В нормальном случае нам нужно только посмотреть на один или два символа для каждой неправильной позиции, чтобы увидеть, что это неправильная позиция, поэтому в среднем случае это занимает O ( n + m ) шагов, где n - длина стог сена и м- длина иглы; но в худшем случае поиск строки типа «aaaab» в строке типа «aaaaaaaaab» занимает O ( нм )
Поиск на основе конечных автоматов [ править ]
В этом подходе мы избегаем отслеживания с возвратом, создавая детерминированный конечный автомат (DFA), который распознает сохраненную строку поиска. Их создание дорого - обычно они создаются с использованием конструкции powerset, - но очень быстро используются. Например, DFA, показанный справа, распознает слово «МАМА». На практике этот подход часто используется для поиска произвольных регулярных выражений .
Заготовки [ править ]
Кнут – Моррис – Пратт вычисляет DFA, который распознает входные данные со строкой для поиска как суффикс, Бойер – Мур начинает поиск с конца иглы, поэтому обычно на каждом шаге он может продвигаться вперед на целую длину иглы. Баеза-Йейтс отслеживает, были ли предыдущие j символов префиксом строки поиска, и поэтому может быть адаптирован для поиска по нечеткой строке . Алгоритм bitap является применение подхода Баеза-Йейтс.
Методы индекса [ править ]
Более быстрые поисковые алгоритмы предварительно обрабатывают текст. После создания индекса подстроки , например дерева суффиксов или массива суффиксов , вхождения шаблона можно быстро найти. Например, суффиксное дерево может быть построено во времени, и все вхождения шаблона могут быть найдены во времени при условии, что алфавит имеет постоянный размер и все внутренние узлы в суффиксном дереве знают, какие листья находятся под ними. Последнее может быть выполнено путем запуска алгоритма DFS из корня дерева суффиксов.
Другие варианты [ править ]
Некоторые методы поиска, например поиск по триграмме , предназначены для поиска оценки «близости» между строкой поиска и текстом, а не «совпадение / несоответствие». Иногда это называют «нечетким» поиском .
Классификация поисковых алгоритмов [ править ]
Классификация по количеству паттернов [ править ]
Различные алгоритмы можно классифицировать по количеству используемых ими шаблонов.
Алгоритмы единого паттерна [ править ]
В следующей компиляции m - длина шаблона, n - длина текста, доступного для поиска, k = | Σ | - размер алфавита, а f - константа, вводимая операциями SIMD .
| Алгоритм | Время предварительной обработки | Время совпадения [1] | Космос |
|---|---|---|---|
| Наивный алгоритм поиска строки | никто | Θ (млн) | никто |
| Оптимизированный алгоритм простого поиска по строкам (libc ++ и libstdc ++ string :: find) [3] [4] | никто | Θ (мн / ж) | никто |
| Алгоритм Рабина – Карпа | Θ (м) | среднее Θ (n + m), худшее Θ ((n − m) m) | О (1) |
| Алгоритм Кнута – Морриса – Пратта | Θ (м) | Θ (п) | Θ (м) |
| Алгоритм поиска строки Бойера – Мура | Θ (м + к) | лучшее Ω (n / m), худшее O (mn) | Θ (к) |
| Битовый алгоритм ( shift-or , shift-and , Baeza – Yates – Gonnet ; нечеткий; согласованный) | Θ (м + к) | O (мин) | |
| Двусторонний алгоритм сопоставления строк (glibc memmem / strstr) [5] | Θ (м) | О (п + м) | О (1) |
| BNDM (обратное недетерминированное сопоставление DAWG) (нечеткое + регулярное выражение; nrgrep) [6] | O (м) | На) | |
| BOM (обратное сопоставление Oracle) [7] | O (м) | O (мин) | |
| FM-индекс | На) | O (м) | На) |
- 1. ^ Асимптотические времена выражаются с использованием обозначений O, Ω и .
Алгоритм строк поиска Бойер-Мур был стандартным эталоном для практической строкового поиска литературы. [8]
Алгоритмы, использующие конечный набор шаблонов [ править ]
- Алгоритм сопоставления строк Ахо – Корасика (расширение Knuth-Morris-Pratt)
- Алгоритм Комментца-Вальтера (расширение Бойера-Мура)
- Set-BOM (расширение Backward Oracle Matching)
- Алгоритм поиска строки Рабина – Карпа
Алгоритмы, использующие бесконечное количество шаблонов [ править ]
Естественно, что в этом случае образцы не могут быть перечислены до бесконечности. Обычно они представлены регулярной грамматикой или регулярным выражением .
Классификация с использованием программ предварительной обработки [ править ]
Возможны другие подходы к классификации. Один из наиболее распространенных критериев - предварительная обработка.
| Текст не предварительно обработан | Текст предварительно обработан | |
|---|---|---|
| Шаблоны не обработаны предварительно | Элементарные алгоритмы | Индексные методы |
| Шаблоны предварительно обработаны | Сконструированные поисковые системы | Методы подписи: [10] |
Классификация по стратегиям сопоставления [ править ]
Другой классифицирует алгоритмы по их стратегии сопоставления: [11]
- Сначала сопоставьте префикс (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)
- Сначала сопоставьте суффикс (Бойер-Мур и варианты, Комментарий-Вальтер)
- Сначала сопоставьте лучший фактор (BNDM, BOM, Set-BOM)
- Другая стратегия (Наив, Рабин-Карп)
См. Также [ править ]
- Выравнивание последовательности
- Сопоставление графиков
- Сопоставление с образцом
- Сжатое сопоставление с образцом
- Подстановочные знаки соответствия
- Полнотекстовый поиск
Ссылки [ править ]
- ^ Курц, Стефан; Филлиппи, Адам; Делчер, Артур Л; Смут, Майкл; Шамуэй, Мартин; Антонеску, Корина; Зальцберг, Стивен Л. (2004). «Универсальное и открытое программное обеспечение для сравнения больших геномов» . Геномная биология . 5 (2): R12. DOI : 10.1186 / GB-2004-5-2-r12 . ISSN 1465-6906 . PMC 395750 . PMID 14759262 .
- ^ Хан, Зия; Блум, Джошуа С .; Кругляк Леонид; Сингх, Мона (1 июля 2009 г.). «Практический алгоритм для поиска максимального точного совпадения в больших наборах данных с использованием разреженных массивов суффиксов» . Биоинформатика . 25 (13): 1609–1616. DOI : 10.1093 / биоинформатики / btp275 . PMC 2732316 . PMID 19389736 .
- ^ Кумар, Адитья. "libc ++: Улучшение алгоритма string :: find" . Цитировать журнал требует
|journal=( помощь ) - ^ Кумар, Адитья. "libstdc ++: Улучшение алгоритма string :: find" . Cite journal requires
|journal=(help) - ^ Crochemore, Максим; Перрен, Доминик (1 июля 1991 г.). «Двустороннее сопоставление строк» (PDF) . Журнал ACM . 38 (3): 650–674. DOI : 10.1145 / 116825.116845 . S2CID 15055316 .
- ^ Наварро, Гонсало; Раффино, Матье (1998). «Бит-параллельный подход к суффиксным автоматам: быстрое сопоставление расширенных строк» (PDF) . Комбинаторное сопоставление с образцом . Конспект лекций по информатике. Springer Berlin Heidelberg. 1448 : 14–33. DOI : 10.1007 / bfb0030778 . ISBN 978-3-540-64739-3.
- ^ Fan, H .; Yao, N .; Ма, Х. (декабрь 2009 г.). «Быстрые варианты алгоритма обратного оракула-марша» (PDF) . 2009 Четвертая международная конференция по Интернет-вычислениям для науки и техники : 56–59. DOI : 10,1109 / ICICSE.2009.53 . ISBN 978-1-4244-6754-9. S2CID 6073627 .
- ^ Юм; Воскресенье (1991). «Быстрый поиск строки» . Программное обеспечение: практика и опыт . 21 (11): 1221–1248. DOI : 10.1002 / spe.4380211105 . S2CID 5902579 .
- ^ Melichar, Боривой, Ян Голуб и J. POLCAR. Алгоритмы текстового поиска. Том I: Прямое сопоставление строк. Vol. 1. 2 тома, 2005. http://stringology.org/athens/TextSearchingAlgorithms/ .
- ^ Риад Мокадем; Витольд Литвин http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Быстрый поиск строк на основе nGram по данным, закодированным с использованием алгебраических подписей , 33-я Международная конференция по очень большим базам данных (VLDB)
- ^ Гонсало Наварро; Матье Раффино (2008), Гибкие строки сопоставления с образцом: Практические алгоритмы онлайн -поиска текстов и биологических последовательностей , ISBN 978-0-521-03993-2
- RS Boyer и JS Moore, алгоритм быстрого поиска строки , Carom. АКМ 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) Улучшенное приблизительное сопоставление одиночных и множественных строк
- Kalign2: высокоэффективное множественное выравнивание последовательностей белков и нуклеотидов с учетом внешних функций
- NyoTengu - высокопроизводительный алгоритм сопоставления с образцом в C - Реализации векторных и скалярных алгоритмов сопоставления строк на C
