Perbandingan Algoritma Boyer-Moore dan Brute Force pada Pencarian Kamus Besar Bahasa Indonesia Berbasis Android

  • Candra Irawan Universitas Muhammadiyah Jember
  • Mudafiq Riyan Pratama Politeknik Negeri Jember
Keywords: String Matching, Boyer-Moore, Brute Force, Pencarian, KBBI

Abstract

String matching is an algorithm for matching a text to another text or also known as a text search. There are several algorithms that can be used for string matching, including the Boyer-Moore algorithm and the Brute Force algorithm. The Boyer-Moore algorithm is a string matching algorithm published by Robert S. Boyer and J. Strother Moore in 1977. This algorithm is considered the most efficient algorithm in general applications. The Boyer-Moore algorithm starts matching characters from the pattern on the right. While the Brute Force algorithm is an algorithm that matches a pattern with all text between 0 and n-m to find the existence of a pattern in the text. These two algorithms have different patterns in the search process. In this article, a comparative analysis of the performance of the Boyer-Moore and Brute Force algorithms is carried out in a case study of the search for the Big Indonesian Dictionary (KBBI) based on Android. The search process is carried out by searching based on words and word descriptions. The results of this study indicate that the criteria for running time, the Brute Force algorithm is faster than the Boyer-Moore algorithm with the total running time of the Brute Force algorithm is 168.3 ms in words, 6994.16 ms in word descriptions, while the Boyer-Moore algorithm for running time reached 304.7 ms on the word, 8654.77 ms on the word description. In the testing criteria based on related keywords, the two algorithms can display the same list of related keywords.

References

[1] R. S. Boyer and J. S. Moore, “A Fast String Searching Algorithm,” Commun. ACM, vol. 20, no. 10, pp. 762–772, 1977.

[2] T. Bell, M. Powell, A. Mukherjee, and D. Adjeroh, “Searching BWT compressed text with the Boyer-Moore algorithm and binary search,” Data Compression Conf. Proc., vol. 2002-Janua, pp. 112–121, 2002.

[3] Tomy Satria Alasi, “Algoritma Boyer Moore Untuk Penyaringan Pesan Teks Menggunakan Perbandingan Kata Yang Sama,” Semin. Nas. Sains Teknol. Inf., pp. 488–495, 2018.

[4] A. Abimanyu, “Penerapan Algoritma String Matching pada Proses Penyaringan Teks,” 2019.

[5] M. Y. Soleh, “Implementasi Algoritma KMP dan Boyer-Moore dalam Aplikasi Search Engine Sederhana,” Makal. IF3051 Strateg. Algoritm., 2010.

[6] S. Kristanto, A. Rachmat, and R. G. Santosa, “Implementasi Algoritma Boyer-Moore Pada Permainan Word Search Puzzle,” no. September 2014, pp. 1–8, 2013.
Published
2021-02-11
Section
Articles