Sonek Dizileri ve Ağaçları

Önceki dört algoritma örüntüyü önişledi; metin her aramada baştan tarandı. Bu, tek seferlik aramalar için doğru dengedir.

Denge, aynı metinde binlerce sorgu yapıldığında tersine döner: metin bir kez önişlenip sorgular metin uzunluğuna değil örüntü uzunluğuna bağlı maliyetle yanıtlanabilir. Bu ders o yapıları kurar.

Sonek Dizisi

Bir metnin tüm sonekleri sıralanır ve yalnızca başlangıç konumları saklanır. Ortaya çıkan tam sayı dizisine sonek dizisi (suffix array) denir.

def sonek_dizisi(metin: str) -> list[int]:
    """Sonekleri sözlük sırasına dizen başlangıç konumları."""
    return sorted(range(len(metin)), key=lambda i: metin[i:])


metin = "banana"
sd = sonek_dizisi(metin)
print(sd)                              # [5, 3, 1, 0, 4, 2]
print([metin[i:] for i in sd])
# ['a', 'ana', 'anana', 'banana', 'na', 'nana']

Yapı yalnızca $n$ tam sayı tutar; metnin kendisi bir kez saklanır. Bellek maliyeti, sonekleri ayrı ayrı saklamaya göre çok düşüktür.

Yukarıdaki kurulum, karşılaştırma başına $O(n)$ karakter okuduğu için $O(n^2 \log n)$’dir ve yalnızca gösterim amaçlıdır. Sonek dizisi, uzunlukları ikişer katlayarak sıralayan yöntemle $O(n \log n)$’de, daha ileri yöntemlerle $O(n)$’de kurulur.

Sorgu

Sonekler sıralı olduğuna göre, örüntüyle başlayan sonekler dizide bitişik bir aralıkta bulunur. İkili arama bu aralığın sınırlarını verir.

def aralik(metin: str, sd: list[int], oruntu: str) -> tuple[int, int]:
    """Örüntüyle başlayan soneklerin sonek dizisindeki [bas, son) aralığı."""
    m = len(oruntu)

    lo, hi = 0, len(sd)
    while lo < hi:                                  # alt sınır
        orta = (lo + hi) // 2
        if metin[sd[orta]:sd[orta] + m] < oruntu:
            lo = orta + 1
        else:
            hi = orta
    bas = lo

    lo, hi = bas, len(sd)
    while lo < hi:                                  # üst sınır
        orta = (lo + hi) // 2
        if metin[sd[orta]:sd[orta] + m] <= oruntu:
            lo = orta + 1
        else:
            hi = orta
    return bas, lo


uzun_metin = "ABABDABACDABABCABAB"
sd_uzun = sonek_dizisi(uzun_metin)

bas, son = aralik(uzun_metin, sd_uzun, "ABAB")
print(son - bas, sorted(sd_uzun[bas:son]))     # 3 [0, 10, 15]

bas, son = aralik(uzun_metin, sd_uzun, "ZZ")
print(son - bas)                                # 0

İkili aramanın her adımı $m$ karaktere kadar karşılaştırma yapar; sorgu maliyeti $O(m \log n)$’dir. Geçiş sayısı ise aralık genişliğinden tek işlemde okunur — kaç kez geçtiğini bulmak için metni taramak gerekmez.

İki maliyet karşılaştırılınca denge görünür: KMP her sorguda $O(n + m)$ öder; sonek dizisi bir kez $O(n \log n)$ öder, sonra her sorguya $O(m \log n)$ ile yanıt verir. Sorgu sayısı büyüdükçe ikinci yol kazanır — Zaman ve Alan Ödünleşimi dersindeki önişleme kalıbının metin üzerindeki karşılığı.

En Uzun Ortak Önek Dizisi

Sonek dizisi tek başına eksiktir; komşu sonekler arasındaki örtüşme bilinirse çok daha fazla soru yanıtlanır.

LCP dizisi, sıralamada ardışık iki soneğin en uzun ortak önek uzunluğunu tutar. Kasai yöntemi bunu $O(n)$’de hesaplar.

def lcp_dizisi(metin: str, sd: list[int]) -> list[int]:
    """lcp[k]: sd[k-1] ile sd[k] soneklerinin ortak önek uzunluğu."""
    n = len(metin)
    sira = [0] * n
    for k, i in enumerate(sd):
        sira[i] = k

    lcp = [0] * n
    h = 0
    for i in range(n):
        if sira[i] > 0:
            j = sd[sira[i] - 1]
            while i + h < n and j + h < n and metin[i + h] == metin[j + h]:
                h += 1
            lcp[sira[i]] = h
            if h:
                h -= 1                 # bir sonraki sonek en az h-1 ortak önek taşır
        else:
            h = 0
    return lcp


