Bölüm 5.3: Trie Veri Yapısı

5.3.1Trie kavramı

Dizgilerle (string) çalışan programların büyük bölümü aynı soruyu tekrar tekrar sorar: bu kelime sözlükte var mı? Yazım denetleyicisi her kelime için bu soruyu sorar. Derleyici her tanımlayıcıyı anahtar sözcük tablosunda arar. Bir yönlendirici her paketin adresini rota tablosunda arar. Bu soruların çoğu için hash tablosu iyi bir cevaptır. Ama bazı sorular tam kelimeyle değil, kelimenin başıyla ilgilidir: “an ile başlayan kelimeler hangileri?”, “bu adresin en uzun eşleşen öneki hangisi?” Bu tür sorularda kelimelerin ortak başlangıçlarını bir arada tutan bir yapı gerekir.

Notta sık kullanılan iki terim baştan netleşmelidir. Bir dizginin öneki (prefix), dizginin başından alınan bir parçadır: “and” dizgisinin önekleri “”, “a”, “an” ve “and”dir. Sonek (suffix) ise dizginin sonundan alınan parçadır: “and”in sonekleri “and”, “nd”, “d” ve “”dir. Dizginin içinden ardışık karakterlerle alınan her parça bir alt dizgidir. Her alt dizgi, bir sonekin önekidir. Bu gözlem sonek trie'sinin temelidir.

5.3.1.1Tanım

Bir sözlük düşünülsün: and, ant, dad, do. Bu dört kelimeden ikisi “a”, ikisi “d” ile başlar. “and” ile “ant” ayrıca “an” önekini de paylaşır. Trie bu paylaşımı açıkça gösterir. Kökten aşağı her adım bir karakter okur. Aynı karakterle başlayan kelimeler aynı dala girer ve ancak ilk farklı karakterde ayrılır.

Tanımın son cümlesi önemlidir. Yolun var olması tek başına yetmez. “an” yolu trie'de vardır, ama “an” kümede değildir; “an” düğümü işaretsizdir. Yol, yalnızca kümedeki bir kelimenin önekidir. Trie'nin adı, bilgi geri getirme anlamındaki İngilizce retrieval sözcüğünden gelir. Adı E. Fredkin 1960'ta “Trie Memory” makalesinde önermiştir. Türkçede “önek ağacı” adı da kullanılır; bu notta iki ad aynı yapıyı anlatır.

Şekil 5.3.1'de kökten çıkan iki kenar vardır: “a” ve “d”. “a” düğümünün tek çocuğu “n”dir. “an” düğümünde yol ikiye ayrılır: “d” ile “and”e, “t” ile “ant”e gidilir. Sağ tarafta “d” düğümü de ikiye ayrılır: “a” ile “da”ya, “o” ile “do”ya. “da”nın tek çocuğu “d”dir ve “dad” orada biter. Dört kelimenin toplam karakter sayısı 3 + 3 + 3 + 2 = 11'dir, ama kök dışında yalnız 8 düğüm vardır. Aradaki 3 karakter ortak öneklerin paylaşılmasıyla kazanılmıştır: “and” ile “ant” iki karakter (“a”, “n”), “dad” ile “do” bir karakter (“d”) paylaşır.

Trie'nin kullanım alanları bu yapıdan doğar. Otomatik tamamlamada yazılan önekin düğümüne inilir ve altındaki kelimeler önerilir. Yazım denetiminde kelime trie'de aranır; bulunamazsa ona yakın kelimeler yine trie üzerinde aranır. IP yönlendirmede adresler bit dizisi olarak saklanır ve bir paketin adresine en uzun önekle eşleşen rota bulunur.

5.3.1.2Neden trie?

Soru şudur: bir sözlükte “an” ile başlayan bütün kelimeler bulunacak. Sözlükte n kelime vardır ve kelimelerin uzunluğu en çok L'dir. Farklı veri yapıları bu soruya farklı bedellerle cevap verir.

Dizi ya da liste. Her kelime sırayla alınır ve ilk iki karakteri “an” ile karşılaştırılır. Bir karşılaştırma en çok L karakter okur, toplam iş O(n · L)'dir. Sözlük büyüdükçe süre doğrusal olarak artar. Dizi sıralıysa ikili aramayla ilk eşleşen kelime O(L · log n)'de bulunabilir, ama yeni kelime eklemek dizideki kaydırma yüzünden pahalı olur.

Hash tablosu. Tam bir kelimeyi ortalama O(L) sürede bulur: önce kelimenin L karakterinden hash değeri hesaplanır, sonra ilgili kovaya bakılır. Ancak hash tablosu önek sorusuna cevap veremez. “an” ile “and”in hash değerleri arasında hiçbir ilişki yoktur. İyi bir hash fonksiyonu zaten benzer anahtarları tablonun uzak yerlerine dağıtmak için tasarlanır. Bu yüzden “an ile başlayan kelimeler” sorusu ancak bütün tablo taranarak cevaplanır.

Trie. Kökten önce “a” dalına, sonra “n” dalına inilir; iki adım yeter. Ulaşılan düğümün altındaki her kelime “an” ile başlar ve bu alt ağacın dışında “an” ile başlayan kelime yoktur. Önek düğümünü bulmanın maliyeti sözlükteki kelime sayısına değil, önekin uzunluğuna bağlıdır.

Trie'nin asıl katkısı bu gözlemdir: işlem süresi n'ye değil L'ye bağlıdır. Sözlükte dört kelime de olsa, bir milyon kelime de olsa “dad” en çok üç adımda bulunur. Dengeli bir ikili arama ağacında ise log₂ 10⁶ ≈ 20 karşılaştırma gerekir ve her karşılaştırma kelimenin karakterlerini yeniden okur.

5.3.1.3Temel bileşenler

Trie dört bileşenden oluşur. Bu bileşenlerin her biri koddaki bir öğeye karşılık gelir.

• Kök (root): boş dizgiyi temsil eden düğümdür; hiçbir karaktere karşılık gelmez. Her işlem kökten başlar. Boş bir trie yalnız kökten oluşur.
• Düğümler (nodes): kökten bir düğüme kadarki yol bir önektir. Her düğüm çocuklarına giden bağlantıları tutar. Bir düğümün en çok M çocuğu olabilir; M alfabenin boyudur. Küçük İngilizce harflerde M = 26'dır.
• Kenarlar (edges): bir düğümü çocuğuna bağlar ve bir karakter taşır. Aynı düğümden çıkan iki kenar aynı karakteri taşıyamaz; bu kural her önekin trie'de en çok bir düğümü olmasını sağlar.
• Kelime sonu işareti (end of word): koddaki adı kelimeSonu'dur. Düğümde bir kelimenin bittiğini belirtir. Şekillerde çift çemberle gösterilir.

Bileşenler arasındaki ilişki şöyle özetlenebilir. Düğümle önek arasında birebir bir eşleme vardır: her önek en çok bir düğümle temsil edilir. Kenarlar karakterleri taşır, düğümler ise önekleri. Kelime sonu işareti, hangi öneklerin aynı zamanda kümedeki kelimeler olduğunu söyler. Yaprak düğümler her zaman işaretlidir: işaretsiz bir yaprak, hiçbir kelimenin yolu üzerinde olmayan gereksiz bir düğüm olurdu. Silme işlemi de bu yüzden işaretsiz yaprak bırakmaz.

5.3.1.4Örnek: yedi kelimelik trie

Biraz daha büyük bir örnek kelime sonu işaretinin neden şart olduğunu gösterir. Kelimeler ab, aba, abc, ad, ba, bad ve bag'dir. Yedi kelimenin toplam uzunluğu 2 + 3 + 3 + 2 + 2 + 3 + 3 = 18 karakterdir.

“ab” düğümüne yalnız şekle bakarak karar verilemez. Düğümün iki çocuğu (a ve c) vardır; yani “ab” başka kelimelerin önekidir. Aynı zamanda kendisi de bir kelimedir. Yapı bu iki durumu ayırt edemez; ayrımı yalnız kelimeSonu işareti yapar. İşaret olmasaydı “ab” ile “a” aynı türden düğümler olurdu ve “ab” sözlükte mi sorusunun cevabı kaybolurdu.

5.3.1.5Değer taşıyan trie

Trie yalnız bir kelime kümesini değil, bir eşlemeyi (map) de saklayabilir. Bunun için kelimeSonu bayrağının yerine düğümde bir değer tutulur. Değer null ise düğüm bir anahtarın sonu değildir; değilse o düğümde biten anahtarın değeridir. Böylece trie, anahtarları dizgi olan bir sözlük gibi çalışır.

Şekilde sekiz anahtar vardır ve her biri bir düğümde biter. “i”, “in” ve “inn” zincir hâlinde birbirinin önekidir; üçü de değer taşır. “t” düğümü ise iki dala ayrılır: “to” ve “te”. “te”nin üç çocuğu vardır: tea, ted ve ten. Anahtar sayısı 8, kök dışındaki düğüm sayısı 10'dur: A, i, in, inn, t, te, tea, ted, ten, to. Değer taşımayan iki düğüm (t ve te) yalnız yolu oluşturur.

Bu örnekte bir ayrıntı daha vardır: “A” büyük harftir. Çocukları 26 öğeli bir dizide tutan olağan trie yalnız küçük harfleri saklayabilir. Büyük harfli bir anahtar için ya daha geniş bir alfabe gerekir ya da çocuklar bir HashMap içinde tutulur. Alfabe büyüdükçe düğüm başına bellek de büyür; bu bedel trie'nin en zayıf yanıdır.

5.3.2Düğüm sınıfı

5.3.2.1TrieDugumu sınıfı

Trie'yi Java'da kurmanın en doğrudan yolu, her düğümde alfabenin her harfi için bir çocuk referansı tutmaktır. Alfabe küçük İngilizce harflerden oluşuyorsa her düğümde 26 öğeli bir dizi yeterlidir. Dizinin i. hücresi, düğümden i. harfle inilen çocuğu gösterir; o harfle başlayan bir devam yoksa hücre null'dır.

public class TrieDugumu {
  TrieDugumu[] cocuk;  // 'a'..'z'
  boolean kelimeSonu;  // kelime biter mi?

  public TrieDugumu() {
    kelimeSonu = false;
    cocuk = new TrieDugumu[26];
  }
}

Sınıfın iki alanı vardır. cocuk dizisi 26 referans tutar; Java yeni bir dizinin bütün referans hücrelerini null ile başlatır. kelimeSonu, kökten bu düğüme gelen yolun kümedeki bir kelime olup olmadığını söyler; yapıcıda false yapılır. Java bu değeri de varsayılan olarak verir, ama açıkça yazmak niyeti belli eder.

Sınıfta karakterin kendisi saklanmaz. Bir düğümün hangi karakteri temsil ettiği, ebeveyninin dizisinde hangi indiste durduğundan anlaşılır. Kökün cocuk[0] hücresindeki düğüm “a”dır, cocuk[3] hücresindeki düğüm “d”dir. Karakteri ayrıca saklamak bellek harcamaktan başka bir şey kazandırmaz. Ancak bazı türevlerde, örneğin üçlü arama trie'sinde, karakter düğümün içinde tutulmak zorundadır.

