Share to: share facebook share twitter share wa share telegram print page

Algoritma Knuth-Morris-Pratt

Algoritme Knuth-Morris-Pratt adalah salah satu algoritme pencarian string, dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, tetapi keduanya mempublikasikannya secara bersamaan pada tahun 1977.

Jika kita melihat algoritme 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.[1]

Cara kerja

Perhitungan penggeseran pada algoritme ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan , kita bisa menganggap ketidakcocokan pertama terjadi di antara dan , dengan . Berarti, dan tidak sama dengan . Ketika kita menggeser, sangat beralasan bila ada sebuah awalan dari pattern akan sama dengan sebagian akhiran dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan tersebut sejajar dengan akhiran dari .

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- dari pattern. Tabel itu harus memuat yang merupakan posisi karakter setelah digeser, sehingga kita bisa menggeser pattern sebesar relatif terhadap teks.[2]

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

  1. Algoritme Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.
  2. Dari kiri ke kanan, algoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
    1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
    2. Semua karakter di pattern cocok. Kemudian algoritme akan memberitahukan penemuan di posisi ini.
  3. Algoritme kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

Pseudocode

Berikut adalah pseudocode algoritme KMP pada fase pra-pencarian:

procedure preKMP(
    input P: array[0..n-1] of char,
    input n: integer,
    input/output kmpNext: array[0..n] of integer
)
Deklarasi:
i,j: integer

Algoritme
  i:= 0;
  j:= kmpNext[0]:= -1;
  while (i < n) {
     while (j > -1 and not(P[i] = P[j]))
        j:= kmpNext[j];
     i:= i+1;
     j:= j+1;
     if (P[i] = P[j])
        kmpNext[i]:= kmpNext[j];
     else
        kmpNext[i]:= j;
     endif
  endwhile

Dan berikut adalah pseudocode algoritme KMP pada fase pencarian:

procedure KMPSearch(
    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
)

Deklarasi:
i, j,next: integer 
kmpNext: array[0..n] of interger

Algoritme:
preKMP(n, P, kmpNext) 
i:=0
while (i<= m-n) do
    j:=0
    while (j < n and T[i+j] = P[j]) do 
       j:=j+1
    endwhile
    if(j >= n) then
       ketemu[i]:=true;
    endif
    next:= j - kmpNext[j]
    i:= i+next
endwhile

Kompleksitas

Algoritme ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritme 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

Referensi

  1. ^ (Inggris)Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5
  2. ^ (Inggris) Knuth, Donald E. Morris, James H. Pratt, Vaughan R. 1977. Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6 No.2.

Lihat pula

Pranala luar

Baca informasi lainnya yang berhubungan dengan : Algoritma Knuth Morris Pratt

Algoritma Algoritma greedy Algoritma Euklides Algoritma ekspektasi-maksimisasi Algoritma C4.5 Algoritma terdistribusi Algoritma Lanczos Algoritma Frank–Wolfe Algoritma Berlekamp–Rabin Hill climbing (algoritma) Algoritma Elgamal Algoritma kunang-kunang Algoritma semut Algoritma SPIKE Metode ensemble Konjektur Collatz Algoritma genetik Algoritma Dijkstra Algoritma Prim Algoritma Hungaria Algoritma penyortiran Algoritma Ostrich Algoritma gabung Algoritma Bellman–Ford Algoritma Strassen Algoritma Floyd-Warshall Algoritma perambatan mundur Algoritma Perambatan Maju Algoritma Boyer-Moore Algor…

itma Gauss-Newton Algoritma pencari-siklus Floyd Algoritma Knuth-Morris-Pratt Algoritma dekker Algoritma seleksi Algoritma pencarian Algoritma RC4 Algoritma pencarian string Algoritma a-star Algoritma penggantian halaman Algoritma pencarian biner Daftar algoritme Algoritme Floyd–Steinberg Algoritma Kata Sandi Sekali-pakai berbasis Waktu Algoritme k tetangga terdekat Sandi Vigenère

Kembali kehalaman sebelumnya