Поиск подстроки в строке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сравнение алгоритмов)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''pattern'') в тексте (''text'').  
 
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''pattern'') в тексте (''text'').  
 
== Классификация алгоритмов поиска подстроки в строке ==
 
== Классификация алгоритмов поиска подстроки в строке ==

Версия 07:31, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Поиск подстроки в строке (англ. String searching algorithm) — класс алгоритмов над строками, которые позволяют найти паттерн (pattern) в тексте (text).

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

Сравнение — «чёрный ящик»

Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.

Преимущества:

  • позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.

Недостатки:

  • не выдается точка, в которой произошло несовпадение.

По порядку сравнения паттерна в тексте

Прямой

Преимущества:

  • отсутствие регрессии на «плохих» данных.

Недостатки:

  • не самая хорошая средняя асимптотическая сложность.

Обратный

Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.

Преимущества:

  • при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов.

Недостатки:

  • производительность сильно зависит от данных.

Сравнение в необычном порядке

Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.[1]

По количеству поисковых шаблонов

Сколько поисковых шаблонов может обработать алгоритм за один раз.

  • один шаблон (англ. single pattern algorithms)
  • конечное количество шаблонов (англ. finite set of patterns)
  • бесконечное количество шаблонов (англ. infinite number of patterns) (см. Теория формальных языков)

По необходимости препроцессинга текста

Виды препроцессинга:

Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.

Сравнение алгоритмов

  • [math]|\Sigma| = \sigma[/math]­ — размер алфавита
  • [math]|text| = t[/math] — длина текста
  • [math]|pattern| = p[/math] — длина паттерна
  • [math]a[/math] — размер ответа(кол-во пар)
  • [math]m[/math] — суммарная длина всех паттернов
Название Среднее Худшее Препроцессинг Дополнительная память Кол-во поисковых шаблонов Порядок сравнения Описание
Наивный алгоритм
(Brute Force algorithm)
[math]O(p \cdot (t - p))[/math] [math]O(t^2)[/math] [math]O(1)[/math] Single Прямой Сравнение — «чёрный ящик». Если [math]p[/math] достаточно мало по сравнению с [math]t[/math], то асимптотика будет близкой к [math]O(t)[/math], что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, Ctrl+F в браузерах)
Поиск подстроки в строке с помощью Z-функции [math]O(t)[/math] [math]O(t)[/math] [math]O(p + t)[/math] [math]O(p)[/math] Single Прямой
Алгоритм Рабина-Карпа
(Karp-Rabin algorithm)
[math]O(p + t)[/math] [math]O(pt)[/math] [math]O(p)[/math] [math]O(1)[/math] Single / Finite Прямой Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
Алгоритм Кнута-Морриса-Пратта
(Knuth-Morris-Pratt algorith)
[math]O(p + t)[/math] [math]O(p + t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой Использует префикс-функцию
Алгоритм Колусси
(Colussi algorithm)
[math]O(t)[/math] [math]O(t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой / Обратный Оптимизация Алгоритма Кнута-Морриса-Пратта использует как прямой, так и обратный обход
Алгоритм Ахо-Корасик
(Aho–Corasick string matching algorithm)
[math]O(m + t + a)[/math] [math]O(t)[/math]
[math]O(m)[/math]
[math]O(m\sigma)[/math] Finite Прямой Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как Красно-черное дерево. В последнем случае уменьшится расход памяти, но ухудшится асимптотика
Алгоритм Shift-Or [math]O(t)[/math] [math]O(t \cdot \dfrac{n}{w})[/math]
[math]w[/math] — размер машинного слова
[math]O(p + \sigma)[/math] [math]O(p + \sigma)[/math] Single Прямой Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если [math]p \leqslant w[/math]. Иначе деградирует и по памяти, и по сложности
Алгоритм Бойера-Мура
(Boyer-Moore algorithm)
[math]O(t)[/math] [math]O(pt)[/math] [math]O(p + \sigma)[/math] [math]O(p + \sigma)[/math] Single Обратный Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций[2]
Поиск подстроки в строке с помощью суффиксного массива
(Suffix array)
[math]O(p\log t)[/math] [math]O(p\log t)[/math] [math]O(t)[/math] [math]O(t)[/math] Single Прямой Использует Суффиксный массив. Если использовать Largest common prefix (lcp), то можно уменьшить асимптотику до [math]O(p + \log t)[/math]. Суффиксный массив можно строить стандартными способами или алгоритмом Карккайнена-Сандерса. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Карккайнена-Сандерса
Поиск подстроки в строке с помощью суффиксного дерева
(Suffix tree)
[math]O(p)[/math] [math]O(p)[/math] [math]O(t)[/math] [math]O(t)[/math] Single Прямой Позволяет выполнять поиск подстроки в строке за линейное время
Алгоритм Апостолико-Крочемора
( Apostolico-Crochemore algorithm)
[math]O(t)[/math] [math]O(t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой В худшем случае выполнит [math]\dfrac{3}{2} n[/math] сравнений.

Примечания

Источники информации