Алгоритм Бояра-Мура

Алгоритм пошуку рядка Боєра — Мура, — ефективний алгоритм пошуку рядка, який є еталоном при практичних дослідженнях алгоритмів пошуку рядка. Був розроблений ^[en] і ^[en] у 1977 році. Перевага цього алгоритму в тому, що ціною деякої кількості попередніх обчислень над зразком або шаблоном (але не над рядком, в якому ведеться пошук) шаблон порівнюється з вихідним текстом не у всіх позиціях — частина перевірок пропускаються як такі, що не дадуть результату. Цей алгоритм швидко працює у ситуаціях коли зразок набагато коротший від тексту пошуку, або коли відбувається пошук в декількох документах. Зазвичай, чим довше зразок, тим швидше працює алгоритм.

Загальна оцінка обчислювальної складності алгоритму — O(|haystack|+|needle|+|Σ|) на неперіодичних шаблонах і O(|haystack|·|needle|+|Σ|) на періодичних, де haystack — рядок, в якому виконується пошук, needle — шаблон пошуку, Σ — алфавіт, на якому проводиться порівняння. У 1991 році Коул показав, що на неперіодичних шаблонах за повний прохід по рядку алгоритм зробить не більше 3·|haystack| порівнянь.

Опис алгоритму

Алгоритм заснований на трьох ідеях.

1. Сканування зліва направо, порівняння справа наліво. Поєднується початок тексту (рядки) і шаблону, перевірка починається з останнього символу шаблону. Якщо символи збігаються, проводиться порівняння передостаннього символу шаблону і т. д. Якщо всі символи шаблону збіглися з накладеними символами рядка, значить, підрядок знайдений, і пошук закінчено.

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

Ці «декілька», згадані в попередньому абзаці, обчислюються за двома евристиками.

2. Евристика стоп-символу. Припустимо, що ми проводимо пошук слова «колокол». Перша ж буква не збіглася — «к» (назвемо цю букву стоп-символом). Тоді можна зсунути шаблон вправо до останньої його букви «к».

Стрічка: * * * * * * к * * * * ** Шаблон: к о л о к о л Наступний крок: к о л о к о л 

Якщо стоп-символу в шаблоні взагалі немає, шаблон зміщується за цей стоп-символ.

Стрічка: * * * * * а л * * * * * * * * Шаблон: к о л о к о л Наступний крок: к о л о к о л 

В даному випадку стоп-символ — «а», і шаблон зсувається так, щоб він виявився прямо за цією буквою. В алгоритмі Боєра-Мура евристика стоп-символу взагалі не дивиться на співпавший суфікс (див. Нижче), так що перша буква шаблону («к») опиниться під «л», і буде проведена одна завідома холоста перевірка.

Якщо стоп-символ «к» опинився за іншою буквою «к», евристика стоп-символу не працює.

Стрічка: * * * * к к о л * * * * * Шаблон: к о л о к о л Наступний крок: к о л о к о л  ????? 

У таких ситуаціях виручає третя ідея АБМ — евристика співпавшого суфікса.

3. Евристика співпавшого суфікса. Якщо при порівнянні рядка і шаблону збіглося один або більше символів, шаблон зсувається в залежності від того, який суфікс збігся.

Стрічка: * * т о к о л * * * * * Шаблон: к о л о к о л Наступний крок: к о л о к о л 

В даному випадку збігся суфікс «ок», і шаблон зсувається вправо до найближчого «окол». Якщо підрядка «окол» в шаблоні більше немає, але він починається на «кол», зрушується до «кол», і т. д.

Обидві евристики вимагають попередніх обчислень — залежно від шаблону пошуку заповнюються дві таблиці. Таблиця стоп-символів за розміром відповідає алфавіту (наприклад, якщо алфавіт складається з 256 символів, то її довжина 256); таблиця суфіксів — шуканому шаблону. Саме через це алгоритм Боєра-Мура не враховує співпавший суфікс і неспівпавший символ одночасно — це вимагало б занадто багато попередніх обчислень.

Опишемо докладніше обидві таблиці.

Таблиця стоп-символів

У таблиці стоп-символів вказується остання позиція в needle (виключаючи останню букву) кожного з символів алфавіту. Для всіх символів, що не увійшли вneedle, пишемо 0 (для нумерації з 0 — відповідно, −1). Наприклад, якщо needle=«abcdadcd», таблиця стоп-символів буде виглядати так.

Символ a b c d [всі інші] Остання позиція 5 2 7 6 0 

Зверніть увагу, для стоп-символу «d» остання позиція буде 6, а не 8 — остання буква не враховується. Це відома помилка, що приводить до неоптимальності. Для АБМ вона не фатальна («витягує» евристика суфікса), але фатальна для спрощеної версії АБМ — алгоритму Хорспула.

