際際滷

際際滷Share a Scribd company logo

Algoritma Knuth-Morris-Pratt

Download as PPTX, PDF
Fajar Sany
Fajar Sany

Tugas mata kuliah Algoritma dan Pemrograman semasa semester-II di Politeknik TEDC Bandung.

1 of 11
Downloaded 127 times
MUHAMMAD FAJAR SAID (TK 101021) TEKNIK KOMPUTER DAN INFORMATIKA D-3 SEMESTER-2 / 2010-2011 POLITEKNIK TEDC BANDUNG TUGAS MATA KULIAH ALGORITMA
Algoritma Knuth-Morris-Prath (KMP) adalah salah satu algoritma pencarian string, dikembangkan secara terpisah oleh James H. Morris bersama Vaughan R. Pratt pada tahun 1966, dan oleh Donald E. Knuth pada tahun 1967. Namun keduanya mempublikasikan secara bersamaan pada tahun 1977. Algoritma pencarian string lainnya yang terkenal yaitu algoritma Brute Force, Boyer-Moore dan Aho-Corasick. Namun dalam presentasi ini akan dijelaskan tentang algoritma Knuth-Morris-Prath saja.
Persoalan pencarian string dirumuskan sebagai berikut: 1. Sebuah teks (text), yaitu sebuah (long) string yang panjangnya n karakter. 2. Pattern, yaitu sebuah string dengan panjang m karakter (m<n) yang akan dicari dalam teks. Cari lokasi pertama di dalam teks yang bersesuaian dengan pattern. Aplikasi permasalahan pencocokan string biasa ditemukan dalam pencarian sebuah kata dalam dokumen (misalnya menu Find dalam Microsoft Word). Contoh: Pattern: formasi Teks : info inform diinformasikan Dalam algoritma pencarian string, teks diasumsikan berada di dalam memori, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu dibaca terlebih dahulu, kemudian disimpan di dalam memori. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern ditemukan pertama kali.
Algoritma Knuth-Morris-Pratt
Mula-mula pattern dan teks sejajar pada posisi paling kiri, dan dibandingkan karakter pertamanya. Langkah 1 dan 2 sama dengan algoritma Brute Force. Pada langkah 3, ketidakcocokan terjadi saat membandingkan karakter ke-3 dari pattern (R) dan karakter ke-5 dari teks (spasi). Metode KMP akan memeriksa apakah pada teks yang dilewati pada langkah ini (yaitu F-O-spasi) terdapat karakter awal pattern (yaitu F), dan ternyata cocok di karakter pertama yang sudah dibandingkan pada langkah ini. Karena itu tidak perlu menggeser pattern satu per satu, pattern dapat langsung digeser sejauh 3 karakter pada langkah selanjutnya (langkah 4). Kasus yang sama ditemui lagi pada langkah 6, di mana pattern dapat digeser sejauh 5 karakter ke kanan pada langkah 7. Demikian seterusnya, hingga pada akhirnya hanya diperlukan 11 langkah untuk menemukan pattern pada teks.
Algoritma Knuth-Morris-Pratt
Kata pertama yang diminta adalah kata ATRIUM, dengan menggunakan algoritma pencocokan string, kata tersebut akan dicari pada baris pertama, jika tidak ditemukan, pencarian dilanjutkan dengan baris kedua, dan jika tidak ditemukan juga, pencarian akan dilanjutkan pada baris-baris selanjutnya, dan jika pada baris tidak ditemukan, pencarian dilanjutkan pada setiap kolom. Jika kata ATRIUM telah ditemukan, kata berikutnya yaitu BLUEWHITE akan dicari pada papan permainan dengan cara yang sama. Setiap setelah kata yang diminta ditemukan pada kumpulan karakter di papan permainan, pencarian akan dilanjutkan untuk katakata berikutnya. Pada permainan ini, yang didefinisikan sebagai pattern adalah katakata yang diminta oleh program (yang terletak pada bagian kanan dari tampilan permainan), sedangkan yang didefinisikan sebagai teks adalah kumpulan karakter-karakter pada setiap baris atau kolomnya. Algoritma yang lebih baik digunakan pada proses pencarian solusi dari permainan ini adalah algoritma Knuth-Morris-Pratt. Dengan menggunakan loop pencarian tiap baris dan kolom.
procedure KMPsearch(input m, n:integer, input P: array[1..m]of char, input T: array[1..n] of char, output idx: integer) {Mencari kecocokan pattern P di dalam teks T dengan algoritma Knuth-MorrisPratt. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx. Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasikan sebagai string [array of character] Keluaran: posisi awal kecocokan [idx]. Jika P tidak ditemukan, idx=-1.} Deklarasi i,j: integer ketemu: boolean b: array[1..m] of integer procedure HitungPinggiran(input m: integer, P: array[1..m] of char, output b: array[1..m] of integer) {menghitung nilai b[1..m] untuk pattern P[1..m]} Algoritma for ((setiap baris) and (not ketemu)) HitungPinggiran(m,P,b) j 0 i 1 ketemu false while (i n and not ketemu) do while((j>0) and (P[j+1]T[i]))do j b[j] endwhile
if P[j+1]=T[i] then j j+1 endif if j= m then ketemu true else i i+1 endif endwhile if ketemu then idx i-m+1 {catatan: jika indeks array dimulai dari 0, maka idx else idx -1 endif endfor if (not ketemu) for ((setiap kolom) and (not ketemu)) {lakukan yang sama seperti pada baris} endfor endif i-m}
PC Media (04/2010), Konsep Pencarian String. Wikipedia. 2011, Algoritma Knuth-Morris-Pratt. http://id.wikipedia.org/wiki/Algoritma_Knuth-Morris-Pratt Desi Hadiati, Penerapan Algoritma String Matching Pada Permainan Word Search Puzzle, Program Studi Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung, Bandung, 2007.
Algoritma Knuth-Morris-Pratt

