String Matching

Permasalahan pencocokan string (string matching) merupakan permasalahan yang sangat terkenal dalam dunia informatika. Contoh implementasi dari permasalahan pencocokan string adalah pada pencocokan sebuah string pada Microsoft Word atau editor, atau dalam kasus yang lebih besar lagi, yaitu pencocokan website dengan memasukkan kata-kata kunci sebagaimana yang telah diimplementasikan pada search engine, seperti Yahoo atau Google.

Berbagai cara yang telah diterapkan untuk menyelesaikan permasalahan ini, diantaranya Algoritma Staightforward Matching, dengan menggunakan Finite Automata, Algoritma Knuth-Morris-Pratt, Algoritma Boyer-Moore.

String matching adalah pencarian sebuah pattern pada sebuah teks. Algoritma string matching adalah algoritma yang ditujukan untuk melakukan string matching. Prinsip kerja algoritma string matching adalah sebagai berikut:

1.      Men-scan teks dengan 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 [l].

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, 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.

Analisis berbagai Algoritma String Matching Sederhana

Analisis Straightforward matching

Algoritma straightforward matching adalah cara brute-force untuk menyelesaikan permasalahan pencarian string. Jalannya algoritma ini adalah sebagai berikut.

Awalnya kita membandingkan karakter pertama dari string dangan karakter pertama dari text. Jika sama

maka kita bergerak ke karakter selanjutnya sampai kita telah mencocokan keseluruhan string atau menemukan karakter yang tidak sama Jika kita menemukan karakter yang tidak sama maka kita akan bergerak satu langkah kedepan dan akan memulai lagi mencocokan string dari awal.

Kasus terburuk adalah kita sukses dalam setiap perbandingan kecuali pada karakter terakhir string. Dalam kasus ini kita melakukan S*(T-S+1) kali perbandingan. Algoritma ini sangat powerfull, namun akan sangat lama dan tidak efektif bila kita harus mencari sebuah string dalam text yang sangat panjang. Bayangkan bila search engine yang ada sekarang menggunakan Algoritma ini, betapa lamanya kita harus menunggu karena informasi yang kita inginkan baru akan muncul setelah search engine membandingkan karakter demi karakter yang ada di seluruh dunia.

Analisis Finite Automata

Finite Automata digunakan untuk memutuskan apakah sebuah kata atau string adalah kata yang diterima oleh mesin automata tersebut. Sebuah aoutomata memiliki status dan fungsi transisi yang merubah status berdasarkan status saat ini dan karakter yang dibaca saat ini. Ada yang disebut sebagai status akhir dan status ini mungkin lebih dari satu. Bila string itu dijalankan dan berakhir disalah satu status akhir maka string itu diterima atau termasuk dalam behasa tersebut.

Kita bisa membuat finite automata untuk menerima string yang kita cari dan jika kita menemukan sebuah kata yang berakhir di status akhir finite automata yang kita buat maka kita bisa mengetahui bahwa kita telah menemukan string yang kita cari.

Karena kita melihat setiap karakter yang ada pada text, maka sedikitnya kita telah melakukan T perbandingan, namun keistimewaan finite automata kita bisa menentukan status mana yang akan dituju setelah sebuah status menerima sebuah karakter. Hal ini yang kemudian menjadi dasar pemikiran untuk Algoritma Knuth-Morris-Pratt.

Analisis Algoritma Knuth-Morris-Pratt

Dalam Algoritma Knuth-Morris-Pratt (KMP), untuk setiap karakter yang dibandingkan kita bisa memutuskan apakah berhasil atau gagal. Algoritma KMP membangun sebuah mesin automata yang status-statusnya adalah status dari string yang sedang kita cari. Dan setiap status memiliki fungsi berhasil dan gagal. Berhasil artinya status akan bergerak lebih mendekat ke status akhir dan gagal artinya status bisa jadi semakin jauh atau tetap terhadap status akhir. Kita akan mendapatkan sebuah karakter dari text saat kita berhasil dalam membandingkan dan akan mereuse karakter bila kita gagal.

Contohnya :

Perbandingan yang gagal paling banyak adalah sejumlah S-1 kali. Dan yang membuat algoritma ini lebih baik dari brute-force adalah jumlah perbandingan yang lebih sedikit dari algoritma standar brute force. Kompleksitas brute force adalah O(S * T) , sedangkan algoritma KMP memiliki kompleksitas O(S + T).

Analisis Algoritma Boyer-Moore

Rinaldi[1] mendefinisikan bahwa Algoritma Boyer-Moore merupakan variasi lain dari pencarian string dengan melompat maju sejauh mungkin. Tetapi, algoritma Boyer Moore(BM) berbeda dengan algoritma Knuth-Morris-Pratt (KMP), dimana algoritma Boyer Moore melakukan perbandingan pattern mulai dari kanan sedangkan algoritma Knuth-Morris-Pratt melakukan perbandingan dari kiri.

Jika kita mencocokan dari kanan string atau pattern maka ketidakcocokan mungkin membantu kita untuk menggerakkan pattern tersebut dengan jarak yang lebih jauh yang artinya akan lebih signifikan dalam mengurangi proses perbandingan. Jadi kita bisa melompati atau tidak melakukan perbandingan-perbandingan

karakter yang diprediksikan akan gagal.

Contoh :

Text : there they are

Pattern : they

Dengan satu kali perbandingan karakter ‘r’ dan ‘y’ kita bisa melihat bahwa gerakan dari 4 karakter adalah yang terbaik. Kita juga harus mempertimbangkan karakter-karakter yang telah kita cocokan jadi kita tidak bergeser terlalu sedikit. 

Algoritma Boyer Moore ini menggunakan gerakan geser (slide) dan lompat (jump). Garakan geser memberikan informasi berapa banyak pattern harus digeser untuk mendapatkan karekter yang cocok. Gerakan Lompat memberikan informasi berapa banyak pattern harus digeser untuk mencocokan karakter terakhir yang cocok dengan kemunculan awalnya dengan pattern. Studi telah menunjukan bahwa dengan text bahasa natural dan dengan sebuah pattern yang terdiri dari enam atau lebih karakter, maka jumlah perbandingan sekita 0,4T. Seiring dengan meningkatnya panjang pattern maka algoritma Boyer Moore ini memiliki perbandingan yang lebih rendah, sekitar 0,25T.

Permasalahan Pencarian String (String Macthing) pada dasarnya adalah permasalahan mencari sebuah string (pattern) pada sebuah teks.

Referensi :

Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.
www.ics.uci.edu