04:38
Rad
Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.
Σ bir alfabe (sonlu küme) olmak üzere örüntü ve aranan metin Σ kümesinin elemanlarından oluşan bir zincir olarak tanımlanabilmektedir. Σ olağan bir alfabe (Türkçede yer alan harfler kümesi) olabileceği gibi ikili alfabe (Σ = {0,1}) ve DNA alfabesi (Σ = {A,C,G,T}) biçiminde de bulunabilmektedir.
Dizinin kodlanma biçimi dizi arama algoritmalarının başarımını etkilemektedir. Değişken uzunluklu kodlama yöntemi kullanıldığında n. karakteri bulmak güçleşmekte; bu, gelişmiş dizi algoritmalarını yavaşlatıcı bir etken olarak öne çıkmaktadır. Bu sorunun üstesinden gelmenin yolu belirli karakterler yerine kod dizilerini eşleştirmektedir ancak bu yöntem, kodlamanın yanlış sonuçların önüne geçecek biçimde tasarlanmadığı durumlarda pek güvenilir değildir.
Algoritmalar kullandıkları örüntü sayısına göre sınıflandırılabilmektedirler.
Tek örüntülü algoritmalar
m örüntünün, n aranan metnin uzunluğu olsun.
AlgoritmaÖnişlem süresiEşleme süresi1
Saf dizi arama algoritması 0 Θ((n-m+1) m)
Rabin-Karp dizi arama algoritması Θ(m) ortalama: Θ(n+m)
en düşük: Θ((n-m+1) m)
Sonlu durum makinesi tabanlı arama Θ(m |Σ|) Θ(n)
Knuth-Morris-Pratt algoritması Θ(m) Θ(n)
Boyer–Moore dizi arama algoritması Θ(m + |Σ|) Ω(n/m), O(n)
Bitkin algoritma (Baeza-Yates-Gonnet) Θ(m + |Σ|) O(mn)
1Sonuşmaz süreler O, Ω, and Θ gösterimi biçiminde ifade edilmektedir.
Boyer–Moore dizi arama algoritması, ilgili yazında kullanılan başlıca algoritma olarak kabul edilmektedir.[1]
Sonlu örüntü kümesi kullanan algoritmalar [değiştir]
Aho-Corasick algoritması
Commentz-Walter algoritması
Rabin-Karp dizi arama algoritması
Sonsuz sayıda örüntü kullanan algoritmalar [değiştir]
Doğal olarak sayılamayan örüntüler genellikle düzenli dilbilgisi ya da düzenli ifadeler biçiminde gösterilmektedir.
İkincil sınıflandırma [değiştir]
En sık kullanılan sınıflandırma yöntemlerinden biri önişlemi ana ölçüt olarak kabul etmektedir.
Dizi arama algoritması sınıflarıÖnişlem gerektirmeyen metinÖnişlem gerektiren metin
Önişlem gerektirmeyen örüntüler Temel algoritmalar Dizin yöntemleri
Önişlem gerektiren algoritmalar Yapısal arama motorları İmza yöntemleri
Saf dizi arama [değiştir]
Bir dizinin başka bir dizi içinde yer alıp almadığını anlamanın en basit olmasına karşın en verimsiz yolu dizinin her karakterini sırayla eşleştirmeye çalışmaktır. Bu yöntemde aranan dizi metnin ilk karakteriyle karşılaştırılır. Bu karakterlerin birbiriyle uyuşmaması durumunda aynı işlem metnin ikinci karakteri için yinelenir. Olağan koşullarda karakterlerin eşleşmediğini anlamak için ortalama olarakO(n + m) adım gerekliyken (n metnin, m örüntünün uzunluğunu göstermektedir) en elverişsiz durumda ("aaaab" dizisini "aaaaaaaaab" içinde aramak gibi) gerekli ortalama adım sayısı O(nm)'ye eşittir.
Sonlu dizi makinesi tabanlı arama [değiştir]
"MOMMY" sözcüğünü farkedebilen bir DFA
Bu yöntemde geri dönüşler, istenen diziyi içeren örüntüleri farkedebilen bir gerekirci sonlu durum makinesi (DFA) oluşturularak ortadan kaldırılabilmektedir.Üstküme yapımı yöntemiyle tasarlanan bu gereçlerin tutarı yüksek olsa da kullanımları görece kolaydır. Bu yöntem gelişigüzel düzenli ifadelere ilişkin aramalarda sıklıkla kullanılmaktadır.
Kısa yöntemler [değiştir]
Knuth–Morris–Pratt, aranan diziyi sonek biçiminde algılayabilen bir DFA oluştururken Boyer–Moore aramaya örüntünün sonundan başlamakta, böylece her adımda örüntü uzunluğu ölçüsünde yol kat edebilmektedir. Baeza–Yates önceki j karakterin aranan dizinin bir öneki olup olmadığını takip edebildiğinden bulanık dizi aramayla bağdaştırılabilmektedir. Bitkin algoritma Baeza-Yates'in bir uygulamasıdır.
Dizin yöntemleri [değiştir]
Görece hızlı çalışan arama algoritmaları metnin önişlemden geçirilmesini gerektirmektedir. Sonek ağacı ya da sonek dizisi gibi altdizi dizinleri oluşturularak örüntü daha kolay biçimde bulunabilmektedir. Bir sonek ağacı
sürede hazırlanabilmekte ve metin içinde yer alan 
sayıdaki örüntü 
sürede bulunabilmektedir (alfabe büyüklüğü sabit olmak koşuluyla).
Diğer yöntemler [değiştir]
Üçlük arama gibi bazı arama yöntemleri metin ve örüntüyü birebir eşlemek yerine bu iki dizi arasında bir "yakınlık" değeri hesaplamayı amaçlamaktadır. Bu tür yöntemler "bulanık" aramalar olarak da adlandırılmaktadır.
tr.wikipedia.org
m örüntünün, n aranan metnin uzunluğu olsun.
AlgoritmaÖnişlem süresiEşleme süresi1
Saf dizi arama algoritması 0 Θ((n-m+1) m)
Rabin-Karp dizi arama algoritması Θ(m) ortalama: Θ(n+m)
en düşük: Θ((n-m+1) m)
Sonlu durum makinesi tabanlı arama Θ(m |Σ|) Θ(n)
Knuth-Morris-Pratt algoritması Θ(m) Θ(n)
Boyer–Moore dizi arama algoritması Θ(m + |Σ|) Ω(n/m), O(n)
Bitkin algoritma (Baeza-Yates-Gonnet) Θ(m + |Σ|) O(mn)
1Sonuşmaz süreler O, Ω, and Θ gösterimi biçiminde ifade edilmektedir.
Boyer–Moore dizi arama algoritması, ilgili yazında kullanılan başlıca algoritma olarak kabul edilmektedir.[1]
Sonlu örüntü kümesi kullanan algoritmalar [değiştir]
Aho-Corasick algoritması
Commentz-Walter algoritması
Rabin-Karp dizi arama algoritması
Sonsuz sayıda örüntü kullanan algoritmalar [değiştir]
Doğal olarak sayılamayan örüntüler genellikle düzenli dilbilgisi ya da düzenli ifadeler biçiminde gösterilmektedir.
İkincil sınıflandırma [değiştir]
En sık kullanılan sınıflandırma yöntemlerinden biri önişlemi ana ölçüt olarak kabul etmektedir.
Dizi arama algoritması sınıflarıÖnişlem gerektirmeyen metinÖnişlem gerektiren metin
Önişlem gerektirmeyen örüntüler Temel algoritmalar Dizin yöntemleri
Önişlem gerektiren algoritmalar Yapısal arama motorları İmza yöntemleri
Saf dizi arama [değiştir]
Bir dizinin başka bir dizi içinde yer alıp almadığını anlamanın en basit olmasına karşın en verimsiz yolu dizinin her karakterini sırayla eşleştirmeye çalışmaktır. Bu yöntemde aranan dizi metnin ilk karakteriyle karşılaştırılır. Bu karakterlerin birbiriyle uyuşmaması durumunda aynı işlem metnin ikinci karakteri için yinelenir. Olağan koşullarda karakterlerin eşleşmediğini anlamak için ortalama olarakO(n + m) adım gerekliyken (n metnin, m örüntünün uzunluğunu göstermektedir) en elverişsiz durumda ("aaaab" dizisini "aaaaaaaaab" içinde aramak gibi) gerekli ortalama adım sayısı O(nm)'ye eşittir.
Sonlu dizi makinesi tabanlı arama [değiştir]
"MOMMY" sözcüğünü farkedebilen bir DFABu yöntemde geri dönüşler, istenen diziyi içeren örüntüleri farkedebilen bir gerekirci sonlu durum makinesi (DFA) oluşturularak ortadan kaldırılabilmektedir.Üstküme yapımı yöntemiyle tasarlanan bu gereçlerin tutarı yüksek olsa da kullanımları görece kolaydır. Bu yöntem gelişigüzel düzenli ifadelere ilişkin aramalarda sıklıkla kullanılmaktadır.
Kısa yöntemler [değiştir]
Knuth–Morris–Pratt, aranan diziyi sonek biçiminde algılayabilen bir DFA oluştururken Boyer–Moore aramaya örüntünün sonundan başlamakta, böylece her adımda örüntü uzunluğu ölçüsünde yol kat edebilmektedir. Baeza–Yates önceki j karakterin aranan dizinin bir öneki olup olmadığını takip edebildiğinden bulanık dizi aramayla bağdaştırılabilmektedir. Bitkin algoritma Baeza-Yates'in bir uygulamasıdır.
Dizin yöntemleri [değiştir]
Görece hızlı çalışan arama algoritmaları metnin önişlemden geçirilmesini gerektirmektedir. Sonek ağacı ya da sonek dizisi gibi altdizi dizinleri oluşturularak örüntü daha kolay biçimde bulunabilmektedir. Bir sonek ağacı
sürede hazırlanabilmekte ve metin içinde yer alan sayıdaki örüntü sürede bulunabilmektedir (alfabe büyüklüğü sabit olmak koşuluyla).Diğer yöntemler [değiştir]
Üçlük arama gibi bazı arama yöntemleri metin ve örüntüyü birebir eşlemek yerine bu iki dizi arasında bir "yakınlık" değeri hesaplamayı amaçlamaktadır. Bu tür yöntemler "bulanık" aramalar olarak da adlandırılmaktadır.
tr.wikipedia.org
Etiketler: 
0 yorum:
Yorum Gönder