Kaba Kuvvet Örüntü Arama

Çizge algoritmaları, aralarında bağlantı bulunan verilerle çalıştı. Bu konu farklı bir yapıya geçer: sıralı simge dizileri — metin.

Metin işlemenin temel sorusu örüntü aramadır ve bu ders, sorunun kendisini ve en yalın çözümünü kurar. Sonraki dört ders aynı problemi farklı fikirlerle iyileştirecek; ölçüt hep aynı olacak: karakter karşılaştırma sayısı.

Problem

Örüntü arama: Uzunluğu $n$ olan bir metin ve uzunluğu $m$ olan bir örüntü verilir; örüntünün metinde geçtiği konumlar istenir.

Sorunun üç yaygın biçimi vardır ve maliyetleri farklıdır:

• İlk geçiş. Bulunduğu anda durulur.
• Tüm geçişler. Metnin sonuna kadar sürer.
• Geçiş sayısı. Konumlar saklanmadan sayılır.

Bu konu boyunca aynı metin ve örüntü kullanılır:

metin = "ABABDABACDABABCABAB"
oruntu = "ABABCABAB"

Örüntü metinde 10 numaralı dizinde bir kez geçer. Örnek, örüntünün kendi içinde tekrarlar barındırdığı için sonraki derslerin fikirlerini de sınamaya elverişlidir.

Kaydırmalı Tarama

En yalın çözüm, örüntüyü metnin her konumuna yerleştirip karakter karakter karşılaştırmaktır. Uyuşmazlıkta örüntü bir konum sağa kaydırılır ve karşılaştırma baştan başlar.

def kaba_kuvvet(metin: str, oruntu: str) -> tuple[list[int], int]:
    """(bulunan konumlar, karakter karşılaştırma sayısı)"""
    n, m = len(metin), len(oruntu)
    konumlar: list[int] = []
    sayac = 0
    for kaydirma in range(n - m + 1):
        j = 0
        while j < m:
            sayac += 1
            if metin[kaydirma + j] != oruntu[j]:
                break
            j += 1
        if j == m:
            konumlar.append(kaydirma)
    return konumlar, sayac


print(kaba_kuvvet(metin, oruntu))        # ([10], 29)
print(kaba_kuvvet("ABABAB", "AB"))       # ([0, 2, 4], 8)

Değişmez şudur: kaydirma konumundan önceki hiçbir konumda tam eşleşme yoktur. Sonlanma, kaydırmanın her turda bir artmasından gelir.

Algoritma doğrudur ve ek alan kullanmaz. Sorunu maliyetindedir.

Maliyet

Dış döngü $n - m + 1$ kez, iç döngü en çok $m$ kez çalışır:

$$O\big((n - m + 1)\, m\big) = O(nm)$$

En kötü duruma ulaşmak için, her kaydırmada uzun bir öneki eşleşen ama sonda uyuşmayan bir girdi gerekir.

kotu_metin = "A" * 30 + "B"
kotu_oruntu = "A" * 10 + "B"

print(kaba_kuvvet(kotu_metin, kotu_oruntu))     # ([20], 231)
print(len(kotu_metin), len(kotu_oruntu))        # 31 11

Her kaydırmada on A eşleşir, sonuncu karakter uyuşmaz ve tüm iş boşa gider. Karşılaştırma sayısı $(n - m + 1) \cdot m$ çarpımına yaklaşır: $21 \times 11 = 231$.

Bu tür girdiler yapay görünür, ancak ikilik veri, sınırlı abeceli diziler (genetik diziler gibi) ve tekrarlı yapılar taşıyan kütükler bu davranışı gerçekten üretir.

Gerçek Metinde Davranış

Doğal dilde durum farklıdır: uyuşmazlık genellikle ilk birkaç karakterde ortaya çıkar ve iç döngü erken kırılır.

uzun_metin = ("bir metin icinde oruntu aramanin maliyeti "
              "abecenin buyuklugune ve tekrarlara baglidir. ") * 10

for desen in ("oruntu", "maliyeti", "zzz"):
    konumlar, sayac = kaba_kuvvet(uzun_metin, desen)
    print(desen, len(konumlar), sayac, len(uzun_metin))

# oruntu 10 915 870
# maliyeti 10 963 870
# zzz 0 868 870

Karşılaştırma sayısı, metin uzunluğunun küçük bir katı kadardır — çarpımsal en kötü duruma hiç yaklaşılmaz. Beklenen karşılaştırma sayısı, abece büyüklüğü $\sigma$ iken kaydırma başına yaklaşık $1/(1 - 1/\sigma)$’dır; abece büyüdükçe bu değer 1’e yaklaşır.

