String Processing

Algoritma pencarian string atau sering juga disebut algoritma pencocokan string yaitu algoritma untuk melakukan pencarian semua kemunculan string pendek dan string panjang. Untuk string pendek disebut pattern dan string yang lebih panjang disebut teks.
Prinsip kerja algoritma string matching (Effendi, D. et al. 2013) adalah sebagai berikut:
1. Memindai 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 pergeseran 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, 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 pencarian string ini dapat juga diklasifikasikan menurut arah pencariannya, berikut ini adalah  algoritma yang termasuk dalam algoritma ini dan teknik string matching.

- Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:

Analisis Staightforward 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 Algoritma Knuth-Moriss-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.

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

- Dari kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:

Analisis Algoritma Boyer-Moore
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.

Analisis Algoritma Turbo BM
Algoritma Turbo BM merupakan varian dari algoritma Boyer Moore. Algoritma ini membutuhkan preprocessing yang sama tapi membutuhkan memori sedikit lebih banyak dibandingkan dengan algoritma Boyer Moore. Algoritma Turbo BM menggunakan metode pencocokan string dari kanan ke kiri.

Analisis Algoritma Horspol
Algoritma Horspool adalah penyederhanaan dari algoritma Boyer-Moore yang dibuat oleh R. Nigel Horspool. Menurut Horspool, R.N. (1980), masalah dalam pencarian teks ini adalah mencari dalam teks yang besar untuk menemukan pattern pertama. Karena teks yang dicari bisa sangat besar (memungkinkan ratusan ribu karakter) maka penting untuk menggunakan teknik yang lebih efisien. Algoritma Horspool bekerja dengan metode yang hampir sama dengan algoritma Boyer-Moore namun tidak melakukan lompatan berdasarkan karakter pada pattern yang ditemukan tidak cocok pada teks.
Algoritma Horspool mempunyai nilai pergeseran karakter yang paling kanan dari window. Pada tahap observasi awal (preprocessing), nilai shift akan dihitung untuk semua karakter. Pada tahap ini, dibandingkan pattern dari kanan ke kiri hingga kecocokan atau ketidakcocokan pattern terjadi. Karakter yang paling kanan pada window digunakan sebagai indeks dalam melakukan nilai shift. Dalam kasus ketidakcocokan (karakter tidak terdapat pada pattern) terjadi, window digeser oleh panjang dari sebuah pattern. Jika tidak, window digeser menurut karakter yang paling kanan pada pattern (Baeza-Yates, R.A. & Regnier, M. 1992).


- 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


Sumber :
- http://www.ilmuskripsi.com/2016/05/algoritma-pencarian-string-string.html
- http://elib.unikom.ac.id/download.php?id=108746
- http://informatika.stei.itb.ac.id
- http://www.amethystaiko.com/string-matching-algorithm/