Algoritma Rabin-Karp

Dalam tutorial ini, anda akan mengetahui apa itu algoritma rabin-karp. Anda juga akan mendapat contoh algoritma rabin-karp yang berfungsi di C, C ++, Java dan Python.

Algoritma Rabin-Karp adalah algoritma yang digunakan untuk mencari / mencocokkan corak dalam teks menggunakan fungsi hash. Tidak seperti algoritma pemadanan rentetan Naive, ia tidak melalui setiap watak pada fasa awal melainkan menyaring watak yang tidak sepadan dan kemudian melakukan perbandingan.

Fungsi hash adalah alat untuk memetakan nilai input yang lebih besar ke nilai output yang lebih kecil. Nilai output ini dipanggil nilai hash.

Bagaimana Algoritma Rabin-Karp Berfungsi?

Urutan watak diambil dan diperiksa untuk kemungkinan adanya rentetan yang diperlukan. Sekiranya kemungkinan itu dijumpai, pencocokan watak dilakukan.

Mari kita memahami algoritma dengan langkah-langkah berikut:

  1. Biarkan teksnya: Teks
    Dan rentetan yang akan dicari dalam teks di atas adalah: Corak
  2. Mari kita menetapkan numerical value(v)/weightwatak untuk watak yang akan kita gunakan dalam masalah tersebut. Di sini, kami hanya mengambil sepuluh huruf pertama (iaitu A hingga J). Berat Teks
  3. m menjadi panjang corak dan n menjadi panjang teks. Di sini, m = 10 and n = 3.
    Biarkan d menjadi bilangan watak dalam set input. Di sini, kami telah mengambil set input (A, B, C,…, J). Jadi , d = 10. Anda boleh menganggap nilai yang sesuai untuk d.
  4. Mari kita mengira nilai hash corak. Nilai Hash teks
nilai hash untuk corak (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Dalam pengiraan di atas, pilih nombor perdana (di sini, 13) sedemikian rupa sehingga kita dapat melakukan semua pengiraan dengan aritmetik ketepatan tunggal.

Sebab untuk mengira modulus diberikan di bawah.

  1. Hitung nilai hash untuk tetingkap teks berukuran m.
Untuk tetingkap pertama ABC, nilai hash untuk teks (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Bandingkan nilai hash corak dengan nilai hash teks. Sekiranya ia sesuai, pencocokan watak dilakukan.
    Dalam contoh di atas, nilai hash tetingkap pertama (iaitu t) sesuai dengan p jadi, cari pencocokan watak antara ABC dan CDD. Oleh kerana ia tidak sesuai, pergi ke tetingkap seterusnya.
  2. Kami mengira nilai hash tetingkap seterusnya dengan mengurangkan istilah pertama dan menambahkan istilah seterusnya seperti yang ditunjukkan di bawah.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Untuk mengoptimumkan proses ini, kami menggunakan nilai hash sebelumnya dengan cara berikut.

t = ((d * (t - v (watak yang akan dikeluarkan) * h) + v (watak yang akan ditambahkan)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Di mana , h = d m-1 = 10 3-1 = 100.
  1. Untuk BCC, t = 12 ( ≠ 6). Oleh itu, pergi ke tetingkap seterusnya.
    Selepas beberapa carian, kami akan mendapatkan padanan untuk CDA tetingkap dalam teks. Nilai Hash tingkap yang berbeza

Algoritma

 n = t. panjang m = p. panjang h = dm-1 mod qp = 0 t0 = 0 untuk i = 1 hingga mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q untuk s = 0 hingga n - m jika p = ts jika p (1… m) = t (s + 1… s + m) cetak "corak dijumpai pada kedudukan" s Jika s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Contoh Python, Java dan 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); )

Batasan Algoritma Rabin-Karp

Hit palsu

Apabila nilai hash corak sesuai dengan nilai hash tetingkap teks tetapi tetingkap bukan corak yang sebenarnya maka ia disebut hit palsu.

Pukulan palsu meningkatkan kerumitan masa algoritma. Untuk mengurangkan hit palsu, kami menggunakan modulus. Ini sangat mengurangkan hentaman palsu.

Kerumitan Algoritma Rabin-Karp

Rata-rata kes dan kerumitan kes terbaik algoritma Rabin-Karp adalah O(m + n)dan kerumitan kes terburuk adalah O (mn).

Kerumitan yang paling teruk berlaku apabila hits palsu berlaku untuk semua tetingkap.

Aplikasi Algoritma Rabin-Karp

  • Untuk pemadanan corak
  • Untuk mencari rentetan dalam teks yang lebih besar

Artikel menarik...