Trie'nin kendisi, kökü tutan bir sınıftır. Notta verilen bütün metotlar bu sınıfın içinde yazılmış sayılır ve kok alanını kullanır:

public class Trie {
  private final TrieDugumu kok = new TrieDugumu();
  // ekle, ara, onekVarMi, tamamla, sil ... bu sınıfın metotlarıdır
}

Şekil 5.3.6 kökün dizisini açık hâliyle gösterir. 26 hücrenin yalnız ikisi doludur. Bu tablo trie'nin bellek sorununun ilk işaretidir. Kökün altındaki düğümlerde durum daha da seyrektir: “an” düğümünde 2, “a” düğümünde yalnız 1 hücre doludur. Yapraklarda dizinin 26 hücresinin hepsi boştur, ama dizi yine de ayrılmıştır.

5.3.2.2Karakterden indise

Bir karakterin dizideki indisini bulmak için Java'nın char türünün bir sayı olduğu kullanılır. char, karakterin UTF-16 kod değerini saklar ve aritmetik işlemlerde int'e dönüşür. Küçük harflerin kodları ardışıktır: 'a' 97'dir, 'z' 122'dir. Bu yüzden ch - 'a' ifadesi 'a'yı 0'a, 'z'yi 25'e eşler.

Çocuğa erişim bir dizi indisiyle yapıldığı için O(1)'dir: dugum.cocuk[ch - 'a']. “and” kelimesi için sırasıyla cocuk[0], cocuk[13] ve cocuk[3] kullanılır. Bu hız, dizi gösteriminin en büyük üstünlüğüdür. Çocuk bulmak için ne karşılaştırma ne de hash hesabı gerekir.

Aynı formül alfabe dışındaki karakterlerde çalışmaz. Büyük 'A' harfinin kodu 65'tir ve 'A' - 'a' = 65 − 97 = −32 olur. Türkçe 'ç' harfinin kodu 231'dir: 'ç' - 'a' = 231 − 97 = 134. 'ş' için sonuç 351 − 97 = 254'tür. Bu indislerin hiçbiri 0–25 aralığında değildir ve dizi erişimi ArrayIndexOutOfBoundsException fırlatır. Çözüm iki türlüdür: girdi önceden küçük harfe ve a–z alfabesine dönüştürülür ya da çocuklar karakterle anahtarlanan bir HashMap'te tutulur.

5.3.3Ekleme

5.3.3.1Algoritma ve kod

Bir kelimeyi trie'ye eklemek, kelimenin yolunu kökten başlayarak yürümek ve eksik kalan kısmı tamamlamaktır. Yolun başı başka kelimelerle paylaşılıyorsa o kısım zaten vardır; ekleme ilk eksik karakterden sonra yeni düğümler açar. Yol bitince son düğüm işaretlenir.

1. Kökten başlanır.
2. Kelimenin her karakteri için ilgili çocuğa bakılır: cocuk[ch − 'a'].
3. Çocuk null ise yeni düğüm oluşturulur; varsa (ortak önek) mevcut düğüm kullanılır.
4. O çocuğa ilerlenir.
5. Karakterler bitince son düğümde kelimeSonu = true yapılır.

public void ekle(String kelime) {
  TrieDugumu dugum = kok;
  for (char ch : kelime.toCharArray()) {
    int i = ch - 'a';
    if (dugum.cocuk[i] == null)
      dugum.cocuk[i] = new TrieDugumu();
    dugum = dugum.cocuk[i];
  }
  dugum.kelimeSonu = true;
}

Kod bu beş adımı satır satır izler. dugum değişkeni kökle başlar ve döngünün her turunda bir düzey aşağı iner. toCharArray() kelimeyi karakter dizisine çevirir; for-each döngüsü karakterleri soldan sağa verir. Her karakter için i = ch - 'a' hesaplanır. dugum.cocuk[i] == null ise o karakterle devam eden bir yol henüz yoktur; yeni bir TrieDugumu oluşturulur ve hücreye bağlanır. Koşul yanlışsa yol zaten vardır ve hiçbir şey oluşturulmaz. İki durumda da dugum = dugum.cocuk[i] ile çocuğa inilir. Döngü bittiğinde dugum, kelimenin son karakterinin düğümüdür ve işaretlenir.

Kodun bir özelliği dikkat çeker: ekleme hiçbir zaman var olan bir düğümü değiştirmez, yalnız yeni düğüm bağlar ve son düğümün işaretini true yapar. Aynı kelime ikinci kez eklenirse döngü bütün düğümleri hazır bulur, yeni düğüm açmaz ve zaten true olan işareti yeniden true yapar. Yapı değişmez. Trie bu yüzden bir küme gibi davranır: tekrar eden kelimeler bir kez saklanır.

5.3.3.2Adım adım: and, ant, dad, do

Boş trie'ye sırayla and, ant, dad ve do eklensin. Başlangıçta trie yalnız kökten oluşur: kökün 26 çocuğunun hepsi null'dır ve kelimeSonu = false'tur. Tablo 5.3.3, her karakterde ilgili hücrenin durumunu ve yapılan işi verir.

“and” eklenirken trie boştur; üç karakterin üçü de yeni düğüm açar ve son düğüm işaretlenir. Kökten itibaren cocuk[0] → cocuk[13] → cocuk[3] yolu kurulmuştur.

“ant” eklenirken ilk iki karakter hazır bir yol bulur. 'a' için cocuk[0], 'n' için cocuk[13] doludur; döngü yalnız ilerler. 't' için cocuk[19] boştur ve tek bir yeni düğüm açılır. “an” öneki iki kelime arasında paylaşılmıştır. Bu paylaşım trie'nin bellek kazancının kaynağıdır.

“dad” kökte boş bir hücreye (cocuk[3]) rastlar ve üç yeni düğümle kendi dalını kurar. Dikkat edilirse “dad” içindeki iki 'd' farklı düğümlerdir: biri kökün çocuğu, öbürü “da”nın çocuğudur. Aynı karakter farklı öneklerde farklı düğümlere karşılık gelir. Son olarak “do”, 'd' düğümünü paylaşır ve 'o' için tek bir yeni düğüm açar.

Dört eklemede açılan yeni düğümlerin sayısı sırasıyla 3, 1, 3 ve 1'dir; toplam 8. Kelimelerin toplam uzunluğu 11 olduğuna göre üç karakterlik bir paylaşım sağlanmıştır. Kelimeler başka bir sırayla eklenseydi ara durumlar değişirdi, ama son trie aynı olurdu. Trie'nin şekli yalnız kelime kümesine bağlıdır, ekleme sırasına bağlı değildir. Bu özellik ikili arama ağacından önemli bir farktır: orada ekleme sırası ağacın yüksekliğini belirler.

5.3.3.3Kod izleme: ekle("ant")

Kodun satır düzeyinde nasıl çalıştığını görmek için trie'de yalnız “and” varken ekle("ant") çağrısı izlensin. Tablo 5.3.4 her adımda değişkenlerin değerini verir.

İzleme üç noktayı açıkça gösterir. Birincisi, koşul yalnız bir kez doğru olur; yani yalnız bir düğüm oluşturulur. İkincisi, yeni düğüm oluşturulduğu anda kelimeSonu değeri false'tur; işaret ancak döngü bittikten sonra ve yalnız son düğüme konur. Ara düğümler (“a”, “an”) işaretsiz kalır. Üçüncüsü, döngü her zaman kelimenin bütün karakterlerini dolaşır; ekleme erken bitmez. Bu yüzden ekleme her durumda tam L tur sürer.

5.3.3.4Eklemenin maliyeti

Döngü kelimenin her karakteri için bir kez döner. Her turda bir indis hesabı, bir dizi erişimi, gerekirse bir düğüm oluşturma ve bir atama yapılır. Düğüm oluşturmak 26 hücrelik bir dizi ayırmak demektir. Bu iş alfabe boyu kadar sürer, ama alfabe sabit kabul edildiği için sabit bir maliyettir. Toplam süre O(L)'dir; L kelimenin uzunluğudur. Süre trie'deki kelime sayısından tamamen bağımsızdır.

Bellek açısından bir ekleme en çok L yeni düğüm açar; bu en kötü durum, kelimenin hiçbir öneki trie'de yokken ortaya çıkar. Her düğüm 26 referans ve bir mantıksal değer taşır, yani bir ekleme en çok O(L · M) bellek ayırır. Kelime tamamen var olan bir yolun üzerindeyse (örneğin “kalem” varken “ka” eklenirse) hiç düğüm açılmaz; yalnız işaret değişir.

5.3.4Arama ve önek sorguları

5.3.4.1Arama algoritması

Arama, eklemenin okuma yapan karşılığıdır. Aynı yol yürünür; fark, eksik bir dalla karşılaşıldığında düğüm oluşturulmaması, aramanın hemen bitirilmesidir.

1. Kökten başlanır.
2. Her karakter için ilgili dala (çocuğa) gidilir.
3. Dal yoksa (null) kelime trie'de yoktur.
4. Kelimenin sonuna gelince kelimeSonu denetlenir: true ise kelime bulunmuştur; false ise kelime yoktur, yalnız var olan bir kelimenin önekidir.

public boolean ara(String kelime) {
  TrieDugumu dugum = kok;
  for (char ch : kelime.toCharArray()) {
    int i = ch - 'a';
    if (dugum.cocuk[i] == null)
      return false;
    dugum = dugum.cocuk[i];
  }
  return dugum.kelimeSonu;
}

Kod eklemeyle neredeyse aynıdır. Farklı olan iki satırdır. Birincisi: çocuk null ise yeni düğüm oluşturulmaz, return false ile çıkılır. İkincisi: döngü bittikten sonra işaret konmaz, okunur: return dugum.kelimeSonu. Bu son satır aramanın en önemli satırıdır. Yolun bütün karakterleri bulunmuş olsa bile, son düğüm işaretli değilse kelime trie'de yoktur.

Arama da O(L) sürer. Kelime trie'de yoksa döngü daha erken bitebilir: yol k. karakterde kesiliyorsa yalnız k tur döner. Trie'de bir milyon kelime de olsa “dad” en çok 3 adımda bulunur ya da bulunamaz.

5.3.4.2Kod izleme: ara("dad")

Trie and, ant, dad ve do kelimelerinden oluşsun. ara("dad") çağrısının izlemesi Tablo 5.3.5'tedir.

Birinci ve üçüncü turda aynı indis (3) kullanılır, ama farklı düğümlerin dizilerinde: ilki kökün, ikincisi “da”nın dizisidir. Aramanın her turu bir düzey aşağıda çalışır. Üç tur sonunda yol tamamdır ve son düğümün işareti okunur.

5.3.4.3Aramanın üç sonucu

