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

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

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.

1.  <?php

2.  // Knuth-Morris-Pratt Algorithm

3.  // Created March 31, 2010 - 07:10:33 WIB

4.  // Modified March 13, 2013 - 09:39:31 WIB

5.  // x90

6.  class KMP{

7.    function KMPSearch($p,$t){

8.      $hasil = array();

9.   // pattern dan text dijadikan array

10.    $pattern = str_split($p);

11.    $text    = str_split($t);

12. 

13. // hitung tabel lompatan dengan preKMP()

14.    $lompat = $this->preKMP($pattern);

15. print_r($lompat);

16. 

17. // perhitungan KMP

18. $i = $j = 0;

19.    $num=0;

20.    while($j<count($text)){

21.      while($i>-1 && $pattern[$i]!=$text[$j]){

22.     // jika tidak cocok, maka lompat sesuai tabel lompatan

23.        $i = $lompat[$i];

24.      }

25.      $i++;

26.      $j++;

27.      if($i>=count($pattern)){

28.     // jika cocok, tentukan posisi string yang cocok

29.  // kemudian lompat ke string berikutnya

30.        $hasil[$num++]=$j-count($pattern);

31.        $i = $lompat[$i];

32.      }

33.    }

34. return $hasil;

35.  }

36. 

37.  // menetukan tabel lompatan dengan preKMP

38.  function preKMP($pattern){

39.    $i = 0;

40.    $j = $lompat[0] = -1;

41.    while($i<count($pattern)){

42.      while($j>-1 && $pattern[$i]!=$pattern[$j]){

43.        $j = $lompat[$j];

44.      }

45.      $i++;

46.      $j++;

47.      if($pattern[$i]==$pattern[$j]){

48.        $lompat[$i]=$lompat[$j];

49.      }else{

50.        $lompat[$i]=$j;

51.      }

52.    }

53.    return $lompat;

54.  }

55.}

56.?>