Відкрити головне меню

Постановка задачіРедагувати

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

Нехай текст задано у вигляді масиву   довжини  , а зразок — масиву   довжини  . Передбачається, що елементи масивів — символи із скінченного алфавіту  . Наприклад, алфавіт може мати вигляд   чи  .

Зразок   зустрічається у тексті   зі зсувом   (англ. occurs with shift s), якщо   і   (іншими словами  ).

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

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

ТермінологіяРедагувати

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

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

Приклад:

 

 

 

Рядок   називається префіксом рядка   (позначається  ), якщо  . Якщо  , то  .

Аналогічно, рядок   називається суфіксом рядка   (позначається  ), якщо  .

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

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

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

Припустимо, що  ,   і   — рядки, для яких виконується співвідношення   і  . Тоді, якщо  , то  ; якщо  , то  . Якщо  , то  .

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

 


Позначимо k-символьний префікс   зразка   через  . Таким чином,   і  . Аналогічно через   позначимо k-символьний префікс тексту  .

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

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

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

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

Алгоритм Складність передобробки Складність пошуку
Примітивний алгоритм пошуку рядка 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