Bir arama üç farklı biçimde sonuçlanabilir. Üçünü ayırt etmek, arama ile önek sorgusu arasındaki farkı anlamanın da yoludur.

• ara("dad") → true. Bütün karakterler bulunur ve son düğüm işaretlidir.
• ara("da") → false. Yol vardır, ama “da” düğümünde kelimeSonu = false'tur. “da” yalnız “dad”in önekidir. Döngü iki turu tamamlar ve son satır false döndürür.
• ara("dog") → false. “do” düğümünün cocuk[6] hücresi ('g' − 'a' = 6) null'dır. Dal yoktur; döngü üçüncü turda erken çıkar. “do” bir kelime olsa bile bu sonucu değiştirmez.

İkinci ve üçüncü durum aynı değeri (false) döndürür, ama nedenleri farklıdır. İkincisinde yol tamdır, eksik olan işarettir. Üçüncüsünde yol kesilmiştir. Bu fark önek sorgusunda belirleyici olur: önek sorgusu ikinci durumda true, üçüncüsünde false döndürür.

5.3.4.4Önek sorgusu

Önek sorgusu (prefix query), trie'de verilen önekle başlayan en az bir kelime olup olmadığını sorar. Java'nın String sınıfındaki startsWith metodunun bir küme üzerindeki karşılığıdır. Trie'de bu soru, önekin yolunun var olup olmadığı sorusuyla aynıdır. Trie'deki her düğüm, en az bir kelimenin yolu üzerindedir; çünkü düğümler yalnız ekleme sırasında açılır ve silme işaretsiz yaprak bırakmaz. Bu yüzden yol varsa o önekle başlayan bir kelime de vardır.

public boolean onekVarMi(String onek) {
  TrieDugumu dugum = kok;
  for (char ch : onek.toCharArray()) {
    int i = ch - 'a';
    if (dugum.cocuk[i] == null)
      return false;
    dugum = dugum.cocuk[i];
  }
  return true;  // ara: dugum.kelimeSonu
}

Kod ara ile aynıdır; tek fark son satırdır. onekVarMi döngüyü yolu kesilmeden bitirirse true döndürür ve son düğümün işaretine bakmaz. Yorum satırı farkı açıkça yazar: ara bu noktada dugum.kelimeSonu döndürür. Süre O(P)'dir; P önekin uzunluğudur.

Tablodaki sonuçlar iki metodun tek farkını gösterir: işaretsiz bir düğümde biten sorgularda ara false, onekVarMi true döndürür. Yolun kesildiği sorgularda ikisi de false döndürür.

Kod izlemesi için iki çağrı alınsın: onekVarMi("da") ve onekVarMi("dog"). İlk çağrıda dugum köke konur. 'd' için i = 3, cocuk[3] doludur ve “d” düğümüne inilir. 'a' için i = 0, cocuk[0] doludur ve “da”ya inilir. Önek bitmiştir ve yol kesilmemiştir; metot true döndürür. “da” düğümü işaretsiz olduğu için ara("da") burada false verirdi.

İkinci çağrıda dugum yeniden köke konur. 'd' (i = 3) ve 'o' (i = 14) için hücreler doludur; “do” düğümüne inilir. 'g' için i = 6'dır ve “do” düğümünün cocuk[6] hücresi null'dır. Metot false döndürür. “do” bir kelimedir, ama “dog” ile başlayan hiçbir kelime yoktur.

5.3.4.5Önek sayacı

onekVarMi bir önekle başlayan kelime olup olmadığını söyler, ama kaç tane olduğunu söylemez. “an ile başlayan kaç kelime var?” sorusu, önek düğümünün alt ağacındaki işaretli düğümleri saymayı gerektirir. Bu sayım alt ağacın bütün düğümlerini dolaşır. Alt ağaçta S düğüm varsa ve her düğümde 26 hücre denetleniyorsa sorgu O(P + S · M) sürer. Sözlük büyükse ve önek kısaysa (örneğin tek harf) bu, sözlüğün büyük bir bölümünü gezmek demektir.

Daha iyi bir yol, sayımı ekleme sırasında yapmaktır. TrieDugumu sınıfına bir int gecen alanı eklenir. Bu alan, düğümün yolundan geçen kelime sayısını tutar. Ekleme kökten başlayıp her geçtiği düğümün sayacını bir artırır. Sorgu sırasında önek düğümüne inilir ve sayaç okunur.

void ekle(String kelime) {
  TrieDugumu d = kok;
  d.gecen++;
  for (char ch : kelime.toCharArray()) {
    int i = ch - 'a';
    if (d.cocuk[i] == null) d.cocuk[i] = new TrieDugumu();
    d = d.cocuk[i];
    d.gecen++;          // bir kelime daha geçti
  }
  d.kelimeSonu = true;
}
int onekSayisi(String onek) {
  TrieDugumu d = kok;
  for (char ch : onek.toCharArray()) {
    d = d.cocuk[ch - 'a'];
    if (d == null) return 0;
  }
  return d.gecen;
}

Eklemede kökün sayacı döngüden önce artırılır; böylece kökte trie'deki toplam kelime sayısı tutulur. Döngü içindeki d.gecen++ satırı, yeni oluşturulmuş ya da var olan her düğümün sayacını artırır. onekSayisi metodunda yol kesilirse 0 döner; yol bitince önek düğümünün sayacı döner. Döngü önce çocuğa iner, sonra null denetimi yapar; bu sıra ara'dakinden farklıdır ama aynı işi görür.

Sayaç yöntemi sorguyu O(P)'ye indirir. Bedeli düğüm başına bir int'tir; 26 referanslık bir düğümde bu ek bellek çok küçüktür. Silme işleminde ise yol boyunca bütün sayaçlar bir azaltılmalıdır. Azaltma unutulursa sayaçlar silinmiş kelimeleri saymaya devam eder. Ayrıca aynı kelime iki kez eklenirse sayaçlar iki kez artar; kümede tekrar istenmiyorsa ekleme öncesinde ara ile kelimenin varlığı denetlenmelidir.

5.3.4.6Joker karakterli arama

Bulmaca çözen ya da kelime oyunu oynayan bir program şu soruyu sorabilir: “d, bilinmeyen bir harf, d” biçiminde bir kelime var mı? Desende nokta (.) herhangi bir harf yerine geçer. Bu tür sorguya joker karakterli arama (wildcard search) denir. Normal harf aramayı tek bir yola indirir. Nokta ise o düzeydeki her dolu dalın denenmesini gerektirir. Arama bu yüzden özyinelemeli yazılır.

boolean joker(TrieDugumu d, String s, int j) {
  if (d == null) return false;
  if (j == s.length()) return d.kelimeSonu;
  char ch = s.charAt(j);
  if (ch != '.')
    return joker(d.cocuk[ch - 'a'], s, j + 1);
  for (int i = 0; i < 26; i++)
    if (joker(d.cocuk[i], s, j + 1)) return true;
  return false;
}

Metot üç parametre alır: şu anki düğüm d, desen s ve desende sıradaki karakterin indisi j. İlk çağrı joker(kok, desen, 0) biçimindedir. Düğüm null ise bu dal yoktur ve false döner. Desen bitmişse (j == s.length()) sonuç düğümün işaretidir; tıpkı ara'nın son satırında olduğu gibi. Sıradaki karakter bir harfse yalnız o harfin çocuğuna inilir. Nokta ise 26 çocuğun her biri sırayla denenir; birinde eşleşme bulunursa true hemen yukarı taşınır ve kalan dallar denenmez. Boş bir çocuk için yapılan çağrı ilk satırda hemen döner.

Maliyet desene ve trie'ye bağlıdır. Desende k nokta varsa en kötü durumda 26^k dal denenir. Ancak boş dallar hemen döndüğü için gerçek maliyet, trie'de gerçekten var olan yollarla sınırlıdır. “....” deseni bütün trie'yi en çok dördüncü düzeye kadar gezer ve 4 harfli kelime bulamaz. Hash tablosu bu sorguyu ancak bütün kelimeleri tek tek deneyerek cevaplayabilir: deseni bilinen bir anahtara çevirmenin yolu yoktur.

5.3.4.7Yazım denetimi: trie üzerinde düzenleme uzaklığı

Yazım denetleyicisi sözlükte bulunmayan bir kelimeye öneriler sunar. Öneriler, kelimeye “yakın” sözlük kelimeleridir. Yakınlığın ölçüsü olarak çoğunlukla düzenleme uzaklığı (edit distance) kullanılır: bir dizgiyi ötekine çevirmek için gereken en az tek karakterlik ekleme, silme ve değiştirme sayısı. Bu ölçünün öteki adı Levenshtein uzaklığıdır. “dod” ile “dad” arasındaki uzaklık 1'dir (o → a). “dod” ile “do” arasındaki uzaklık da 1'dir (son d silinir).

İki dizgi arasındaki uzaklık dinamik programlamayla bir tablo doldurularak hesaplanır. Sorgu dizgisi q, sözlük kelimesi w olsun. Tablonun i. satırı, w'nun ilk i karakteri ile q'nun bütün önekleri arasındaki uzaklıkları tutar. Satır, bir önceki satırdan şu kuralla hesaplanır:

S_i[0] = i,   S_i[j] = min( S_i[j − 1] + 1,   S_i−1[j] + 1,   S_i−1[j − 1] + (w_i ≠ q_j ? 1 : 0) )

Üç terim sırasıyla ekleme, silme ve değiştirmenin (ya da karakterler eşitse ücretsiz geçişin) maliyetidir. Son satırın son hücresi iki dizgi arasındaki uzaklıktır.

Saf yöntem, sözlükteki her kelime için ayrı bir tablo doldurur. Ama tablonun i. satırı yalnız kelimenin ilk i karakterine bağlıdır. Ortak öneki olan kelimeler bu satırları paylaşır. Trie tam olarak bu paylaşımı sağlar: her düğüm bir önektir ve düğümün satırı ebeveyninin satırından tek adımda hesaplanır. Trie derinlik öncelikli gezilir; her düğümde bir satır üretilir. “d” düğümünün satırı bir kez hesaplanır ve hem “dad” hem “do” için kullanılır.

Gezinmeye bir de budama eklenir. Bir satırın en küçük değeri k'yı aşıyorsa, bu düğümün altındaki hiçbir kelime sorguya k uzaklıkta olamaz. Yeni satırın her hücresi, doğrudan ya da soldaki komşusu üzerinden, önceki satırın bir hücresine 0 ya da daha fazla eklenerek elde edilir. Bu yüzden satırın en küçük değeri derinlik arttıkça azalmaz. Böyle bir düğümün alt ağacına inilmez.

