String Matching

String matching atau pencocokan string adalah algoritma yang digunakan unuk melakukan pencarian suatu string yang disebut pattern dalam string yang disebut teks.

Algoritma string matching mempunyai tiga komponen utama, yaitu :

1. Pattern, yaitu deretan karakter yang akan dicocokkan dengan teks, dinyatakan dengan [0…𝑚−1], panjang pattern dinyatakan dengan 𝑚.

2. Teks, yaitu tempat pencocokan pattern dilakukan. Dinyatakan dengan [0…𝑛−1], panjang teks dinyatakan dengan 𝑛.

3. Alfabet, berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern, dinyatakan dengan Σ dengan ukuran dinyatakan ASIZE. 

Prinsip kerja algoritma string matching adalah sebagai berikut :

1.      Memindai teks dengan bantuan sebuah window yang ukurannya sama dengan panjang pattern.

2.      Menempatkan window pada awal teks.

3.      Mekanisme sliding window yaitu 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.

Cara Kerja String Matching

Cara yang jelas untuk mencari pattern yang cocok dengan teks adalah dengan mencoba mencari di setiap posisi awal dari teks dan mengabaikan pencarian secepat mungkin jika karakter yang salah ditemukan. Proses pertama adalah menyelaraskan bagian paling kiri dari pattern dengan teks. Kemudian dibandingkan karakter yang sesuai dari teks dan pattern. Setelah seluruhnya cocok maupun tidak cocok dari pattern, window digeser ke kanan sampai posisi (𝑛−𝑚+1) pada teks.

Efisiensi dari algoritma terletak pada dua tahap:

1.      Tahap praproses, tahap ini mengumpulkan informasi penuh tentang pattern dan menggunakan informasi ini pada tahap pencarian

2.      Tahap pencarian, pattern dibandingkan dengan window dari kanan ke kiri atau kiri ke kanan sampai kecocokan atau ketidakcocokan terjadi.

Dengan sebuah nilai karakter (m < n) yang akan dicari dalam teks. Dalam algoritma pencocokan string, teks diasumsikan berada di dalam memori, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu dibaca terlebih dahulu kemudian disimpan di dalam memori. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern ditemukan pertama kali. 

Klasifikasi Algoritma String Matching

Menurut arah pencariannya, algoritma string matching dapat diklasifikasikan menjadi tiga bagian, yaitu sebagai berikut :

1.      From left to right

Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca. Algoritma yang termasuk dalam kategori ini adalah algoritma Brute Force, algoritma Morris dan Pratt yang kemudian dikembangkan menjadi algoritma Knuth-Morris-Pratt.

2.      From right to left

Dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara partikal. Contoh algoritma ini adalah algoritma Boyer-Moore, yang kemudian banyak dikembangkan menjadi algoritma Tuned Boyer-Moore, algoritma Turbo Boyer-Moore, algoritma Zhu Takaoka dan algoritma Horspool.

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 Colussi dan algoritma Crochemore-perrin. 

Contoh Algoritma String Matching

Berikut ini kami berikan contoh string matching atau pencocokan string dengan menggunakan algoritma brute force.

Algortima brute force adalah algoritma yang ditulis dengan pemikiran secara langsung tanpa memikirkan peningkatan performa seperti kompleksitas algoritma.

Pseudocode dalam pencocokan string dengan menggunakan brute force adalah :

Contoh tahapan penyelesaian dengan menggunakan brute force adalah :

Dalam penyelesaian pencarian string dengan menggunakan brute force memiliki best case, worst case dan juga average case.

Best case

•         Kompleksitas kasus terbaik adalah O(n).

•         Terjadi bila karakter pertama pattern P tidak pernah sama dengan karakter teks T yang dicocokkan

•         Jumlah perbandingan maksimal n kali:

Contoh: 

T: String ini berakhir dengan zzz

P: zzz

Worst Case

Jumlah perbandingan: m(n – m + 1) = O(mn)

Contoh:

T: "aaaaaaaaaaaaaaaaaaaaaaaaaah"

P: "aaah"

Average Case

Menggunakan kompleksitas O (m+n)

Contoh :

T : "a string searching example is standard"

P : "store" 

Selanjutnya - Graph Problem >