Algoritma Knuth-Morris-Pratt: Perbedaan antara revisi

'''AlgoritmaAlgoritme Knuth-Morris-Pratt''' adalah salah satu [[algoritmaalgoritme pencarian string]], dikembangkan secara terpisah oleh [[Donald Knuth|Donald E. Knuth]] pada tahun 1967 dan [[James Morris|James H. Morris]] bersama [[Vaughan Pratt|Vaughan R. Pratt]] pada tahun 1966, namuntetapi keduanya mempublikasikannya secara bersamaan pada tahun 1977.

Jika kita melihat [[AlgoritmaAlgoritme pencarian string#AlgoritmaAlgoritme brute force dalam pencarian string|algoritmaalgoritme brute force]] lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.<ref>{{en}}Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref>

Perhitungan penggeseran pada algoritmaalgoritme ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan <math>teks[i..i+n-1]</math>, kita bisa menganggap ketidakcocokan pertama terjadi diantaradi antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i..i+j-1] = pattern[0..j-1]</math> dan <math>a=teks[i+j]</math> tidak sama dengan <math>b=pattern[j]</math>. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan <math>v</math> dari pattern akan sama dengan sebagian akhiran <math>u</math> dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan <math>v</math> tersebut sejajar dengan akhiran dari <math>u</math>.

Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke-<math>j</math> dari pattern. Tabel itu harus memuat <math>next[j]</math> yang merupakan posisi karakter <math>pattern[j]</math> setelah digeser, sehingga kita bisa menggeser pattern sebesar <math>j-next[j]</math> relatif terhadap teks.<ref>{{en}} Knuth, Donald E. Morris, James H. Pratt, Vaughan R. 1977. Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6 No.2. </ref>

Secara sistematis, langkah-langkah yang dilakukan algoritmaalgoritme Knuth-Morris-Pratt pada saat mencocokkan string:

# AlgoritmaAlgoritme Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.

# Dari kiri ke kanan, algoritmaalgoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

## Semua karakter di pattern cocok. Kemudian algoritmaalgoritme akan memberitahukan penemuan di posisi ini.

# AlgoritmaAlgoritme kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

Berikut adalah pseudocode algoritmaalgoritme KMP pada fase pra-pencarian:

input P : array[0..n-1] of char,

input n : integer,

input/output kmpNext : array[0..n] of integer

i := 0;

j := kmpNext[0] := -1;

j := kmpNext[j];

kmpNext[i] := kmpNext[j];

kmpNext[i] := j;

Dan berikut adalah pseudocode algoritmaalgoritme KMP pada fase pencarian:

input m, n : integer,

input P : array[0..n-1] of char,

input T : array[0..m-1] of char,

output ketemu : array[0..m-1] of boolean

kmpNext : array[0..n] of interger

AlgoritmaAlgoritme ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). AlgoritmaAlgoritme ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet

* [[Daftar algoritmaalgoritme]]

* [[AlgoritmaAlgoritme pencarian string]]

* [[AlgoritmaAlgoritme Boyer-Moore]]

* [http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Halaman berisi penjelasan tentang algoritmaalgoritme Knuth-Morris-Pratt dan juga sebuah applet yang menganimasikan cara kerjanya]

[[Kategori:AlgoritmaAlgoritme pencarianstring]]