Gezinti sonunda öneriler dad (o → a) ve do (son d silinir) olur. “an” satırının en küçüğü 2'dir ve 1'i aşar; “and” ve “ant” düğümlerine hiç inilmez. Gerçekten de “and” ile “dod” arasındaki uzaklık 2, “ant” ile 3'tür. Ziyaret edilen düğümler a, an, d, da, dad ve do'dur. Her satır O(|q|) iş tutar. Budama sayesinde büyük bir sözlüğün çoğu hiç ziyaret edilmez. Aynı gezinti, klavyede yan yana harfleri daha ucuz sayan ağırlıklı bir uzaklıkla da çalışır. Ancak k büyüdükçe budama zayıflar ve ziyaret edilen düğüm sayısı hızla artar; uygulamalarda k çoğunlukla 1 ya da 2 seçilir.

5.3.5Otomatik tamamlama ve en uzun ortak önek

5.3.5.1tamamla ve topla

Otomatik tamamlama (autocomplete), yazılan öneke göre olası kelimeleri önerir. Trie'de bu iş iki aşamada yapılır. Önce önek düğümü bulunur; bu adım önek sorgusuyla aynıdır. Ardından bu düğümün alt ağacı derinlik öncelikli gezilir ve işaretli her düğümün kelimesi listeye eklenir.

List<String> tamamla(String onek) {
  List<String> sonuc = new ArrayList<>();
  TrieDugumu d = dugumBul(onek);
  if (d != null)
    topla(d, new StringBuilder(onek), sonuc);
  return sonuc;
}
void topla(TrieDugumu d, StringBuilder yol,
           List<String> sonuc) {
  if (d.kelimeSonu) sonuc.add(yol.toString());
  for (int i = 0; i < 26; i++)
    if (d.cocuk[i] != null) {
      yol.append((char) ('a' + i));
      topla(d.cocuk[i], yol, sonuc);
      yol.setLength(yol.length() - 1);
    }
}

tamamla önce dugumBul yardımcısıyla önek düğümünü arar. Yardımcı, onekVarMi'nin boolean yerine düğümün kendisini döndüren sürümüdür:

TrieDugumu dugumBul(String onek) {
  TrieDugumu d = kok;
  for (char ch : onek.toCharArray()) {
    d = d.cocuk[ch - 'a'];
    if (d == null) return null;  // yol kesildi
  }
  return d;
}

Önek düğümü yoksa dugumBul null döndürür ve tamamla boş bir liste verir. Düğüm varsa topla çağrılır. topla'nın yol parametresi, kökten şu anki düğüme kadarki dizgiyi tutan bir StringBuilder'dır; başlangıçta önekin kendisidir. Metot önce düğümün işaretine bakar: düğüm bir kelime sonuysa yol'un o anki değeri sonuca eklenir. Sonra 26 indis sırayla dolaşılır. Dolu her çocuk için üç iş yapılır: çocuğun karakteri yol'a eklenir, çocuk için topla özyinelemeli çağrılır, çağrı dönünce eklenen karakter silinir.

Son adım, yol.setLength(yol.length() - 1), bir geri izleme (backtracking) adımıdır. Bütün çağrılar aynı StringBuilder nesnesini paylaşır. Bir alt ağaçtan dönülürken o alt ağaç için eklenen karakter silinmezse, bir sonraki kardeşin kelimesi yanlış bir önekle kurulur. Her çağrı yol'u, kendisine verildiği hâliyle geri bırakır.

5.3.5.2Kod izleme: tamamla("te")

Trie a, to, tea, ted, ten, i, in ve inn kelimelerinden oluşsun. Bu, değer taşıyan trie örneğinin küçük harfli biçimidir. tamamla("te") çağrısı izlensin.

Sonuç [tea, ted, ten]'dir ve alfabetik sıradadır. Bu sıra rastlantı değildir: döngü indisleri 0'dan 25'e dolaşır ve indis sırası harf sırasıdır (a < d < n). Ayrıca bir düğüm, çocuklarından önce listeye eklenir; bu yüzden bir önek, onu uzatan kelimelerden önce gelir. Kelimeler trie'ye hangi sırayla eklenmiş olursa olsun çıktı aynıdır.

Maliyet iki parçalıdır. Önek düğümünü bulmak O(P) sürer. Alt ağaçta S düğüm varsa her biri bir kez ziyaret edilir ve her ziyarette 26 hücre denetlenir: O(S · M). Toplam O(P + S · M)'dir. Ayrıca her bulunan kelime için toString() bir kopya üretir; bu kopyaların toplam uzunluğu çıktının boyudur. Önek kısaysa alt ağaç büyük olabilir. Uygulamalar bu yüzden çoğunlukla ilk birkaç öneriyle yetinir. En sık kullanılan kelimeleri önce göstermek için düğümlerde kullanım sıklığı da saklanır.

5.3.5.3En uzun ortak önek

Bir dizgi kümesinin en uzun ortak öneki (longest common prefix), kümedeki bütün dizgilerin paylaştığı en uzun baş kısımdır. Trie'de bu önek kökten başlayan tek dallı bir zincirdir. Kökten inilir; düğümün tek çocuğu varsa ve düğüm bir kelimenin sonu değilse ilerlenir. Geçilen karakterler cevaptır.

String enUzunOrtakOnek() {
  StringBuilder sb = new StringBuilder();
  TrieDugumu d = kok;
  while (!d.kelimeSonu) {
    int tek = -1, sayi = 0;
    for (int i = 0; i < 26; i++)
      if (d.cocuk[i] != null) { sayi++; tek = i; }
    if (sayi != 1) break;  // dal ya da yaprak
    sb.append((char) ('a' + tek));
    d = d.cocuk[tek];
  }
  return sb.toString();
}

Döngü koşulu !d.kelimeSonu'dur: işaretli bir düğüme gelindiğinde durulur. Döngü gövdesinde 26 hücre sayılır; sayi dolu hücre sayısını, tek son görülen dolu indisi tutar. sayi 1 değilse (0 ise yaprağa, 2 ya da daha fazlaysa dallanmaya gelinmiştir) döngü kırılır. Tek çocuk varsa karakteri eklenir ve çocuğa inilir.

“kar” düğümünün tek çocuğu (t) vardır, ama iniş orada durur. Neden? Ortak önek kümedeki her kelimenin öneki olmalıdır. “kar” kelimesinin kendisi “kar”dan uzun bir önek taşıyamaz. Koşulda işaret denetimi olmasaydı iniş “karton”a kadar sürerdi ve yanlış olarak “karton” döndürülürdü. Trie'de yalnız kart ve karton olsaydı iniş “kart”a kadar devam ederdi ve orada kelimeSonu durdururdu: cevap “kart” olurdu.

Maliyet, cevabın uzunluğu P ise O(P · M)'dir: her düzeyde 26 hücre sayılır. Kökün birden fazla çocuğu varsa döngü ilk turda kırılır ve cevap boş dizgidir; örneğin and, ant, dad, do kümesinin ortak öneki yoktur.

5.3.6Silme

5.3.6.1Üç durum

Silme, trie işlemlerinin en dikkat isteyenidir. Bir kelimenin yolu başka kelimelerle paylaşılıyor olabilir. Yolu baştan sona silmek, öneki paylaşan öteki kelimeleri de yok eder. Bu yüzden silme yalnız kelimeye özgü düğümleri kaldırmalıdır. Kelimenin trie'deki konumuna göre üç durum ortaya çıkar.

1. Kelime başka bir kelimenin önekidir. Son düğümün çocuğu vardır. Yalnız kelimeSonu = false yapılır; düğüm silinmez, çünkü başka kelimelerin yolu üzerindedir.
2. Kelimenin kendine ait bir kuyruğu vardır. Sondan başa doğru, çocuğu kalmayan ve işaretsiz düğümler silinir. Paylaşılan bir öneke ya da başka bir kelimenin sonuna gelince durulur.
3. Kelime trie'de yoktur. Dal bulunamaz ya da son düğüm işaretsizdir. Hiçbir şey değişmez.

İkinci durumdaki “kuyruk”, kelimenin son düğümünden yukarı doğru, yalnız bu kelimeye hizmet eden düğümler zinciridir. Bir düğüm iki koşul birlikte sağlanırsa silinebilir: çocuğu yoktur ve işaretsizdir. Çocuğu varsa başka bir kelimenin yolundadır. İşaretliyse kendisi bir kelimedir. Kuyruk, bu iki koşuldan birini bozan ilk düğümde biter.

5.3.6.2Adım adım: app, apple, apt

Trie app, apple ve apt kelimelerinden oluşsun. Kök dışında 6 düğüm vardır: a, ap, app, appl, apple, apt. Aşağıdaki iki senaryonun ikisi de bu ilk trie'den başlar.

Senaryo 1: sil("app"). a → p → p yolu izlenir. “app” düğümü işaretlidir, yani kelime vardır. İşaret kaldırılır: kelimeSonu = false. Düğümün 'l' çocuğu olduğu için silinmez. Bu durum 1'dir. “apple” hâlâ bulunur; düğüm sayısı 6 olarak kalır.

Senaryo 2: sil("apple"). Yol a-p-p-l-e izlenir ve “apple” bulunur. 'e' düğümünün işareti kalkar. Bu düğümün çocuğu yoktur; ebeveyni onu siler (cocuk[4] = null). Sonra 'l' düğümüne bakılır: artık çocuksuz ve işaretsizdir, o da silinir. Ardından “app” düğümüne gelinir. Bu düğüm işaretlidir, çünkü “app” başka bir kelimedir. Silme burada durur.

İki senaryo, silme kararlarının aşağıdan yukarı verildiğini gösterir. Bir düğümün silinip silinmeyeceği, çocuklarının silinmesine bağlıdır. 'l' düğümü başlangıçta silinemezdi, çünkü 'e' çocuğu vardı. 'e' silindikten sonra 'l' silinebilir hâle geldi. Bu bağımlılık, silmenin doğal olarak özyinelemeyle yazılmasının nedenidir: önce kelimenin sonuna inilir, kararlar dönüş yolunda verilir.

5.3.6.3Özyinelemeli kod

// true: ebeveyn d'yi silebilir
boolean sil(TrieDugumu d, String k, int j) {
  if (j == k.length()) {        // kelime bitti
    if (!d.kelimeSonu) return false;
    d.kelimeSonu = false;
    return bosMu(d);            // çocuksuz mu?
  }
  int i = k.charAt(j) - 'a';
  TrieDugumu c = d.cocuk[i];
  if (c == null) return false;  // kelime yok
  if (sil(c, k, j + 1)) {
    d.cocuk[i] = null;          // çocuğu sil
    return !d.kelimeSonu && bosMu(d);
  }
  return false;
}

Metodun dönüş değeri ebeveyne iletilen bir karardır: true, ebeveynin bu düğümü silebileceği anlamına gelir. Çağrı sil(kok, kelime, 0) biçimindedir; kökün dönüş değeri yok sayılır, çünkü kök hiçbir zaman silinmez. j, kelimede sıradaki karakterin indisidir.

Metot iki kısımdan oluşur. İlk kısım taban durumdur: j == k.length() ise kelimenin son düğümüne gelinmiştir. Düğüm işaretsizse kelime trie'de yoktur ve false döner (durum 3). İşaretliyse işaret kaldırılır ve düğümün çocuğu olup olmadığına bakılır. Çocuğu yoksa true döner: ebeveyn bu düğümü silebilir. Çocuğu varsa false döner (durum 1).

