DETAIL KOLEKSI

Perbandingan algoritma naive brute force, algoritma knuth morris pratt, dan algoritma boyer moore dalam pencocokan string berbasis teks


Oleh : R. Aryo Bayu Bimantara

Info Katalog

Penerbit : FTI - Usakti

Kota Terbit : Jakarta

Tahun Terbit : 2005

Pembimbing 1 : Abdul Rochman

Subyek : Computer - Assisted instruction;Web-based instruction

Kata Kunci : algorithm comparison, force, morris pratt, boyer moore, string, matching, text.

Saat ini file hanya dapat diakses dari perpustakaan.

Status : Lengkap

P Pencocokan String merupakan teknik pencarian yang digunakan dalam pencarian pola String tertentu dalam sebuah teks. Ada beberapa algoritma yang digunakan untuk menjalankan proses pencocokan String tersebut, antara lain, Algoritma Naive Brute Force, •Knuth Morris Pratt serta Boyer Moore.Walaupun memiliki tujuan yang sama, namun ketiga algoritma tersebut memiliki langkah - langkah yang berbeda dalam pelaksanaannya. Untuk itu dilakukanlah suatu perbandingan dengan tujuan mengetahui kelebihan serta kelemahan yang ada.Ketiga algoritma tersebut akan dilakukan proses pencocokan String pada teks yang sama. Banyaknya membandingkan karakter ( komparasi) dan waktu eksekusi akan menjadi faktor pembanding dari ketiga algoritma yang dimaksud.Dari uji coba yang dilakukan dengan dokumen acak dan dokumen berpola dihasilkanlah suatu data, yang jika dilihat dari segi waktu eksekusi bahwa algoritma Boyer Moore memiliki waktu eksekusi yang paling cepat. Kemudian jika dilihat dari segi komparasi algoritma Knuth Morris Pratt memiliki jumlah komparasi yang paling sedikit. Dan dapat disimpulkan pula bahwa waktu eksekusi berbanding lurus terhadap jumlah komparasi, kecuali untuk algoritma Knuth Morris Pratt yang waktu eksekusi tidak berbanding lurus terhadap komparasi.

S String matching method is a kind of searching technique which is use to find a certain tring pattern in a text document. There are many algorithms which can be used to run this string matching process, Nai\'ve Brute Force Algorithm , Knuth Morris Pratt Algorithm and Boyer Moore Algorithm.Even though it has a same goal, but every algorithm has different ways in eachprocess . Therefore, it should do a comparison between each other to know more or less in every each other.Every algorithm will run a same document and proceed string matching in that document. Times to comparison character and the execution time will be comparisons result from each algorithm.From the test that have been done with random documents and pattern documentsit resulted a data. Which is can be seen from the running time, Boyer moore has the fastest running time during the execution. And then Which is can be seen from the comparisons, Knuth Morris Pratt has the smallest comparison during the execution. From the tests that have been done, there is a conclusion can be take, running time doesn \'t equally with comparisons.

Bagaimana Anda menilai Koleksi ini ?