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

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.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.