Sözcük Ağaçları

Buraya kadarki arama yapıları anahtarları bütün olarak karşılaştırdı: iki dizgi eşit mi, hangisi büyük. Anahtarlar dizgi olduğunda bu karşılaştırmaların her biri, en kötü durumda dizgi uzunluğu kadar karakter incelemesi demektir.

Farklı bir yaklaşım, anahtarı bir bütün değil karakter dizisi olarak görmektir. Bu durumda anahtar, ağaçta bir düğüm değil bir yol olur; karşılaştırma da bir kerede değil, karakter karakter yapılır.

Anahtar Bir Yoldur

Sözcük ağacında (trie) her kenar bir karaktere karşılık gelir. Kökten bir düğüme giden yol üzerindeki karakterler, o düğümün temsil ettiği öneki oluşturur.

        (kök)
       /     \
     o         a
     |         |
     l         l
     |        / \
     ç       t   a
     |       |   |
     ü*      ı*  n*     (* : burada biten bir anahtar var)
     |
     m*

Bu ağaçta dört anahtar saklıdır: olçü, olçüm, altı, alan. olçü ve olçüm anahtarlarının ortak öneki bir kez saklanmıştır; ikisini ayıran tek şey, ü düğümünün de anahtar sonu işaretli olmasıdır.

Anahtar sonu işareti zorunludur: bir yolun üzerinden geçmek, o yolun bir anahtar olduğu anlamına gelmez. ol yolu vardır ama ol anahtar değildir. Bu işaret olmadan yapı, yalnızca hangi öneklerin var olduğunu söyleyebilir; hangi dizgilerin gerçekten saklandığını söyleyemez.

Maliyet: Uzunluğa Bağlı, Sayıya Değil

Sözcük ağacında arama, anahtarın karakterlerini sırayla izlemektir. Adım sayısı, anahtarın uzunluğu kadardır — ağaçta kaç anahtar bulunduğundan bağımsız.

$$O(m), \quad m = \text{anahtar uzunluğu}$$

Bu, dengeli arama ağacındaki $O(\log n)$ ile karşılaştırıldığında ilginç bir farktır: milyon anahtar da olsa, on karakterlik bir anahtarın aranması on adımdır.

Karma tablosuyla karşılaştırma daha inceliklidir. Karma tablosunda arama “sabit” sayılır, ancak karma değerinin hesaplanması anahtarın tamamını okur — yani $O(m)$. İki yapının tekil arama maliyeti aynı mertebededir; ayrıldıkları yer, karma tablosunun sunamadığı işlemlerdir.

class SozcukAgaci:
    """Karakter dizilerini önek paylaşımıyla saklar."""

    def __init__(self) -> None:
        self.cocuklar: dict[str, "SozcukAgaci"] = {}
        self.anahtar_sonu = False

    def ekle(self, kelime: str) -> None:
        dugum = self
        for karakter in kelime:
            dugum = dugum.cocuklar.setdefault(karakter, SozcukAgaci())
        dugum.anahtar_sonu = True

    def _dugum_bul(self, onek: str) -> "SozcukAgaci | None":
        dugum = self
        for karakter in onek:
            if karakter not in dugum.cocuklar:
                return None
            dugum = dugum.cocuklar[karakter]
        return dugum

    def iceriyor_mu(self, kelime: str) -> bool:
        dugum = self._dugum_bul(kelime)
        return dugum is not None and dugum.anahtar_sonu

    def onek_var_mi(self, onek: str) -> bool:
        return self._dugum_bul(onek) is not None

    def onekle_baslayanlar(self, onek: str) -> list[str]:
        """Verilen önekle başlayan tüm anahtarları sıralı döndürür."""
        kok = self._dugum_bul(onek)
        if kok is None:
            return []
        sonuc: list[str] = []

        def gez(dugum: "SozcukAgaci", biriken: str) -> None:
            if dugum.anahtar_sonu:
                sonuc.append(onek + biriken)
            for karakter in sorted(dugum.cocuklar):        # sıralı gezinme
                gez(dugum.cocuklar[karakter], biriken + karakter)

        gez(kok, "")
        return sonuc


agac = SozcukAgaci()
for kelime in ("olcu", "olcum", "olcek", "alan", "alti"):
    agac.ekle(kelime)

print(agac.iceriyor_mu("olcum"), agac.iceriyor_mu("olc"))   # True False
print(agac.onek_var_mi("olc"))                              # True
print(agac.onekle_baslayanlar("ol"))     # ['olcek', 'olcu', 'olcum']
print(agac.onekle_baslayanlar("al"))     # ['alan', 'alti']
print(agac.onekle_baslayanlar("xy"))     # []

iceriyor_mu("olc") çağrısının yanlış dönmesi, anahtar sonu işaretinin işlevini gösterir: yol vardır, anahtar yoktur.

Önek Sorguları