Якщо розбіжність сталася на позиції i, а стоп-символ c, то зсув буде i-StopTable[c].

Таблиця суфіксів

Для кожного можливого суфікса  S шаблону needle вказати найменшу величину, на яку потрібно зрушити вправо шаблон, щоб він знову збігся з S. Якщо такий зсув неможливий, ставиться |needle| (в обох системах нумерації). Наприклад, для того жneedle=«abcdadcd» буде:

Суфікс [пустий] d cd dcd ... abcdadcd Зсув 1 2 4 8 ... 8 Ілюстрація було  ? ?d ?cd ?dcd ... abcdadcd стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd 

Якщо шаблон починається і закінчується однією і тією ж комбінацією букв, |needle| взагалі не з'явиться в таблиці. Наприклад, для needle=«колокол» для всіх суфіксів (крім, звичайно, порожнього) зсув буде дорівнювати 4.

Суфікс [пустий] л ол ... олокол колокол Зсув 1 4 4 ... 4 4 Ілюстрація було  ? ?л ?ол ... ?олокол колокол стало колокол колокол колокол ... колокол колокол 

Існує швидкий алгоритм обчислення таблиці суфіксів. Цей алгоритм використовує префікс-функцію рядка.

m = length(needle) pi[] = префікс-функція(needle) pi1[] = префікс-функція(звернення(needle)) for j=0..m suffshift[j] = m - pi[m] for i=1..m j = m - pi1[i] suffshift[j] = min(suffshift[j], i - pi1[i]) 

Тут suffshift[0] відповідає всій стрічці яка збіглася; suffshift[m] — пустому суфіксу. Оскільки префікс-функція обчислюється за O(|needle|) операцій, обчислювальна складність цього кроку також дорівнює O(|needle|).

Приклад роботи алгоритму

Шуканий шаблон — «abbad». Таблиця стоп-символів буде виглядати як

Символ a b [інші] Позиція 4 3 0 

Таблиця суфіксів для всіх можливих суфіксів (крім порожнього) дає максимальний зсув — 5.

abeccaabadbabbad abbad 

Накладаємо зразок на рядок. Збіги суфікса немає — таблиця суфіксів дає зсув на одну позицію. Для символу вихідної стрічки, що не збігся, «с» (5-а позиція) у таблиці стоп-символів записаний 0. Зсуваємо зразок вправо на 5-0=5 позицій.

abeccaabadbabbad abbad 

Символи 3-5 збіглися, а другий — ні. Евристика стоп-символу для «а» не працює (2-4=-2). Але оскільки частина символів збіглася, у справу включається евристика суфікса, що збігся, який робить зсув шаблон відразу на п'ять позицій!

abeccaabadbabbad abbad 

І знову збігу суфікса немає. Відповідно до таблиці стоп-символів зсуваємо зразок на 1 позицію і отримуємо шукане входження зразка:

abeccaabadbabbad abbad 

Доведення коректності

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

Отже, нехай збігся суфікс S, needle=PbS, стоп-символ — a (надалі малі літери — символи, великі — стрічки).

Стрічка: * * * * * * * a [-- S --] * * * * Шаблон: [--- P ---] b [-- S --] 

Евристика стоп-символу. Працює, коли в стрічці S символ а відсутній. Якщо P=WaV і в стрічці V немає символу а, то евристика стоп-символу пропонує зрушення на |V|+1 позицію.

Стрічка: * * * * * * * * * * * * a [-- S --] * * * * * * * * Шаблон: [- W -] a [--- V ---] b [-- S --] Пропустити: [- W -] a [--- V ---] b [-- S --] Новий крок: [- W -] a [--- V ---] b [-- S --] 

Дійсно, якщо в стрічці V немає букви a, нічого пробувати пропущенні |V| позиції.

Якщо ж в needle взагалі немає символу а, то евристика стоп-символу пропонує зсув на |P|+1 позицію — і також немає сенсу пробувати припущення |P|.

Стрічка: * * * * * * * * a [-- S --] * * * * * * * * Шаблон: [--- P ---] b [-- S --] Пропустити: [--- P ---] b [-- S --] Новий крок: [--- P ---] b [-- S --] 

Евристика суфікса, який збігся. Сама неформальна фраза — «найменша величина, на яку потрібно зрушити вправо шаблон, щоб він знову збігся з S» — каже, що менші зрушення марні. Тому замість них покажемо коректність прискореного алгоритму обчислення таблиці суфіксів — тобто, продемонструємо, що він обчислює саме цей «мінімальний зсув».

