Boyer-Moore Algoritması Nedir?
Boyer-Moore algoritması, bilgisayar bilimlerinde metin içinde belirli bir deseni (alt dizeyi) aramak için kullanılan oldukça verimli bir algoritmadır. Özellikle uzun metinlerde ve desenlerde yüksek performans gösterir.
Boyer-Moore algoritması, sağdan sola doğru eşleştirme yaparak ve 'kötü karakter' (bad character) ve 'sonraki eşleşme' (good suffix) kurallarını kullanarak desenin eşleşmediği durumlarda büyük adımlarla ilerleyerek metin arama işlemini hızlandırır.
Adım adım çözümlü örnekler
Boyer-Moore algoritmasını basit bir örnekle açıklayın.
Metin: 'ABABDABACDABABCABAB' ve Desen: 'ABABCABAB'. Algoritma, deseni metnin sonundan başlayarak sağdan sola doğru eşleştirir. 'ABABCABAB' deseni, metnin sonunda 'ABABCABAB' ile eşleşir. Eğer eşleşme olmasaydı, 'kötü karakter' ve 'sonraki eşleşme' kuralları kullanılarak desenin ne kadar kaydırılacağı belirlenirdi.
Boyer-Moore algoritmasının avantajları nelerdir?
Büyük kaydırma adımları sayesinde, özellikle uzun metinlerde ve desenlerde diğer basit algoritmaları (örn. Naive algoritma) geride bırakır. Ortalama durumda doğrusal zaman karmaşıklığına yaklaşır (O(n/m)).
Bilgi kartları
Mini test
S1.Boyer-Moore algoritması, deseni hangi yönde eşleştirmeye başlar?
S2.Aşağıdakilerden hangisi Boyer-Moore algoritmasında kullanılan kurallardan biri DEĞİLDİR?
S3.Boyer-Moore algoritmasının ortalama zaman karmaşıklığı nedir?
Sık yapılan hatalar
Boyer-Moore algoritması her zaman O(n*m) karmaşıklığında çalışır. — Doğrusu: Boyer-Moore algoritması ortalama durumda O(n/m) gibi çok daha iyi bir karmaşıklığa sahiptir; en kötü durum O(n*m) olsa da pratikte nadirdir.
Algoritma, deseni soldan sağa doğru eşleştirir. — Doğrusu: Algoritma, verimliliğini artıran sağdan sola doğru bir eşleştirme stratejisi kullanır.
Sıkça sorulan sorular
Boyer-Moore algoritması neden bu kadar hızlıdır?
Sağdan sola eşleştirme yapması ve eşleşme başarısız olduğunda 'kötü karakter' ve 'sonraki eşleşme' kuralları sayesinde deseni büyük adımlarla kaydırabilmesi nedeniyle hızlıdır.
Hangi durumlarda Boyer-Moore algoritması tercih edilir?
Özellikle uzun metinler ve uzun desenler arandığında, performansın kritik olduğu uygulamalarda (metin editörleri, arama motorları vb.) tercih edilir.
Boyer-Moore'un 'kötü karakter' kuralı ne işe yarar?
Eşleşmenin başarısız olduğu karakterin (metindeki) desende hiç bulunmadığı veya en sağdaki konumunun ne kadar ileride olması gerektiğini belirleyerek deseni kaydırmaya yardımcı olur.