Sözcük ağacının ayırt edici yeteneği son iki çağrıdadır. Bir önekle başlayan tüm anahtarları bulmak, karma tablosunda tüm anahtarların taranmasını gerektirir; sözcük ağacında önek düğümüne inip alt ağacı gezmek yeterlidir.

Tipik kullanım alanları:

• Otomatik tamamlama. Kullanıcının yazdığı önekle başlayan adaylar.
• Sözlük ve yazım denetimi. Var olan öneklerin izlenmesi, olası tamamlamalar; yazım önerileri, ağaçta küçük sapmalara izin veren bir gezinmeyle üretilir.
• Yönlendirme tabloları. Ağ müfredatındaki en uzun önek eşleme, adres bitleri üzerinde çalışan bir sözcük ağacıyla yapılır.
• Sıralı gezinme. Alt ağacın sıralı gezilmesi, anahtarları sözlük sırasında verir; karma tablosunun sunamadığı bir işlem.

Bellek Ödünleşimi

Sözcük ağacının bedeli bellektir. Her karakter için bir düğüm oluşur ve her düğüm bir çocuk eşlemesi taşır. Alfabesi geniş ve anahtarları ortak önek paylaşmayan bir kümede, ağaç kendi verisinden büyük olabilir.

İki yaygın sıkıştırma vardır:

Yolların birleştirilmesi. Tek çocuklu düğüm zincirleri tek bir düğümde toplanır ve kenar bir karakter yerine bir karakter dizisi taşır. Bu yapıya sıkıştırılmış sözcük ağacı denir; anahtar sayısı az, anahtarlar uzun olduğunda büyük kazanç sağlar.

Çocuk gösteriminin seçimi. Küçük alfabelerde sabit boyutlu dizi (her karakter için bir göz) hızlıdır ama seyrek düğümlerde yer israfıdır; eşleme kullanmak yeri azaltır, erişimi bir miktar yavaşlatır.

Bit Düzeyinde Sözcük Ağaçları

Anahtarlar dizgi olmak zorunda değildir. Herhangi bir değerin bit dizisi de bir yol olarak kullanılabilir; bu durumda her düğümün en fazla iki çocuğu olur ve yapı ikili ağaca dönüşür.

En bilinen uygulaması ağ yönlendirmesidir. Bir adres öneki, adresin ilk $k$ bitidir; en uzun önek eşleme, kökten aşağı inip eşleşen en derin düğümü bulmaktır. Ağ müfredatındaki yönlendirme tablosu araması bu yapıyla yapılır.

İkinci uygulama, tam sayı anahtarlı sözlüklerdir. Bit düzeyinde çalışan sıkıştırılmış sözcük ağaçları, karma tablosuna alternatif olarak kullanılır: sıralı gezinme ve önek sorgusu sunar, karma hesabı gerektirmez ve en kötü durum garantisi anahtar genişliğiyle sınırlıdır.

Bilgisayarlar Nasıl Çalışır kursundaki bit düzeyi işlemler burada da doğrudan kullanılır: her adımda ilgili bit, kaydırma ve maskeleme ile okunur.

Karşılaştırma

Ölçüt	Sözcük ağacı	Karma tablosu	Dengeli arama ağacı
Tekil arama	$O(m)$	$O(m)$ ortalama	$O(m \log n)$
Önek sorgusu	Doğrudan	Desteklemez	Aralık sorgusuyla kısmen
Sıralı gezinme	Var	Yok	Var
Bellek	Yüksek	Orta	Orta
En kötü durum	$O(m)$	$O(n \cdot m)$	$O(m \log n)$

Tablodaki değerler, anahtarların dizgi olduğu durumu varsayar; sayısal anahtarlarda karşılaştırma sabit maliyetlidir ve karşılaştırmalı yapılar öne geçer.

Dengeli arama ağacındaki $\log n$ çarpanı, her düğümde bir dizgi karşılaştırması yapılmasındandır — sözcük ağacında bu çarpan yoktur.

Özet

• Sözcük ağacında anahtar bir düğümde değil, kökten inen bir yolda saklanır; ortak önekler bir kez tutulur.
• Anahtar sonu işareti zorunludur; bir yolun var olması, o yolun anahtar olduğu anlamına gelmez.
• Arama maliyeti anahtar uzunluğuna bağlıdır, saklanan anahtar sayısından bağımsızdır.
• Önekle başlayan tüm anahtarları listelemek, önek düğümünün alt ağacını gezmektir.
• Bedeli bellektir; yol sıkıştırma ve çocuk gösterimi seçimi bu maliyeti azaltır.
• Karma tablosunun sunamadığı önek sorgusu ve sıralı gezinme, bu yapının varlık nedenidir.

Sonraki Adım

Buraya kadarki yapılar tekil anahtarlar üzerinde çalıştı. Bazı problemlerde ise sorgu bir aralık hakkındadır: “şu iki dizin arasındaki değerlerin toplamı nedir” — ve bu sorgu, veriler değişirken tekrar tekrar sorulur. Sonraki ders bu soruyu logaritmik maliyetle yanıtlayan yapıları ele alacak.