Algoritma Rabin Karp

Posted by Admin on 14 April 2016, 19:11 algoritma, dokumen, fingerprint, karp rabin, menentukan kesamaan antar dokumen, plagiat, rabin karp

Algoritma Rabin Karp adalah algoritma pencarian kata yang mencari sebuah pola berupa substring dalam sebuah teks menggunakan hashing. Algoritma ini sangat efektif untuk pencocokan kata dengan pola banyak. Salah satu aplikasi praktis dari algoritma Rabin Karp adalah dalam pendeteksian plagiarisme.

Untuk teks dengan panjang n dan pola dengan panjang m, waktu komputasi terbaik adalah O(n), sedangkan terburuknya adalah O((n-m+1)m).

Langkah-langkah dalam algoritma Rabin Karp

    1. Menghilangkan tanda baca dan mengubah ke teks sumber dan kata yang ingin dicari menjada kata-kata tanpa huruf kapital.
    2. Membagi teks ke dalam gram-gram yang ditentukan nilai k-gram nya.
    3. Mencari nilai hash dengan fungsi rolling hash dari tiap gram yang terbentuk.
    4. Mencari nilai hash yang sama antara 2 teks.
    5. Menentukan persamaan 2 buah teks dengan persamaan Dice's Similarity Coefficient.

CONTOH PROGRAM dapat dilihat disini