Analisis Algoritma: String Matching

String matching adalah pencarian sebuah pattern pada sebuah teks atau dengan kata lain sebuah pencarian pola string yang lebih pendek didalam string yang lebih panjang. String matching atau pencocokan merupakan bagian penting dari sebuah proses pencarian. Pencarian kata merupakan cara untuk mempermudah pengguna dalam mencari kata yang mereka inginkan. Contoh dari penggunaan metode pencarian kata adalah sebuah aplikasi alquran berbasis android, dimana metode ini akan mempermudah pengguna dalam mencari surat atau ayat yang dikehendaki.

Adapun algoritma String Matching dibagi menjadi tiga kategori menurut arah pencariannya :
• Dari arah kiri ke kanan, atau bisa disebut dari awal ke akhir :
1.    Algoritma Brute Force
2.    Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt

• Dari arah kanan ke kiri :
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, 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

Untuk lebih memudahkan penjelasan dalam setiap penjelasan algoritma-algoritma diatas kita asumsikan kalo String pattern yang akan dicari adalah S[0..n-1], dan String yang dijadikan sebagai tempat dicarinya S (text) kita asumsikan dengan T[0..m-1].

A. Algoritma Brute Force

Penelusuran dari kiri ke kanan merupakan cara algoritma ini dalam menyelesaikan masalah pencarian string. Berikut merupakan cara algoritma ini bekerja :
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. 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.

Contoh:
Teks : nobody noticed him
Pattern : noticed

nobody noticed him
s=0 noticed
s=1 noticed
s=2 noticed
s=3 noticed
s=4 noticed
s=5 noticed
s=6 noticed
s=7    noticed
Pattern noticed ditemukan pada posisi indeks kedelapan (8) dari awal teks.

Pseudecode :

B. Algoritma Knuth-Morris-Pratt

Algoritma memiliki arah penelusuran yang sama dengan algoritma Brute Force, yaitu dari kiri ke kanan. Algoritma string matching Knuth-Morris-Pratt Cara kerja algoritma dengan knuth-Marris-Pratt adalah dengan memelihara informasi yang digunakan untuk melakukan jumlah pergeseran, sehingga bias lebih efisien dibandingkan dengan algoritma Brute Force.

Contoh:

Teks : B A C B A B A B A B

Pattern : A B A B

Langkah 1: B A C B A B A B A B

A B A B

Ket: Pattern 1 tidak cocok dengan Teks 1, maka digeser 1 langkah.

Langkah 2: B A C B A B A B A B

A B A B

Ket: Pattern 1 cocok dengan Teks 2,tetapi Pattern 2 tidak cocok dengan Teks 3, maka Pattern digeser 2 langkah.

Langakah 3: B A C B A B A B A B

A B A B

Ket: Pattern 1 tidak cocok dengan Teks 4, maka Pettern digeser 1 langkah.

Langkah 4: B A C B A B A B A B

A B A B

Ket : Patter 1 sampai dengan Pattern 4 cocok dengan Teks 5 sampai dengan Text 9, maka tidak ada lagi pergeseran.

Berdasarkan contoh diatas maka dapat disimpulkan bahwa informasi yang digunakan untuk melakukan pergeseran adalah berdasarkan hitungan ketidak cocokan Pattern dari kiri pada Teks.

Contoh Pseudocode :

C. Algoritma Boyer-Moore

Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum. Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.

Rinaldi Munir mendefinisikan bahwa Algoritma BoyerMoore 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.

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.

Secara sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore pada saat mencocokkan string adalah:

1. Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.

2. Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan

karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).

2. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di

posisi ini.

3. Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran

good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern

berada di ujung teks.

Sumber :

https://id.wikipedia.org/

Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.

Buulolo, Efori. 2013. Implementasi Algoritma String Matching Dalam Pencarian Surat Dan Ayat Dalam Bible Berbasis Android, Pelita Informatika Budi Darma.