Implementasi Algoritma String Matching Knuth-Morris-Pratt MenggunakanPHP (1) - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

Implementasi Algoritma String Matching Knuth-Morris-Pratt MenggunakanPHP (1)

34 komentar
Mari kita bahas tentang pencarian kata pada suatu artikel. Kronologisnya adalah, kita mencari suatu kata pada artikel kemudian menghitung seberapa sering kata itu muncul dan menandainya dengan perubahan warna pada kata tersebut. Aplikasi ini bisa dipakai untuk menganalisa gaya bahasa seseorang berdasarkan kompleksitas dan keragaman kata dalam tulisan yang dia buat.

Untuk metode pencariannya yaitu menggunakan Knuth-Morris-Pratt, saya harap kita sudah menengoknya pada pada artikel sebelumnya, Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP. Tulisan tersebut berisi source code PHP sebagai core class atau kelas utama algoritma pencocokan string (string matching) yang akan kita bahas kali ini. Baik, berikut langkah-langkah yang akan kita lakukan:
1. Buat database yang berisi artikel. Biar seragam, kita buat tabel seperti di bawah.
2. Buat halaman pencarian untuk menampilkan artikel
3. Proses pencarian dan hasil

Eksekusi perintah SQL berikut untuk membuat database dan tabel
CREATE DATABASE /*!32312 IF NOT EXISTS*/`web` /*!40100 DEFAULT CHARACTER SET latin1 */;

USE `web`;

/*Table structure for table `artikel` */

DROP TABLE IF EXISTS `artikel`;

