Алгоритм Рабіна-Карпа

У цьому підручнику ви дізнаєтесь, що таке алгоритм рабін-карпа. Також ви знайдете робочі приклади алгоритму rabin-karp на мовах C, C ++, Java та Python.

Алгоритм Рабіна-Карпа - це алгоритм, який використовується для пошуку / узгодження шаблонів у тексті за допомогою хеш-функції. На відміну від Naive алгоритму узгодження рядків, він не проходить через кожен символ у початковій фазі, а фільтрує символи, які не відповідають, а потім виконує порівняння.

Хеш-функція - це інструмент для зіставлення великого вхідного значення з меншим вихідним значенням. Це вихідне значення називається хеш-значенням.

Як працює алгоритм Рабіна-Карпа?

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

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

  1. Нехай текст буде: Text
    А рядок, який потрібно шукати у наведеному тексті, буде: Pattern
  2. Давайте призначимо a numerical value(v)/weightдля символів, які ми будемо використовувати в задачі. Тут ми взяли лише перші десять алфавітів (тобто від A до J). Ваги тексту
  3. m - довжина візерунка і n - довжина тексту. Тут m = 10 and n = 3.
    нехай d - кількість символів у наборі введення. Тут ми взяли набір введення (A, B, C,…, J). Так, d = 10. Ви можете прийняти будь-яке відповідне значення для d.
  4. Обчислимо хеш-значення шаблону. Хеш-значення тексту
хеш-значення для шаблону (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

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

Причина для обчислення модуля наведена нижче.

  1. Обчисліть хеш-значення для текстового вікна розміром m.
Для першого вікна ABC, хеш-значення для тексту (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 мод 13 = 6
  1. Порівняйте хеш-значення шаблону з хеш-значенням тексту. Якщо вони збігаються тоді, виконується збіг символів.
    У наведених вище прикладах хеш-значення першого вікна (тобто t) збігається з p, тому слід переглядати збіг символів між ABC та CDD. Оскільки вони не збігаються, перейдіть до наступного вікна.
  2. Ми обчислюємо хеш-значення наступного вікна, віднімаючи перший член і додаючи наступний член, як показано нижче.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

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

t = ((d * (t - v (символ, який потрібно видалити) * h) + v (символ, який потрібно додати)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Де , h = d m-1 = 10 3-1 = 100.
  1. Для BCC t = 12 ( ≠ 6). Тому перейдіть до наступного вікна.
    Після кількох пошуків ми отримаємо в тексті відповідність для віконного CDA. Хеш-значення різних вікон

Алгоритм

 n = t. довжина m = p. довжина h = dm-1 mod qp = 0 t0 = 0 для i = 1 до mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q для s = 0 до n - m, якщо p = ts, якщо p (1 … m) = t (s + 1 … s + m) друкує "шаблон, знайдений у положенні" s Якщо s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Приклади Python, Java та C / C ++

Python Java C C ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

Обмеження алгоритму Рабіна-Карпа

Неправдивий удар

Коли хеш-значення шаблону збігається з хеш-значенням вікна тексту, але вікно не є фактичним шаблоном, тоді це називається помилковим потраплянням.

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

Складність алгоритму Рабіна-Карпа

Середня складність та найкраща складність випадку алгоритму Рабіна-Карпа є, O(m + n)а найгірша складність - O (mn).

Найгірша складність виникає, коли помилкові звернення мають число для всіх вікон.

Застосування алгоритму Рабіна-Карпа

  • Для узгодження зразків
  • Для пошуку рядка у більшому тексті

Цікаві статті...