print(lcp_dizisi("banana", sd))        # [0, 1, 3, 0, 0, 2]

Dizinin en büyük değeri, metinde iki kez geçen en uzun parçayı verir.

def en_uzun_tekrar(metin: str) -> str:
    sd = sonek_dizisi(metin)
    lcp = lcp_dizisi(metin, sd)
    k = max(range(len(lcp)), key=lambda i: lcp[i])
    return metin[sd[k]:sd[k] + lcp[k]]


print(en_uzun_tekrar("banana"))                # ana
print(en_uzun_tekrar("ABABDABACDABABCABAB"))   # ABAB

Aynı yapı başka soruları da yanıtlar: iki metnin en uzun ortak parçası (birleştirilip tek metin gibi işlenerek), farklı parça sayısı, ve sıkıştırmada tekrar tespiti.

Sonek Ağacı

Sonek ağacı, metnin tüm soneklerini içeren sıkıştırılmış bir sözlük ağacıdır: tek çocuklu düğüm zincirleri birleştirilir ve kenarlar metnin alt aralıklarını gösterir.

Sonek dizisiyle aynı bilgiyi taşır, farklı düzenler:

Ölçüt	Sonek dizisi	Sonek ağacı
Kurulum	$O(n)$ (ileri yöntemler)	$O(n)$
Sorgu	$O(m \log n)$	$O(m)$
Bellek sabiti	Küçük ($n$ tam sayı)	Büyük (düğüm ve işaretçiler)
Gerçekleştirim	Basit	Karmaşık

Sorgu maliyetindeki logaritmik çarpan, sonek dizisine LCP bilgisi eklenerek de kaldırılabilir. Pratikte sonek dizisi tercih edilir: bellek sabiti küçük ve kodu daha denetlenebilirdir. Sonek ağacı, ağaç yapısının kendisini gerektiren kuramsal çözümlemelerde ve bazı özel sorgularda öne çıkar.

Aynı ailedeki üçüncü yapı sonek otomatıdır; metnin tüm alt dizgilerini tanıyan en küçük otomattır ve alt dizgi sayma gibi soruları doğrudan yanıtlar.

Nerede Kullanılır

Önişlemeli metin yapıları, metnin sabit ve sorguların çok olduğu her yerde görünür:

• Tam metin dizinleme. Belge kümesinde arama; sorgu başına metni taramak ölçeklenmez.
• Biyoenformatik. Genetik diziler uzun, abece küçük ve aynı dizi üzerinde binlerce sorgu yapılır.
• Yinelenen kod ve içerik tespiti. En uzun ortak parça sorgularıyla.
• Sıkıştırma. Tekrar eden parçaların bulunması; Burrows–Wheeler dönüşümü doğrudan sonek sıralamasına dayanır.

Ortak ölçüt aynıdır: önişleme maliyeti sorgu sayısına bölündüğünde kazanç kalıyor mu? Bu soru, Karmaşıklık Sınıflarını Okumak dersinde alt doğrusal sınıflar için sorulmuştu; yanıtı burada somut bir veri yapısı seçimine dönüşür.

Özet

• Sonek dizisi, metnin tüm soneklerini sözlük sırasına dizen başlangıç konumlarıdır ve $n$ tam sayı yer kaplar.
• Örüntüyle başlayan sonekler bitişik bir aralıktadır; ikili arama sorguyu $O(m \log n)$’de yanıtlar ve geçiş sayısını aralık genişliği verir.
• LCP dizisi ardışık soneklerin ortak önek uzunluğunu tutar ve $O(n)$’de hesaplanır; en büyük değeri en uzun tekrar eden parçayı verir.
• Sonek ağacı aynı bilgiyi ağaç olarak düzenler; sorgusu $O(m)$’dir ama bellek sabiti ve gerçekleştirim karmaşıklığı yüksektir.
• Yapı seçimi, önişleme maliyetinin sorgu sayısına bölünmesiyle verilir.

Sonraki Adım

Metin algoritmalarının son sorusu aramadan farklıdır: aynı bilgiyi daha az yerle saklamak. Sonraki ders, karakter sıklıklarına göre değişken uzunlukta kod üreten Huffman yöntemini kuracak ve açgözlü bir seçimin neden eniyi kodu verdiğini gösterecek.