PERANCANGAN FITUR AUTOCOMPLETE PADA APLIKASI KAMUS ISTILAH TEKNOLOGI INFORMASI MENGGUNAKAN ALGORITMA BOYER-MOORE
SKRIPSI
SITI MORIZA TANIA 101402076
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
PERANCANGAN FITUR AUTOCOMPLETE PADA APLIKASI KAMUS ISTILAH TEKNOLOGI INFORMASI MENGGUNAKAN ALGORITMA BOYER-MOORE SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Teknologi Informasi
SITI MORIZA TANIA 101402076
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
: PERANCANGAN FITUR AUTOCOMPLETE PADA APLIKASI KAMUS ISTILAH TEKNOLOGI INFORMASI MENGGUNAKAN ALGORITMA BOYER-MOORE
Kategori
: SKRIPSI
Nama
: SITI MORIZA TANIA
Nomor Induk Mahasiswa : 101402076 Program Studi
: SARJANA (S1) TEKNOLOGI INFORMASI
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dr. Erna Budhiarti Nababan M.IT
M. Andri Budiman, ST.M.Comp.Sc., M.E.M
NIP. -
NIP. 19751008 1200801 1 011
Diketahui/Disetujui oleh Program Studi S1 Teknologi Informasi Ketua,
Muhammad Anggia Muchtar, ST., MM.IT NIP. 19800110 200801 1 010
Universitas Sumatera Utara
iii
PERNYATAAN
PERANCANGAN FITUR AUTOCOMPLETE PADA KAMUS ISTILAH TEKNOLOGI INFORMASI MENGGUNAKAN ALGORITMA BOYER-MOORE
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 4 Juni 2015
Siti Moriza Tania 101402076
Universitas Sumatera Utara
iv
UCAPAN TERIMA KASIH
Alhamdulillah, segala puji dan syukur kepada Allah SWT yang telah memberikan rahmat, karunia dan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini. Penulis mengucapkan banyak terima kasih kepada: 1. Bapak M. Andri Budiman, ST.M.Comp.Sc., M.E.M, selaku pembimbing 1 dan Ibu Dr. Erna Budhiarti Nababan, M.IT, selaku pembimbing 2 yang telah banyak memberikan bimbingan, arahan, motivasi dan membantu penulis dalam penyusunan dan penulisan skripsi ini. 2. Bapak Sajadin Sembiring, S.Si, M.Comp.Sc dan Bapak Seniman, S.Kom, M.Kom sebagai tim pembanding, atas segala kritik dan saran dalam penyempurnaan penulisan skripsi ini. 3. Bapak Muhammad Anggia Muchtar, ST., MM.IT, selaku ketua program studi Teknologi Informasi, serta seluruh Bapak dan Ibu dosen yang telah memberikan ilmu yang bermanfaat bagi penulis. 4. Seluruh staf TU (Tata Usaha) program studi Teknologi Informasi yang telah banyak membantu dalam segala kegiatan administrasi penulis. 5. Kedua Orang tua penulis, Ayahanda Sakhrizal dan Ibunda Rita Morita yang selalu mendoakan, sabar dan senantiasa memberikan kasih sayang sepanjang masa kepada penulis. Adik-adik penulis, Siti Sovie Sakhrani dan Siti Ulfha Salita serta keluarga besar penulis yang selalu memberikan semangat kepada penulis. 6. Sahabat penulis, Pratiwi Widya Utami S.Pd dan Rizka Aini Hasibuan S.Psi yang tiada henti memberikan semangat dan doa, terkhusus untuk Naniek B.J. Matanari dan Handra Akira Saito yang selalu memberikan semangat, setia dan sabar menemani dan mendorong penulis dalam penyelesaian skripsi ini. Abang-abang, kakak-kakak, adik-adik, dan teman-teman program studi teknologi informasi angkatan 2010 yang tidak dapat penulis cantumkan satu per satu atas segala dukungan dan kebersamaannya selama melewati perkuliahan di Teknologi Informasi USU ini.
Universitas Sumatera Utara
v
ABSTRAK
Penggunaan kamus elektronik saat ini terbukti lebih efisien dibandingkan penggunaan kamus dalam bentuk buku. Hal tersebut dikarenakan pada kamus elektronik pengguna akan menuliskan kata yang mereka inginkan pada kolom pencarian dan mesin pencari akan menemukan dan memberikan informasi kata tersebut kepada pengguna. Untuk menampilkan informasi tersebut, beberapa kamus elektronik menampilkan informasi setelah pengguna selesai mengetikkan satu kata pada mesin pencari. Tetapi ketika pengguna selesai mengetikkan kata pada mesin pencari, kata tersebut belum tentu ditemukan, hal ini menjadikan kamus elektronik kurang optimal dalam hal pemakaian waktu. Oleh karena itu, fitur autocomplete yang dibangun pada aplikasi kamus ini diharapkan dapat mempersingkat waktu pengetikan sebuah kata yang dilakukan pengguna, dimana fitur ini akan menampilkan daftar kata yang mungkin dimaksudkan pengguna atau yang disebut dengan word suggestion tanpa harus mengetikkan kata tersebut secara utuh. Word suggestion ini dihasilkan melalui pencocokan string yang dilakukan oleh algoritma Boyer-Moore, dimana input yang diketikkan pengguna akan dicocokkan dengan setiap kata yang terdapat dalam database. Fitur autocomplete pada aplikasi kamus ini berhasil menampilkan word suggestion berupa kata yang mengandung potongan kata yang diketikkan pengguna, tetapi untuk kesalahan letak huruf pada kata yang diketikkan pengguna, fitur autocomplete tidak akan menampilkan word suggestion karena kata tersebut dianggap tidak ditemukan pada database.
Kata kunci : autocomplete, exact string matching, algoritma Boyer-Moore, kamus bahasa Inggris, kamus teknologi informasi.
Universitas Sumatera Utara
vi
THE AUTOCOMPLETE FEATURE DESIGN ON THE APPLICATION OF TERMINOLOGY DICTIONARY OF INFORMATION TECHNOLOGY USING THE BOYER-MOORE ALGORITHM
ABSTRACT
The usage of electronic dictionary nowadays has proven that it is more efficient than the physical one. This happens because in electronic dictionary the user are able to look for a word easily by just typing the keyword and the search engine will return the result instantly to the user. To display the information, some electronic dictionaries display information after the user is finished typing one word in a search engine. But when the user is finished typing words into a search engine, the word is not necessarily found, this makes the electronic dictionaries are less optimal in terms of time consumption. Therefore, auto-complete feature that is built on this dictionary application is expected shorten the time of typing a word that is perfomed by the user, where this feature will suggest the list of words which is similar to the user’s input with word suggestion feature without having to complete the typing. The word suggestion is derived by the matching of string which is done using Boyer-Moore algorithm, where the user’s input will be matched with every words in the database. Auto-complete feature in this application manage to show the word suggestion by reading the word which contains the piece of word the user typed, but for misplaced alphabet user made, the auto-complete feature won’t show any word suggestion because that word might not be found in the database.
Keyword : auto-complete, exact string matching, Boyer-Moore algorithm, English Dictionary, Dictionary of Information Technology.
Universitas Sumatera Utara
vii
DAFTAR ISI
Hal. PERSETUJUAN
ii
PERNYATAAN
iii
UCAPAN TERIMA KASIH
iv
ABSTRAK
v
ABSTRACT
vi
DAFTAR ISI
vii
DAFTAR TABEL
ix
DAFTAR GAMBAR
x
BAB 1
BAB 2
PENDAHULUAN 1.1 Latar Belakang
1
1.2 Rumusan Masalah
2
1.3 Batasan Masalah
3
1.4 Tujuan Penelitian
3
1.5 Manfaat Penelitian
3
1.6 Sistematika Penulisan
3
LANDASAN TEORI 2.1 Kamus
5
2.2 Fitur atau Layanan Autocomplete
7
2.3 Algoritma Exact String Matching
8
2.4 Algoritma Boyer-Moore 2.4.1 Pergeseran Bad-Character
11
2.4.2 Pergeseran Good-Suffix
13
2.5 Penelitian Terdahulu
BAB 3
10
17
ANALISIS DAN PERANCANGAN SISTEM 3.1 Identifikasi Masalah
21
Universitas Sumatera Utara
viii
3.2 Analisis Data
21
3.3 Analisis Sistem
22
3.3.1 Penerapan algoritma Boyer-Moore untuk menampilkan autocomplete
22
3.3.2 Perhitungan algoritma Boyer-Moore
24
3.4 Perancangan Sistem
BAB IV
32
IMPLEMENTASI DAN PENGUJIAN SISTEM 35
4.1 Implementasi Sistem 4.1.1 Spesifikasi software dan hardware yang digunakan
35
4.1.2 Implementasi antarmuka sistem
35
4.1.3 Implementasi data
38
4.1.4 Implementasi pencocokan string
39
4.1.5 Implementasi fungsi autocomplete
47
4.2 Evaluasi Pengujian Sistem
BAB V
51
4.2.1 Rencana pengujian sistem
51
4.2.2 Hasil pengujian sistem
52
KESIMPULAN DAN SARAN 5.1 Kesimpulan
53
5.2 Saran
53
DAFTAR PUSTAKA
55
Universitas Sumatera Utara
ix
DAFTAR TABEL
Hal Tabel 2.1 Penelitian terdahulu yang berkaitan dengan autocomplete
18
Tabel 2.2 Penelitian terdahulu yang menggunakan algoritma Boyer-Moore
20
Tabel 4.1 Rangkuman database pada sistem
39
Tabel 4.2 Rencana pengujian sistem
52
Tabel 4.3 Hasil pengujian sistem
52
Universitas Sumatera Utara
x
DAFTAR GAMBAR
Hal Gambar 2.1 Autocomplete pada Google Search
8
Gambar 2.2 Pencocokan dari karakter paling kiri ke karakter paling kanan pattern
9
Gambar 2.3 Pencocokan dari karakter paling kanan ke karakter paling kiri pattern
9
Gambar 2.4 Pencocokan pada pattern y2 dimulai dari karakter paling kiri
10
Gambar 2.5 Pencocokan pada pattern y1 dimulai dari karakter paling kanan
10
Gambar 2.6 Pergeseran bad-character, a muncul pada y
12
Gambar 2.7 Pergeseran bad-character, tidak ada kemunculan a pada y
12
Gambar 2.8 Pergeseran good-suffix, v muncul didahului oleh karakter c
13
Gambar 2.9 Pergeseran good-suffix, hanya akhiran dari v yang muncul pada y
13
Gambar 3.1 Flowchart sistem
23
Gambar 3.2 Rancangan tampilan utama sistem
32
Gambar 3.3 Tampilan untuk abbreviations used
33
Gambar 3.4 Tampilan untuk fungsi autocomplete
34
Gambar 4.1. Tampilan awal aplikasi kamus
36
Gambar 4.2 Tampilan Abbrevation Used
37
Gambar 4.3 Tampilan untuk fungsi autocomplete
37
Gambar 4.4. Tampilan untuk informasi kata
38
Gambar 4.5 (a) Tabel bad-character untuk ‘com’
40
Gambar 4.5 (b) Tabel good-suffix untuk ‘com’
40
Gambar 4.6 (a) Tabel bad-character untuk ‘proc’
40
Gambar 4.6 (b) Tabel good-suffix untuk ‘proc’
41
Gambar 4.7 (a) Tabel bad-character untuk ‘prco’
41
Gambar 4.7 (b) Tabel good-suffix untuk ‘prco’
42
Gambar 4.8 Pencocokan string ‘com’ terhadap string target
42
Gambar 4.8(a) Pencocokan pertama dimulai pada indeks ke-2 dari string target
43
Gambar 4.8(b) Pencocokan kedua dimulai pada indeks ke-5 dari string target
43
Gambar 4.8(c) Pencocokan ketiga dimulai pada indeks ke-7 dari string target
44
Gambar 4.9 Pencocokan string ‘proc’ terhadap string target
44
Universitas Sumatera Utara
xi
Gambar 4.9(a) Pencocokan pertama dimulai pada indeks ke-3 dari string target
45
Gambar 4.9(b) Pencocokan kedua dimulai pada indeks ke-5 dari string target
45
Gambar 4.9(c) Pencocokan ketiga dimulai pada indeks ke-8 dari string target
45
Gambar 4.9(c) Pencocokan ketiga dimulai pada indeks ke-8 dari string target
46
Gambar 4.10 Pencocokan string ‘prco’ terhadap string target
46
Gambar 4.10(a) Pencocokan pertama dimulai pada indeks ke-3 dari string target
47
Gambar 4.10(b) string ‘prco’telah melewati string ‘access’
47
Gambar 4.11. Hasil pencocokan untuk input ‘com’
48
Gambar 4.12 Fungsi autocomplete untuk input ‘com’
48
Gambar 4.13 Hasil pencocokan untuk input ‘proc’
49
Gambar 4.14 Fungsi autocomplete untuk input ‘proc’
50
Gambar 4.15 Hasil pencocokan untuk input ‘prco’
50
Gambar 4.16 Fungsi autocomplete untuk input ‘prco’
51
Universitas Sumatera Utara
