Desen Eşleştirme, bilgisayar bilimlerinde ve diğer birçok alanda yaygın olarak kullanılmaktadır. Desen Eşleştirme algoritmaları, daha büyük bir metin veya veri kümesi içindeki kalıpları aramak için kullanılır. Desen eşleştirme için en popüler algoritmalardan biri Boyer-Moore algoritması ilk kez 1977 yılında yayınlanmıştır. Bu yazımızda C'deki Desen Eşleştirme algoritmalarını ve nasıl çalıştıklarını ele alacağız.
Desen Eşleştirme Algoritması Nedir?
Desen Eşleştirme algoritmaları, daha büyük bir veri veya metin kümesi içindeki kalıpları bulmak için kullanılır. Bu algoritmalar, bir modeli daha büyük bir veri seti veya metinle karşılaştırarak ve modelin mevcut olup olmadığını belirleyerek çalışır. Desen Eşleştirme algoritmaları önemlidir çünkü büyük veri kümelerindeki kalıpları hızlı bir şekilde aramamıza olanak tanırlar.
kapsülleme java'sı
Kaba Kuvvet Desen Eşleştirme Algoritması:
Kaba Kuvvet Desen Eşleştirme, en basit Desen Eşleştirme Algoritmasıdır. Desendeki karakterlerin metindeki karakterlerle tek tek karşılaştırılmasını içerir. Tüm karakterler eşleşirse algoritma, metindeki desenin başlangıç konumunu döndürür. Değilse, algoritma metinde bir sonraki konuma geçer ve bir eşleşme bulunana veya metnin sonuna ulaşılana kadar karşılaştırmayı tekrarlar. Kaba Kuvvet Algoritmasının Zaman Karmaşıklığı Ç(MXN) , Neresi M metnin uzunluğunu belirtir ve N desenin uzunluğunu belirtir.
Naif Desen Eşleştirme Algoritması:
Naive Pattern Matching algoritması, Brute Force algoritmasına göre bir gelişmedir. Metindeki bazı yerleri atlayarak gereksiz karşılaştırmaların önüne geçer. Algoritma, deseni ilk konumda metinle karşılaştırmaya başlar. Karakterler eşleşirse bir sonraki konuma geçer ve karşılaştırmayı tekrarlar. Karakterlerin eşleşmemesi durumunda algoritma metindeki bir sonraki konuma geçer ve deseni tekrar metinle karşılaştırır. Naive algoritmasının zaman karmaşıklığı da Ç(MXN) ancak çoğu durumda Brute Force algoritmasından daha hızlıdır.
Knuth-Morris-Pratt Algoritması:
Knuth-Morris-Pratt (KMP) algoritması daha gelişmiş bir Desen Eşleştirme algoritmasıdır. Bir uyumsuzluk oluştuğunda gereksiz karşılaştırmalardan kaçınmak için metin ve kalıpla ilgili bazı bilgilerin kullanılabileceği gözlemine dayanmaktadır. Algoritma, model hakkında bilgi içeren bir tabloyu önceden hesaplar. Tablo, bir uyumsuzluk meydana geldiğinde desende kaç karakterin atlanabileceğini belirler. Zaman Karmaşıklığı KMP algoritma Ç(E+H) .
Boyer-Moore Algoritması:
En popüler Desen Eşleştirme algoritmalarından biri, Boyer-Moore algoritma. Bu algoritma ilk olarak 1977'de Robert S. Boyer ve J Strother Moore tarafından yayınlandı. Boyer-Moore Algoritma, diğer desen eşleştirme algoritmalarının çoğunda olduğu gibi, bir modeli daha büyük bir veri veya metin kümesiyle soldan sağa yerine sağdan sola karşılaştırır.
Boyer-Moore Algoritmanın iki ana bileşeni vardır: Kötü karakter kuralı ve iyi sonek kuralı. Kötü karakter kuralı, kalıptaki karakteri veri veya metindeki karşılık gelen karakterle karşılaştırarak çalışır. Karakterler eşleşmiyorsa algoritma, eşleşen bir karakter bulana kadar deseni sağa doğru hareket ettirir. İyi son ek kuralı, desenin son ekini veri veya metnin karşılık gelen son ekiyle karşılaştırır. Son ekler eşleşmezse algoritma, eşleşen bir son ek bulana kadar modeli sağa doğru hareket ettirir.
Boyer-Moore Algoritmanın verimliliği biliniyor ve birçok uygulamada yaygın olarak kullanılıyor. Mevcut en hızlı desen eşleştirme algoritmalarından biri olarak kabul edilir.
Boyer-Moore algoritmasının C'de uygulanması:
Uygulamak için Boyer-Moore C'deki algoritmaya kötü karakter kuralını tanımlayarak başlayabiliriz. Desendeki her karakterin son oluşumunu depolamak için bir dizi kullanabiliriz. Bu dizi, bir uyumsuzluk meydana geldiğinde modeli ne kadar sağa kaydırmamız gerektiğini belirleyebilir.
Kötü karakter kuralını C'de nasıl uygulayabileceğimize dair bir örnek:
youtube videolarını vlc ile indirme
C kodu:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>