Algoritma pencarian string atau sering disebut juga pencocokan string adalah algoritma untuk melakukan pencarian semua yang di temukan, untuk string yang pendek di sebut dengan pattern dan untuk string yg panjang di sebut dengan text
Pencocokkan string adalah permasalahan paling sederhana dari semua permasalahan string lainnya, dan dianggap sebagai bagian dari pemrosesan data, pengkompresian data, analisis leksikal, dan temu balik informasi. Teknik untuk menyelesaikan permasalahan pencocokkan string biasanya akan menghasilkan implikasi langsung ke aplikasi string lainnya :
Algoritma-algoritma pencocokkan string dapat di bedakan menjadi tiga menurut arah pencariannya.
1. Dari arah dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:
· Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt
2. Dari kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:
· Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka;
3. dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:
Algoritma Bruce Force
Jenis algoritma ini merupakan algoritma yang mencocokan sebuah pattern atau kata kunci dalam suatu data yang tersimpan antara indeks 0 sampai indeks n – m untuk mengetahui keberadaan pattern dalam suatu text ( Mesran ).
Text disini merupakan suatu data yang tersimpan dalam komputer sedangkan pattern merupakan kata kunci yang akan dicari dalam suatu data. Bentuk algoritma Brute Force ini akan dilakukan dengan cara mengecek satu huruf pada pattern dengan text pada indeks awal atau biasanya pada array 0. Kemudian, algoritma ini akan mencocokan antara kedua huruf tersebut dan jika tidak, maka program akan langsung ke huruf selanjutnya. Proses pencocokan satu huruf antara pattern dengan text dari kiri ke kanan yang bersesuaian sampai salah satu kondisi berikut terpenuhi :
1. Karakter atau huruf di pattern dan di text yang dibandingkan tidak cocok.
2. Jika semua karakter pattern cocok dengan text, program akan memberitahukan penemuan pada di posisi ini dan menambahkan nilai suatu variabel sebagai banyaknya pattern yang ditemukan dalam text.
Algoritma ini akan terus menggeser pattern sebesar satu ke kanan dan mengulang lagi yaitu mengecek karakter lagi sampai pattern berada di ujung text. Penggunaan algoritma Bruce Foore ini juga memiliki kelebihan dan kelemahan. Adapun kelebihan dari algoritma ini adalah sebagai berikut :
1. Algoritma ini dapat memecahkan hampir sebagian besar masalah.
2. Sederhana dan mudah dimengerti. Hal ini dapat dilihat dari bentuk algoritma bahwa karakter pattern akan mengecek pada karakter di text. Jika tidak cocok, maka langsung ke karakter berikut. sedangkan jika cocok, karakter lanjut ke kanan dengan mengecek karakter pattern dari awal dengan karate text berikutnya.
3. Algoritma Bruce Force ini mampu menghasilkan algoritma yang layak untuk beberapa masalah terpenting seperti pencarian, pengurutan, pencocokan, dan lain – lain.
4. Algoritma ini mampu menghasilkan baku untuk tugas – tugas komputasi.
Sedangkan kelemahan pada penggunaan algoritma Bruce Force ini dapat diuraikan sebagai berikut :
1. Algoritma ini jarang menghasilkan algoritma yang baik.
2. Algoritma ini bisa dikatakan kurang kontruktif dalam teknik pemecahan masalah. Bentuk algoritma Bruce Force dapat digambarkan sebagai berikut : Misalkan : Ada seorang anak menulis kalimat “anak ayam.” Anak tersebut mencari kata kunci ( pattern ) “ayam”, maka jalan algoritma Bruce Force dapat diuraikan sebagai berikut : Text : anak ayam Pattern : ayam.
Proses 1 :
Program akan diawali dengan mengecek dari karakter awal pada pattern dan text. Pada karakter pertama dan memiliki kecocokan pada pattern dan teks yaitu “a”. Tetapi, pada indeks kedua tidak mengalami kecocokan pada karakter pattern dan text sehingga pada pattern akan berpindah ke indeks kedua
INDEKS
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
TEXT
|
a
|
n
|
a
|
k
|
|
a
|
y
|
a
|
M
|
PATERN
|
a
|
y
|
a
|
m
|
|
|
|
|
|
Proses 2 :
Program akan mengecek karakter pertama pattern dengan text pada indeks kedua. Jika dilihat, karakter pada indeks ini cocok sehingga pattern ini melajutkan ke indeks selanjut nya tetapi pada indeks ketiga patern dan text tidak cocok jadi patern akan berpindah ke indeks keempat. Dilihat dari gambar di bawah ini, dari indeks kedua cocok tetapi indeks ketiga tidak cocok sehingga beralih ke indeks keempat pada karakter text.
INDEKS
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
TEXT
|
a
|
n
|
a
|
k
|
|
a
|
y
|
a
|
m
|
PATERN
|
|
|
a
|
y
|
a
|
m
|
|
|
|
INDEKS
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
TEXT
|
a
|
n
|
a
|
k
|
|
a
|
y
|
a
|
m
|
PATERN
|
|
|
|
|
a
|
y
|
a
|
m
|
|
Proses 3 :
Pada indeks kelima ( karakter text ) memiliki kecocokan dengan karakter awal pada pattern yaitu “a”. Kemudian maju ke indeks selanjutnya pada text. Pada indeks keenam sampai kedelapan pada text ini memiliki kesamaan pada tiap karakter pattern sehingga program ini akan menambahkan nilai variabel sebagai bentuk bahwa kata kunci yang dimaksud sudah ditemukan.
INDEKS
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
TEXT
|
a
|
n
|
a
|
k
|
|
a
|
y
|
a
|
m
|
PATERN
|
|
|
|
|
|
a
|
y
|
a
|
m
|
Dalam pencocokan karakter antara pattern dan text akan menjadi berbeda status pada saat mengecek kedua karakter tersebut sama tetapi karakter pattern berhuruf besar sedangkan text berhuruf kecil atau sebaliknya. Hal ini tentunya akan menjadi pembeda karena dalam pemrograman memiliki karakter tersendiri baik huruf besar maupun huruf kecil(case sensitive).
Contoh pseudo code dari algoritma brute force.
procedure BruteForceSearch(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)
Deklarasi:
i, j: integer
Algoritma:
for (i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
endfor
Algoritma Knuth-Morris-Pratt
Jenis algoritma ini merupakan proses matching yang dilakukan untuk mengetahui jumlah penggeseran yang dilihat dari kesamaan String antara prefix dan suffix. Dengan menggunakan kedua tersebut, algoritma ini akan membuat penggeseran lebih jauh lagi tidak hanya satu karakter saja seperti algoritma Bruce Force. Proses pengecekan karakter pattern dengan karakter text hampir sama dengan algoritma Bruce Force. Namun, yang berbeda adalah pada saat kondisi antara kedua karakter pattern dan text tidak sama yang akan melakukan penggeseran dilihat dari kesamaan prefix dan suffix.
Algoritma KMP dapat membangun sebuah mesin automata yang statusstatusnya adalah status dari string dimana sistem sedang 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. Sistem akan mendapatkan sebuah karakter dari text saat kita berhasil dalam membandingkan dan akan mereuse karakter apabila sistem mengalami kegagalan.
Persoalan pencarian string dirumuskan sebagai berikut:
- Sebuah teks (text), yaitu sebuah (long) string yang panjangnya n karakter.
- Pattern, yaitu sebuah string dengan panjang m karakter (m<n) yang akan dicari dalam teks.
Cari lokasi pertama di dalam teks yang bersesuaian dengan pattern. Aplikasi permasalahan pencocokan string biasa ditemukan dalam pencarian sebuah kata dalam dokumen (misalnya menu Find dalam Microsoft Word).
Contoh:
Pattern: formasi
Teks : info inform diinformasikan
- Mula-mula pattern dan teks sejajar pada posisi paling kiri, dan dibandingkan karakter pertamanya.
- Langkah 1 dan 2 sama dengan algoritma Brute Force.
- Pada langkah 3, ketidakcocokan terjadi saat membandingkan karakter ke-3 dari pattern (“R”) dan karakter ke-5 dari teks (spasi). Metode KMP akan memeriksa apakah pada teks yang dilewati pada langkah ini (yaitu F-O-spasi) terdapat karakter awal pattern (yaitu F), dan ternyata cocok di karakter pertama yang sudah dibandingkan pada langkah ini. Karena itu tidak perlu menggeser pattern satu per satu, pattern dapat langsung digeser sejauh 3 karakter pada langkah selanjutnya (langkah 4).
- Kasus yang sama ditemui lagi pada langkah 6, di mana pattern dapat digeser sejauh 5 karakter ke kanan pada langkah 7. Demikian seterusnya, hingga pada akhirnya hanya diperlukan 11 langkah untuk menemukan pattern pada teks.
Dalam algoritma pencarian 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.
ALGORITMA:
procedure KMPsearch(input m, n:integer, input P: array[1..m]of char, input T: array[1..n] of char, output idx: integer)
{Mencari kecocokan pattern P di dalam teks T dengan algoritma Knuth-Morris-Pratt. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx.
Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasikan sebagai string [array of character]
Keluaran: posisi awal kecocokan [idx]. Jika P tidak ditemukan, idx=-1.}
Deklarasi
i,j: integer
ketemu: boolean
b: array[1..m] of integer
procedure HitungPinggiran(input m: integer, P: array[1..m] of char, output b: array[1..m] of integer)
{menghitung nilai b[1..m] untuk pattern P[1..m]}
Algoritma
for ((setiap baris) and (not ketemu)) HitungPinggiran(m,P,b)
j 0
i 1
ketemu false
while (i ≤ n and not ketemu) do
while((j>0) and (P[j+1]≠T[i]))do
j b[j]
endwhile
if P[j+1]=T[i] then
j j+1
endif
if j= m then
ketemu true
else
i i+1
endif
endwhile
if ketemu then
idx i-m+1 {catatan: jika indeks array dimulai dari 0, maka idx i-m}
else
idx -1
endif
endfor
if (not ketemu)
for ((setiap kolom) and (not ketemu))
{lakukan yang sama seperti pada baris}
endfor
endif
Algoritma Boyer Moore
Algoritma Boyer Moore ini merupakan lawan dari algoritma Bruce Force. Hal ini dapat dilihat bahwa untuk melakukan proses matching akan memulai pencocokkan karakter dari kanan, dan bukan dari kiri.
Didalam algoritma Boyer Moore ini menggunkan metode gerakan geser (slide) dan lompat (jump). Garakan geser untuk memberikan jumlah berapa kali pattern agar cocok sedangkan Gerakan Lompat untuk memberikan jumlah berapa kali pattern digeser agar cocok karakter terakhir yang kemunculan awalnya dengan pattern.
Algoritma Boyer Moore adalah algoritma yang tepat untuk proses matching. ini dapat diketahui bahwa algoritma ini dapat 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.
Misalkan ada sebuah teks seperti ini “saya mau pergi sekolah” yang akan dicari dengan kata kunci “sekolah”. Pada kata pattern ini akan dibuat array dengan menggunakan indeks huruf pattern dan posisi huruf tersebut adalah nilai ukuran indeks dari 0 sampai n yang dapat digambarkan sebagai berikut :
Pattern[]
|
[s]
|
[e]
|
[k]
|
[o]
|
[l]
|
[a]
|
[h]
|
Indeks
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses matching sebagai berikut:
Proses 1 :
Pertama tama di cocokan antara karakter terakhir dari pattern dengan karakter kelima dari text. Maka di gunakan rumus dibawah ini:
Karakter ke i = i + m - Math.min(j, 1+lo); dengan lo = last[pattern.chartArt(i)]
Dengan keterangan :
i = nilai indeks pada karakter text yang tidak cocok dengan karakter pattern.
m = panjang karakter pattern.
j = nilai indeks pada karakter pattern yang tidak cocok dengan karakter text.
lo = nilai pengembalian indeks huruf text yang tidak cocok dengan karate pattern.
Nilai lo=last(a), pada indeks pattern h bernilai 5 maka last[h] = 1 jadi di gunakan rumus
I = 6 + 7 –min(6,1) = 6 +7 – 1 = 12 (menuju karakter kesebelas atau indeks kesepuluh)
T
|
s
|
a
|
y
|
a
|
|
m
|
a
|
u
|
|
p
|
e
|
r
|
g
|
i
|
|
s
|
e
|
K
|
o
|
l
|
a
|
h
|
P
|
s
|
e
|
k
|
o
|
l
|
a
|
h
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
Proses 2:
Proses selanjutnya mengecek huruf terakhir dari pattern ternyata tidak cocok jadi akan berpindah lagi menggunakan rumus ke i = 11 + 7 – min(6,-1) = 18 + 1 = 19 (menuju karakter kesembilan belas atau indeks kedelapan belas)
T
|
s
|
a
|
y
|
a
|
|
m
|
a
|
u
|
|
p
|
e
|
r
|
g
|
i
|
|
s
|
e
|
K
|
o
|
l
|
a
|
h
|
P
|
|
|
|
|
|
s
|
e
|
k
|
o
|
l
|
a
|
h
|
|
|
|
|
|
|
|
|
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
Proses 3:
Sama dengan proses sebelumnya di cek kembali apakah huruh terakhir dari pattern karena tidak cocok, kembali gunakan rumus ke i = 18 + 7 – min(6,3) = 25 - 3 = 22 (menuju karakter ke duapuluh dua atau indeks keduapuluh satu )
T
|
s
|
a
|
y
|
a
|
|
m
|
a
|
u
|
|
p
|
e
|
r
|
g
|
i
|
|
s
|
e
|
K
|
o
|
l
|
a
|
h
|
P
|
|
|
|
|
|
|
|
|
|
|
|
|
s
|
e
|
k
|
o
|
l
|
a
|
h
|
|
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
Proses 4:
Kembali di cek apakah huruf akhir dari pattern sama dengan text, ternyata tidak sama kembali maka kembali kita gunakan rumus ke i = 19 + 7 – min(6,last[h]=4) = 26 - 4 = 22 (menuju karakter ke duapuluh dua atau indeks ke duapuluh satu)
Proses 5 :
Telah di temukan nya tulisan ya di cari = “sekolah”
T
|
s
|
a
|
y
|
a
|
|
m
|
a
|
u
|
|
p
|
e
|
R
|
g
|
i
|
|
s
|
e
|
K
|
o
|
l
|
a
|
h
|
P
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s
|
e
|
K
|
o
|
l
|
a
|
h
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
Sumber:
https://id.wikipedia.org/wiki/Algoritma_pencarian_string
E-Book [Anany Levitin]-Intro_2_Design&Analysis_Algorithms
