--- title: 'Sonek Dizileri ve Ağaçları' source: 'https://academia.sh/tr/kurslar/algoritmalar/sonek-dizileri-ve-agaclari' course: Algoritmalar language: tr updated: '2026-08-17T18:07:49+00:00' license: 'CC BY-SA 4.0' --- # Sonek Dizileri ve Ağaçları Metni önişleyen yapılar, sonek dizisi kurulumu ve ikili aramayla sorgu, en uzun ortak önek dizisi, sonek ağacı ile karşılaştırma ve uygulama alanları. Ö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. ```python 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. ```python 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. ```python 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. ```python 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.