Sonuç, çözümleme derslerinin bir uyarısını hatırlatır: en kötü durum ile tipik durum farklı sorulardır. Kaba kuvvet arama, büyük abeceli metinlerde pratikte hızlıdır; onu sorunlu kılan, kötü girdide sessizce karesele düşmesidir.

Karşılaştırma Birimi

Algoritmalar “karakter” üzerinde tanımlanır, ama gerçek metinde bu birimin ne olduğu bir seçimdir ve sonucu değiştirir.

Bilgisayarlar Nasıl Çalışır kursundaki kodlama dersi üç düzeyi ayırmıştı: bayt, kod noktası ve kullanıcının tek harf saydığı öbek. Bir örüntü arama, bunların hangisinde çalıştığını belirtmek zorundadır.

Bayt düzeyinde arama en hızlısıdır ve çok baytlı kodlamalarda hatalı eşleşme üretmez — kodlama, bir karakterin baytlarının başka bir karakterin baytlarının ortasında görünmemesini sağlar. Ancak bulunan konum bayt cinsindendir; karakter konumu isteniyorsa dönüşüm gerekir.

Kod noktası düzeyinde arama, birleşik yazılan harflerde şaşırtır: aynı görünen iki metin farklı kod noktası dizileriyle yazılmış olabilir. Bu durumda arama öncesinde bir normalleştirme adımı gerekir.

Büyük–küçük harf duyarsız arama ise dile bağlıdır; harf katlama kuralları her dilde aynı değildir ve tek karakterlik bir dönüşümün her zaman tek karakter üretmesi de garanti değildir.

Bu ayrımlar algoritmayı değiştirmez, ama karşılaştırma işleminin maliyetini ve doğruluğunu belirler. Bu derste ve sonrakilerde karşılaştırma birimi tek kod birimi sayılır.

Kaybedilen Bilgi

Algoritmanın israfı tek bir noktada toplanır: uyuşmazlıktan önce yapılan karşılaştırmalar unutulur.

ABABC örüntüsü ABABD… metniyle karşılaştırılırken ilk dört karakterin eşleştiği bilinir. Kaba kuvvet bunu atar ve bir sağa kayıp yeniden başlar — oysa eşleşen kısmın yapısından, bazı kaydırmaların denenmesinin gereksiz olduğu çıkarılabilir.

Sonraki üç ders bu bilgiyi üç farklı biçimde kullanır:

Yaklaşım	Kullanılan bilgi
Rabin–Karp	Pencerenin karma değeri; karşılaştırma yerine sayı eşitliği
Knuth–Morris–Pratt	Örüntünün kendi önek–sonek yapısı
Boyer–Moore	Uyuşmayan metin karakteri ve örüntünün sonundan eşleme

Üçü de aynı problemi çözer ve aynı sonucu üretir; ayrıldıkları nokta, hangi ön bilgiyi hesaplayıp aramada kullandıklarıdır.

Ne Zaman Yeterli

Kaba kuvvet aramanın iki üstünlüğü vardır: önişleme yapmaz ve ek alan kullanmaz. Bu, şu durumlarda onu doğru seçim yapar:

• Örüntü kısa ve metin küçükse; kurulum maliyeti kazançtan büyüktür.
• Her arama farklı bir örüntüyle yapılıyorsa; önişleme her seferinde yeniden ödenir.
• Abece büyük ve metin doğal dilse; tipik davranış zaten doğrusala yakındır.

Buna karşılık aynı örüntü çok kez aranacaksa önişlemeli yöntemler, aynı metin çok kez sorgulanacaksa metni önişleyen yapılar öne çıkar. Bu ikinci yol, sonek dizileri dersinin konusudur.

Özet

• Örüntü arama, bir metinde verilen dizinin geçtiği konumları bulur; ilk geçiş, tüm geçişler ve sayım biçimleri farklı maliyetlidir.
• Kaba kuvvet arama her kaydırmada baştan karşılaştırır; ek alan kullanmaz ve önişleme gerektirmez.
• En kötü durum $O(nm)$’dir ve tekrarlı, küçük abeceli girdilerde gerçekten ortaya çıkar.
• Doğal dilde uyuşmazlık erken oluştuğu için tipik maliyet doğrusala yakındır.
• Algoritmanın israfı, uyuşmazlıktan önce elde edilen bilginin atılmasıdır.
• Sonraki yöntemler bu bilgiyi karma değeri, örüntünün önek–sonek yapısı veya sondan eşleme yoluyla kullanır.

Sonraki Adım

İlk iyileştirme fikri şaşırtıcıdır: karakterleri hiç karşılaştırmamak. Metnin her penceresi bir sayıya indirgenip örüntünün sayısıyla karşılaştırılırsa, çoğu konum tek işlemde elenir. Sonraki ders, pencereden pencereye sabit maliyetle güncellenen yuvarlanan karma fikrini ve karma çakışmalarının nasıl ele alındığını kuracak.