CREATE TABLE `artikel` (
  `id_artikel` int(11) NOT NULL,
  `judul` varchar(1024) DEFAULT NULL,
  `isi` text,
  PRIMARY KEY (`id_artikel`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

/*Data for the table `artikel` */

insert  into `artikel`(`id_artikel`,`judul`,`isi`) values (1,'Bahasa Sanskerta','Bahasa Sanskerta (ejaan tidak baku: \"Sansekerta\") adalah salah satu bahasa Indo-Eropa paling tua yang masih dikenal dan sejarahnya termasuk yang terpanjang. Bahasa yang bisa menandingi \'usia\' bahasa ini dari rumpun bahasa Indo-Eropa hanya bahasa Het. Kata Sanskerta, dalam bahasa Sanskerta Sa?sk?tabh?sa artinya adalah bahasa yang sempurna. Maksudnya, lawan dari bahasa Prakerta, atau bahasa rakyat.\r\n\r\nBahasa Sanskerta merupakan sebuah bahasa klasik India, sebuah bahasa liturgis dalam agama Hindu, Buddhisme, dan Jainisme dan salah satu dari 23 bahasa resmi India. Bahasa ini juga memiliki status yang sama di Nepal.\r\n\r\nPosisinya dalam kebudayaan Asia Selatan dan Asia Tenggara mirip dengan posisi bahasa Latin dan Yunani di Eropa. Bahasa Sanskerta berkembang menjadi banyak bahasa-bahasa modern di anakbenua India. Bahasa ini muncul dalam bentuk pra-klasik sebagai bahasa Weda. Yang terkandung dalam kitab Rgweda merupakan fase yang tertua dan paling arkhais. Teks ini ditarikhkan berasal dari kurang lebih 1700 SM dan bahasa Sanskerta Weda adalah bahasa Indo-Arya yang paling tua ditemui dan salah satu anggota rumpun bahasa Indo-Eropa yang tertua.\r\n\r\nKhazanah sastra Sanskerta mencakup puisi yang memiliki sebuah tradisi yang kaya, drama dan juga teks-teks ilmiah, teknis, falsafi, dan agamis. Saat ini bahasa Sanskerta masih tetap dipakai secara luas sebagai sebuah bahasa seremonial pada upacara-upacara Hindu dalam bentuk stotra dan mantra. Bahasa Sanskerta yang diucapkan masih dipakai pada beberapa lembaga tradisional di India dan bahkan ada beberapa usaha untuk menghidupkan kembali bahasa Sanskerta.');

/*!40101 SET SQL_MODE=@OLD_SQL_MODE */;
/*!40014 SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS */;

Kode untuk halaman pencarian kata dalam PHP dan HTML
<?php
$c  = mysql_connect("localhost", "root", "");
$db = mysql_selectdb("web", $c);

if(!$db){
    echo "Purcase DB! :p";
    exit();
}

include_once("kmp.php");
$kata = '';
if(isset($_GET['kata']))
  $kata = $_GET['kata'];

?>
<div style="width:600px;">
<form method="get" action="">
Cari Kata : <input type="text" name="kata" value="<?php echo $kata; ?>" /> <input type="submit" value="Cari">
</form>
</div>
<?php
$KMP = new KMP();

$art = mysql_query("select * from artikel");
while($teks = mysql_fetch_array($art)){

  if($kata!=''){
    $hasil = $KMP->KMPSearch($kata,$teks['isi']);
 echo "Kata yang dicari adalah : ".$kata."<br/>";
 echo "Jumlah kata yang ditemukan : ".count($hasil)."<br/>";
 echo "Yaitu pada posisi string ke : ";
 foreach($hasil as $h) echo $h." ";
 echo "<br/>";
  }
  echo "<div style='width:600px;'>";
  echo "<h3>".$teks['judul']."</h3><hr/>";
  echo nl2br(str_replace($kata,"<font color='red'>".$kata."</font>",$teks['isi']));
  echo "</div>";
}
?>

Hasil pencarian

Implementasi Algoritma String Matching Knuth-Morris-Pratt MenggunakanPHP


Untuk yang mau berdiskusi saya persilakan untuk mengisi komentar... :)

Written by ElangSakti
Implementasi Algoritma String Matching Knuth-Morris-Pratt MenggunakanPHP (1)
Bahasan: Mari kita bahas tentang pencarian kata pada suatu artikel. Kronologisnya adalah, kita mencari suatu kata pada artikel kemudian menghitung ...
Published at Kamis, 14 Maret 2013, Updated at Kamis, 14 Maret 2013
Reviewed by dr. on
Rating: 4.7

34 komentar :

  1. Terima kasih atas artikelnya mas, sangat membantu untuk penyelesaian tugas.hehe..
    Mo nanya, programnya mash ada muncul tulisan "Notice: Undefined offset: 4" kadang2 "Notice: Undefined offset: 6" itu kenapa ya mas..nubie nii..thx

    BalasHapus
  2. Thanks sudah mampir :)
    Untuk penjelasan tentang error tersebut, bisa cek di http://www.elangsakti.com/2013/04/solusi-peringatan-notice-undefined-offset-n-pada-php/

    Untuk script kmp.php yang baru bisa cek di http://www.elangsakti.com/2013/04/modifikasi-core-algoritma-knuth-morris-pratt-pada-kmp-php/

    Semoga membantu .. :)

    BalasHapus
  3. makasih atas artikelnya, cukup memberi pencerahan....

    klo bisa tanya, bagaimana implementasi klo menggunakan algoritma string matcing boyer-moore...

    BalasHapus
  4. mz, aku tanya tabel kmpNext mz.. aq smpe skr blm fham menentukan nilai untuk tabel kmpNext.. thanks mz sebelumnya

    BalasHapus
  5. KMP ini merupakan pengembangan dari booyer moore, jadi tinggal modifikasi saja.. :)

    BalasHapus
  6. mas klo algoritma bawaan dari KMPnya sndri emang bisa dipake buat nyari kata yang lebih dari 1 kata misal search "saya makan"
    trims
    XD

    BalasHapus
  7. Ndak bisa, kalo dari KMP itu dianggap satu kata. Jadi kalo pengen dianggap dua kata, kita pecah saja berdasarkan spasi. Misal:

    $search = 'saya makan';
    $kata = explode(' ',$search); // <== explode('spasi',$search)
    foreach($kata as $kata){
    //KMPSearch() di sini...
    }

    BalasHapus
  8. membantu sekali gan postingan ini, terima kasih. Tapi saya uda coba berulang kali otak atik untuk mencari total jumlah kata yang cocok dalam database. seperti ini

    if($hasil<5) <== $hasil adalah jumlah kata yang cocok dari rumus KMP
    {
    //file diijinkan untuk diupload
    }
    elseif(hasil>=5)
    {
    //data ditolak
    }

    selalu muncul angka 0

    BalasHapus
    Balasan
    1. boleh tahu script sebelumnya mas dvein?
      kalau misal keberatan posting script di sini, monggo diskusi lewat email saja. :)

      Hapus
    2. http://stackoverflow.com/questions/37288986/get-the-result-number-inside-foreach-and-while

      saya sudah sempat post di web atas, bisa dicek gan kalo sempat.

      Hapus
    3. mas dvein bisa cek di baris :

      $result = $KMP->KMPSearch($word,$text['$abstract']);

      pada $text['$abstract'], sepertinya tidak perlua $, jadi coba ganti dengan $text['abstract']

      Hapus
    4. sudah saya ganti gan, masih blum ada perkembangan. mungkin yang salah di logika ambil variabel angka tersebut, yang terakhir saya coba :

      echo count($result);
      jika didalam foreach dan while berhasil muncul output = 1
      (semestinya lebih dari 1 karena saya menginput 5 kata yang mirip dengan abstrak di dalam database)

      jika saya taruh echo tersebut diluar foreach dan while muncul output = 0

      nah jika sudah dapat angka tersebut saya mau taruh di kondisi if tadi supaya bisa membatalkan upload jika kata - kata yang cocok melebihi dari 5

      ada pencerahan?

      Hapus
    5. sudah coba cara yang begini?

      $total = 0;
      $b= mysqli_query("select * from my_table");
      while($text = mysqli_fetch_array($b)){
      ...
      ...
      $result = $KMP->KMPSearch($word,$text['abstract']);
      $total = count($result);
      ...
      ...
      }

      echo $total;

      Hapus
    6. itu variabel totalnya diletakkan di luar foreach..

      Hapus
    7. if (isset($_POST['upload']))
      {
      include_once("kmp.php");

      $kata = explode(' ',$desc_jurnal); // <== explode('spasi',$search)
      foreach($kata as $kata){

      $total = 0;
      $KMP = new KMP();

      $b= mysql_query("select * from jurnal_tampil");
      while($teks = mysql_fetch_array($b)){

      if($kata!=''){
      $hasil = $KMP->KMPSearch($kata,$teks['desc_jurnal']);
      echo "Kata yang dicari adalah : ".$kata."
      ";
      echo "Jumlah kata yang ditemukan : ".count($hasil)."
      ";
      echo "Yaitu pada posisi string ke : ";
      $total = count($hasil);
      foreach($hasil as $h) echo $h." ";
      echo "
      ";

      }


      }

      }

      echo $total;
      }

      itu code setelah saya sambung ke database yang mau dicocokkan. dan outputnya sama masih 0 gan

      kalo agan sempet coba mampir ke web ini http://jurnalonline.esy.es/showbox/
      register atau login id ini:
      id:sule
      pass:12345

      lalu klik kirim jurnal, input deksripsi jurnalnya lalu klik upload nanti ada hasil output pencarian KMP dan angka 0 tersebut ada di paling bawah

      Hapus
    8. Mungkin lebih tepatnya dibuat begini:

      if (isset($_POST['upload'])){
      $total = 0;
      ...
      foreach($kata as $kata){
      ...
      $hasil = $KMP->KMPSearch($kata,$teks['desc_jurnal']);
      $total += count($hasil);
      ...
      }
      ...
      echo $total;
      }

      Hapus
    9. jika dengan struktur di atas masih belum solved juga, coba berikan contoh string yang diinputkan.

      Hapus
    10. rumus += berhasil gan hasil output $total = 2, meskipun total angka hasil pencarian kata terhadap database = 8 (ada 8 jurnal dan angka 8 saya hitung secara manual). terima kasih, nanti saya coba utak atik jika berhasil saya posting di komentar lagi.

      Hapus
    11. Mas @dvein, saya juga mempunyai kasus seperti punya mas. Boleh minta code fixnya Mas?

      Hapus
    12. saya udah nyoba yg make rumus +=, tapi hasil kata yg sama cuma satu mas, padahal jumlah kata didatabase yg sama dg kata yg saya input = 3. Gimana caranya benerinnya mas?

      Hapus
    13. boleh dikasi liat script dan teks yg di database?

      Hapus
    14. Ini scriptnya mas http://pastebin.com/9iD2Yc3J
      ini teks yg ada didatabase http://postimg.org/image/uj3xskrhj/
      Dan ini output dari programnya mas http://postimg.org/image/4vlknqsbr/
      padahal hasilnya udah bener, tapi kalau dihitung totalnya 1, padahal 2 kata yg sama.

      Hapus
    15. Ningung nih mas, udah otak atik tapi masih ga bisa. Apakah untuk kasus tersebut tidak bisa dihitung kata yg samanya ya mas?

      Hapus
  9. Mas kalau menggunakan brute force gimana mas?

    BalasHapus
  10. Mas, kalau menggunakan brute force gimana mas?

    BalasHapus
  11. Mas, saya sedang membuat program pencarian kamus dengan kmp buatan mas. tapi hasil pencarian nya tidak bisa muncul. sintaknya seperti ini :

    KMPSearch($kata,$teks);
    $result = count($hasil);
    echo $result['id']. ' - ';
    echo $result['kata']. ' - ';
    echo $result['arti'];
    }
    }


    ?>

    Tolong bantuannya mas, letak kekurangannya seperti apa, terima kasih :)

    BalasHapus
  12. Mas, saya sedang membuat program pencarian kamus dengan kmp buatan mas. tapi hasil pencarian nya tidak bisa muncul. sintaknya seperti ini :

    include_once("kmp.php");
    $kmp = new KMP();

    if(isset($_GET['kata']))
    $kata = $_GET['kata'];


    $sql = mysql_query("select * from translate");
    while($teks = mysql_fetch_array($sql)){

    if($kata!=''){
    $hasil = $kmp->KMPSearch($kata,$teks['kata']);
    $result = count($hasil);
    echo $result['id']. ' - ';
    echo $result['kata']. ' - ';
    echo $result['arti'];
    }
    }




    Tolong bantuannya mas, letak kekurangannya seperti apa, terima kasih :)

    BalasHapus
  13. saya udah coba bang, dan ternyata ini case sensitive ya bang? biar gk case sensitive gmn ya bang?

    BalasHapus
  14. Terimakasih.. Sangat membantu postingannya..
    Tetapi untuk menampilkan list dari isi field yg berisi kata yg dicari saja yg muncul bagaimana ya? Jadi isi field yg tidak terdapat kata yg dicari tidak usah di tampilkan?

    BalasHapus
  15. kalau brute force gimana ya kak?

    BalasHapus
  16. Assallamuallaikum
    mas bisa minta bantu klw untuk penerapan algoritma brute force dengan PHP bagaimana ya ??
    mohon bantuanya..

    BalasHapus
  17. gan ada script untuk versi laravelnya gk?

    BalasHapus
  18. Bang ada kontak yang bisa dihubungi ? soalnya ini penting banget buat skripsi saya

    BalasHapus