·
Definisi
String matching (Pencarian
string) yaitu algoritma pencarian semua kemunculan string pendek dan panjang.
String pendek disebut pettern dan string panjang disebut teks.
String Pendek = Pattern [0..n – 1]
String Panjang = Teks [0..m – 1]
Komponen utama algoritma String Matching:
-
Pattern, deretan karakter yang
dicocokan dengan teks.
-
Teks,
tempat dimana pencocokan pattern dilakukan.
-
Alfabet, berisi semua symbol yang digunakan oleh
Bahasa pada teks dan pattern.
Dinyatakan dengan ∑ dengan ukuran ASIZE.
·
Prinsip Kerja String Matching
Prinsip kerja algoritma string matching:
-
Memindai
teks dengan bantuan sebuah window
(ukurannya sama dengan panjang pettern).
-
Tempatkan
window di awal teks.
-
Membandingkan
karakter pada window dengan karakter
dari pettern (baik hasilnya cocok
atau tidak cocok) dilakukan pergeseran ke kanan pada window. Prosedur ini dilakukan berulang-ulang sampai window berada diakhir teks. Mekanisme
ini disebut sliding window.
Efisiensi
algoritma terletak pada dua tahap:
-
Tahap
praproses, tahap ini mengumpulkan informasi penuh tentang pattern dan menggunakan informasi ini
pada tahap pencarian.
-
Tahap
pencarian, pattern dibandingkan dengan window dari kanan ke kiri atau kiri ke
kanan sampai kecocokan atau ketidakcocokan terjadi.
·
Klasifikasi
Algoritma string matching dibagi
menjadi 3 bagian menurut arah pencariannya. Berikut adalah algoritma yang
termasuk dalam algoritma ini :
1 .
From
left to rihght
Dari arah kiri ke kanan, yang
merupakan arah untuk membaca. Contoh :
1.
Algoritma
Brute Force
2.
Algoritma
Morris dan Pratt
2.
From
right to left
Dari arah kanan ke kiri, arah
yang biasanya menghasilkan hasil terbaik secara praktikal. Contohnya:
1.
Algoritma
Boyer dan Moore
3.
In
a specific order
Dari arah yang ditentukan secara
spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara
teoritis. Contohnya:
1.
Algoritma
Collusi
2.
Algoritma
Crochemore-perrin
·
Teknik Algoritma String Matching
Teknik Utama dalam algortima
string matching:
1. Exact
string matching.
Pencocokan string secara tepat
dengan susunan karakter dalam string yang dicocokkan memiliki jumlah
maupun urutan karakter dalam string yang sama. Bagian algoritma ini bermanfaat
jika pengguna ingin mencari string dalam dokumen yang sama persis
dengan string masukan. Beberapa algoritma exact
string matching,
yaitu:
-
Knuth-Morris-Pratt
Metode ini mencari kehadiran
sebuah kata dalam teks dengan melakukan
observasi awal (preprocessing) dengan cara mengecek ulang
kata sebelumnya.
-
Boyer-Moore
Algoritma ini adalah algoritma yang
paling effesien, sebelum melakukan pencarian string, algoritma melakukan proses
terlebih dahulu pada pattern, bukan pada string pada teks tempat pencarian.
2. Approximate
string matching atau
Fuzzy string matching.
Merupakan
pencocokan string secara samar, dengan kata lain pencocokan string dimana
string yang dicocokan memiliki
kemiripan, memiliki susunan karakter yang berbeda (jumlah atau urutannya).
String tersebut memiliki kemiripan baik kemiripan penulisan (approximate string
matching) atau kemiripan ucapan (phonetic string matching).Daftar Pustaka :
ilmuskripsi.com
Baca juga :
0 komentar:
Posting Komentar