İkinci kısım özyinelemeli durumdur. Sıradaki karakterin çocuğu c bulunur. c null ise kelime trie'de yoktur ve false döner (durum 3). Varsa sil(c, k, j + 1) çağrılır. Çağrı true döndürürse çocuk silinebilir demektir: d.cocuk[i] = null ile bağ koparılır. Ardından aynı soru bu düğüm için sorulur: düğüm işaretsiz ve artık çocuksuz mu? Cevap bir üst düzeye iletilir. Çağrı false döndürürse hiçbir şey silinmez ve false yukarı taşınır. Bir düzeyde zincir kırılınca üstteki hiçbir düğüm silinmez.

Kod, bosMu yardımcısını kullanır. Yardımcı 26 hücrenin hepsinin null olup olmadığını denetler:

boolean bosMu(TrieDugumu d) {
  for (int i = 0; i < 26; i++)
    if (d.cocuk[i] != null) return false;
  return true;
}

Java'da bir düğümü “silmek”, ona giden son referansı null yapmaktır. Kopan düğüm artık erişilebilir değildir ve çöp toplayıcı belleği geri alır. Bu yüzden kod yalnız ebeveyndeki hücreyi boşaltır.

5.3.6.4Kod izleme: sil("dad")

Trie and, ant, dad ve do kelimelerinden oluşsun. sil(kok, "dad", 0) çağrısı izlensin. Özyineleme önce üç düzey iner, sonra dönüş yolunda kararlar verilir. Tablo 5.3.12 iniş ve dönüş adımlarını sırayla verir.

İzlemede iki düğüm silinir: “dad” ve “da”. “d” düğümü işaretsizdir, ama “do” için 'o' çocuğu vardır; bosMu false verir ve zincir orada kırılır. Kökteki çağrı false alır ve kökün dönüş değeri yok sayılır. Kalan trie and, ant ve do kelimelerini içerir; kök dışında 6 düğüm vardır.

Silmenin maliyeti şöyle hesaplanır. İniş L düzey sürer. Dönüşte her düzeyde en çok bir bosMu çağrısı yapılır ve her biri 26 hücreyi tarar. Toplam O(L · M)'dir. Düğümde dolu çocuk sayısını tutan bir sayaç olsaydı bosMu sabit sürede cevap verirdi ve silme O(L)'ye inerdi. Bu sayaç, eklemede bir hücre doldurulurken artırılır, silmede bir hücre boşaltılırken azaltılır.

5.3.7Analiz

5.3.7.1Karmaşıklık

Trie işlemlerinin maliyeti iki büyüklüğe bağlıdır: işlenen dizginin uzunluğu ve alfabenin boyu. L kelimenin, P önekin uzunluğudur. M alfabenin boyudur; küçük İngilizce harflerde 26'dır. S, önek düğümünün alt ağacındaki düğüm sayısıdır.

Tablonun en önemli özelliği bir sütunun eksik olmasıdır: hiçbir satırda n, yani saklanan kelime sayısı yoktur. İkili arama ağacındaki log n çarpanı trie'de görünmez. Trie bir milyon kelime de saklasa “dad” aramasının adım sayısı 3'tür. Bu özellik, trie işlemlerinin maliyetini O(log n) ya da O(n) diye ifade etmenin neden yanlış olduğunu da açıklar.

Burada L'nin de bir sınırı olduğu unutulmamalıdır. Bir sözlükte n farklı kelime varsa ve alfabe M harfliyse kelimelerin en az bir kısmının uzunluğu log_M n mertebesinde olmak zorundadır. Kısa bir alfabeyle çok sayıda farklı kelime ancak uzun kelimelerle kurulabilir. Yine de gerçek sözlüklerde L küçüktür (Türkçe ve İngilizce kelimelerin çoğu 15 harften kısadır) ve trie'nin üstünlüğü pratikte geçerlidir.

Bellek gereksinimi O(N · M)'dir. N düğüm sayısıdır ve en çok bütün kelimelerin toplam uzunluğu artı 1'dir (kök). Bu sınıra, hiçbir kelime başka bir kelimeyle önek paylaşmıyorsa ulaşılır. Her düğüm M referanslık bir dizi taşıdığı için toplam bellek N · M ile orantılıdır.

5.3.7.2Bellek: sayısal örnek

and, ant, dad ve do kelimelerinin trie'si üzerinden bellek tek tek sayılsın.

Dolu referans sayısı kenar sayısına eşittir, çünkü her kenar tam olarak bir dolu hücreyle temsil edilir. Ağaçta kökten başka her düğümün tek bir ebeveyni olduğu için kenar sayısı N − 1 = 8'dir. Geri kalan 234 − 8 = 226 hücre boştur; oran 226 / 234 ≈ 0,966, yani yaklaşık %97'dir. Ortak önekler 11 karakteri 8 düğüme indirmiştir, ama 26 öğeli diziler belleğin neredeyse tamamını null ile doldurur.

Büyük ölçekte tablo daha da çarpıcıdır. Bir milyon düğümlü bir trie 26 milyon referans tutar. 64 bitlik bir Java sanal makinesinde bir referans 8 bayttır; sıkıştırılmış referanslar açıksa 4 bayttır. Yalnız referans dizileri 26 · 10⁶ · 8 ≈ 208 · 10⁶ bayt, yani yaklaşık 200 MB tutar; 4 baytlık referanslarla yaklaşık 100 MB. Buna her nesnenin başlık bilgisi eklenir. Alfabe büyüdükçe sorun ağırlaşır. Unicode'un temel düzlemi 65 536 karakterdir; her düğümde bu boyda bir dizi ayırmak açıkça olanaksızdır.

5.3.7.3Güçlü ve zayıf yanlar

Trie'nin güçlü yanları şunlardır:

