String Matching

Yaa kali ini kami akan mengupas sedikit tentang String Matching.

Apa itu String Matching?
String Matching adalah sebuah proses pencarian string yang penting dalam sebuah dokumen. Hasil dari sebuah pencarian tersebut tergantung dari teknik dan cara pencocokan string yang digunakan.

Menurut N. Singla & D. Garg Algoritma String Matching mempunyai 2 teknik utama yaitu :

1. Exact Matching : Merupakan hasil pencocokan yang mengandung string yang sama persis dengan string yang di input.
   Contohnya pada algoritma Needleman Wunsch, algoritma Smith Waterman, algoritma Knuth-Morris-Pratt, algoritma Boyer- Moore-Horspool
2. Approximate Matching : Merupakan hasil pencocokan yang mengandung string yang tidak harus sama persis dengan string yang di input.
   Contohnya pada algoritma Fuzzy String Searching, algoritma Rabin Karp, algoritma Brute Force.

Prinsip kerja algoritma string matching sebagai berikut :

1. Memindai teks dengan bantuan sebuah window yang ukurannya sama dengan pattern.
2. Menempatkan window pada awal teks.
3. Membandingkan karakter pada window dengan karakter dari pattern.

Algoritma String Matching mempunyai 3 komponen, yaitu :

1. Pattern,  yaitu  deretan  karakter  yang  akan  dicocokkan  dengan  teks,  dinyatakan dengan x[0..m-1], panjang pattern dinyatakan dengan m.  
2. Teks,  yaitu  tempat  pencocokan  pattern  dilakukan,  dinyatakan  dengan  y[0..n-1], panjang teks dinyatakan dengan n.  
3. Alfabet, yang berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern, dinyatakan  dengan  Σ  dengan  ukuran  dinyatakan  dengan ASIZE.

Algoritma String Matching mempunyai 3 bagian menurut arah pencariaannya :

• Dari arah yang paling alami, From left to right, algoritma yang termasuk kategori ini adalah :

1. Algoritma Brute Force
2. Algoritma dari Morris dan Pratt, yang kemudian oleh Knuth, Morris, dan Pratt.

• Right to Left, secara pratikal arah ini menghasilkan hasil terbaik, contohnya :

1. Algoritma dari Boyer dan Moore, dan kemudian banyak dikembangkan menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka; 

• Dan ini kategori terakhir, algoritma ini arahnya ditentukan secara spesifik, maka arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk ini adalah:
1. Algoritma Colussi
2. Algoritma Crochemore-Perrin

Contoh Algortima Brute Force mencari string

Inilah salah satu contoh untuk mencari string menggunakan Algoritma Brute Force. Dan dibawah ini Pseudocode algortima Brute Force :

procedure BruteForceSearch(
        input m, n : integer,
        input P : array[0..n-1] of char,
        input T : array[0..m-1] of char,
        output ketemu : array[0..m-1] of boolean
       )

Deklarasi:
       i, j: integer 

Algoritma:
        for (i:=0 to  m-n) do
               j:=0
               while (j < n and T[i+j] = P[j]) do    
                        j:=j+1
               endwhile
               if(j >= n) then
                         ketemu[i]:=true;
               endif  

endfor

         

10115448

sumber : disini

               disini