SKRIPSI TEUKU IGHFAR HAJAR

IMPLEMENTASI ALGORITMA LEVENSHTEIN DISTANCE DAN BOYER MOORE UNTUK FITUR AUTOCOMPLETE DAN AUTOCORRECT PADA APLIKASI KATALOG PERPUSTAKAAN DAERAH ACEH TIMUR

SKRIPSI

TEUKU IGHFAR HAJAR 131421063

PROGRAM STUDI S1 EKSTENSI ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015

Universitas Sumatera Utara

IMPLEMENTASI ALGORITMA LEVENSHTEIN DISTANCE DAN BOYER MOORE UNTUK FITUR AUTOCOMPLETE DAN AUTOCORRECT PADA APLIKASI KATALOG PERPUSTAKAAN DAERAH ACEH TIMUR

SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer

TEUKU IGHFAR HAJAR 131421063

PROGRAM STUDI S1 EKSTENSI ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015


PERSETUJUAN

Judul

: IMPLEMENTASI ALGORITMA LEVENSHTEIN DISTANCE DN BOYER MOORE UNTUK FITUR AUTOCOMPLETE DAN AUTOCORRECT PADA APLIKASI KATALOG PERPUSTAKAAN ACEH TIMUR Kategori : SKRIPSI Nama : TEUKU IGHFAR HAJAR Nomor Induk Mahasiswa : 131421063 Program Studi : SARJANA (S1) ILMU KOMPUTER Departemen : ILMU KOMPUTER Fakultas : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOMTI) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 2 Agustus 2015

Komisi Pembimbing Pembimbing 2

Maya Silvi Lydia, B.Sc, M.Sc NIP. 19740127 200212 2 001

: Pembimbing 1

Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001

Diketahui/Disetujui oleh Program Studi S1 Teknologi Informasi Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001


PERNYATAAN

IMPLEMENTASI ALGORITMA LEVENSHTEIN DISTANCE DAN BOYER MOORE UNTUK FITUR AUTOCOMPLETE DAN AUTOCORRECT PADA APLIKASI PERPUSTAKAAN DERAH ACEH TIMUR

SKRIPSI

Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, Juni 2015

Teuku Ighfar Hajar 131421063


PENGHARGAAN

Puji dan syukur kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Ny a, sehingga Penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi S1 Ilmu Komputer Universit as Sumatera Utara. Penulis ingin menyampaikan rasa hormat dan terima kasih yang sebesar–besar nya kepada :

1. Bapak Prof. Dr. Subhilhar, M.A., Ph.D. selaku Plt Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Muhammad Zarlis 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 dan Dosen Pembimbing I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini. 4. Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi S1 Ilmu Komputer Universitas Sumatera Utara dan sebagai Dosen Pembimbing II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.. 6. Bapak M. Andri Budiman, ST, M.Comp, Sc.M.E.M selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini. 7. Bapak Ade Candra ST, M.Kom selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini. 9. Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, seluruh tenaga pengajar serta pegawai di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 10. Ayahanda H. Bustami T. Ibrahim, S.Ag dan Ibunda Hj. Farida AR yang selalu memberikan doa dan dukungan serta kasih sayang kepada penulis, serta kakanda tersayang Miftahul Wardah, S.Si, Musriyani Safitri, S.Si, Teuku Muarrif Ikramullah, S.Kom dan adik tersayang Teuku Ichsanul Aulia yang terus memberikan dukungan dan dorongan bagi penulis untuk menyelesaikan skripsi ini.


11. Sahabat terbaik saya, terutama Satriyo Wibowo,Ryan Dhika Priyatna, Adli Abdillah Nababan, Ade Rizka, Nurul Zakya Haque,Fera Ferdian,Wiwin Agustini Lubis, Tiany Dwi Lestari, Ratno Zulita dan Tika Puspita Sari serta teman-teman seperjuangan yang sedang menyelesaikan skripsinya terutama stambuk 2013 terkhusus kom B atas semangat dan dorongannya dan Padlian Chairi yang membantu dalam menyelesaikan skripsi ini. 12. Buat Silvia Bilqis Magdalena yang selalu memberikan semangat dan dorongannya sehingga saya bersemangat dalam menyelesaikan skripsi saya ini. 13. Sahabat kecil saya, Sayed Multazam, Teuku Nazarullah dan Cahya Isna Kirani Lubis atas semangat dan dorongannya membantu dalam menyelesaikan skripsi ini. 14. Dan semua pihak yang telah banyak membantu yang tidak bisa disebutkan satu-persatu. Semoga semua kebaikan, bantuan, perhatian, serta dukungan yang telah diberikan kep ada penulis mendapatkan pahala yang melimpah dari Allah SWT.

Medan, Juni 2015

Penulis


ABSTRAK

