AndiEkoSuryono (2008) Pengembangan Aplikasi Katalog File MP3 Menggunakan Algoritma Pencocokan Pola dengan Menggunakan Nondeterministic Finite Automata Boyer-Moore. Sarjana thesis, Universitas Brawijaya.
Abstract
Pencarian data teks dapat dilakukan dengan menggunakan beberapa algoritma String Matching, diantaranya adalah Brute Force, Knuth-Morris-Pratt, Karp-Rabin, dan Reverse Factor. Algoritma String Matching Boyer-Moore sering digunakan karena memiliki waktu proses yang secara praktis lebih cepat. Namun algoritma Boyer-Moore hanya dapat digunakan untuk satu kata kunci. Untuk pencarian dengan beberapa kata kunci sekaligus, diperlukan algoritma Pattern Matching sebagai mesin pencari. Atas dasar ini diperlukan pembuatan mesin pencari untuk algoritma Pattern Matching yang bekerja menggunakan prinsip kerja algoritma Boyer-Moore. Pada skripsi ini digunakan algoritma Pattern Matching dengan menggunakan Nondeterministic Finite Automata (NFA) Boyer-Moore untuk pencarian data pada aplikasi katalog file MP3. NFA dimodifikasi untuk bekerja dengan algoritma Boyer- Moore, dimana pencarian dilakukan dari kanan ke kiri. Disini NFA dibangun terbalik terhadap kata kunci yang diberikan. Aplikasi katalog file MP3 melakukan pencarian file, pembacaan data dan penyimpanan data. Data yang digunakan dalam katalog adalah nama dan tag ID3 dari file MP3 yang disimpan dalam bentuk teks. Pengujian terhadap algoritma pencarian dilakukan dengan menggunakan data uji coba yang didasarkan pada data percobaan yang dilakukan oleh Thierry Lecroq pada tahun 1997. Hasil percobaan pada data sebesar 25 juta karakter menunjukkan bahwa algoritma Pattern Matching dengan NFA Boyer-Moore bekerja dalam waktu 28 ms, algoritma Brute Force membutuhkan waktu 187,6 ms, sementara algoritma Knuth- Morris-Pratt membutuhkan waktu 228,2 ms. Waktu pencarian tersebut didapatkan ketika pola pencarian yang diberikan berada antara 64 sampai dengan 128 karakter. Disimpulkan bahwa algoritma Pattern Matching menggunakan NFA Boyer-Moore bekerja dengan baik pada pola pencarian sepanjang 64 sampai dengan 128 karakter bila dibandingkan dengan algoritma Brute Force dan algoritma Knuth-Morris-Pratt. Kata.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/FT/2008/255/050801346 |
| Subjects: | 600 Technology (Applied sciences) > 621 Applied physics > 621.3 Electrical, magnetic, optical, communications, computer engineering; electronics, lighting |
| Divisions: | Fakultas Teknik > Teknik Elektro |
| Depositing User: | Endang Susworini |
| Date Deposited: | 08 May 2008 10:24 |
| Last Modified: | 08 May 2008 10:24 |
| URI: | http://repository.ub.ac.id/id/eprint/139107 |
Actions (login required)
 |
View Item |