Algoritma Rabin-Karp

Dalam tutorial ini, Anda akan mempelajari apa itu algoritme rabin-karp. Selain itu, Anda akan menemukan contoh kerja algoritma rabin-karp di C, C ++, Java dan Python.

Algoritma Rabin-Karp merupakan algoritma yang digunakan untuk mencari / mencocokkan pola pada teks dengan menggunakan fungsi hash. Tidak seperti algoritme pencocokan string naif, algoritme ini tidak melakukan perjalanan melalui setiap karakter pada fase awal melainkan menyaring karakter yang tidak cocok dan kemudian melakukan perbandingan.

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

Bagaimana Algoritma Rabin-Karp Bekerja?

Urutan karakter diambil dan diperiksa kemungkinan keberadaan string yang diperlukan. Jika kemungkinan ditemukan kemudian, pencocokan karakter dilakukan.

Mari kita pahami algoritme dengan langkah-langkah berikut:

  1. Biarkan teks menjadi: Teks
    Dan string yang akan dicari pada teks di atas menjadi: Pola
  2. Mari kita tetapkan a numerical value(v)/weightuntuk karakter yang akan kita gunakan dalam soal. Di sini, kami telah mengambil sepuluh huruf pertama saja (yaitu A ke J). Bobot Teks
  3. m adalah panjang pola dan n adalah panjang teks. Di sini, m = 10 and n = 3.
    Misalkan d adalah jumlah karakter dalam set input. Di sini, kami telah mengambil set input (A, B, C,…, J). Jadi d = 10,. Anda dapat mengasumsikan nilai yang sesuai untuk d.
  4. Mari kita hitung nilai hash dari pola tersebut. Nilai teks hash
nilai hash untuk pola (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Dalam perhitungan di atas, pilih bilangan prima (di sini, 13) sedemikian rupa sehingga kita dapat melakukan semua perhitungan dengan aritmatika presisi tunggal.

Alasan untuk menghitung modulus diberikan di bawah ini.

  1. Hitung nilai hash untuk jendela teks berukuran m.
Untuk jendela 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 dari pola dengan nilai hash teks. Jika cocok, maka pencocokan karakter dilakukan.
    Dalam contoh di atas, nilai hash dari jendela pertama (yaitu t) cocok dengan p jadi, pilih pencocokan karakter antara ABC dan CDD. Karena tidak cocok, lanjutkan ke jendela berikutnya.
  2. Kami menghitung nilai hash dari jendela berikutnya dengan mengurangi suku pertama dan menambahkan suku berikutnya seperti yang ditunjukkan di bawah ini.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

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

t = ((d * (t - v (karakter yang akan dihapus) * h) + v (karakter yang akan ditambahkan)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Dimana , h = d m-1 = 10 3-1 = 100.
  1. Untuk BCC, t = 12 ( ≠ 6). Karena itu, lanjutkan ke jendela berikutnya.
    Setelah beberapa pencarian, kita akan mendapatkan hasil yang cocok untuk jendela CDA di teks. Nilai hash dari jendela yang berbeda

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 sampai n - m if p = ts if p (1… m) = t (s + 1… s + m) print "pola ditemukan pada posisi" 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 ++ 
 # 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

Ketika nilai hash dari pola tersebut cocok dengan nilai hash dari sebuah jendela teks tetapi jendela tersebut bukan pola yang sebenarnya maka itu disebut hit palsu.

Hit palsu meningkatkan kompleksitas waktu dari algoritme. Untuk meminimalkan serangan palsu, kami menggunakan modulus. Ini sangat mengurangi serangan palsu.

Kompleksitas Algoritma Rabin-Karp

Rata-rata kasus dan kompleksitas kasus terbaik dari algoritma Rabin-Karp adalah O(m + n)dan kompleksitas kasus terburuk adalah O (mn).

Kompleksitas kasus terburuk terjadi ketika serangan palsu terjadi sejumlah untuk semua jendela.

Aplikasi Algoritma Rabin-Karp

  • Untuk pencocokan pola
  • Untuk mencari string dalam teks yang lebih besar

Artikel yang menarik...