Rabin-Karpův algoritmus

V tomto výukovém programu se dozvíte, co je rabin-karpský algoroitmus. Také najdete pracovní příklady algoritmu rabin-karp v C, C ++, Java a Python.

Rabin-Karpův algoritmus je algoritmus používaný k vyhledávání / porovnávání vzorů v textu pomocí hashovací funkce. Na rozdíl od naivního algoritmu porovnávání řetězců neprochází v počáteční fázi každým znakem, spíše filtruje znaky, které se neshodují, a poté provede srovnání.

Hašovací funkce je nástroj k mapování větší vstupní hodnoty na menší výstupní hodnotu. Tato výstupní hodnota se nazývá hodnota hash.

Jak funguje Rabin-Karpův algoritmus?

Je odebrána posloupnost znaků a je zkontrolována možnost přítomnosti požadovaného řetězce. Pokud je možnost nalezena, provede se porovnávání znaků.

Rozumíme algoritmu pomocí následujících kroků:

  1. Nechte text být: Text
    A řetězec, který má být vyhledán ve výše uvedeném textu, je: Vzor
  2. Pojďme přiřadit a numerical value(v)/weightpro znaky, které použijeme v úloze. Zde jsme vzali pouze prvních deset abeced (tj. A až J). Váhy textu
  3. m je délka vzoru an je délka textu. Zde m = 10 and n = 3.
    Nechť d je počet znaků ve vstupní sadě. Zde jsme vzali vstupní sadu (A, B, C, …, J). Takže d = 10. Můžete předpokládat jakoukoli vhodnou hodnotu pro d.
  4. Pojďme vypočítat hodnotu hash vzoru. Hodnota hash textu
hash hodnota pro vzor (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Ve výše uvedeném výpočtu vyberte prvočíslo (zde 13) takovým způsobem, že můžeme provádět všechny výpočty s aritmetikou s jednou přesností.

Důvod výpočtu modulu je uveden níže.

  1. Vypočítejte hodnotu hash pro textové okno o velikosti m.
U prvního okna ABC hodnota hash pro text (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Porovnejte hodnotu hash vzoru s hodnotou hash textu. Pokud se shodují, provede se párování znaků.
    Ve výše uvedených příkladech se hash hodnota prvního okna (tj. T) shoduje s p, jděte na shodu znaků mezi ABC a CDD. Protože se neshodují, přejděte do dalšího okna.
  2. Hodnotu hash dalšího okna vypočítáme odečtením prvního členu a přidáním dalšího členu, jak je znázorněno níže.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Abychom tento proces optimalizovali, využíváme předchozí hashovací hodnotu následujícím způsobem.

t = ((d * (t - v (znak, který se má odstranit) * h) + v (znak, který se má přidat)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Kde , h = d m-1 = 10 3-1 = 100.
  1. Pro BCC t = 12 ( ≠ 6). Proto přejděte do dalšího okna.
    Po několika vyhledáváních získáme v textu shodu pro okno CDA. Hodnota hash různých oken

Algoritmus

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 pro i = 1 až mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q pro s = 0 až n - m, pokud p = ts, pokud p (1 … m) = t (s + 1 … s + m) vytisknout „vzor nalezený v poloze“ s Pokud s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python, Java a C / C ++ příklady

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

Omezení Rabin-Karpova algoritmu

Falešný zásah

Když se hodnota hash vzoru shoduje s hodnotou hash okna textu, ale okno není skutečný vzor, ​​pak se nazývá falešný zásah.

Falešný zásah zvyšuje časovou složitost algoritmu. Abychom minimalizovali falešný zásah, používáme modulus. Výrazně snižuje rušivý zásah.

Složitost Rabin-Karpova algoritmu

Složitost průměrného a nejlepšího případu Rabin-Karpova algoritmu je O(m + n)a nejhorší složitost O je (mn).

Složitost v nejhorším případě nastane, když dojde k falešným zásahům u všech oken.

Aplikace Rabin-Karpova algoritmu

  • Pro porovnávání vzorů
  • Pro hledání řetězce ve větším textu

Zajímavé články...