Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP

8 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):
  1. String pattern (kata yang dicari) akan dipecah menjadi array karakter
  2. String text (teks, artikel, dsb) akan dipecah menjadi array karakter
  3. Menentukan lompatan yang akan dilakukan ketika pencarian (funsi preKMP())
  4. Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks. ()
  5. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
  6. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
  7. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
  8. 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... :)


Written by Hari Santoso
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

8 komentar :

  1. mas saya mau bertanya apakah algoritma KMP ini bisa digunakan untuk mengubah kata yg mengandung kombinasi angka dan huruf menjadi kata yang full huruf..
    contoh : P4d4
    menjadi : Pada
    A ibarat menjadi 4

    BalasHapus
    Balasan
    1. bisa mas.. coba cek beberapa posting sebelumnya, semoga manfaat.. :)

      Hapus
  2. makasih penjelasannya Mas, sungguh membantu, cuma saya mau tanya kira2 algoritma ini bisa dimodifikasi buat mentolerir kesalahan penulisan kata gak?
    contoh:Indonesia yg tertulis Indonesa

    BalasHapus
    Balasan
    1. bisa mas, pemeriksaannya nanti harus dicocokkan dengan database/kamus kata.. seperti suggestion

      Hapus
  3. algoritma pencocokan string dengan php untuk algoritma boyer moore ada gak mas...
    mohon share untuk tugas kuliah.

    BalasHapus
    Balasan
    1. ada mas, tapi belum dibahas di blog ini.. :)

      Hapus
  4. mas algoritma brute force untuk pencocokan string mohon dibahas dunk di webnya..

    BalasHapus
  5. mas, algoritma boyer moore dong mas

    BalasHapus