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

У овом упутству ћете научити шта је рабин-карп алгоритам. Такође, наћи ћете радне примере рабин-карп алгоритма на Ц, Ц ++, Јава и Питхон.

Рабин-Карпов алгоритам је алгоритам који се користи за тражење / подударање образаца у тексту помоћу хеш функције. За разлику од Наиве алгоритма за подударање низова, он не пролази кроз сваки знак у почетној фази, већ филтрира знакове који се не подударају и затим врши поређење.

Хасх функција је алат за мапирање веће улазне вредности у мању излазну вредност. Ова излазна вредност назива се хеш вредност.

Како функционише Рабин-Карпов алгоритам?

Узима се низ знакова и проверава се могућност присуства потребног низа. Ако се тада пронађе могућност, врши се подударање знакова.

Да разумемо алгоритам у следећим корацима:

  1. Нека текст буде: Текст
    А низ који се тражи у горњем тексту: Узорак
  2. Додијелимо а numerical value(v)/weightза знакове које ћемо користити у задатку. Овде смо узели само првих десет абецеда (тј. А до Ј). Пондери текста
  3. м је дужина узорка и н дужина текста. Овде m = 10 and n = 3.
    нека је д број знакова у скупу уноса. Овде смо узели скуп улаза (А, Б, Ц,…, Ј). Тако, d = 10. Можете претпоставити било коју погодну вредност за д.
  4. Израчунајмо хеш вредност шаблона. Хасх вредност текста
хеш вредност за образац (п) = Σ (в * дм-1) мод 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) мод 13 = 344 мод 13 = 6

У горњем прорачуну одаберите прост број (овде 13) на такав начин да све прорачуне можемо извршити аритметиком са једном прецизношћу.

Разлог за израчунавање модула дат је у наставку.

  1. Израчунајте хеш вредност за текстуални прозор величине м.
За први прозор АБЦ, хеш вредност за текст (т) = Σ (в * дн-1) мод 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) мод 13 = 123 мод 13 = 6
  1. Упоредите хеш вредност шаблона са хеш вредношћу текста. Ако се тада подударају, врши се упаривање знакова.
    У горњим примерима, хеш вредност првог прозора (тј. Т) поклапа се са п, па идите на подударање знакова између АБЦ и ЦДД. Пошто се не подударају, идите на следећи прозор.
  2. Хасх вредност следећег прозора израчунавамо одузимањем првог члана и додавањем следећег члана као што је приказано у наставку.
т = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) мод 13 = 233 мод 13 = 12

Да бисмо оптимизовали овај процес, користимо претходну хеш вредност на следећи начин.

т = ((д * (т - в (знак који треба уклонити) * х) + в (знак који треба додати)) мод 13 = ((10 * (6 - 1 * 9) + 3) мод 13 = 12 Где , х = д м-1 = 10 3-1 = 100.
  1. За БЦЦ, т = 12 ( = 6). Према томе, идите на следећи прозор.
    После неколико претрага, у тексту ћемо добити подударање за прозорски ЦДА. Хасх вредност различитих прозора

Алгоритам

 н = т.дужина м = п.дужина х = дм-1 мод кп = 0 т0 = 0 за и = 1 до мп = (дп + п (и)) мод к т0 = (дт0 + т (и)) мод к за с = 0 до н - м ако је п = тс ако је п (1… м) = т (с + 1… с + м) принт „образац пронађен на положају“ с Ако је с <нм тс + 1 = (д ( тс - т (с + 1) х) + т (с + м + 1)) мод к

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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)а најгора сложеност је О (мн).

Сложеност у најгорем случају јавља се када се лажни погоци појаве на бројним прозорима.

Примене Рабин-Карп алгоритма

  • За подударање шаблона
  • За претрагу низа у већем тексту

Занимљиви Чланци...