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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Постановка задачі[ред.ред. код]

Формальна постановка задачі пошуку рядка (англ. string-matching problem) така:

Нехай текст задано у вигляді масиву \;T[1..n] довжини n\;, а зразок — масиву \;P[1..m] довжини \;m\le n. Передбачається, що елементи масивів — символи із скінченного алфавіту \;\Sigma. Наприклад, алфавіт може мати вигляд \;\Sigma=\{0,1\} чи \;\Sigma=\{a,b,\dots,z\}.

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

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

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

Термінологія[ред.ред. код]

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

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

Приклад:

\;x=\{abc\}

\;y=\{def\}

\;xy=\{abcdef\}

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

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

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

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

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

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

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

Lemma_prove_stringsearch.JPG‎


Позначимо k-символьний префікс \;P[1..k] зразка \;P[1..m] через \;P_k. Таким чином, \;P_0=\varepsilon і \;P_m=P=P[1..m]. Аналогічно через \;T_k позначимо k-символьний префікс тексту \;T.

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

Базова класифікація алгоритмів[ред.ред. код]

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

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

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