• Hızlı önek tabanlı arama. Önek sorgusu, önek sayacı ve otomatik tamamlama doğal işlemlerdir.
• Kelime araması O(L) sürer ve süre kelime sayısından bağımsızdır.
• Ortak önekler bir kez saklanır. Önek paylaşımı yüksek kümelerde (sözlükler, URL'ler, dosya yolları) düğüm sayısı toplam karakter sayısının çok altında kalır.
• Sıra bilgisi korunur. Derinlik öncelikli gezinme kelimeleri sözlüksel sırada verir. Hash çakışması diye bir sorun yoktur; en kötü durum da O(L)'dir.

Zayıf yanları da açıktır:

• Yüksek bellek tüketimi, özellikle büyük alfabelerde. Alan karmaşıklığı O(N · M)'dir.
• Ortak öneki az olan kümelerde kazanç yoktur. Rastgele anahtarlarda neredeyse her karakter yeni bir düğüm açar.
• Çok sayıda küçük nesne. Bir arama, bellekte birbirinden uzak düğümlere atlar. İşlemcinin önbelleği (cache) bu erişim düzenini iyi karşılamaz. Bu yüzden aynı mertebede iki yapı arasında trie pratikte daha yavaş kalabilir.

5.3.7.4Çocukları saklamanın yolları

Trie'nin mantığı, çocukların nasıl saklandığından bağımsızdır. Değişen yalnız “ch karakterli çocuğu ver” işleminin nasıl yapıldığıdır. Dört yaygın seçenek vardır.

HashMap gösterimi Türkçe karakter sorununu da çözer. Anahtar, karakterin kendisidir; indis hesabı yoktur. Ekleme kodu şöyle kısalır:

class HaritaDugumu {
  Map<Character, HaritaDugumu> cocuk = new HashMap<>();
  boolean kelimeSonu;
}

void ekle(String kelime) {
  HaritaDugumu d = kok;
  for (char ch : kelime.toCharArray())
    d = d.cocuk.computeIfAbsent(ch, x -> new HaritaDugumu());
  d.kelimeSonu = true;
}

computeIfAbsent, anahtar haritada yoksa verilen fonksiyonla yeni bir değer oluşturup ekler ve değeri döndürür; anahtar varsa mevcut değeri döndürür. Böylece dizi sürümündeki “null ise oluştur, sonra in” iki adımı tek çağrıya iner. Bu trie'ye “çay”, “çam”, “şeker” ve “Ankara” eklenebilir; kökün haritasında 'A', 'ç' ve 'ş' anahtarları bulunur. Bedeli, her düğümde bir harita nesnesi ve hash hesabıdır. Ayrıca HashMap anahtarları sırasız tuttuğu için otomatik tamamlamanın alfabetik çıktısı kaybolur. Sıralı çıktı gerekiyorsa TreeMap kullanılır; erişim O(log M)'ye çıkar.

Seçim üç soruya göre yapılır: alfabe ne kadar büyük, bellek ne kadar kısıtlı, sıralı çıktı gerekli mi? Küçük ve sabit bir alfabede dizi en hızlısıdır. Büyük ya da önceden bilinmeyen alfabede harita gerekir. Bellek en önemli kısıtsa üçlü arama trie'si ya da sıkıştırılmış trie tercih edilir.

5.3.7.5Trie, hash tablosu ve dengeli BST

Dizgi anahtarları saklamak için üç yapı sık sık karşılaştırılır. Tablo 5.3.16, n kelimelik ve kelime uzunluğu L olan bir küme için tipik maliyetleri verir.

Tam kelime aramasında trie ile hash tablosu aynı mertebededir. Bu ilk bakışta şaşırtıcı görünebilir, çünkü hash tablosu sık sık “O(1)” diye anılır. Ama o O(1), anahtarın hash değeri hesaplanmış kabul edildiğinde geçerlidir. Bir dizginin hash değerini hesaplamak için L karakterin hepsi okunur. Eşitlik denetimi de L karakteri karşılaştırır. Dolayısıyla hash tablosu da O(L)'dir. Dengeli BST'de ise log n düğüm ziyaret edilir ve her ziyarette iki dizgi karşılaştırılır; bu karşılaştırma en çok L karakter okur.

Trie'nin asıl farkı önek ve sıra sorgularındadır. Hash tablosu öneki hiç desteklemez. BST sıralı olduğu için önekle başlayan kelimeleri ardışık bir aralıkta tutar ve aralığın başını O(P · log n)'de bulur. Trie aynı soruyu log n çarpanı olmadan cevaplar. Bunun karşılığında trie bellekte en pahalı yapıdır. Seçim, yapılacak sorguların türüne göre yapılır: yalnız tam eşleşme gerekiyorsa hash tablosu yeterlidir; önek ve sıra sorguları sıksa trie öne çıkar.

5.3.7.6Trie ile sıralama

Trie'nin kelimeleri sözlüksel sırada verme özelliği bir sıralama algoritmasına dönüştürülebilir. Girdi sırası dog, ant, do, and, dad olsun. Bütün kelimeler trie'ye eklenir. Sonra kökten önce-kök (preorder) gezinme yapılır: bir düğüm önce kendisi işlenir, sonra çocukları 'a'dan 'z'ye sırayla ziyaret edilir. İşaretli her düğümde kelime yazılır. Bu gezinme, topla metodunun kökten çağrılmasıyla aynıdır.

Çıktı and, ant, dad, do, dog olur. İki kural bu sırayı garanti eder. Birincisi, kardeşler indis sırasıyla, yani alfabetik sırayla ziyaret edilir: “a” dalındaki bütün kelimeler “d” dalındakilerden önce gelir. İkincisi, düğüm çocuklarından önce yazılır: “do”, “dog”dan önce gelir. Bu, sözlüksel sıranın tanımıyla örtüşür: bir önek, onu uzatan her dizgiden küçüktür.

Maliyet hesabında toplam karakter sayısı N ile gösterilsin. Ekleme toplam O(N) sürer. Gezinme her düğümde 26 hücreyi denetler: O(N · M). Sabit alfabede bu O(N)'dir. Karşılaştırmalı sıralama ise O(n log n) karşılaştırma yapar ve her karşılaştırma O(L) sürebilir; ortak önekleri uzun kelimelerde aynı karakterler tekrar tekrar okunur. Trie bu tekrarı ortadan kaldırır. Aynı fikir “burst sort” algoritmasının ve MSD basamak sıralamasının dizgi sürümlerinin temelidir. MSD basamak sıralaması da kelimeleri ilk karaktere göre kovalara ayırır, her kovayı ikinci karaktere göre böler; bu bölünme ağacı aslında bir trie'dir.

5.3.8Uygulamalar ve türevler

5.3.8.1Kullanım alanları

Trie'nin temel işlemleri birçok gerçek uygulamanın çekirdeğidir. Dört örnek alan öne çıkar.

• Otomatik tamamlama. Arama kutuları ve tümleşik geliştirme ortamları (IDE) yazılan önekin düğümüne iner ve alt ağaçtaki kelimeleri önerir. Düğümlerde kullanım sıklığı da saklanırsa sık kullanılan kelimeler önce gösterilir.
• Yazım denetimi. Sözlük trie'de tutulur. Kelime bulunamazsa trie üzerinde küçük düzenlemelerle (ekleme, silme, değiştirme) yakın kelimeler aranır; düzenleme uzaklığı satırları trie gezilirken hesaplanır.
• IP yönlendirme. Alfabesi {0, 1} olan bir ikili trie (binary trie) ile en uzun önek eşleşmesi yapılır. Bir paketin adresi, rota tablosundaki öneklerden en uzun eşleşene yönlendirilir.
• Kelime oyunları ve T9. Boggle ya da kelime bulmacası çözen bir program harflerden yollar kurar. Kurulan yol hiçbir kelimenin öneki değilse o yöndeki arama hemen kesilir; bu budama onekVarMi ile yapılır. Eski telefonlardaki T9 sistemi de tuş dizisinden kelime önermek için trie benzeri bir yapı kullanır.

5.3.8.2İkili trie ve en uzun önek eşleşmesi

İnternet yönlendiricileri bir paketi nereye göndereceklerine, paketin hedef adresine bakarak karar verir. Rota tablosu tek tek adresleri değil, adres öneklerini saklar. “0*” biçimindeki bir rota 0 ile başlayan bütün adresleri, “011*” ise 011 ile başlayanları kapsar. Bir adres birden fazla önekle eşleşebilir; kural, en uzun önek eşleşmesinin (longest prefix match) seçilmesidir. Uzun önek daha özel bir rotadır ve genel rotaya göre önceliklidir.

Rotalar 0* → A, 01* → B, 011* → C, 1* → D ve 110* → E olsun. Her rota, ikili trie'de öneki temsil eden düğümde saklanır. Düğüm sınıfı iki çocuklu bir dizi ve bir rota alanı taşır; rota ekleme, olağan eklemeyle aynıdır:

class IkiliDugum {
  IkiliDugum[] cocuk = new IkiliDugum[2];  // '0' ve '1'
  String rota;                             // null: rota yok
}

void rotaEkle(String onek, String rota) {
  IkiliDugum d = kok;
  for (char b : onek.toCharArray()) {
    int i = b - '0';
    if (d.cocuk[i] == null) d.cocuk[i] = new IkiliDugum();
    d = d.cocuk[i];
  }
  d.rota = rota;
}

Adres için en uzun eşleşme şöyle bulunur. Kökten başlanır ve adresin bitleri sırayla izlenir. Yol boyunca rota taşıyan her düğümde rota hatırlanır. Yol kesildiğinde ya da adres bittiğinde, hatırlanan son rota cevaptır. Son görülen rota, yolda görülenler içinde en derindeki, yani en uzun önektir.

String enUzunEslesme(String adres) {
  IkiliDugum d = kok;
  String enIyi = null;
  for (int k = 0; k < adres.length(); k++) {
    if (d.rota != null) enIyi = d.rota;  // daha uzun önek
    d = d.cocuk[adres.charAt(k) - '0'];
    if (d == null) return enIyi;
  }
  return d.rota != null ? d.rota : enIyi;
}

Döngünün her turunda önce şu anki düğümün rotası denetlenir; varsa enIyi güncellenir. Sonra adresin k. bitine göre çocuğa inilir: adres.charAt(k) - '0', '0' karakterini 0'a, '1'i 1'e çevirir. Çocuk yoksa hatırlanan en iyi rota döner. Döngü bütün bitleri işlerse son düğümün rotası da denetlenir: varsa o, yoksa enIyi döner.

0110 adresinde enIyi sırasıyla A, B ve C olur. Her yeni rota bir öncekinden daha uzun bir önektir ve onun yerini alır. 1001 adresinde yalnız D görülür; özel bir rota olmadığı için genel rota kullanılır. 1101 adresinde “11” düğümü yalnız yol üzerindedir ve enIyi'yi değiştirmez. Adım sayısı adresin uzunluğuyla sınırlıdır: 32 bitlik bir IPv4 adresi için en çok 32 adım atılır, rota tablosunda kaç rota olduğu fark etmez.

Gerçek yönlendiriciler bu fikri sıkıştırılmış ikili trie'lerle (Patricia) ve donanım desteğiyle hızlandırır, ama temel ilke aynıdır. Önek tablosu hash tablosunda tutulsaydı her olası önek uzunluğu için ayrı bir arama gerekirdi.

5.3.8.3En büyük XOR çifti

İkili trie'nin daha az bilinen bir kullanımı bit işlemleriyle ilgilidir. Soru şudur: bir sayı dizisinde a ⊕ b değerini en büyük yapan çift hangisidir? ⊕ bit düzeyinde dışlamalı veya (XOR) işlemidir: iki bit farklıysa sonuç 1, aynıysa 0'dır. Dizi [3, 10, 5, 25, 2, 8] olsun. Kaba kuvvet bütün çiftleri dener: n sayı için n(n − 1)/2 çift.

Trie yöntemi sayıları en anlamlı bitten başlayarak sabit uzunlukta (burada 5 bit) bir ikili trie'ye ekler. Sonra her x için kökten inilir ve her bitte, x'in o bitinin tersi olan dal seçilir; dal yoksa mecburen aynı bit seçilir. Ters bit seçildiği her düzeyde sonucun o biti 1 olur.

int enBuyukXor(int[] a, int B) {
  IkiliDugum kok = new IkiliDugum();
  for (int x : a) {                       // her sayıyı B bitle ekle
    IkiliDugum d = kok;
    for (int b = B - 1; b >= 0; b--) {
      int bit = (x >> b) & 1;
      if (d.cocuk[bit] == null) d.cocuk[bit] = new IkiliDugum();
      d = d.cocuk[bit];
    }
  }
  int enIyi = 0;
  for (int x : a) {                       // her sayı için ters bitleri ara
    IkiliDugum d = kok;
    int y = 0;
    for (int b = B - 1; b >= 0; b--) {
      int bit = (x >> b) & 1;
      if (d.cocuk[1 - bit] != null) { d = d.cocuk[1 - bit]; y |= (1 - bit) << b; }
      else { d = d.cocuk[bit]; y |= bit << b; }
    }
    enIyi = Math.max(enIyi, x ^ y);
  }
  return enIyi;
}

Açgözlü seçimin doğruluğu ikili sayıların bir özelliğine dayanır. Bir sayıda üst bitteki 1, alttaki bütün bitlerin toplamından değerlidir: 2^b > 2^b−1 + … + 2 + 1 = 2^b − 1. Bu yüzden üst bitte 1 elde etmek, alt bitlerde ne kaybedilirse kaybedilsin kârlıdır. Her düzeyde mümkünse ters dal seçmek doğru karardır.

Trie yöntemi her sayı için iki kez B düzey dolaşır: bir kez eklerken, bir kez sorgularken. Fark yaklaşık bin kattır. Burada trie'nin “uzunluk” parametresi, sayının bit sayısı B'dir.

5.3.8.4Üçlü arama trie'si

Dizi gösteriminin bellek sorununa bir çözüm üçlü arama trie'sidir (ternary search trie, TST). TST'de her düğüm bir karakter ve üç bağlantı taşır: sol (küçük), orta (eşit, sonraki karaktere geç) ve sag (büyük). Bir düğümün sol ve sağ zinciri, olağan trie'deki kardeş çocuklar için küçük bir ikili arama ağacıdır. Orta bağlantı ise trie'deki “bir düzey aşağı in” adımına karşılık gelir. Kelime sonu düğümde işaretlenir.

class TstDugum {
  char c;                    // düğümün karakteri
  boolean son;               // kelime burada biter mi?
  TstDugum sol, orta, sag;
  TstDugum(char c) { this.c = c; }
}

TstDugum ekle(TstDugum d, String s, int i) {
  char ch = s.charAt(i);
  if (d == null) d = new TstDugum(ch);
  if (ch < d.c) d.sol = ekle(d.sol, s, i);
  else if (ch > d.c) d.sag = ekle(d.sag, s, i);
  else if (i < s.length() - 1) d.orta = ekle(d.orta, s, i + 1);
  else d.son = true;
  return d;
}

Ekleme özyinelemelidir. Düğüm yoksa sıradaki karakterle yeni bir düğüm oluşturulur. Karakter düğümünkinden küçükse sola, büyükse sağa gidilir; bu iki durumda i değişmez, çünkü aynı karakter için kardeş aranır. Karakterler eşitse ve kelime bitmemişse ortaya gidilir ve i bir artar. Eşitse ve son karakterse düğüm işaretlenir.

Şekildeki TST, kelimeler kar, kal, at, ve, kas sırasıyla eklenerek kurulmuştur. İlk kelime “kar” k → a → r omurgasını oluşturur. “kal” bu omurgayı “ka”ya kadar izler; 'l' < 'r' olduğu için 'r'nin soluna eklenir. “at”, kökte 'a' < 'k' olduğu için kökün soluna, “ve” ise 'v' > 'k' olduğu için sağına gider. “kas” 'r'ye kadar iner ve 's' > 'r' olduğu için sağa eklenir. Ekleme sırası şekli değiştirir: önce eklenen kelime omurga olur.

Dizili trie'de kök ve k, ka, kar, kal, kas, a, at, v, ve düğümleri vardır; 10 düğüm 260 referans ayırır. TST'de boş kök yoktur; her karakter bir düğümdür ve 9 düğüm yalnız 27 bağlantı taşır. Fark yaklaşık on katır.

boolean ara(String s) {
  TstDugum d = kok;
  int i = 0;
  while (d != null) {
    char ch = s.charAt(i);
    if (ch < d.c) d = d.sol;
    else if (ch > d.c) d = d.sag;
    else if (i == s.length() - 1) return d.son;
    else { d = d.orta; i++; }
  }
  return false;
}

Arama yinelemeli yazılmıştır. i, kelimede sıradaki karakterin indisidir. Karakter düğümünkinden küçükse sola, büyükse sağa gidilir ve i değişmez. Eşitse iki durum vardır: son karakterse düğümün işareti döner, değilse ortaya inilir ve i artar. Bağlantı null olunca döngü biter ve false döner.

“kas” aramasında 3 karakter için 4 düğüm ziyaret edilir: üçü orta adım, biri “r”nin kardeşlerinden 's'yi bulmak için atılan sağ adımdır. Genel olarak TST'de arama, L orta adım ile her düzeyde kardeşler arasında ikili arama adımlarının toplamıdır. Kelimeler rastgele sırada eklenirse ortalama maliyet O(L + log n)'dir. Kelimeler sıralı eklenirse kardeş ağaçları bozulur: at, kal, kar, kas, ve sırasıyla eklenen TST'de 'a'nın sağına 'k', 'k'nin sağına 'v' dizilir ve 'l', 'r', 's' kardeşleri bir zincir oluşturur. Bu durum, ikili arama ağacına sıralı ekleme sorununun aynısıdır. Bentley ve Sedgewick 1997'deki çalışmalarında TST'yi büyük alfabeler (örneğin Unicode) için bellek ve hız dengesini koruyan bir yapı olarak ayrıntılı incelemiştir.

5.3.8.5Sıkıştırılmış trie

Standart trie'de çoğu düğümün tek çocuğu vardır. “karton” kelimesinin “kar”dan sonraki kısmı, her biri tek çocuklu “t”, “o”, “n” düğümlerinden oluşan bir zincirdir. Bu zincirler hiçbir karar içermez; yalnız karakterleri sırayla taşır. Sıkıştırılmış trie (compressed trie, radix tree), tek çocuklu ve işaretsiz düğüm zincirlerini tek bir kenarda birleştirir. Kenar artık tek bir karakter değil, bir alt dizgi taşır.

Şekilde “a” düğümünün tek çocuğu vardır ve işaretsizdir; “a” ile “an” tek bir “an” kenarında birleşir. “an” düğümü iki çocuklu olduğu için kalır. “da” düğümü de tek çocuklu ve işaretsizdir; “d”den “dad”e giden yol “ad” kenarı olur. “d” düğümü iki çocuklu olduğu için kalır. Sonuçta kök dışında an, and, ant, d, dad ve do düğümleri kalır.

Teorem, düğüm sayısının kelimelerin uzunluğundan bağımsız olarak O(n) olduğunu söyler. Standart trie'de ise düğüm sayısı toplam karakter sayısıyla orantılıdır. and, ant, dad, do örneğinde n = 4 için sınır 7'dir ve gerçek değer 6'dır. Kenar etiketleri yine de toplam olarak karakterleri taşır; ama bu etiketler ayrı dizgiler olarak değil, özgün kelimelere işaret eden (başlangıç, uzunluk) çiftleri olarak saklanabilir. Böylece bellek de O(n) düğüm ve kelimelerin kendisiyle sınırlı kalır.

Morrison 1968'de bu fikrin ikili alfabe sürümünü Patricia adıyla yayımladı. Patricia trie'si, IP yönlendirme tablolarında ve dosya sistemlerinde kullanılır. Sıkıştırmanın bedeli, ekleme ve silmenin karmaşıklaşmasıdır. Yeni bir kelime bir kenarın ortasında ayrılıyorsa kenar ikiye bölünür ve araya yeni bir düğüm girer. Silmede ise tek çocuklu kalan bir düğüm ebeveyn kenarıyla yeniden birleştirilir.

5.3.8.6Sonek trie'si

Şimdiye kadarki örneklerde trie bir kelime kümesini saklıyordu. Bir metnin içinde arama yapmak için farklı bir küme seçilir: metnin bütün sonekleri. T = “abab” metninin sonekleri abab, bab, ab ve b'dir. Bu dört sonek bir trie'ye eklenirse sonek trie'si (suffix trie) elde edilir.

Sonek trie'sinin gücü bir eşdeğerlik zincirinden gelir:

P, T'nin alt dizgisidir ⇔ P, T'nin bir sonekinin önekidir ⇔ P, sonek trie'sinde kökten başlayan bir yoldur.

İlk eşdeğerlik alt dizginin tanımından gelir: P, T'de i. konumda başlıyorsa i. konumdan başlayan sonekin önekidir. İkinci eşdeğerlik, trie'de her önekin bir yol olmasındandır. Sonuç olarak “P, T'de geçiyor mu?” sorusu onekVarMi(P) ile cevaplanır. Süre O(m)'dir; m = |P|'dir ve metnin uzunluğundan bağımsızdır. Metin bir kez işlenir, ardından istenen sayıda örüntü hızla aranır.

TrieDugumu sonekTrie(String t) {
  TrieDugumu kok = new TrieDugumu();
  for (int s = 0; s < t.length(); s++) {
    TrieDugumu d = kok;
    for (int j = s; j < t.length(); j++) {
      int i = t.charAt(j) - 'a';
      if (d.cocuk[i] == null)
        d.cocuk[i] = new TrieDugumu();
      d = d.cocuk[i];
    }
    d.kelimeSonu = true;  // sonek bitti
  }
  return kok;
}

Kod dış döngüde her sonekin başlangıcını (s) dolaşır. İç döngü, s'den başlayarak sonekin karakterlerini olağan ekleme gibi trie'ye ekler. Sonek bitince son düğüm işaretlenir. İşaret alt dizgi sorgusu için gerekli değildir; ama bir dizginin sonek olup olmadığını sormak için kullanılabilir.

İlk iki sonek yeni dallar açar; son ikisi ise önceki soneklerin yolları üzerinde kalır ve yalnız işaret alır. Toplam 7 düğüm açılmıştır; kökle birlikte 8 düğüm vardır. Sorgular şöyle cevaplanır: “ba” kökten bir yoldur (b → a), dolayısıyla “abab”ın alt dizgisidir. “bb” için “b”den sonra 'b' dalı yoktur; “bb” alt dizgi değildir. “bab” üç adımda bulunur, “bb” iki adımda reddedilir.

Sonek trie'sinin bedeli boyudur. n uzunluklu bir metnin en çok n(n + 1)/2 farklı boş olmayan alt dizgisi vardır ve sonek trie'sinin her düğümü farklı bir alt dizgidir. Bütün karakterleri farklı “abcd” metninde bu sınıra ulaşılır: 10 düğüm. “banana” metninin 21 olası alt dizgisinden 15'i farklıdır ve sonek trie'sinde kök dışında 15 düğüm vardır. Genel olarak bellek O(n²)'dir; bir milyon karakterlik bir metin için bu kabul edilemez.

Çözüm yine sıkıştırmadır. Sıkıştırılmış sonek trie'sine sonek ağacı (suffix tree) denir. Sonek ağacında n sonek olduğu için sıkıştırılmış trie teoremine göre O(n) düğüm vardır. Kenar etiketleri metindeki (başlangıç, bitiş) konum çiftleriyle saklanır. Ukkonen'in 1995'te yayımladığı algoritma sonek ağacını O(n) sürede kurar. Daha az bellek isteyen bir seçenek ise sonek dizisidir (suffix array): soneklerin sözlüksel sıradaki başlangıç indislerini tutan bir dizi. Sonek dizisinde alt dizgi araması ikili aramayla O(m log n) sürer.

5.3.8.7Aho–Corasick

Bir virüs tarayıcısı bir dosyada binlerce imzayı aynı anda arar. Her imza için metni ayrı ayrı taramak, örüntü sayısı kadar tarama demektir. Aho–Corasick algoritması bütün örüntüleri bir trie'ye yerleştirir ve metni yalnız bir kez soldan sağa okur. Okuma sırasında trie'de bir düğümden ötekine geçilir. Bu yaklaşım, tek örüntülü KMP algoritmasının çok örüntülü genellemesidir.

Örüntüler he, she, his ve hers olsun. Trie'de h → he → her → hers, h → hi → his ve s → sh → she yolları vardır. Trie'nin yanında her düğüm için bir hata bağlantısı (failure link) hesaplanır.

Örnekte “she”nin sonekleri “he” ve “e”dir; “he” trie'de vardır, hata bağlantısı “he”ye gider. “sh”nin soneki “h” trie'dedir. “hers”in sonekleri “ers”, “rs” ve “s”dir; yalnız “s” trie'dedir. “his”in hata bağlantısı da “s”ye gider. Geri kalan düğümlerin (h, s, he, hi, her) bağlantıları köke gider.

Metin okunurken şu anki düğümden okunan karakterin dalı varsa o dala geçilir. Dal yoksa hata bağlantısıyla geri çekilinir ve aynı karakter yeni düğümde denenir; bu, KMP'de önek tablosuyla geri çekilmenin karşılığıdır. Kökte de dal yoksa kökte kalınır. Her düğümde o düğümün çıktı kümesi bildirilir. Çıktı kümesi, düğümün kendi örüntüsüyle hata zinciri boyunca ulaşılan örüntülerin birleşimidir. “she” düğümünün çıktısı {she, he}'dir, çünkü hata bağlantısı “he”ye gider ve “he” bir örüntüdür.

Dördüncü karakterde (r) “she” düğümünün 'r' dalı yoktur. Hata bağlantısıyla “he”ye çekilinir; “he”nin 'r' dalı vardır ve “her” düğümüne geçilir. Bu geri çekilme, “she” ile okunan son iki karakterin (h, e) boşa gitmesini önler: “he” zaten eşleşmiş bir öneki temsil eder. Metin tek geçişte okunur ve üç eşleşme bulunur: 3. indiste biten she ve he, 5. indiste biten hers.

Hata bağlantıları trie üzerinde genişlik öncelikli gezinmeyle hesaplanır: bir düğümün bağlantısı, ebeveyninin bağlantısından başlayarak aynı karakterin dalı aranarak bulunur. Bu ön işlem örüntü uzunluklarının toplamı m ile orantılıdır. Tarama ise n uzunluklu metin için O(n) geçiş ve z eşleşmenin bildirimi kadar sürer. Toplam süre O(n + m + z)'dir (Aho ve Corasick, 1975). Algoritma virüs imzası taramada, ağ saldırı tespit sistemlerinde ve yasaklı kelime süzgeçlerinde kullanılır. Unix'teki fgrep komutunun ilk sürümleri de bu algoritmaya dayanıyordu.

5.3.8.8Trie ailesi

Trie türevleri ortak bir fikrin farklı biçimleridir. Tablo 5.3.23 hangi sorunun hangi yapıyla en iyi cevaplandığını özetler.

Ortak fikir hep aynıdır: anahtar karakter karakter (ya da bit bit) okunur ve ortak önekler paylaşılır. Farklar, düğümde neyin saklandığında ve çocuklara nasıl erişildiğindedir. Yapı seçiminde önce sorunun türü belirleyicidir: tam eşleşme mi, önek mi, alt dizgi mi, çok örüntü mü? Ardından alfabenin büyüklüğü ve bellek bütçesi dikkate alınır.

5.3.9Sık yapılan hatalar

Trie kodu kısadır, ama birkaç ince nokta sık sık gözden kaçar. Aşağıdaki hataların çoğu küçük testlerde görünmez ve ancak özel girdilerle ortaya çıkar.

5.3.10Özet

• Yapı: trie bir dizgi kümesini köklü bir ağaçta saklar. Kök boş dizgidir, her kenar bir karakter taşır, her düğüm bir önektir. Kelime, kökten başlayan ve son düğümü işaretli bir yoldur. Ortak önekler tek kez saklanır; trie'nin şekli ekleme sırasına bağlı değildir.
• Düğüm: TrieDugumu[26] cocuk ve boolean kelimeSonu. Karakter düğümde saklanmaz; indis ch − 'a' ile bulunur. Alfabe dışı karakterler dizi sınırını aşar.
• Ekleme: çocuk yoksa oluşturulur, varsa ilerlenir; sonda son düğüm işaretlenir. O(L); en çok L yeni düğüm.
• Arama ve önek sorgusu: dal yoksa false; arama sonda kelimeSonu'nu, önek sorgusu true'yu döndürür. O(L) ve O(P). gecen sayacı önekle başlayan kelime sayısını O(P)'de verir.
• Joker ve yazım denetimi: joker karakter her dolu dalı dener. Düzenleme uzaklığı satırları trie üzerinde ebeveynden çocuğa hesaplanır; ortak öneklerin satırı bir kez hesaplanır, satırın en küçüğü sınırı aşan dallar budanır.
• Otomatik tamamlama: önek düğümü bulunur, alt ağaç derinlik öncelikli gezilir; sonuç alfabetik sıradadır. O(P + S · M). En uzun ortak önek, kökten tek çocuklu ve işaretsiz düğümler boyunca inilerek bulunur.
• Silme: işaret kaldırılır; çocuksuz ve işaretsiz düğümler aşağıdan yukarı silinir. Üç durum: kelime önekse yalnız işaret kalkar, kuyruğu varsa kuyruk silinir, kelime yoksa hiçbir şey değişmez. O(L · M), çocuk sayacıyla O(L).
• Bellek: O(N · M); and, ant, dad, do trie'sinde 234 referansın 226'sı null'dır. Seyrek düğümlerde HashMap, TreeMap, üçlü arama trie'si ya da sıkıştırılmış trie kullanılır.
• Karşılaştırma: tam aramada trie ve hash tablosu O(L)'dir; trie'nin farkı önek ve sıra sorgularındadır. Önce-kök gezinme kelimeleri sözlüksel sırada verir.
• Türevler: ikili trie (en uzun önek eşleşmesi, en büyük XOR), üçlü arama trie'si (düğüm başına 3 bağlantı), sıkıştırılmış trie ve Patricia (n kelime için en çok 2n − 1 düğüm), sonek trie'si → sonek ağacı ve sonek dizisi, Aho–Corasick (hata bağlantılarıyla çok örüntülü arama, O(n + m + z)).

5.3.11Kavram listesi

• trie (önek ağacı) trie, prefix tree
• önek prefix
• sonek suffix
• alt dizgi substring
• kelime sonu işareti end of word
• alfabe alphabet
• referans reference (child pointer)
• önek sorgusu prefix query
• joker karakterli arama wildcard search
• düzenleme uzaklığı edit distance
• otomatik tamamlama autocomplete
• geri izleme backtracking
• derinlik öncelikli arama depth-first search (DFS)
• en uzun ortak önek longest common prefix
• sözlüksel sıra lexicographic order
• hash tablosu hash table
• basamak sıralaması radix sort
• ikili trie binary trie
• en uzun önek eşleşmesi longest prefix match
• üçlü arama trie'si ternary search trie (TST)
• sıkıştırılmış trie compressed trie (radix tree)
• sonek trie'si / sonek ağacı suffix trie / suffix tree
• sonek dizisi suffix array
• Aho–Corasick algoritması Aho–Corasick algorithm
• hata bağlantısı failure link

5.3.12Kendini Dene

Sorular 1–7 aynı trie'yi kullanır: sel, selam, sen, ses ve su kelimeleri, 26 öğeli dizili trie'ye eklenmiştir.

1. Trie'de kök dahil kaç düğüm vardır? Toplam kaç çocuk referansı null'dır?

   Cevap

   Düğümler s, se, sel, sela, selam, sen, ses ve su'dur: 8 düğüm, kökle 9. Referans sayısı 9 × 26 = 234'tür. Dolu referans kenar sayısı kadardır (8); 234 − 8 = 226 referans null'dır.

2. ara("se"), onekVarMi("se"), ara("sela") ve onekVarMi("sela") ne döndürür?

   Cevap

   Sırasıyla false, true, false, true. “se” ve “sela” yolları vardır, ama iki düğüm de işaretsizdir; ikisi de yalnız öneklerdir.

3. tamamla("se") hangi listeyi döndürür? Liste neden bu sıradadır?

   Cevap

   [sel, selam, sen, ses]. “se” işaretsiz olduğu için eklenmez. Çocuklar indis sırasıyla gezilir: l (11), n (13), s (18). “sel” düğümü kendisi işaretli olduğu için “selam”dan önce eklenir.

4. Kelimeler önek sayaçlı ekle ile eklenmiş olsun. Kökte, “se” ve “sel” düğümlerinde gecen değeri kaçtır?

   Cevap

   Kökte 5, “se”de 4 (su hariç hepsi), “sel”de 2 (sel ve selam). onekSayisi("se") 4 döndürür.

5. Her soruda trie yeniden kurulmak üzere sil("sel"), sil("selam") ve sil("su") kaçar düğüm siler?

   Cevap

   sil("sel"): 0; “sel”in 'a' çocuğu vardır, yalnız işaret kalkar. sil("selam"): 2; “selam” ve “sela” silinir, işaretli “sel” düğümünde durulur. sil("su"): 1; “su” silinir, “s” düğümünün 'e' çocuğu olduğu için durulur.

6. enUzunOrtakOnek() ne döndürür? “su” kelimesi trie'de olmasaydı sonuç ne olurdu?

   Cevap

   “s”. Kökün tek çocuğu 's'dir, ama “s” düğümünün iki çocuğu (e, u) vardır ve iniş durur. “su” olmasaydı “s”nin tek çocuğu 'e' olurdu; “se” düğümünün üç çocuğu (l, n, s) vardır ve iniş orada durur: “se”.

7. Sorgu “sez” ve k = 1 için trie üzerinde düzenleme uzaklığı araması hangi kelimeleri önerir? Hangi düğümde budama yapılır?

   Cevap

   Satırlar (“”, s, e, z sütunlarıyla): s → 1 0 1 2, se → 2 1 0 1, sel → 3 2 1 1, sen ve ses → 3 2 1 1, su → 2 1 1 2, sela → 4 3 2 2. Son hücresi 1 olan kelimeler sel, sen ve ses'tir; üçü de önerilir. “su”nun son hücresi 2'dir, önerilmez. “sela” satırının en küçüğü 2'dir ve budanır; “selam”a inilmez.

8. Aynı beş kelimenin sıkıştırılmış trie'sinde kök hariç kaç düğüm vardır? Teoremdeki üst sınır kaçtır?

   Cevap

   s (iki çocuklu), se (üç çocuklu), sel, selam (“am” kenarıyla), sen, ses ve su: 7 düğüm. Standart trie'deki “sela” düğümü “am” kenarına katılmıştır. Sınır 2 · 5 − 1 = 9'dur.

9. [2, 9, 12, 5] dizisinde XOR değeri en büyük çift hangisidir? 4 bitlik ikili trie'de 2 için hangi sayıya varılır?

   Cevap

   Gösterimler 0010, 1001, 1100, 0101'dir. 2 için istenen 1101'dir: bit 3'te 1 (9 ve 12 var), bit 2'de 1 (yalnız 12), bit 1'de 0 (12'nin biti 0), bit 0'da 1 istenir ama 12'nin biti 0'dır. Varılan sayı 12'dir ve 2 ⊕ 12 = 1110 = 14. En büyük değer 14'tür (2 ile 12).

