1.3. Алгоритм Рабіна

Алгоритм Рабіна представляє собою модифікацію лінійного алгоритму.

У слові A, довжина якого дорівнює m, шукається зразок X довжини n. Виріжемо "віконечко" розміром n воно рухається по вхідному слову. Чи збігається слово в "віконечку" із заданим зразком? Фіксується деяка числова функція на словах довжини n, тоді завдання зводиться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" та на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах.

Цей алгоритм виконує лінійний прохід по рядку (n кроків) і лінійний прохід по всьому тексту (m кроків), отже, загальний час роботи є O (n + m). При цьому не враховується часова складність обчислення хеш-функції, так як, суть алгоритму в тому і полягає, щоб дана функція була настільки легко обчислюється, що її робота не впливала на загальну роботу алгоритму. Тоді, час роботи алгоритму лінійно залежить від розміру рядка і тексту, стало бути програма працює швидко. Адже замість того, щоб перевіряти кожну позицію на предмет відповідності зі зразком, можна перевіряти тільки ті, які «нагадують» зразок. Отже, для того, щоб легко встановлювати явна невідповідність, буде використовуватися функція, яка повинна:

1. Легко обчислюватися.

2. Як можна краще розрізняти неспівпадаючі рядки.

3. Hash (y [i +1, i + m]) повинна легко обчислюватися за hash (y [i, i + m -1].

Під час пошуку х буде порівнюватися hash (x) з hash (y [i, i + m-1]) для i від 0 до nm включно. Якщо буде виявлено збіг, то перевіряється посимвольно. Реалізація цього алгоритму представлена ​​у додатку 2.

Приклад (зручною для обчислення функції). Замінюються всі букви в слові і зразку їх номерами, що представляють собою цілі числа.Тоді зручною функцією є сума цифр. (При зсуві "віконечка" потрібно додати нове число і відняти "зникле".)

Однак, проблема в тому, що шукана рядок може бути довгою, рядків в тексті теж вистачає. А так як кожному рядку потрібно зіставити унікальне число, то і чисел має бути багато, а стало бути, числа будуть великими (порядку D * n, де D - кількість різних символів), і працювати з ними буде так само незручно. Але який інтерес працювати тільки з короткими рядками і цифрами? Вище розглянутий алгоритм можна поліпшити.

Приклад (сімейства зручних функцій). Вибирається деяке число p (бажано просте) і деякий вирахування x за модулем p. Кожне слово довжини n буде розглядатися як послідовність цілих чисел (замінивши літери їх кодами). Ці числа будуть розглядатися як коефіцієнти многочлена ступеня n-1 і обчислюється значення цього многочлена з модулю p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить своя функція). Зсув "віконечка" на 1 відповідає вирахуванню старшого члена, множенню на x і додаванню вільного члена.Наступне міркування говорить на користь того, що збігу не дуже вірогідні. Нехай число p фіксоване і до того ж воно є простим, а X і Y - два різних слова довжини n. Тоді їм відповідають різні многочлени (ми припускаємо, що коди всіх букв різні - це можливо при p, більшому числа літер алфавіту). Збіг значень функції означає, що в точці x ці два різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця є многочлен ступеня n-1 і має не більше n-1 коренів. Таким чином, якщо n багато менше p, то випадковим значенням x мало шансів потрапити в "невдалу" крапку.

Строго кажучи, час роботи всього алгоритму в цілому, є O (m + n + mn / P), mn / P досить невелика, так що складність роботи майже лінійна. Зрозуміло, що просте число слід вибирати великим, чим більше це число, тим швидше буде працювати програма.

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