BAB 2 TINJAUAN PUSTAKA
2.1. Kamus Buku acuan yang memuat kata dan ungkapan, biasanya disusun menurut abjad berikut keterangan tentang makna, pemakaian, atau terjemahannya, kamus juga disebut buku yang memuat kumpulan istilah atau nama yang disusun menurut abjad beserta penjelasan tentang makna dan pemakaiannya (Pusat Bahasa: 2008). 2.2. String Matching String matching atau pencocokan string adalah suatu teknik yang digunakan untuk menemukan suatu keakuratan dari satu atau beberapa pola teks yang diberikan (Rassol, et al. 2012).
2.2.1. Algoritma Rabin Karp Algoritma Karp-Rabin diciptakan oleh Michael O. Rabin dan Richard M. Karp pada tahun 1987 yang menggunakan fungsi hashing untuk menemukan pattern di dalam string teks (Hamza, et al, 2013). Karakteristik Algoritma Rabin-Karp (Noprisson, et al, 2014) : 1. Menggunakan sebuah fungsi hashing 2. Fase prepocessing menggunakan kompleksitas waktu O(m) untuk fase pencarian kompleksitasnya : O(mn) 3. Waktu yang diperlukan O(n+m) Fungsi hashing menyediakan metode sederhana untuk menghindari perbandingan jumlah karakter yang kuadratik di dalam banyak kasus atau situasi. Dari pada melakuka
Universitas Sumatera Utara
6
pemeriksaan terhadap setiap posisi dari teks ketika terjadi pencocokan pola, akan lebih baik dan efisien melakukan pemeriksaan hanya jika teks yang sedang proses memiliki kemiripan seperti pada pattern. Untuk melakukan pengecekan kemiripan antara dua kata ini digunakan fungsi hash (Charas & Lecroq , 2004). Pada faktanya, fungsi hash menyimpan bentuk string dalam bentuk lain yaitu enumerasi sehingga suatu string tertentu akan memiliki nilai enumerasinya yang unik (Ramdhani, 2012). Karena suatu string hanya memiliki sebuah nilai enumerasi maka hal inilah yang digunakan oleh algoritma Rabin-Karp untuk mempercepat pencarian string dalam tabel hash. Proses pencocokan dalam algoritma Rabin-Karp dilakukan dengan menggunakan sebuah teorema yaitu: Sebuah string A identik dengan string B, jika (syarat perlu) string A memliki hash key yang sama dengan hash key yang dimiliki oleh string B (Raharja, 2015). Rolling hash adalah fungsi hash dengan basis. Basis biasanya adalah bilangan prima.
Contoh
1
penggunaan
fungsi
hash
dengan
basis
string
:
“GCATCGCAGAGAGTATACAGTACG” sebagai string sumber atau teks dan string “GCAGAGAG” sebagai pattern. Raharja (2015) meneliti tentang perancangan dan implementasi sistem penilaian jawaban esai otomatis menggunakan algoritma Rabin-Karp, dimana untuk mencarai nilai hash digunakan persamaan: H = C1 * B(m-1) + C2 * B(m-2) + ... +C(m-1)* Bm + Cm ………………….. (1) Dimana: H = Nilai Hash C = ASCII karakter B = Basis (bilangan prima) m = Banyak karakter (panjang karakter) Dengan nilai ASCII dari A=65, C=67, G= 71 dan T= 84, maka nilai hash dari m “GCAGAGAG” adalah: H(m) = (71*27)+( 67*26)+(65*25)+(71*24)+(65*23)+(71*22)+(65*21)+(71*20) H(m) = 9088+4288+2080+1136+520+284+130+71 H(m) =17597
Universitas Sumatera Utara
7
Dengan menggunakan persamaan 1, fase searching untuk contoh 1 diberikan pada percobaan 1 sampai percobaan 17 ( Charas & Lecroq, 2004): Tabel 2.1. Percobaan 1 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
mG
C
A
G
A
G
A
G
18 A
19
20
G
T
21 A
22
23
C
G
Hash (n[0..7]) = 17819 Tabel 2.2. Percobaan 2 i
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
n
G
A
G
T
A
T
A
C
C
A
T
mG
C
A
C
G
G
A
C
G
A
A
G
A
G
18 A
19 G
20 T
21 A
22 C
23 G
G
Hash (n[1..8]) = 17533 Tabel 2.3. Percobaan 3 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
A
G
Hash (n[2..9]) = 17979 Tabel 2.4. Percobaan 4 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
C
A
mG
G
A
G
A
G
Hash (n[3..10]) = 13389
Universitas Sumatera Utara
8
Tabel 2.5. Percobaan 5 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
A
G
Hash (n[4..11]) = 17339 Tabel 2.6. Percobaan 6 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
G
A
Hash (n[5..12]) = 17597 Hash (m) = 17597., Hash (m) = Hash (n)., string match pada percobaan ke 6 Tabel 2.7. Percobaan 7 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m G C A G A
G
A
G
n G C A T C G C A G A
Hash (n[6..13]) = 17102 Tabel 2.8. Percobaan 8 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
A
G
Hash (n[7..14]) = 17117
Universitas Sumatera Utara
9
Tabel 2.9. Percobaan 9 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
A
G
Hash (n[8..15]) = 17678 Tabel 2.10. Percobaan 10 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
mG
C
A
G
A
G
A
G
Hash (n[9..16]) = 17245 Tabel 2.11. Percobaan 11 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[10..17]) = 17917 Tabel 2.12. Percobaan 12 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[11..18]) = 17723 Tabel 2.13. Percobaan 13 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[12..19]) = 18877
Universitas Sumatera Utara
10
Tabel 2.14. Percobaan 14 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[13..20]) = 19662 Tabel 2.15. Percobaan 15 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[14..21]) = 17885 Tabel 2.16. Percobaan 16 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[15..22]) = 19197 Tabel 2.17. Percobaan 17 i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
m
G
C
A
G
A
G
A
G
Hash (n[16..23]) = 16961
Universitas Sumatera Utara
11
Tabel 2.1 – Tabel 2.17 menjukan proses pencocokan string dan pergeseran yang dilakukan algoritma Rabin-Karp, yang mana string match pada percobaan ke 6 yang mana nilai hash string inputan = nilai hash teks [5-12]. 2.3. Android Android merupakan sistem operasi populer berbasis Linux yang dikembangkan oleh Google. Android secara garis besar merupakan projek open source yang diadopsi. Google secara aktif mengembangkan platform Android tetapi memberikan porsi tertentu secara gratis untuk memproduksi hardware dan bawaan dari ponsel yang inggin menggunakan sistem operasi Android dalam perangkatnya (Karch, 2016). 2.4. Penelitian Yang Relevan Beberapa contoh penelitian tentang string matching dengan algoritma Rabin-Karp sebagai berikut: 1. (Nugroho, 2011) dalam penelitiannya menghasilkan sebuah aplikasi desktop yang memberikan informasi kemiripan suatu dokumen teks terhadap dokumen teks lainnya. 2. (Noprisson, et al, 2014) dalam penelitiannya menghasilkan aplikasi berbasis web. Penelitian ini menyimpulkan algoritma Rabin-Karp dapat digunakan dalam memberikan rekomendasi dokumen teks terkait yang memiliki kesamaan kata secara otomatis dengan hasil rekomendasi berupa maksimal 5 dokumen teks yang memiliki nilai rekomendasi tertinggi berdasarkan dengan metode Dice’s Similarity Coefesient dari hasil proses string matching.
Universitas Sumatera Utara
