A TRIE-HASHMAP APPROACH TO AFFIX SEARCH IN AVIATION MANAGEMENT SYSTEM

Queene Jasmine Delmarva, Azhari, Drs., MT., Dr

2023 | Skripsi | ILMU KOMPUTER

FL3XX, sebuah sistem manajemen penerbangan yang digunakan oleh pemilik pesawat untuk melindungi dan merawat pesawat mereka, menghadapi keterbatasan signifikan dalam fungsionalitas pencariannya. Keterbatasan-keterbatasan ini terutama terlihat saat menangani kesalahan penulisan (typo) dan pencarian dengan awalan yang lebih pendek. Untuk mengatasi tantangan-tantangan ini, penelitian ini memanfaatkan dataset dari Modul Dispatch FL3XX ACAM untuk menjelajahi algoritma trie, khususnya Radix Tries dan Hashmap-based Tries.

Tujuan utama dari penelitian ini adalah meningkatkan fitur pencarian dalam FL3XX dengan memperkenalkan fungsi autocomplete, pencarian kata kunci berdasarkan afiks, dan kemampuan autocorrect. Untuk mengevaluasi kinerja struktur data algoritma trie ini, penelitian ini melakukan analisis komprehensif. Ini mencakup penilaian skor kemiripan antara kata-kata yang salah ketik dan kata-kata dalam kamus, yang merupakan faktor kritis dalam akurasi autocorrect. Selain itu, evaluasi ini mencakup skor awalan (prefix) dan akhiran (suffix), yang berkontribusi dalam menghitung skor keseluruhan kemiripan antara kata-kata yang salah ketik dan kata-kata dalam kamus.

Hasil penelitian menemukan bahwa Radix Trie lebih unggul dibandingkan model lain dalam hal penggunaan ruang dan memori, hanya memerlukan 2.025 node dan 6.075 byte dari ukuran dataset sebesar 20.000. Sementara itu, Hashmap-based Trie unggul dalam kinerja waktu, saat mencari kata-kata 'fuel', 'soekarno', dan '0800z' bisa mencapai sekitar 0.000054 hingga 0.000111 detik. Selain itu, Hashmap-based Trie memiliki skor Mean Reciprocal Rank (MRR) yang lebih baik sebesar 0.9984, menunjukkan kesesuaian untuk aplikasi di mana akurasi pencarian sangat penting.

Meskipun temuan ini memberikan wawasan berharga dalam mengoptimalkan fungsionalitas pencarian dengan efisiensi waktu dan ruang, penelitian masa depan dapat lebih mendalami eksplorasi struktur data lain untuk mempertimbangkan algoritma alternatif seperti binary searh, tabel hash, atau suffix arrays. Selain itu, pendekatan hibrida dapat diselidiki untuk menggabungkan kelebihan dari beberapa struktur, mengurangi kelemahan masing-masing, dan mendorong batasan efisiensi pencarian dalam aplikasi manajemen penerbangan.

FL3XX, an aviation management system used by aircraft owners to protect and maintain their planes, faces significant limitations in its search functionality. These limitations are particularly noticeable when handling typos and shorter prefix searches. To address these challenges, this research leverages the dataset from ACAM's FL3XX Dispatch Module to explore trie algorithms, specifically Radix Tries and Hashmap-based Tries.

The primary aim of this research is to enhance the search feature within FL3XX by introducing autocomplete, affix-based keyword searches, and autocorrect capabilities. To evaluate the performance of these trie algorithmic data structures, the study conducts a comprehensive analysis. This includes an assessment of similarity scores between mistyped words and dictionary words, a critical factor in autocorrect accuracy. Furthermore, the evaluation incorporates prefix and suffix scores, which contribute to calculating the overall similarity score between mistyped and dictionary words.

The research results find that the Radix Trie outperforms other models in terms of space and memory consumption, requiring only 2,025 nodes and 6,075 bytes from a 20,000 dataset size. While the Hashmap-based Trie excels in time performance, when searching for the words ‘fuel’, ‘soekarno’ and ‘0800z’ could reach as low as 0.000054 to 0.000111 seconds. Furthermore, the Hashmap-based Trie has a better Mean Reciprocal Rank (MRR) score of 0.9984, indicating its suitability for applications where search accuracy is essential.

While these findings contribute valuable insights into optimizing search functionality with time and space efficiency. Future works can be further studied in the exploration of other data structures to consider alternative algorithms such as binary search, hash tables, or suffix arrays. Additionally, hybrid approaches can be investigated to combine the strength of multiple structures, reducing their respective disadvantages, and pushing the boundaries of search efficiency in aviation management applications.

Kata Kunci : Trie, Autocomplete, Autocorrect, Search, Performance