Applied Comparison of String Matching Algorithms
Zeynep BARUT, Volkan Altuntaş · DergiPark (Istanbul University) · 2023
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.