Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth Morris Pratt (KMP) dikembangkan oleh D. E. Knuth, bersama dengan J. H. Morris dan V. R. Pratt. Untuk pencarian string dengan algoritma Brute Force , setiap kali ditemukan ketidakcocokan dengan teks, maka pattern akan digeser satu karakter ke kanan. Berbeda dengan algoritma Brute Force, informasi yang digunakan masih dipelihara untuk melakukan jumlah pergeseran. Algoritma menggunakan informasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter Perbandingan antara algoritma brute force dengan algoritma KMP ditunjukkan dengan perpindahan posisi pattern terhadap posisi teks. Dimana dalam hal pencocokan string, pattern yang dicocokkan berawal dari kiri teks.

Kompleksitas algoritma pencocokan string dihitung dari jumlah operasi perbandingan yang dilakukan. Kompleksitas waktu terbaik dari algoritma brute force adalah O(n). Kasus terbaik terjadi jika pada operasi perbandingan, setiap huruf pattern yang dicocokkan dengan awal dari teks adalah sama. Kompleksitas waktu terburuk dari brute force adalah O(mn).

Jika dibandingkan dengan algoritma brute force, maka algoritma KMP mempunyai kompleksitas algoritma O(m+n). Definisi yang digunakan, Y adalah suatu alfabet dan

Z_ = Z_1 Z_1  Z_3… Z_k, k Є N,

adalah string dengan panjang k, yang dibentuk dari karakter di alfabet di dalam alfabet A. Awalan prefix dari z adalah upa-string w, dengan

w =Z_(k-b),Z_(k-b+1)… Z_k, k Є {1, 2, .., k-1}

Pinggiran dari z adalah substring r, sehingga

               r =Z_1 Z_1  Z_3… Z_k, dan r = Z_(k-b),Z_(k-b+1)… Z_k, k Є {1, 2, .., k-1}

 

Algoritma KMP melakukan proses awal terhadap pattern dengan menghitung fungsi pinggiran Dengan adanya fungsi pinggiran ini, maka dapat dicegah pergeseran yang tidak berguna, seperti yang terjadi pada algoritma brute force. Fungsi pinggiran hanya bergantung pada karakter yang ada di dalam pattern, tidak bergantung kepada karakter di dalam teks. Berikut adalah algoritma untuk mencari fungsi pinggiran di dalam pattern.

A.      Procedure Perhitungan Pinggiran Algoritma KMP

A.      Procedure Algoritma KMP

 Sumber :

Eko Gunocipto Hartoyo, Yus Gias Vembrina, and Anggia Ferdina Meilana, “Analisis Algoritma Pencarian String (String Matching),” in www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik10.pdf, Departemen Teknik Informatika, Institut Teknologi Bandung, Bandung, 2007

 Download Paper