Алгоритм пошуку рядка

Алгори́тми по́шуку рядка́ (англ. string searching algorithms) — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків (зразків, англ. pattern) входять у довший рядок або текст.

Постановка задачі

Формальна постановка задачі пошуку рядка (англ. string-matching problem) така: Нехай текст задано у вигляді масиву ${\displaystyle \;T[1..n]}$ довжини ${\displaystyle n\;}$, а зразок — масиву ${\displaystyle \;P[1..m]}$ довжини ${\displaystyle \;m\leq n}$. Передбачається, що елементи масивів — символи із скінченного алфавіту ${\displaystyle \;\Sigma }$. Наприклад, алфавіт може мати вигляд ${\displaystyle \;\Sigma =\{0,1\}}$ чи ${\displaystyle \;\Sigma =\{a,b,\dots ,z\}}$.

Зразок ${\displaystyle \;P}$ зустрічається у тексті ${\displaystyle \;T}$ зі зсувом ${\displaystyle \;s}$ (англ. occurs with shift s), якщо ${\displaystyle 0\leq s\leq n-m}$ і ${\displaystyle \;T[s+1..s+m]=P[1..m]}$ (іншими словами ${\displaystyle 1\leq j\leq m,T[s+j]=P[j]}$).

Якщо зразок ${\displaystyle \;P}$ зустрічається у тексті ${\displaystyle \;T}$ зі зсувом ${\displaystyle \;s}$, то величину ${\displaystyle \;s}$ називають допустимим зсувом (англ. valid shift); інакше її називають недопустимим зсувом (англ. invalid shift)

Задача полягає в знаходженні всіх допустимих зсувів, з якими зразок ${\displaystyle \;P}$ зустрічається у тексті ${\displaystyle \;T}$.

Термінологія

${\displaystyle \;\Sigma ^{*}}$ — множина всіх рядків скінченної довжини, утворенних за допомогою символів алфавіту ${\displaystyle \;\Sigma }$. Порожній рядок ${\displaystyle \;\varepsilon }$ також належить ${\displaystyle \;\Sigma ^{*}}$.

Довжина рядка ${\displaystyle \;x}$ позначається як ${\displaystyle |x|\;}$. Конкатенація (об'єднання) двох рядків ${\displaystyle \;x}$ і ${\displaystyle \;y}$ записується як ${\displaystyle \;xy}$, її довжина відповідно дорівнює ${\displaystyle \;|x|+|y|}$. Конкатенація складається з символів рядка ${\displaystyle \;x}$ після яких записані символи рядка ${\displaystyle \;y}$.

Приклад:

${\displaystyle \;x=\{abc\}}$

${\displaystyle \;y=\{def\}}$

${\displaystyle \;xy=\{abcdef\}}$

Рядок ${\displaystyle \;\omega }$ називається префіксом рядка ${\displaystyle \;x}$ (позначається ${\displaystyle \omega \sqsubset x}$), якщо ${\displaystyle \exists y\in \Sigma ^{*},x=\omega y}$. Якщо ${\displaystyle \omega \sqsubset x}$, то ${\displaystyle |\omega |\leq |x|}$.

Аналогічно, рядок ${\displaystyle \;\omega }$ називається суфіксом рядка ${\displaystyle \;x}$ (позначається ${\displaystyle \omega \sqsupset x}$), якщо ${\displaystyle \exists y\in \Sigma ^{*},x=y\omega }$.

Пустий рядок є одночастно префіксом і суфіксом будь-якого рядка.

Відношення ${\displaystyle \sqsubset }$ і ${\displaystyle \sqsupset }$ є транзитивними.

Лема про суфікси, що перекриваються

Припустимо, що ${\displaystyle \;x}$, ${\displaystyle \;y}$ і ${\displaystyle \;z}$ — рядки, для яких виконується співвідношення ${\displaystyle x\sqsubset z}$ і ${\displaystyle y\sqsubset z}$. Тоді, якщо ${\displaystyle |x|\leq |y|}$, то ${\displaystyle x\sqsubset y}$; якщо ${\displaystyle |x|\geq |y|}$, то ${\displaystyle y\sqsubset x}$. Якщо ${\displaystyle \;|x|=|y|}$, то ${\displaystyle \;x=y}$.

Доведення: Всі три випадки розібрані на малюнку:

Позначимо k-символьний префікс ${\displaystyle \;P[1..k]}$ зразка ${\displaystyle \;P[1..m]}$ через ${\displaystyle \;P_{k}}$. Таким чином, ${\displaystyle \;P_{0}=\varepsilon }$ і ${\displaystyle \;P_{m}=P=P[1..m]}$. Аналогічно через ${\displaystyle \;T_{k}}$ позначимо k-символьний префікс тексту ${\displaystyle \;T}$.

За допомогою цих позначень, задачу пошуку рядка можна сформулювати, як задачу виявлення всіх зсувів ${\displaystyle 0\leq s\leq n-m}$, таких що, ${\displaystyle P\sqsupset T_{s+m}}$.

Базова класифікація алгоритмів

Різноманітні алгоритми розв'язання цієї задачі можна класифікувати за кількістю зразків, що обробляються одночасно. Крім того, алгоритми мають різну складність роботи. Окремо розглядається складність передобробки (передобробка здійснюється або тільки для тексту і не залежить від зразків, або ж тільки для зразків і не залежить від тексту), і складність самого пошуку.

Алгоритми пошуку для одного зразка

Алгоритм	Складність передобробки	Складність пошуку
(Примітивний алгоритм пошуку рядка)	0 (без передобробки)	Θ(n m)
(Алгоритм Рабіна-Карпа)	Θ(m)	в середньому Θ(n+m), в найгіршому випадку Θ(n m)
Пошук за допомогою скінченного автомата	Σ|)	Θ(n)
(Алгоритм Кнута-Моріса-Прата)	Θ(m)	Θ(n)
(Алгоритм Бояра-Мура)	Σ|)	Ω(n/m), O(n)
	Σ|)	Θ(n)

Алгоритми пошуку скінченної множини зразків

• (Алгоритм Ахо — Корасік)
• (Алгоритм Коменц-Вальтер)
• (Алгоритм Рабіна-Карпа)

Алгоритми пошуку необмеженої множини зразків

Для пошуку зразків, що утворюють нескінченну (або дуже велику) множину, користуються формальними граматиками і регулярними виразами.

Інші класифікації

Класифікація, що бере наявність переобробки, за основний критерій:

Класи алгоритмів пошуку рядку

	Текст не передобробляється	Текст передобробляється
Зразки не передобробляються	Елементарні алгоритми (англ. Elementary algorithms)	Індексуючі методи (англ. Index methods)
Зразки передобробляються	Конструктивні пошукові системи (англ. Constructed search engines)	Підписуючі методи (англ. Signature methods)

Індексуючі методи

Швидкі алгоритми пошуку використовують передобробку тексту. Входження зразка може бути швидко знайдене, якщо для тексту побудувати (індекс підрядків) (наприклад, (суфіксне дерево) чи ). Так, суфіксне дерево можна побудувати за час Θ(n), а всі z входжень зразка можна знайти за час O(n + z) (якщо вважати, що розмір алфавіту — константа).

Інші варіанти

Деякі алгоритми пошуку, такі як , замість точного входження зразка, шукають частину тексту, що найбільш близька до зразка.

Література

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press.