7
BAB II TINJAUAN PUSTAKA
2.1. Algoritma Pencocokan String Algoritma pencocokan string merupakan komponen dasar dalam pengimplementasian berbagai perangkat lunak praktis yang sudah ada. String matching digunakan untuk menemukan satu atau lebih string yang disebut dengan pattern (string yang akan dicocokkan ke dalam text) dalam string yang disebut dengan text (string yang diinput) (Charras & Lecroq 2004). Pencocokan string adalah permasalahan untuk menemukan satu atau lebih umum semua kejadian dari pola dalam teks. Suatu pola dan teks keduanya merupakan string yang dibangun di atas alphabet yang terbatas (satu set simbol yang terbatas) (Gonzalez,et al. 2014) Menurut cara pembacaan teks, algoritma pencocokan string dapat dibedakan atas dua cara pembacaan : 1.
Dari kiri ke kanan Algoritma pencarian dengan teknik ini sangat banyak. Hampir sebagian besar algoritma pencarian menggunakan cara pembacaan teks dari kiri ke kanan.
2.
Dari kanan ke kiri Dalam Algoritma ini, terdapat algoritma Boyer-Moore yang dianggap merupakan salah satu algoritma yang utama dan algoritma standar dalam pencocokan
string.
(Hume
&
Sunday
1991)
Universitas Sumatera Utara
2.2. Algoritma Zhu-Takaoka Algoritma Zhu-Takaoka merupakan algoritma pencocokan string (String Matching) yang dipublikasikan oleh Zhu Rui Feng dan Tadao Takaoka pada tahun 1986. Dalam makalahnya, Zhu dan Takaoka menyebut algoritma pencocokan string ini sebagai BM‟ Algorithm (Boyer-Moore‟ Algorithm). BM‟ Algorithm merupakan algoritma modifikasi dari algoritma pencocokan stringBoyer-Moore Algorithm yang dibuat oleh Boyer R.S dan Moore J.S. Algoritma BM‟ (Algoritma Zhu-Takaoka) yang merupakan modifikasi dari Algoritma BM mempunyai ciri-ciri yang sama dalam proses pencarian string. Ciri-ciri tersebut yaitu adanya tahap Preprocessing, Right-to-left scan, Bad character rule, dan Good-suffix rule. Perbedaan antara Algoritma Boyer-Moore dan Algoritma Zhu-Takaoka yaitu terletak pada tahap penentuan bad character rule. Dalam Boyer-Moore, bad character hanya terdiri array satu dimensi, sedangkan dalam Zhu-Takaoka dimodifikasi menjadi array dua dimensi (Ramdhani,2012). Pada tahap preprocessing algoritma Zhu-Takaoka membangun tabel bad character 2 dimensi karena algoritma tersebut menghitung untuk pasangan karakter. Kompleksitas waktu dari fase preprocessing adalah O(m+o2) dankompleksitas waktu fase pencarian adalah O(mn) (Bhandari & Kumar 2014). Proses inti pencarian Algoritma Zhu-Takaoka yaitu dilakukan dengan teknik right-to-left scan rule. Teknik ini membandingkan pattern yang dicari dengan sumber teks dimulai dari kanan ke kiri (Michailidis & Margaritis 2009). Langkah pertama yang dilakukan adalah tahapan preprocessing yaitu meciptakan
dua
buah
tabel
shif/pergesaran
ztBc
(Zhu-Takaoka
Bad
Character)&bmGs (Boyer-Moore Good Suffixes). Kedua tabel ini diciptakan merujuk kepada pattern yang akan dicari oleh karena itu jika pattern berubah maka tabel juga akan berubah. Hasil preprocessing untuk patternMATA terlihat pada tabel 2.1 dan tabel 2.2.
Universitas Sumatera Utara
12
Tabel 2.1 Zhu-Takaoka Bad Character Table ztBc
A
M
T
*
A
4
3
1
4
M
2
3
4
4
T
4
3
4
4
*
4
3
4
4
Tabel ztBc berbentuk array dua dimensi yang baris dan kolom diisi sesuai dengan karakter yang ada pada pattern, tanda *(star) mewakili seluruh karakter yang tidak ada pada pattern. Tabel inilah yang merupakan hasil modifikasi dari algoritma Boyer Moore yang memiliki table bad character hanya terdiri dari array satu dimensi.
Tabel 2.2 Boyer-Moore Good Suffixes Table I
0
1
2
3
x[i]
M
A
T
A
suff[i]
0
1
0
4
bmGs[i]
4
4
2
1
Tahapan selanjutnya adalah tahapan pencarian yaitu dengan menggunakan teknik right-to-left scan rule. Pencarian dilakukan dengan membandingkan karakter demi karakter dari mulai karakter paling kanan menuju karakter paling kiri. Jika terjadi ketidakcocokan karakter, pergeseran akan dilakukan dengan mencari nilai max antara ztBc dan bmGs, dan apabila semua pattern cocok pergeseran menggunakan nilai dari bmGs[0]. Indeks dari ztBc diambil dari dua karakter terakhir teks yang bersesuaian dengan window, sedangkan indeks bmGs diambil dari indeks pattern pada posisisi karakter yang tidak cocok. Langkah-langkah pencarian dengan algoritma Zhu-Takaoka adalah sebagai berikut:
Universitas Sumatera Utara
13
Langkah 1 Tabel 2.3Pencarian pada Teks Langkah ke- 1 Window
A
C
Text
K
A
C
A
Pattern
M
A
T
A
i
0
1
2
3
M
A
T
A
F
A
A
I
Z
A
H
I
Z
A
H
I
Z
A
H
ztBc[ A ][ C ] = 4 bmGs[i] = bmGs[2] = 2 Pergeseran dilakukan sebanyak 4
Langkah 2 Tabel 2.4Pencarian pada Teks Langkah ke- 2 Window M
A
T
A
Pattern
M
A
T
A
i
0
1
2
3
Text
K
A
C
A
F
A
A
Karakter cocok semua. Pergeseran dilakukan sebanyak bmGs[0] =2
Langkah 3 Tabel 2.4Pencarian pada Teks Langkah ke- 3 F
Window Text
K
A
C
Pattern i
A
M
A
T
A
F
M A
T
A
0
2
3
1
A
A
ztBc[ ][ F ] = 4 bmGs[i] = bmGs[3] = 1
Universitas Sumatera Utara
14
Pergeseran dilakukan sebanyak 4
Langkah 4 Tabel 2.4Pencarian pada Teks Langkah ke- 4 Window A
C
A
M
A
T
A
F
Z
A
A
I
Z
Pattern
M
A
T
A
i
0
1
2
3
Text
K
I
A
H
ztBc[ I ][ Z ] = 4 bmGs[i] = bmGs[3] = 1 Pergeseran dilakukan sebanyak 4
Terlihat dari hasil langkah empat tidak ditemukan kecocokan pattern dan text maka dilakukan shif sebesar ztBc[ I ][ Z ] = 4. Karena panjang teks sudah habis maka proses pencocokan dihentikan. Dari contoh diatas dapat ditarik kesimpulan bahwa dengan text KACAMATA FAAIZAH dan pattern MATA menggunakan Algoritma ZhuTakaoka menghasilkan satu pola yang cocok yaitu pada shif ke 4. Banyak komparasi yang terjadi adalah 8(delapan) kali perbandingan karakter.
2.3. Android Android adalah suatu sistem operasi yang didesain sebagai platform open source untuk perangkat mobile berbasis linux yang mencakup sistem operasi, middleware, dan aplikasi. Android menyediakan platform yang terbuka bagi para pengembang untuk menciptakan aplikasi mereka. Android menyediakan semua tools dan framework untuk mengembangkan aplikasi dengan mudah dan cepat. Dengan adanya Android SDK pengembang aplikasi dapat memulai pembuatan aplikasi pada platform Android menggunakan bahasa pemrograman Java (Asmono,2013) Safaat (2012) menyatakan android merupakan platform yang lengkap, terbuka dan bebas yang artinya :
Universitas Sumatera Utara
15
1.
Lengkap artinya para desainer dapat melakukan pendekatan yang komprehensif ketika mereka sedang mengembangkan platform android. Sistem operasinya aman dan banyak menyediakan tools dalam membangun software dan memungkinkan peluang untuk pengembangan aplikasi
2.
Terbuka artinya platform android disediakan melalui lisensi terbuka (open source) sehingga pengembang dapat dengan bebas mengembangkan aplikasi.
3.
Bebas artinya tidak ada lisensi atau biaya royalti untuk dikembangkan pada platform android. Tidak ada biaya keanggotaan diperlukan. Tidak diperlukan biaya pengujian. Aplikasi android dapat didistribusikan dan diperdagangkan dalam bentuk apapun.
4.
Aplikasi android sendiri dikembangkan pada sistem operasi berikut : a. Windows XP. b. Vista/Seven. c. Mac OS X (Mac OS X 10.4.8 atau lebih baru). d. Linux.
2.4
Penelitian yang Relevan
Berikut ini beberapa penelitian yang relevan dengan penelitian ini: 1.
Puji Pra Ramdhani (2012) dalam skripsi yang berjudul Analisis Perbandingan Performansi Algoritma Zhu-Takaoka dan Karp-Rabin pada Pencarian Kata di Rumah Buku Baca Sunda. Dengan melakukan analisis perbandingan performansi dari algoritma Karp-Rabin dan algoritma Zhu-Takaoka maka akan dapat diketahui cara kerja dan performansi dalam kecepatan dan ketepatan dari kedua algoritma tersebut. Agar selanjutnya algoritma yang lebih mangkus dapat digunakan pada perangkat lunak pencocokan kata.
2.
Abraham Khrisnandi Wicaksono (2015) dalam skripsi yang berjudul Perbandingan Algoritma Horspool dan Agoritma Zhu-Takaoka Dalam Pencarian String Berbasis Desktop. Pencarian string adalah proses pencarian dengan menggunakan indeks untuk menemukan teks yang dapat membantu dalam sistem
Universitas Sumatera Utara
16
pencarian informasi. Melanjutkan penelitian sebelumnya, penelitian ini menggunakan algoritma Horspool dan Zhu-Takaoka untuk menemukan kinerja masing-masing algoritma ini dalam mencari pola dalam teks.
Universitas Sumatera Utara
