STRING MATCHING

Pengertian

Algoritma pencarian string atau sering disebut juga string matching adalah algoritma untuk melakukan pencarian semua kemunculan string  pendek dan dan panjang, untuk string yang pendek disebut pattern dan  string yang lebih panjang disebut teks.

string pendek   =  

string panjang  = 

Algoritma pencarian string ini dapat juga diklasifikasikan menjadi 3 bagian menurut arah pencariannya ,berikut ini adalah  algoritma yang termasuk dalam algoritma ini.

• Dari arah yang paling alami yaitu dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:
1. Algoritma Brute Force.
2. Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt
• Kategori kedua yaitu dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:
1. Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka
• Dan kategori terakhir yaitu adalah dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:
1. Algoritma Colussi
2. Algoritma Crochemore-Perrin

Persoalan pencarian string

1. teks (text), yaitu (long) string yang panjangnya n karakter
2. pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari dalam teks.

Carilah lokasi pertama di dalam teks yang bersesuaian dengan pattern.

Contoh 1:

•          Pattern: hari

•          Teks:  kami pulang hari kamis

                                             target

Contoh 2:

•          Pattern: not

•          Teks : nobody noticed him

                                      target

Contoh 3:

•          Pattern: apa

•          Teks :    Siapa yang menjemput Papa dari kota Balikpapan?

Algoritma Brute Force

Contoh 4:

Teks : nobody noticed him

Pattern: not

                               

    nobody noticed him

s=0   not

s=1    not

s=2     not

s=3      not

s=4       not

s=5        not

s=6         not

s=7          not

Contoh 5:

Teks:     10010101001011110101010001

Pattern:  001011

    10010101001011110101010001

s=0 001011

s=1  001011

s=2   001011

s=3    001011

s=4     001011

s=5      001011

s=6       001011

s=7        001011

s=8         001011

Kompleksitas algoritma brute-force:

•          Kompleksitas kasus terbaik adalah O(n).

•          Kasus terbaik terjadi jika yaitu bila karakter pertama pattern P tidak pernah sama dengan karakter teks T yang dicocokkan

•          Pada kasus ini, jumlah perbandingan yang dilakukan paling banyak n kali misalnya:

•          Teks:  String ini berakhir dengan zz

•          Pattern: zz

•          Kasus terburuk: m(n – m + 1) = O(mn)

•          Teks:    aaaaaaaaaaaaaaaaaaaaaaaaaaaaab

•          Pattern: aaaab

Algoritma Knuth-Morris-Pratt (KMP)

•          Dikembangkan oleh D. E. Knuth, bersama-sama dengan J. H. Morris dan V. R. Pratt.

•          Pada algoritma brute force, setiap kali ditemukan ketidakcocokan pattern dengan teks, maka pattern digeser satu karakter ke kanan.

•          Sedangkan pada algoritma KMP, kita memelihara informasi yang digunakan untuk melakukan jumlah pergeseran. Algoritma menggunakan informasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter seperti pada algoritma brute force.

              123456789…       

Teks:      bimbingan belajar atau bimbel

Pattern:  bimbel

                          ­

                               j = 5        

              123456789…     

Teks:     bimbingan belajar atau bimbel

Pattern:     bimbel

                           ­

                  j = 2             

Definisi :

•          Misalkan A adalah alfabet dan x = x₁x₂…x_k  adalah string yang panjangnya k yang dibentuk dari karakter-karakter di dalam alfabet A.

•          Awalan (prefix) dari x adalah upa-string (substring) u dengan

                               

•          u = x₁x₂…x_{k – 1} , k Î {1, 2, …, k – 1} 

                   dengan kata lain, x diawali dengan u.

•          Akhiran (suffix) dari x adalah upa-string (substring) u dengan

               

•          u = x_{k – b} x_{k – b + 1} …x_k , k Î {1, 2, …, k – 1} 

dengan kata lain, x di akhiri dengan v.

•          Pinggiran (border) dari x adalah upa-string r sedemikian sehingga

          r = x₁x₂…x_{k – 1} dan

         u = x_{k – b} x_{k – b + 1} …x_k ,

                                                 k Î {1, 2, …, k – 1} 

•          dengan kata lain, pinggiran dari x adalah upa-string yang keduanya awalan dan juga akhiran sebenarnya dari x.

Contoh 6.   Misalkan x = abacab.

                        Awalan sebenarnya dari x adalah

                                        , a, ab, aba, abac, abaca             

                        Akhiran sebenarnya dari x adalah

                                        , b, ab, cab, acab, bacab

                        Pinggiran dari x adalah

                                        , ab

        Pinggiran  mempunyai panjang 0, pinggiran ab mempunyai panjang 2.

Fungsi Pinggiran (Border Function)

Fungsi pinggiran b(j) didefinisikan sebagai ukuran awalan terpanjang dari P yang merupakan akhiran dari P[1..j]. 

Sebagai contoh, tinjau pattern P = ababaa. Nilai F untuk setiap karakter di dalam P adalah sebagai berikut:

	j	1	2	3	4	5	6
	P[j]	a	B	A	b	A	a
	b(j)	0	0	1	2	3	1

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] }

Deklarasi

  k,q : integer

Algoritma:

  b[1]¬0

  q¬2

  k¬0

  for q¬2 to m do

    while ((k > 0) and (P[q] ¹ P[k+1])) do

      k¬b[k]

    endwhile

    if P[q]=P[k+1] then

      k¬k+1

    endif

    b[q]=k   

  endfor  

Contoh 7:                                           

Teks:     abcabcabd

                Pattern: abcabd

Mula-mula kita hitung fungsi pinggiran untuk pattern tersebut:

	j	1	2	3	4	5	6
	P[j]	a	b	C	a	b	d
	b(j)	0	0	0	1	2	0

                                               

Teks:     abcabcabd

                Pattern:        abcabd

                                                     ­

                                                    j = 3

Kompleksitas Waktu Algoritma KMP

•          Menghitung fungsi pinggiran : O(m),

•          Pencarian string  : O(n)

•          Kompleksitas waktu algoritma KMP adalah O(m+n).