Analisis kinerja struktur data trie pada penyusunan kamus refensi

Abstract

Pada proses pemeriksaan ejaan, program pemeriksa ejaan memerlukan kamus referensi sebagai acuan dalam memeriksa ejaan setiap kata yang terdapat di dalam dokumen. Agar pemeriksa ejaan memiliki kinerja yang baik, maka diperlukan struktur data yang efisien untuk merepresentasikan kamus. Struktur data tersebut harus memungkinkan proses pencarian kata berjalan cepat dan dapat menghemat pemakaian ruang pada media penyimpan kamus. Dalam penelitian ini dilakukan perbandingan dua jenis representasi kamus yang menggunakan struktur data trie, yaitu trie yang menggunakan struktur data double-array (selanjutnya disebut trie-DA) dan trie yang menggunakan strukturdata list (selanjutnya disebut trie-list). Perbandingan dilakukan untuk melihat efisiensi kedua jenis representasi kamus, ditinjau dari waktu pencarian kata pada trie dan jumlah memori yang terpakai untuk merepresentasikan kamus oleh masing-masing frie. Pada pengujian yang dilakukan terhadap kedua jenis trie dengan menggunakan delapan kelompok kamus yang dibagi berdasarkan jumlah kata di dalam kamus, diperoleh hasil bahwa dalam hal besar ruang memori yang digunakan, kinerja.trie-DA. lebih baik dibandingkan frie-list,, yaitu membutuhkan, memori 39% hingga 71% lebih kecil dibandingkan nie-list. Namun waktu yang dibutuhkan trie-DA untuk menyusun kamus referensi lebih lama bila dibandingkan trie-list. Waktu rata-rata untuk penyusunan: kamus pada trie-list adalah 2 hingga 32 kali lebih cepat dibandingkan trie-DA. Sedangkan pada proses pencarian kata, waktu yang digunakan oleh frie-DA tidak berbeda nyata dengan waktu pencarian kata pada trie-list, sehingga antara kedua trie tersebut tidak ada yang memiliki waktu pencarian kata yang lebih :baik. Pada program pemeriksa ejaan, pemakaian ruang memori yang lebih kecil dan waktu pencarian kata yang lebih cepat sangat dibutuhkan. Dengan melihat pada kondisi ini, maka di antara kedua bentuk trie yang dibandingkan, trie-DA lebih baik dibandingkan trie-list. Namun demikian, penggunaan kedua jenis trie tersebut sepenuhnya tergantung pada kebutuhan pemakai.