10. “aab” metninin sonek trie'sinde kök hariç kaç düğüm vardır? “ba” ve “ab” alt dizgi midir?

    Cevap

    Sonekler aab, ab, b'dir. Düğümler a, aa, aab, ab, b: 5 düğüm; bu sayı metnin farklı alt dizgilerinin sayısıdır (“a” iki kez geçer, bir kez sayılır). “ab” kökten a → b yoludur, alt dizgidir. “ba” için “b”nin hiç çocuğu yoktur; alt dizgi değildir.

5.3.13İleri okuma

• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 5.2: R'li trie'ler ve üçlü arama trie'leri için Java kodunu, silmeyi ve bellek ölçümlerini ayrıntılı verir.
• D. Gusfield, Algorithms on Strings, Trees, and Sequences (1997): sonek ağaçlarını, Ukkonen algoritmasını ve Aho–Corasick'i biyolojik dizi uygulamalarıyla birlikte işler.
• J. L. Bentley ve R. Sedgewick, “Fast Algorithms for Sorting and Searching Strings”, Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997: üçlü arama trie'sinin ve ona dayalı üç yollu dizgi hızlı sıralamasının analizini yapar.
• A. V. Aho ve M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM 18(6), 1975: hata bağlantılı çok örüntülü eşleme algoritmasının özgün makalesidir.

5.3.14Kaynaklar

1. A. V. Aho, M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM 18(6), 1975.
2. J. L. Bentley, R. Sedgewick, “Fast Algorithms for Sorting and Searching Strings”, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
4. E. Fredkin, “Trie Memory”, Communications of the ACM 3(9), 1960.
5. D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
6. U. Manber, G. Myers, “Suffix Arrays: A New Method for On-Line String Searches”, SIAM Journal on Computing 22(5), 1993.
7. D. R. Morrison, “PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric”, Journal of the ACM 15(4), 1968.
8. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Bölüm 5.2: Tries).
9. E. Ukkonen, “On-line Construction of Suffix Trees”, Algorithmica 14(3), 1995.

İlgili sayfalar: Bölüm 5.3 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.