String Matching Algoritmalarının Uygulamalı Karşılaştırılması

Year 2023, Volume: 12 Issue: 1, 76 - 85, 30.06.2023

Zeynep Barut , Volkan Altuntaş

Abstract

Belirli bir string içerisinde bir pattern bulunması gerektiğinde, String matching algoritmaları kullanılır. Bu araştırmanın amacı güncel algoritmaların temel fikirlerini, karmaşıklıklarını açıklamak ve uygulamalı karşılaştırmasını gerçekleştirmektir. String matching için kullanılan birçok algoritma vardır. Bu çalışmada Knuth-Morris-Pratt, Rabin Karp ve Boyer Moore Horspool algoritmaları karşılaştırılmıştır. Farklı yapıdaki algoritmalar seçilerek çalışmanın doğruluğunun arttırılması amaçlanmıştır. Algoritmaların temel fikirleri, olası zorlukları ve karmaşıklıkları açıklanarak, bu sorunların nasıl çözülebileceği üzerinde durulmuştur. Yapılan çalışmalar sonucunda Knuth-Morris-Pratt algoritmasının çoğu durumda diğer algoritmalardan daha iyi performans gösterdiği görülmüştür. En iyi ikinci performansı gösteren algoritma Boyer Moore Horspool algoritması, en kötü performansı gösteren algoritma ise Rabin Karp algoritması olmuştur.

Keywords

String matching, DNA sekansı, Gen analizi

Applied Comparison of String Matching Algorithms

Abstract

String matching algorithms are used when a pattern needs to be found in a particular string. The aim of this research is to explain the basic ideas and complexities of current algorithms and to make an applied comparison. There are many algorithms used for string matching. In this study, Knuth-Morris-Pratt, Rabin Karp and Boyer Moore Horspool algorithms were compared. It is aimed to increase the accuracy of the study by choosing different algorithms. By explaining the basic ideas, possible difficulties and complexities of the algorithms, it is emphasized how these problems can be solved. As a result of the studies, it has been seen that the Knuth-Morris-Pratt algorithm outperforms other algorithms in most cases. The second best performing algorithm was Boyer Moore Horspool algorithm, and the worst performing algorithm was Rabin Karp algorithm.

Keywords

String matching, DNA sequence, Gene analysis

References

• Alshahrani, A.M., Khalil, M.I., 2022. Exact and Like String Matching Algorithm for Web and Network Security. 2013 World Congress on Computer and Information Technology (WCCIT).
• Anonymous. Index of bucket tripdata, https://s3.amazonaws.com/tripdata/index.html. Accessed: 29 January 2023.
• Anonymous. Rabin - Karp Algorithm, https://www.programiz.com/dsa/rabin-karp-algorithm. Accessed: 29 January 2023.
• Biçer, M., Zhang, X., 2019. An Efficient, Hybrid, Double-Hash String Matching Algorithm. 2019 IEEE Long Island Systems, Applications and Technology Conference (LISAT).
• Hakak, S.I., Kamsın, A., Shıvakumara, P., Gılkar, G.A., Khan, W.Z., Imran, M., 2019. Exact String Matching Algorithms: Survey, Issues, and Future Research Directions. Special Section On New Trends in Brain Signal Processing and Analysis, 7, 69614-69637.
• Islam, T., Talukder, K.H., 2017. An Improved Algorithm for String Matching using Index Based Shifting Approach. 20th International Conference of Computer and Information Technology (ICCIT), 22-24 December.
• Kanuga, P., 2015. New Shift table Algorithm For Multiple Variable Length String Pattern Matching. 2015 International Conference on Circuit, Power and Computing Technologies [ICCPCT].
• Mathur, T., 2022. KMP Algorithm, https://www.scaler.com/topics/data-structures/kmp-algorithm/. Accessed: 29 January 2023.
• Navarro, G., 2001. A Guided Tour to Approximate String Matching. ACM Computer Surveys, 33(1), 31-88.
• Pop, P. G., 2015. DNA Repeats Detection Using a Dedicated Dot-Plot Analysis. 2015 38th International Conference on Telecommunications and Signal Processing (TSP).
• Saldana, F., 2021. The Boyer-Moore-Horspool Algorithm, https://www.encora.com/insights/the-boyer-moore-horspool-algorithm. Accessed: 29 January 2023.
• Singla, N., Garg, D., 2012. String Matching Algorithms and their Applicability in various Applications. International Journal of Soft Computing and Engineering (IJSCE), 1(6), 218-222.
• Tripathi, S., Pandey, A. K., 2016. Identifying DNA Sequence by using Stream Matching Techniques. 5th International Conference on System Modeling & Advancement in Research Trends, 25th_27'h November, 334-338.
• Yuan, L., 2011. An Improved Algorithm for Boyer-Moore String Matching in Chinese Information Processing. 2011 International Conference on Computer Science and Service System (CSSS), 182-184.