PERBANDINGAN STRING MATCHING ALGORITMA QUICK SEARCH DENGAN ALGORITMA BERRY RAVINDRAN PADA APLIKASI KAMUS BAHASA INDONESIA – PERANCIS BERBASIS WEB
SKRIPSI
NADHIRA DWI SABRINA 121401084
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2017
Universitas Sumatera Utara
PERBANDINGAN STRING MATCHING ALGORITMA QUICK SEARCH DENGAN ALGORITMA BERRY RAVINDRAN PADA APLIKASI KAMUS BAHASA INDONESIA – PERANCIS BERBASIS WEB
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
NADHIRA DWI SABRINA 121401084
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2017
Universitas Sumatera Utara
PERSETUJUAN
Judul
: PERBANDINGAN STRING MATCHING ALGORITMA QUICK SEARCH DENGAN ALGORITMA BERRY RAVINDRAN PADA APLIKASI KAMUS BAHASA INDONESIA – PERANCIS BERBASIS WEB
Kategori
: SKRIPSI
Nama
: NADHIRA DWI SABRINA
Nomor Induk Mahasiswa : 121401084 Program Studi
: S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Amalia, S.T, M.T
Prof. Dr. Iryanto, M.Si.
NIP. 197812212014042001
NIP. 194604041971071001
Diketahui/disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom. NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
PERBANDINGAN STRING MATCHING ALGORITMA QUICK SEARCH DENGAN ALGORITMA BERRY RAVINDRAN PADA APLIKASI KAMUS BAHASA INDONESIA – PERANCIS BERBASIS WEB
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing – masing telah disebutkan sumbernya.
Medan,
Nadhira Dwi Sabrina 121401084
Universitas Sumatera Utara
UCAPAN TERIMA KASIH
Alhamdulillah. Segala puji dan syukur penulis ucapkan kepada Allah SWT yang telah memberikan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan penyusunan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Ucapan terima kasih penulis berikan kepada pihak yang telah memberikan dukungan dan dorongan kepada penulis, baik secara materil maupun moril dan baik secara langsung maupun tidak langsung. Pada kesempatan ini, penulis ingin mengucapkan terima kasih kepada:
1.
Bapak Prof. Dr. Runtung Sitepu, S.H, M.Hum selaku Rektor Universitas Sumatera Utara.
2.
Bapak Prof. Dr. Opim Salim Sitompul, M.Si. selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
3.
Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
4.
Bapak Prof. Dr. Iryanto, M.Si. selaku Dosen Pembimbing I yang telah banyak memberikan bimbingan, saran, dan dukungan kepada penulis dalam pengerjaan skripsi ini.
5.
Ibu Amalia, S.T, M.T selaku Dosen Pembimbing II yang telah banyak memberikan bimbingan, saran, dan dukungan kepada penulis dalam pengerjaan skripsi ini.
6.
Bapak Dr. Syahril Efendi, S.Si, M.IT selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
7.
Bapak Drs. Dahlan Sitompul, M.Eng selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
8.
Seluruh tenaga pengajar dan pegawai Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
Universitas Sumatera Utara
9.
Keluarga besar penulis yang selalu memberikan doa, dukungan, dan dorongan tiada henti, kepada Ayahanda (alm.) Ir. Mochammad Sjofian Sihombing, Ibunda Sri Wita Siregar, S.H, serta kakak dan adik tersayang, Sheila Eka Putri, M.Si. dan Azzahra Tri Najla.
10. Teman – teman seperjuangan tingkat akhir, Adhee Mohammad Rizky, Aisyatu Rabbiah, S.Ked, Aulia Rahman, Cut Amelinda Shafira, Dea Pratiwi Akbari, Marisa Handiani Putri Siregar, Monica Maulidia Anilza, S.Hum, Rahmi Sari Marina Daulay, A.Md, Rika Pebriyanti, S.Pd., Tengku Mutiara Azti, dan Zahara Marhamah Siregar, S.Pd. yang selalu memberikan semangat dan dorongan. 11. Teman – teman semasa kuliah dan seperjuangan skripsi, S1 Ilmu Komputer stambuk 2012 dan Kom B, khususnya kepada Jeklin Indriani Purba, S.Kom, Johan Surya, S.Kom, Novia Anggraini, Neno Rama Dhianita, S.Kom, Robes Nudson Purba, dan Said Muhammad Mahfuz yang telah banyak memberikan semangat. 12. Rekan – rekan pengurus organisasi Ikatan Mahasiswa S1 Ilmu Komputer (Imilkom) periode 2015/2016 yang banyak memberikan pembelajaran organisasi dan manajemen kehidupan kampus. 13. Adik – adik junior kampus, terkhusus untuk Akhmad Yusuf Ritonga, Khairina Syafitri, Kiki Nurlailani Hutabarat, Kiky Farida Simbolon, Nadia Al Karina, dan Rizky Hakim Lubis yang selalu memberikan semangat dan keceriaan kepada penulis. 14. Semua pihak yang telah banyak membantu dalam pengerjaan skripsi ini yang tidak bisa disebutkan satu-persatu. Semoga Allah SWT melimpahkan berkah-Nya kepada seluruh pihak yang telah membantu, memberikan doa, dan semangat kepada penulis selama pengerjaan skripsi. Medan, 16 November 2016 Penulis,
Nadhira Dwi Sabrina 121401084
Universitas Sumatera Utara
ABSTRAK
Membuat aplikasi kamus dengan menggunakan metode pencocokan string (string matching) dapat diimplementasikan untuk proses pencarian kata. String matching adalah sebuah proses pencarian tempat dari satu atau beberapa string yang ditemukan dalam sebuah kumpulan string atau teks. String matching memiliki beberapa algoritma, beberapa diantaranya adalah algoritma Quick Search dan algoritma Berry Ravindran. Kedua algoritma ini akan diimplementasikan dan dibandingkan hasilnya, baik dari segi kecepatan waktu proses (running time) dan kompleksitas algoritma. Algoritma Quick Search dan algoritma Berry Ravindran masing-masing memiliki dua fase, yaitu fase preprocessing dan fase pencarian. Fase preprocessing merupakan proses untuk membuat nilai pergeseran yang akan digunakan pada fase pencarian. Nilai pergeseran didapat dari aturan masing-masing algoritma tersebut. Setelah didapatkan nilai pergeseran, maka akan berlanjut pada proses pencarian teks yang aturan pengecekan karakternya didasarkan pada nilai pergeseran tersebut. Algoritma Quick Search akan bergeser sejauh satu karakter dari karakter paling kanan, sedangkan algoritma Berry Ravindran bergeser sejauh dua karakter dari karakter paling kanan. Proses pencarian pattern ini akan berhenti bergeser saat pattern telah ditemukan pada teks. Hasil dari penelitian ini menunjukkan bahwa algoritma Quick Search dan algoritma Berry Ravindran dapat diimplementasikan dalam proses pencocokan string dan berjalan dengan baik. Pada penelitian ini dapat disimpulkan bahwa running time dari algoritma Quick Search lebih cepat dibandingkan algoritma Berry Ravindran serta kompleksitas algoritma Quick Search lebih kecil dari algoritma Berry Ravindran. Rata-rata total running time untuk algoritma Quick Search adalah 0,081 ms dan algortima Berry Ravindran adalah 42,267 ms. Kompleksitas algoritma Quick Search adalah 𝑶 (𝑛) dan algoritma Berry Ravindran adalah 𝑶 (𝑚𝑛). Kata Kunci : String Matching, Web, Quick Search, Berry Ravindran.
Universitas Sumatera Utara
STRING MATCHING COMPARISON OF QUICK SEARCH ALGORITHM WITH BERRY RAVINDRAN ALGORITHM ON INDONESIA – FRENCH WEB BASED DICTIONARY APPLICATION
ABSTRACT
Process of making the dictionary with string matching methode can be implemented for word searching process. String matching is a place searching process from one or some string which found in a whole string or text. String matching has some algorithm, like Quick Search algorithm and Berry Ravindran algorithm. Both of these algorithm will be implemented and the result will be compared, even from running time process and algorithm complexity. Both of these algorithm have two phase, that are preprocessing process and searching process. Preprocessing process is a process for making the suitable friction numbers. Friction numbers can be built from each rules of algorithms. After friction numbers are available, that will be continue on word searching process which the rule’s character checking is based on the friction numbers. Quick Search algorithm will make a shift as far as one character from the rightmost, while Berry Ravindran algorithm make a shift as far as two characters from the rightmost. This pattern searching process will stop if pattern has been found. The result of this research is Quick Search and Berry Ravindran algorithm can be implemented in string matching process and work well. This research can be concluded that the running time from Quick Search algorithm is faster than Berry Ravindran algorithm and the algorithm complexity of Quick Search is smaller than Berry Ravindran algorithm. The average total running time for Quick Search algorithm is 0,081 ms and Berry Ravindran is 42,267 ms. Algorithm complexity of Quick Search is 𝑶 (𝑛) and Berry Ravindran algorithm is 𝑶 (𝑚𝑛).
Keywords : String Matching, Web, Quick Search, Berry Ravindran.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan
ii
Pernyataan
iii
Ucapan Terima Kasih
iv
Abstrak
vi
Abstract
vii
Daftar Isi
viii
Daftar Tabel
xi
Daftar Gambar
xiii
Daftar Lampiran
xiv
BAB 1.
BAB 2.
PENDAHULUAN 1.1. Latar Belakang
1
1.2. Rumusan Masalah
3
1.3. Ruang Lingkup Penelitian
3
1.4. Tujuan Penelitian
3
1.5. Manfaat Penelitian
3
1.6. Metodologi Penelitian
4
1.7. Sistematika Penulisan
5
LANDASAN TEORI 2.1. Pengertian Aplikasi Berbasis Web
6
2.2. Pengertian Kamus
6
2.3. Pengertian Pencocokan String (String Matching)
7
2.4. Pengertian Algoritma
8
2.4.1. Algoritma pencocokan string (string matching)
8
2.4.1.1. Algoritma Quick Search
8
2.4.1.2. Algoritma Berry Ravindran
12
2.5. Penelitian yang Relevan
19
Universitas Sumatera Utara
BAB 3.
ANALISIS DAN PERANCANGAN 3.1. Analisis Sistem
20
3.1.1. Analisis masalah
20
3.1.2. Analisis persyaratan
22
3.1.2.1. Persyaratan fungsional
22
3.1.2.2. Persyaratan non-fungsional
22
3.1.3. Analisis proses
23
3.2. Perancangan Sistem
BAB 4.
24
3.2.1. General Arsitektur Sistem
24
3.2.2. Use Case Diagram
25
3.2.3. Activity Diagram
27
3.2.4. Sequence Diagram
29
3.2.5. Flowchart
29
3.3. Pseudocode
34
3.4. Perancangan Antarmuka Sistem (System Interface)
36
3.4.1. Rancangan Halaman Utama
37
3.4.2. Rancangan Halaman Kamus
38
3.4.3. Rancangan Halaman Tentang
39
IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1. Implementasi Sistem
41
4.1.1. Halaman Utama
41
4.1.2. Halaman Kamus
42
4.1.3
42
Halaman Tentang
4.2. Pengujian Sistem
43
4.2.1. Pengujian pencarian kata dengan Algoritma Quick
43
Search 4.2.2. Pengujian pencarian kata dengan Algoritma Berry
45
Ravindran 4.3. Hasil Pengujian Sistem
48
4.4. Kompleksitas Algoritma
53
4.4.1. Kompleksitas Algoritma Quick Search
53
4.4.2. Kompleksitas Algoritma Berry Ravindran
55
Universitas Sumatera Utara
BAB 5.
KESIMPULAN DAN SARAN 5.1. Kesimpulan
57
5.2. Saran
58
DAFTAR PUSTAKA
59
LAMPIRAN Listing Program
A-1
Daftar Riwayat Hidup
B-1
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1.
Nilai pergeseran karakter [𝑐] bernilai 𝑚 + 1
9
Tabel 2.2.
Nilai pergeseran karakter [𝑐] bernilai 𝑚 − 1
10
Tabel 2.3.
Tabel nilai pergeseran fase preprocessing algoritma
10
Quick Search Tabel 2.4.
Fase pencarian teks
11
Tabel 2.5.
Fase pencarian teks (a)
11
Tabel 2.6.
Fase pencarian teks (b)
11
Tabel 2.7.
Fase pencarian teks (c)
12
Tabel 2.8.
Nilai pergeseran karakter [𝑎, 𝑏] bernilai 𝑚 + 2
14
Tabel 2.9.
Nilai pergeseran karakter 𝑏 = 𝑥[0] bernilai 𝑚 + 1
14
Tabel 2.10.
Nilai pergeseran karakter 𝑏 = 𝑥[0] bernilai 𝑚 + 1 (a)
15
Tabel 2.11.
Nilai pergeseran karakter [𝑎, 𝑏] adalah 𝑥[𝑖] dan 𝑥[𝑖 + 1]
15
bernilai 𝑚 − 𝑖 Tabel 2.12.
Nilai pergeseran karakter [𝑎, 𝑏] adalah 𝑥[𝑖] dan 𝑥[𝑖 + 1]
16
bernilai 𝑚 − 𝑖 (a) Tabel 2.13.
Nilai pergeseran karakter [𝑎, 𝑏] adalah 𝑥[𝑖] dan 𝑥[𝑖 + 1]
16
bernilai 𝑚 − 𝑖 (b) Tabel 2.14.
Nilai pergeseran karakter 𝑎 bernilai 𝑥[𝑚 − 1]
17
Tabel 2.15.
Tabel nilai pergeseran pada fase preprocessing algoritma
17
Berry Ravindran Tabel 2.16.
Fase pencarian teks
17
Tabel 2.17.
Fase pencarian teks (a)
18
Tabel 2.18.
Fase pencarian teks (b)
18
Tabel 2.19.
Fase pencarian teks (c)
18
Tabel 3.1.
Tabel Skenario Use Case proses menentukan jenis
27
terjemahan Tabel 3.2.
Tabel Skenario Use Case proses memasukkan kata
27
Universitas Sumatera Utara
Tabel 3.3.
Keterangan rancangan halaman utama
38
Tabel 3.4.
Keterangan rancangan halaman kamus
39
Tabel 3.5.
Keterangan rancangan halaman tentang
40
Tabel 4.1.
Pengujian sistem pencocokan string dengan Algoritma
43
Quick Search Tabel 4.2.
Pengujian sistem pencocokan string dengan Algoritma
46
Berry Ravindran Tabel 4.3.
Hasil pengujian Algoritma Quick Search
49
Tabel 4.4.
Hasil pengujian Algoritma Berry Ravindran
49
Tabel 4.5.
Hasil pengujian pencarian kata terpanjang
50
Tabel 4.6.
Hasil pengujian pencarian kata terpendek
50
Tabel 4.7.
Kompleksitas fungsi fase preprocessing Algoritma
53
Quick Search Tabel 4.8.
Kompleksitas fungsi fase pencarian Algoritma Quick Search
54
Tabel 4.9.
Kompleksitas fungsi fase preprocessing Algoritma
55
Berry Ravindran Tabel 4.10.
Kompleksitas fungsi fase pencarian Algoritma Berry
56
Ravindran
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1.
Fase preprocessing algoritma Quick Search
9
Gambar 2.2.
Fase preprocessing algoritma Berry Ravindran
13
Gambar 3.1.
Diagram Ishikawa untuk analisis masalah
21
Gambar 3.2.
General arsitektur sistem
25
Gambar 3.3.
Use Case Diagram sistem
26
Gambar 3.4.
Activity Diagram sistem
28
Gambar 3.5.
Sequence Diagram sistem
29
Gambar 3.6.
Flowchart tampilan sistem
30
Gambar 3.7.
Flowchart fase preprocessing Algoritma Quick Search
31
Gambar 3.8.
Flowchart fase pencarian Algoritma Quick Search
32
Gambar 3.9.
Flowchart fase preprocessing Algoritma Berry Ravindran
33
Gambar 3.10. Flowchart fase pencarian Algoritma Berry Ravindran
34
Gambar 3.11. Pseudocode fase preprocessing Algoritma Quick Search
35
Gambar 3.12. Pseudocode fase pencarian Algoritma Quick Search
35
Gambar 3.13. Pseudocode fase preprocessing Algoritma Berry Ravindran
36
Gambar 3.14. Pseudocode fase pencarian Algoritma Berry Ravindran
36
Gambar 3.15. Rancangan tampilan halaman utama
37
Gambar 3.16. Rancangan tampilan halaman kamus
38
Gambar 3.17. Rancangan tampilan halaman tentang
39
Gambar 4.1.
Halaman Utama
41
Gambar 4.2.
Halaman Kamus
42
Gambar 4.3.
Halaman Tentang
42
Gambar 4.4.
Perbandingan hasil running time Algoritma Quick Search
51
dan Algoritma Berry Ravindran Gambar 4.5. Perbandingan hasil running time pencarian kata terpanjang
52
Gambar 4.6. Perbandingan hasil running time pencarian kata terpendek
52
Universitas Sumatera Utara
DAFTAR LAMPIRAN
Halaman Lampiran 1
Listing Program
A-1
Lampiran 2
Daftar Riwayat Hidup
B-1
Universitas Sumatera Utara