More Related Content

Algoritma Knuth-Morris-Pratt

  • 1. MUHAMMAD FAJAR SAID (TK 101021) TEKNIK KOMPUTER DAN INFORMATIKA D-3 SEMESTER-2 / 2010-2011 POLITEKNIK TEDC BANDUNG TUGAS MATA KULIAH ALGORITMA
  • 2. Algoritma Knuth-Morris-Prath (KMP) adalah salah satu algoritma pencarian string, dikembangkan secara terpisah oleh James H. Morris bersama Vaughan R. Pratt pada tahun 1966, dan oleh Donald E. Knuth pada tahun 1967. Namun keduanya mempublikasikan secara bersamaan pada tahun 1977. Algoritma pencarian string lainnya yang terkenal yaitu algoritma Brute Force, Boyer-Moore dan Aho-Corasick. Namun dalam presentasi ini akan dijelaskan tentang algoritma Knuth-Morris-Prath saja.
  • 3. Persoalan pencarian string dirumuskan sebagai berikut: 1. Sebuah teks (text), yaitu sebuah (long) string yang panjangnya n karakter. 2. Pattern, yaitu sebuah string dengan panjang m karakter (m<n) yang akan dicari dalam teks. Cari lokasi pertama di dalam teks yang bersesuaian dengan pattern. Aplikasi permasalahan pencocokan string biasa ditemukan dalam pencarian sebuah kata dalam dokumen (misalnya menu Find dalam Microsoft Word). Contoh: Pattern: formasi Teks : info inform diinformasikan Dalam algoritma pencarian string, teks diasumsikan berada di dalam memori, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu dibaca terlebih dahulu, kemudian disimpan di dalam memori. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern ditemukan pertama kali.
  • 5. Mula-mula pattern dan teks sejajar pada posisi paling kiri, dan dibandingkan karakter pertamanya. Langkah 1 dan 2 sama dengan algoritma Brute Force. Pada langkah 3, ketidakcocokan terjadi saat membandingkan karakter ke-3 dari pattern (R) dan karakter ke-5 dari teks (spasi). Metode KMP akan memeriksa apakah pada teks yang dilewati pada langkah ini (yaitu F-O-spasi) terdapat karakter awal pattern (yaitu F), dan ternyata cocok di karakter pertama yang sudah dibandingkan pada langkah ini. Karena itu tidak perlu menggeser pattern satu per satu, pattern dapat langsung digeser sejauh 3 karakter pada langkah selanjutnya (langkah 4). Kasus yang sama ditemui lagi pada langkah 6, di mana pattern dapat digeser sejauh 5 karakter ke kanan pada langkah 7. Demikian seterusnya, hingga pada akhirnya hanya diperlukan 11 langkah untuk menemukan pattern pada teks.
  • 7. Kata pertama yang diminta adalah kata ATRIUM, dengan menggunakan algoritma pencocokan string, kata tersebut akan dicari pada baris pertama, jika tidak ditemukan, pencarian dilanjutkan dengan baris kedua, dan jika tidak ditemukan juga, pencarian akan dilanjutkan pada baris-baris selanjutnya, dan jika pada baris tidak ditemukan, pencarian dilanjutkan pada setiap kolom. Jika kata ATRIUM telah ditemukan, kata berikutnya yaitu BLUEWHITE akan dicari pada papan permainan dengan cara yang sama. Setiap setelah kata yang diminta ditemukan pada kumpulan karakter di papan permainan, pencarian akan dilanjutkan untuk katakata berikutnya. Pada permainan ini, yang didefinisikan sebagai pattern adalah katakata yang diminta oleh program (yang terletak pada bagian kanan dari tampilan permainan), sedangkan yang didefinisikan sebagai teks adalah kumpulan karakter-karakter pada setiap baris atau kolomnya. Algoritma yang lebih baik digunakan pada proses pencarian solusi dari permainan ini adalah algoritma Knuth-Morris-Pratt. Dengan menggunakan loop pencarian tiap baris dan kolom.
  • 8. procedure KMPsearch(input m, n:integer, input P: array[1..m]of char, input T: array[1..n] of char, output idx: integer) {Mencari kecocokan pattern P di dalam teks T dengan algoritma Knuth-MorrisPratt. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx. Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasikan sebagai string [array of character] Keluaran: posisi awal kecocokan [idx]. Jika P tidak ditemukan, idx=-1.} Deklarasi i,j: integer ketemu: boolean b: array[1..m] of integer procedure HitungPinggiran(input m: integer, P: array[1..m] of char, output b: array[1..m] of integer) {menghitung nilai b[1..m] untuk pattern P[1..m]} Algoritma for ((setiap baris) and (not ketemu)) HitungPinggiran(m,P,b) j 0 i 1 ketemu false while (i n and not ketemu) do while((j>0) and (P[j+1]T[i]))do j b[j] endwhile
  • 9. if P[j+1]=T[i] then j j+1 endif if j= m then ketemu true else i i+1 endif endwhile if ketemu then idx i-m+1 {catatan: jika indeks array dimulai dari 0, maka idx else idx -1 endif endfor if (not ketemu) for ((setiap kolom) and (not ketemu)) {lakukan yang sama seperti pada baris} endfor endif i-m}
  • 10. PC Media (04/2010), Konsep Pencarian String. Wikipedia. 2011, Algoritma Knuth-Morris-Pratt. http://id.wikipedia.org/wiki/Algoritma_Knuth-Morris-Pratt Desi Hadiati, Penerapan Algoritma String Matching Pada Permainan Word Search Puzzle, Program Studi Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung, Bandung, 2007.