Rabin-Karp Algoritması

Bu eğitimde rabin-karp algoroitminin ne olduğunu öğreneceksiniz. Ayrıca, rabin-karp algoritmasının çalışma örneklerini C, C ++, Java ve Python'da bulacaksınız.

Rabin-Karp algoritması, bir hash fonksiyonu kullanarak metindeki kalıpları aramak / eşleştirmek için kullanılan bir algoritmadır. Naive dizge eşleştirme algoritmasının aksine, ilk aşamada her karakterde dolaşmaz, eşleşmeyen karakterleri filtreler ve ardından karşılaştırmayı yapar.

Karma işlevi, daha büyük bir girdi değerini daha küçük bir çıktı değeriyle eşlemek için kullanılan bir araçtır. Bu çıktı değerine hash değeri denir.

Rabin-Karp Algoritması Nasıl Çalışır?

Bir dizi karakter alınır ve gerekli dizinin varlığı olasılığı için kontrol edilir. Olasılık bulunursa, karakter eşleştirmesi yapılır.

Algoritmayı aşağıdaki adımlarla anlayalım:

  1. Metin şöyle olsun: Metin
    Ve yukarıdaki metinde aranacak dize: Model
  2. Problemde numerical value(v)/weightkullanacağımız karakterler için bir atayalım. Burada sadece ilk on alfabeyi aldık (yani A'dan J'ye). Metin Ağırlıkları
  3. m desenin uzunluğu ve n metnin uzunluğu. Burada, m = 10 and n = 3.
    d giriş kümesindeki karakter sayısı olsun. Burada girdi setini (A, B, C,…, J) aldık. Yani d = 10,. D için herhangi bir uygun değeri varsayabilirsiniz.
  4. Desenin hash değerini hesaplayalım. Metnin karma değeri
desen için karma değeri (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Yukarıdaki hesaplamada, tüm hesaplamaları tek duyarlıklı aritmetik ile yapabileceğimiz bir asal sayı (burada, 13) seçin.

Modülü hesaplamanın nedeni aşağıda verilmiştir.

  1. M boyutundaki metin penceresi için hash değerini hesaplayın.
ABC ilk penceresi için, metin (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = için hash değeri 123 mod 13 = 6
  1. Desenin hash değerini metnin hash değeri ile karşılaştırın. Eşleşirlerse, karakter eşleştirme gerçekleştirilir.
    Yukarıdaki örneklerde, ilk pencerenin karma değeri (yani t) p ile eşleşir, bu nedenle ABC ve CDD arasındaki karakter eşleşmesine gidin. Eşleşmedikleri için bir sonraki pencereye gidin.
  2. Bir sonraki pencerenin hash değerini, ilk terimi çıkararak ve bir sonraki terimi aşağıda gösterildiği gibi ekleyerek hesaplıyoruz.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Bu süreci optimize etmek için önceki hash değerini aşağıdaki şekilde kullanırız.

t = ((d * (t - v (kaldırılacak karakter) * h) + v (eklenecek karakter)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Burada , h = d m-1 = 10 3-1 = 100.
  1. BCC için t = 12 ( ≠ 6). Bu nedenle, bir sonraki pencereye gidin.
    Birkaç aramadan sonra, metinde CDA penceresi için eşleşmeyi alacağız. Farklı pencerelerin karma değeri

Algoritma

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 for i = 1 to mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q s = 0 ila n - m için p = ts ise p (1… m) = t (s + 1… s + m) print "desen konumunda" s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python, Java ve C / C ++ Örnekleri

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

Rabin-Karp Algoritmasının Sınırlamaları

Sahte Hit

Desenin hash değeri, metnin bir penceresinin hash değeriyle eşleştiğinde ancak pencere gerçek desen olmadığında, buna sahte vuruş denir.

Sahte isabet, algoritmanın zaman karmaşıklığını artırır. Sahte isabeti en aza indirmek için modül kullanıyoruz. Sahte isabeti büyük ölçüde azaltır.

Rabin-Karp Algoritma Karmaşıklığı

Rabin-Karp algoritmasının ortalama durumu ve en iyi durum karmaşıklığı O(m + n)ve en kötü durum karmaşıklığı O (mn) 'dir.

En kötü durum karmaşıklığı, tüm pencereler için sahte isabetler bir sayı olduğunda ortaya çıkar.

Rabin-Karp Algoritma Uygulamaları

  • Desen eşleştirme için
  • Daha büyük bir metinde dizeyi aramak için

Ilginç makaleler...