Dizi Eşleştirme
Dizi eşleştirme, bir metin içindeki bir örüntünün tüm tekrarlarını bulur; klasik algoritmalar, gereksiz karşılaştırmaları atlamak ve doğrusal veya alt doğrusal arama süresi elde etmek için örüntüyü ön işleme tabi tutar.
Tanım
Dizi eşleştirme, bir metinde belirli bir örüntü dizisinin geçtiği tüm konumları bulma problemidir; tam bir dizi eşleştirme algoritması, örüntünün metnin bir alt dizisiyle özdeş olarak hizalandığı her ofseti rapor etmektedir.
Kapsam
Bu konu, tam tek örüntü eşleştirme algoritmalarını — naif yöntem, Knuth-Morris-Pratt, Boyer-Moore ve karma tabanlı Rabin-Karp — bunların verimli olmasını sağlayan ön işlemelerle (hata fonksiyonları, kaydırma tabloları, kayan karmalar) birlikte ve Aho-Corasick otomatı aracılığıyla çoklu örüntü eşleştirmeye uzantısını kapsamaktadır. Yaklaşık eşleştirme ve indeks tabanlı arama ilgili konularda ele alınmaktadır.
Temel sorular
- Naif eşleştirme neden örüntü ve metin uzunluklarının çarpımıyla orantılı zaman alır?
- Örüntüyü ön işleme tabi tutmak, metin karakterlerini yeniden incelemeyi nasıl önler?
- Knuth-Morris-Pratt hata fonksiyonu ve Boyer-Moore kaydırma kuralları nasıl çalışır?
- Rabin-Karp, hizalamaları hızlı bir şekilde test etmek için karmayı nasıl kullanır?
- Eşleştirme, aynı anda birçok örüntüye nasıl genişletilir?
Anahtar kavramlar
- naif eşleştirme
- Knuth-Morris-Pratt algoritması
- hata fonksiyonu
- Boyer-Moore algoritması
- kötü karakter ve iyi sonek kuralları
- Rabin-Karp algoritması
- kayan karma
- Aho-Corasick otomatı
Temel kuramlar
- Knuth-Morris-Pratt hata fonksiyonu
- Knuth-Morris-Pratt algoritması, her örüntü öneki için aynı zamanda bir sonek olan en uzun uygun öneki önceden hesaplayarak, bir uyumsuzluktan sonra örüntüyü akıllıca kaydırır ve metin karakterlerini asla yeniden incelemez, böylece doğrusal zamanlı eşleştirme sağlar.
- Boyer-Moore sağdan sola tarama
- Boyer-Moore, örüntüyü son karakterinden geriye doğru karşılaştırır ve kötü karakter ile iyi sonek kurallarını kullanarak metnin büyük kısımlarını atlar, böylece tipik girdilerde alt doğrusal ortalama durum performansı elde eder.
Klinik önem
Dizi eşleştirme, günlük araçların ve altyapının temelini oluşturmaktadır: metin düzenleyicilerde ve komut satırı yardımcı programlarında arama, içerik filtreleme ve izinsiz giriş algılama imza taraması, intihal tespiti ve biyolojik dizilerdeki motiflerin konumlandırılması. Çoklu örüntü eşleştirme, bunları aynı anda birçok örüntü sözlüğüne ölçeklendirmektedir.
Tarihçe
Knuth-Morris-Pratt algoritması (1977'de yayımlandı, daha önce geliştirildi) ilk yaygın olarak bilinen doğrusal zamanlı tam eşleştiriciyi sunmuş, Boyer ve Moore (1977) ise aynı yıl alt doğrusal ortalama durum eşleştirmesini tanıtmıştır. Rabin ve Karp'ın karma yaklaşımı ve Aho-Corasick çoklu örüntü otomatı (1975) alanı daha da genişletmiştir.
Öne çıkan isimler
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Michael Rabin
- Richard Karp
İlgili konular
Temel eserler
- knuth1977
- boyer1977
- cormen2009
Sıkça sorulan sorular
- Hangi tam dizi eşleştirme algoritması en hızlıdır?
- Bu, girdiye bağlıdır. Knuth-Morris-Pratt doğrusal en kötü durum süresini garanti eder; Boyer-Moore, karakterleri atladığı ve ortalama olarak alt doğrusal çalıştığı için doğal metinlerde pratikte genellikle en hızlıdır; Rabin-Karp, birçok örüntü aranırken veya parmak izi karşılaştırmaları yapılırken öne çıkmaktadır. Tek bir evrensel kazanan bulunmamaktadır.
- Rabin-Karp, her konumdaki her karakteri karşılaştırmaktan nasıl kaçınır?
- Örüntüyü ve aynı uzunluktaki her metin penceresini, pencere kaydıkça sabit zamanda güncellenen kayan bir karma (rolling hash) kullanarak karmalar. Yalnızca karmalar eşleştiğinde gerçek karakterleri doğrular, böylece çoğu eşleşmeyen konum tek ve ucuz bir karşılaştırma ile reddedilmektedir.