String Matching

Pengertian String merupakan pencarian sebuah pattern pada sebuah teks. dan biasanya direpresentasikan sebagai struktur data array. String dapat berupa kata, frase, atau kalimat.
Algoritma string matching adalah algoritma yang ditujukan untuk melakukan string matching. Prinsip kerja pada algoritma string matching adalah sebagai berikut:

1. Men-scan teks dengan menggunakan bantuan sebuah window yang ukurannya sama dengan panjang pattern.
2. Menempatkan window pada awal teks.
3. Membandingkan karakter pada window dengan karakter dari pattern. Setelah pencocokan (baik hasilnya cocok atau tidak cocok), dilakukan shft ke kanan pada window. Prosedur ini dilakukan berulang-ulang sampai window berada pada akhir teks. Mekanisme ini disebut mekanisme sliding-window.

Algoritma-algoritma string matching mempunyai tiga komponen, yaitu: pattern, teks dan alfabet dengan asumsi sebagai berikut:

1. Pattern, yaitu deretan karakter yang dicocokkan dengan teks.
2. Teks, yaitu tempat pencocokan pattern dilakukan.
3. Alfabet, yang berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern.

String merupakan bagian penting dari sebuah proses pencarian string (string searching) dalam  sebuah dokumen. Hasil dari pencarian sebuah string dalam dokumen tergantung dari teknik atau cara pencocokan string yang digunakan.

Pencarian string yang juga bisa disebut pencocokan string (String Matching) merupakan algoritma untuk melakukan pencarian semua kemunculan string pendek pattern [ 0....n-1] yang disebut pattern di string yang lebih panjang teks [0...m-1] yang disebut teks

Pengertian Pencocokan String
Pencocokan String (string matching) secara garis besar dapat dibedakan menjadi dua yaitu :

1. Exact string matching, merupakan pencocokan String secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama.
   Contoh : kata Step akan menunjukkan kecocokan hanya dengan kata step.
2. Inexact string matching atau Fuzzy string matching, merupakan pencocokan String secara samar, maksudnya pencocokan string dimana string yang dicocokkan memiliki kemiripan dimana keduanya memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya) tetapi string-String tersebut memiliki kemiripan baik kemiripan tekstual/penulisan (approximate string matching) atau kemiripan ucapan(phonetic string matching).

Algoritma string matching dapat diklasifikasikan menjadi 3 bagian menurut arah pencariannya, yaitu:

1. From left to right Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca. Algoritma yang termasuk kategori ini adalahalgoritma brute force, algoritma knuth moris Pratt.
2. From right to left  Dari arah kanan ke kiri, arah yang bisanya menghasilkan hasil terbaik secara partikal. Algoritma yang termasuk kategori ini adalah algoritma boyer-moore.
3. In a specific order  Dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis. Algoritma yang termasuk kategori ini adalah algoritma colossi dan algoritma crochemore-perrin.

Procedure PencocokanString(input P : string, T : string, n, m : integer,output idx : integer)
{  Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: lokasi awal kecocokan (idx) }

Deklarasi
  i            : integer
  ketemu : boolean
Algoritma:
  i←0
  ketemu←false
  while(i ≤ n - m) and (not ketemu) do
  j←1
  while (j ≤ m) and (Pj = Ti+j ) do
  j←j+1
  endwhile
  { j > m or Pj  ≠ Ti+j }
  if j = m then{ kecocokan string ditemukan }
  ketemu ←true
  else
  i← i+1 {geser pattern satu karakter ke kanan teks }
  endif
  endfor
  { i > n – m or ketemu }
  if ketemu then
  idx←i+1                                                    
  else
  idx ←-1
  endif

Sumber :

• Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.
• Charras, Christian., et al. 1997. Handbook of Exact String Matching Algorithms. Oxford University Press