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

В този урок ще научите какво е алгоритъм rabin-karp. Освен това ще намерите работещи примери за алгоритъм rabin-karp в C, C ++, Java и Python.

Алгоритъмът на Рабин-Карп е алгоритъм, използван за търсене / съвпадение на модели в текста с помощта на хеш функция. За разлика от алгоритъма за наивно съвпадение на низове, той не преминава през всеки символ в началната фаза, а филтрира символите, които не съвпадат, и след това извършва сравнението.

Хеш функцията е инструмент за картографиране на по-голяма входна стойност към по-малка изходна стойност. Тази изходна стойност се нарича хеш стойност.

Как работи алгоритъмът на Рабин-Карп?

Последователност от символи се взема и проверява за възможността за наличие на необходимия низ. Ако тогава е намерена възможността, се извършва съвпадение на символите.

Нека разберем алгоритъма със следните стъпки:

Нека текстът бъде: Текст,
а низът, който ще се търси в горния текст, е: Шаблон
Нека определим а numerical value(v)/weightза символите, които ще използваме в проблема. Тук сме взели само първите десет азбуки (т.е. A до J). Текстови тежести
m е дължината на шаблона и n е дължината на текста. Тук m = 10 and n = 3.
нека d е броят на символите във въведения набор. Тук взехме набор от входни данни (A, B, C,…, J). И така d = 10,. Можете да приемете всяка подходяща стойност за d.
Нека изчислим хеш стойността на шаблона. Хеш стойност на текста

хеш стойност за шаблон (p) = Σ (v * dm-1) mod 13 = ((3 * 10 ² ) + (4 * 10 ¹ ) + (4 * 10 ⁰ )) mod 13 = 344 mod 13 = 6

В изчислението по-горе изберете просто число (тук, 13) по такъв начин, че да можем да извършим всички изчисления с аритметика с една прецизност.

Причината за изчисляване на модула е дадена по-долу.

Изчислете хеш стойността за текстовия прозорец с размер m.

За първия прозорец ABC, хеш стойност за текст (t) = Σ (v * dn-1) mod 13 = ((1 * 10 ² ) + (2 * 10 ¹ ) + (3 * 10 ⁰ )) mod 13 = 123 мод 13 = 6

Сравнете хеш стойността на шаблона с хеш стойността на текста. Ако те съвпадат тогава, се извършва съпоставяне на символи.
В горните примери, хеш стойността на първия прозорец (т.е. t) съвпада с p, така че отидете за съвпадение на символи между ABC и CDD. Тъй като те не съвпадат така, преминете към следващия прозорец.
Изчисляваме хеш стойността на следващия прозорец, като изваждаме първия член и добавяме следващия член, както е показано по-долу.

t = ((1 * 10 ² ) + ((2 * 10 ¹ ) + (3 * 10 ⁰ )) * 10 + (3 * 10 ⁰ )) 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.

За 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); )

Ограничения на алгоритъма на Рабин-Карп

Фалшив хит

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

Фалшивото попадение увеличава сложността във времето на алгоритъма. За да сведем до минимум фалшивото попадение, използваме модул. Това значително намалява фалшивото попадение.