# Hack Your Skills! to be Professional Mechatronics
Jika ada masukan dan saran, silakan isi di komentar ya... :)
Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP
ElangSakti
Algorithm
,
Algoritma KMP
,
Informatika
,
Knuth-Morris-Pratt
,
PHP
,
Scrap of Scripts
11 komentar
Pre Note: Kadang Algoritma Knuth-Morris-Pratt ini dijadikan tugas akhir untuk pencarian kata dalam teks / artikel, list kata biasanya ada dalam database atau berdasarkan pencarian, atau ada ide lain? hehe. :)
Algoritma Knuth-Morris-Pratt merupakan salah satu algoritma pencarian string (string matcing) yang dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, namun keduanya mempublikasikannya secara bersamaan pada tahun 1977 (Wikipedia : Knuth-Morris-Pratt). Langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string yaitu (modifikasi):
- String pattern (kata yang dicari) akan dipecah menjadi array karakter
- String text (teks, artikel, dsb) akan dipecah menjadi array karakter
- Menentukan lompatan yang akan dilakukan ketika pencarian (funsi preKMP())
- Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks. ()
- Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
- Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
- Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
- Algoritma kemudian menggeser pattern berdasarkan tabel next (lompat), lalu mengulangi langkah 2 sampai pattern berada di ujung teks.
Script di bawah ini merupakan core (inti) dari algoritma Knuth-Morris-Pratt dalam kode PHP. Jadi untuk penggunaan dan implementasinya kita bahas pada artikel berikutnya. :). (Update: kelas PHP ini sudah mengalami modifikasi, silakan kunjungi PHP : Modifikasi Class Algoritma KMP Untuk Replace String)
<?php // Knuth-Morris-Pratt Algorithm // Created March 31, 2010 - 07:10:33 WIB // Modified March 13, 2013 - 09:39:31 WIB // x90 class KMP{ function KMPSearch($p,$t){ $hasil = array(); // pattern dan text dijadikan array $pattern = str_split($p); $text = str_split($t); // hitung tabel lompatan dengan preKMP() $lompat = $this->preKMP($pattern); print_r($lompat); // perhitungan KMP $i = $j = 0; $num=0; while($j<count($text)){ while($i>-1 && $pattern[$i]!=$text[$j]){ // jika tidak cocok, maka lompat sesuai tabel lompatan $i = $lompat[$i]; } $i++; $j++; if($i>=count($pattern)){ // jika cocok, tentukan posisi string yang cocok // kemudian lompat ke string berikutnya $hasil[$num++]=$j-count($pattern); $i = $lompat[$i]; } } return $hasil; } // menetukan tabel lompatan dengan preKMP function preKMP($pattern){ $i = 0; $j = $lompat[0] = -1; while($i<count($pattern)){ while($j>-1 && $pattern[$i]!=$pattern[$j]){ $j = $lompat[$j]; } $i++; $j++; if($pattern[$i]==$pattern[$j]){ $lompat[$i]=$lompat[$j]; }else{ $lompat[$i]=$j; } } return $lompat; } } ?>
Jika ada masukan dan saran, silakan isi di komentar ya... :)
Top Artikel :
Written by ElangSakti
Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP
Bahasan: Pre Note: Kadang Algoritma Knuth-Morris-Pratt ini dijadikan tugas akhir untuk pencarian kata dalam teks / artikel, list kata biasanya ada...
Published at Rabu, 13 Maret 2013, Updated at Rabu, 13 Maret 2013
Reviewed by dr. on
Rating: 4.7
Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP
Bahasan: Pre Note: Kadang Algoritma Knuth-Morris-Pratt ini dijadikan tugas akhir untuk pencarian kata dalam teks / artikel, list kata biasanya ada...
Published at Rabu, 13 Maret 2013, Updated at Rabu, 13 Maret 2013
Reviewed by dr. on
Rating: 4.7
Langganan:
Posting Komentar
(
Atom
)
mas saya mau bertanya apakah algoritma KMP ini bisa digunakan untuk mengubah kata yg mengandung kombinasi angka dan huruf menjadi kata yang full huruf..
BalasHapuscontoh : P4d4
menjadi : Pada
A ibarat menjadi 4
bisa mas.. coba cek beberapa posting sebelumnya, semoga manfaat.. :)
Hapusmakasih penjelasannya Mas, sungguh membantu, cuma saya mau tanya kira2 algoritma ini bisa dimodifikasi buat mentolerir kesalahan penulisan kata gak?
BalasHapuscontoh:Indonesia yg tertulis Indonesa
bisa mas, pemeriksaannya nanti harus dicocokkan dengan database/kamus kata.. seperti suggestion
Hapusmas, boleh dibantu untuk code pencocokan nya?
Hapusalgoritma pencocokan string dengan php untuk algoritma boyer moore ada gak mas...
BalasHapusmohon share untuk tugas kuliah.
ada mas, tapi belum dibahas di blog ini.. :)
Hapusmas algoritma brute force untuk pencocokan string mohon dibahas dunk di webnya..
BalasHapusbelajar sendiri broo
Hapusmas, algoritma boyer moore dong mas
BalasHapusmas, kalau di buat aplikasi pencarian gimana ? ec : pencarian judul
BalasHapus