Спочатку розглянемо перший цикл. pi(m) —це довжина максимального суфікса needle, який є префіксом. Тому m−pi(m) — максимальний зсув, який обумовлюється тим, що S та needle можуть перекриватися і частково; далі рухати неприпустимо.

Наприклад: навіть якщо весь шаблон «колокол» збігся, далі 4 символів зсув неможливий — наприклад, у стрічці«колоколокол» шаблон «колокол» зустрічається двічі, на 1-й і на 5-й позиції.

haystack: колоколокол Спроба 1: колокол Спроба 2: колокол 

Тепер розглянемо другий цикл — він відповідає повному перекриттю S та needle. Покажемо такий факт: якщо needle=P′SX=P′YS та інших входжень S в SX=YS немає, то в позиції, яка відповідає суфіксу S (тобто, m−|S|), буде записано рівно |X|=|Y|.

Попередня оцінка, пов'язана з частковим перекриттям S та needle, не менше |P|+1 і тому ролі не грає.

Розглянемо ітерацію i=|SX|=|YS|. Очевидно, що pi1(i) — це довжина максимального префікса-суфікса рядки SX=YS. Покажемо, що ця величина дорівнює саме |S|. Дійсно, якщо ця величина більше |S|, то стрічку SX=YS можливо розкласти так TV=WT, причому |T|>|S|. ОскількиYS=WT, то T=QS, и SX=QSV при порожніх рядках Q и V. Отримуємо третє входження стрічки S в SX, протиріччя. Звідси pi1(i)=|S|, значить, в позицію m−pi1(i)=m−|S| записується число i−pi1(i)=|SX|−|S|=|X|.

З'ясуємо, чи може на якийсь ітерації в цю комірку записатися менше число. При i1<i: з умови відсутності третього входження S не може бути pi1(i1)=pi1(i), а значить, j(i1)≠j(i). При i2>i: j(i2)=j(i) можливо, но в такому випадку в комірку буде записано |X|+i2−i, що більше |X|.

Порівняння з іншими алгоритмами

Переваги

Алгоритм Боєра-Мура на «хороших» даних дуже швидкий, а ймовірність появи «поганих» даних вкрай мала. Тому він оптимальний в більшості випадків, коли немає можливості провести попередню обробку тексту, в якому проводиться пошук (haystack). Хіба що на коротких текстах виграш не виправдовує попередніх обчислень.

На x86 існує гарна асемблерна реалізація АБМ, заснована на командах std; rep cmpsb. Після невдалого порівняння в регістрі ecx залишається індекс символу, якій збігся; вказівники esi и edi вказують на відповідні символи рядків needle та haystack. 

Недоліки

Алгоритми сімейства Боєра-Мура не розширюються до приблизного пошуку, пошуку будь-якого рядка з декількох.

Порівняння не є «чорним скринею», тому при реалізації найбільш швидкого пошуку доводиться або розраховувати на вдалу роботу оптимізатора, або вручну оптимізувати пошук на асемблерному рівні.

Якщо текст змінюється рідко, а операцій пошуку проводиться багато (наприклад, пошукова машина), у тексті варто було б провести індексацію, після чого пошук можна буде виконувати в рази швидше, ніж навіть алгоритмом Боєра-Мура.

На великих алфавітах (наприклад, Юнікод) таблиця стоп-символів може займати багато пам'яті. У таких випадках або обходяться хеш-таблицями, або дроблять алфавіт, розглядаючи, наприклад, 4-байтовий символ як пару двобайтових.

На штучно підібраних «невдалих» текстах (наприклад, needle=«колоколоколоколоколокол») швидкість алгоритму Боєр-Мура серйозно знижується. Існують спроби поєднати притаманну алгоритмом Кнута-Морріса-Пратта ефективність у «поганих» випадках і швидкість Боєра-Мура в «хороших» — наприклад, турбо-алгоритм, зворотний алгоритм Колуссі  та інші.

Примітки

1. Hume; Sunday (November 1991). Fast String Searching. Software—Practice and Experience. 21 (11): 1221—1248.
2. ; (October 1977). . Comm. ACM. New York, NY, USA: Association for Computing Machinery. 20 (10): 762—772. doi:10.1145/359842.359859. ISSN 0001-0782. Архів оригіналу за 16 лютого 2019. Процитовано 25 липня 2018.
3. . Архів оригіналу за 4 лютого 2012. Процитовано 14 грудня 2015.
4. (англ.). Архів оригіналу за 9 березня 2016.

Література

• Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000. . — с. 801. = T. Cormen, E. Leiserson, R. Rivest. Introduction to Algorithms. The MIT Press, 1990.