Katalog perpustakaan adalah suatu media yang dapat menampilkan sejumlah data buku atau koleksi pada suatu perpustakaan. Dengan mencari judul buku pada katalog perpustakaan maka informasi mengenai judul buku yang dicari dapat diperoleh dengan mudah. Namun, terkadang dalam pengetikan judul buku terdapat kendala ketika ingin memperoleh informasi mengenai judul buku yang dicari. Kendala tersebut adalah kesalahan dalam pengetikan judul buku pada kotak pencarian. Kesalahan dalam pengetikan judul buku tersebut akan mengakibatkan informasi dari buku tersebut tidak dapat ditemukan. Oleh karena itu, diperlukan suatu aplikasi yang dapat membantu penguna ketika mengetikkan judul buku yang akan dicari seperti autocomplete dan autocorrect. Autocomplete merupakan suatu fitur atau layanan yang dapat menampilkan prediksi kata yang diketikkan belum lengkap, sedangkan autorrect merupakan suatu fitur/layanan yang dapat menampilkan perbaikan kata. Algoritma Levenshtein Distance merupakan algoritma pencocokan string berdasarkan pendekatan perkiraan dan digunakan untuk menampilkan autocorrect sedangkan algoritma Boyer Moore adalah algoritma pencocokan string berdasarkan lompatan dari setiap string yang digunakan untuk menghasilkan autocomplete. Keluaran yang dihasilkan dari sistem ini berupa prediksi judul buku yang diketikkan oleh pengguna

Kata kunci : Algoritma Levenshtein Distance, Algoritma Boyer Moore, Autocomplete, Autocorrect, katalog perpustakaan, Aceh Timur


Implementation Levenshtein Distance Algorithm and Boyer Moore for Autocomplete and Autocorrect Feature in Aceh Timur’s Library Catalog ABSTRACT

A library catalogue is a medium which can show some data, book, or collection in a library by searching for a title in the library catalogue. Therefore, the information connected to the title which the readers are looking for can be found easily. However, sometimes, there are some difficulties in searching some books by using its title. The difficulties are the type missing in the searching box. As a result, the book which is searched for cannot be found. Therefore, it is needed to create an application to help the users when they type the title of the book,with some essential feature such as auto complete and autocorrect. Autocomplete is a feature that can show missing word. Algorithm Levenshtein Distance is an algorithm which can match string based on hypotheses approach. Boyer Moore is used to make autocomplete. The output create from this system is a oprediction of the book’s title that is typed by the users. Keywords: Algorithm Levenshtein Distance, Algoritm Boyer Moore, Autocomplete, Autocorrect, Library catalogue, Aceh Timur


DAFTAR ISI

Halaman

PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR Bab 1

PENDAHULUAN 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Ruang Lingkup Penelitian 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan

BAB 2 LANDASAN TEORI 2.1 Katalog Perpustakaan 2.2 Fitur atau Layanan Autocomplete 2.3 Fitur atau Layanan Autocorrect 2.4 Approximate String Matching 2.4.1 Operasi penghapusan 2.4.2 Operasi penyisipan 2.4.3 Operasi penukaran 2.5 Algoritma Levenshtein Distance 2.6 Algoritma Boyer Moore 2.6.1 Cara Kerja Algoritma Boyer Moore 2.6.2 Prosedur Algoritma Boyer Moore 2.7 Penelitian Terdahulu

ii iii iv vi vii viii x xi

1 3 3 3 4 4 5

6 7 8 8 8 9 10 10 13 16 19 22


BAB 3 ANALISIS DAN PERANCANGAN SISTEM 3.1 Analisis Masalah 3.2 Analisis Kebutuhan Sistem 3.2.1 Kebutuhan fungsional sistem 3.2.2 Kebutuhan nonfungsional sistem 3.3 Pemodelan sistem 3.3.1 Use case Diagram 3.3.2 Activity Diagram 3.3.3 Sequence Diagram

BAB 4

24 25 25 26 27 27 29 31

3.4 Analisis Data

31

3.5 Perancangan Sistem 3.5.1 Flowchart sistem Autocomplete 3.5.2 Proses pencarian Boyer Moore untuk autocomplete 3.5.3 Flowchart sistem Autocorrect 3.5.4 Proses pencarian pada Levenshtein Distance untuk

34 34 35 40 41

3.6 Antarmuka Sistem 3.6.1 Flowchart Sistem 3.6.2 Rancangan Halaman Awal User 3.6.3 Rancangan Halaman Hasil pencarian Judul Buku 3.6.4 Rancangan Halaman Informasi Data Buku 3.6.5 Rancangan Halaman Login Admin 3.6.6 Rancangan Halaman Awal/Home Admin 3.6.7 Rancangan Halaman Daftar Buku 3.6.8 Rancangan Halaman Tambah Buku

51 52 53 53 54 54 55 55 56

IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1 Perhitungan Nilai Levenshtein Distance dan Boyer Moore pada Fitur Autocomplete dan Autocorrect secara manual 4.1.1 Perhitungan Nilai Levenshtein Distance Untuk Fitur Autocorrect 4.1.1.1 Potongan Program dari Metode Levenshtein Distance 4.1.2 Perhitungan Nilai Boyer Moore untuk Fitur Autocomplete 4.1.2.1 Potongan Program dari Metode Boyer Moore

4.2

57 57 59 61 65

Pengujian Sistem 4.2.1 Rencana Pengujian Sistem 4.2.2 Pengujian fungsi dasar sistem 4.2.3 Pengujian hasil pencarian autocorrect 4.2.4 Pengujian hasil pencarian autocomplete

67 67 68 69


4.3

Implementasi Perancangan Antarmuka 4.3.1 Tampilan halaman awal user 4.3.2 Tampilan halaman hasil pencarian judul buku 4.3.3 Tampilan halaman informasi data buku 4.3.4 Tampilan halaman login admin 4.3.5 Tampilan halaman awal admin 4.3.6 Tampilan halaman daftar buku 4.3.7 Tampilan halaman tambah buku 4.3.8 Tampilan halaman edit buku

69 70 70 71 71 72 73 73 74

BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran

75 76

DAFTAR PUSTAKA

77

LAMPIRAN


DAFTAR TABEL

Halaman

Tabel 2.1 Penelitian sebelumnya Tabel 3.1 Tabel Use Case Proses Pencarian Judul Buku Tabel 3.2 Keterangan Bagian-Bagian Rancangan Halaman Utama Tabel 3.3 Sampel Data Buku Tabel 3.4 Occurence Heuristic Tabel 3.5 Math Heuristic Tabel 3.6 Math Heuristic Tabel 4.1 Occurence Heuristic Tabel 4.2 Math Heuristic Tabel 4.3 Tabel nilai OH dan MH Tabel 4.4 Rencana Pengujian Sistem Tabel 4.5 Hasil Pengujian Fungsi Dasar Sistem Tabel 4.6 Pengujian Hasil pencarian Autocorrect Tabel 4.7 Pengujian Hasil pencarian Autocomplete

22 28 30 32 37 37 39 63 63 65 67 68 68 69


DAFTAR GAMBAR

Halaman Gambar 2.1 Ilustrasi Penggunaan Autocomplete Gambar 2.2 Ilustrasi Penggunaan Autocorrect Gambar 2.3 Good-Suffix shift u Gambar 2.4 Good-Suffix shift Gambar 2.5 Bad Character shift Gambar 2.6 Bad Character shift Gambar 2.7 Prosedur preBmBc algoritma Boyer Moore Gambar 2.8 Prosedur preBmGs algoritma Boyer Moore Gambar 3.1 Diagram Ishikawa untuk lingkup penelitian Gambar 3.2 Use case diagram Gambar 3.3 Activity diagram Gambar 3.4 Sequence diagram sistem Gambar 3.5 Flowchart sistem autocorrect Gambar 3.6 Pencocokan 1 Gambar 3.7 Pencocokan 2 Gambar 3.8 Pencocokan 3 Gambar 3.9 Proses pencarian Math Heuristic 1 Gambar 3.10 Proses pencarian Math Heuristic 2 Gambar 3.11 Proses pencarian Math Heuristic 3 Gambar 3.12 Proses pencarian Math Heuristic 4 Gambar 3.13 Flowchart sistem autocorrect Gambar 3.14 Flowchart sistem Gambar 3.15 Rancangan halaman awal Gambar 3.16 Rancangan halaman hasil pencarian judul buku Gambar 3.17 Rancangan halaman informasi data buku Gambar 3.18 Rancangan halaman login untuk admin Gambar 3.19 Rancangan halaman awal/home admin Gambar 3.20 Rancangan halaman daftar buku Gambar 3.21 Rancangan halaman tambah buku Gambar 4.1 Pencocokan 1 Gambar 4.2 Pencocokan 2 Gambar 4.3 Pencocokan 3 Gambar 4.4 Proses pencarian Math Heuristic 2 Gambar 4.5 Proses pencarian Math Heuristic 3 Gambar 4.6 Proses pencarian Math Heuristic 4 Gambar 4.7 Tampilan halaman awal user Gambar 4.8 Tampilan halaman hasil pencarian judul buku

7 8 14 14 15 15 19 21 25 27 29 31 34 35 36 36 38 38 38 39 40 52 53 53 54 54 55 55 56 61 62 62 64 64 65 67 67


Gambar 4.9 Tampilan halaman informasi data buku Gambar 4.10 Tampilan halaman login admin Gambar 4.11 Tampilan halaman awal admin Gambar 4.12 Tampilan halaman daftar buku Gambar 4.13 Tampilan halaman tambah buku Gambar 4.14 Tampilan halaman edit buku Gambar 4.15 Autocomplete untuk “panduan” Gambar 4.16 Autocorrect untuk “sehat”

68 69 69 70 70 71 72 73


SKRIPSI TEUKU IGHFAR HAJAR

Recommend Documents