Trie
- Türkçe karşılığı
- önek ağacı
- Okunuşu
- tri ya da tray
Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.
Kısaca
Trie, string'leri karakter karakter saklayan ağaç biçimli bir veri yapısıdır; aynı öneki paylaşan tüm kelimeler kökten itibaren aynı yolu paylaşır.
Trie nedir?
Önek ağacı (prefix tree) olarak da adlandırılan trie, kelimeler ya da anahtarlar gibi bir string kümesini her seviyede bir karakter olacak şekilde saklayan bir ağaçtır. Kök boş string'i temsil eder, her kenar bir karakter ekler ve düğüme giden yol eksiksiz bir kaydı hecelediğinde düğüm bir kelimenin sonu olarak işaretlenir. Aynı başlangıca sahip kelimeler bir yolu paylaştığı için car, card ve care kelimelerinin üçü de c, a ve r düğümlerini yeniden kullanır.
m uzunluğunda bir kelimeyi eklemek ya da aramak için kökten başlar ve karakter başına bir çocuk bağını izlersiniz; bu yüzden trie kaç kelime tutarsa tutsun ikisi de O(m) sürer. Bir önekle başlayan tüm kelimeleri bulmak da aynı derecede doğrudandır: önekin düğümüne O(m)'de inin, sonra altındaki her kelimeyi toplayın. Her düğüm genellikle çocuklarını küçük bir hash map'te ya da her olası karakter için bir yuvası olan sabit bir dizide saklar.
Kâğıt bir sözlükteki kenar dizinlerini düşünün: C bölümüne atlarsınız, sonra ca ile başlayan kelimelere, sonra car'a daraltırsınız; her harften sonra seçenekler azalır. Trie'ler otomatik tamamlamaya ve arama önerilerine, yazım denetleyicilerine ve kelime oyunlarına güç verir. Yönlendiriciler, yönlendirme tablolarında en uzun eşleşen adres önekini bulmak için yakın bir akrabasını kullanır.
Trie sıklıkla hash tablosuyla karşılaştırılır. Hash tablosu da her karakteri hash'lemesi gerektiği için tüm bir anahtarı ortalamada O(m) sürede arar, ancak pre ile başlayan kelimelerin hangileri olduğu gibi önek sorularını verimli yanıtlayamaz ve anahtarları sıralı tutmaz. Ödünleşim bellektir: sade bir trie çok sayıda düğüm kullanabilir; bu yüzden radix ağaçları gibi sıkıştırılmış türler tek çocuklu düğüm zincirlerini tek bir düğümde birleştirir.
Önemli noktalar
- Trie, string'leri her seviyede bir karakter olacak şekilde saklar ve ortak öneke sahip kelimeler düğümleri paylaşır.
- Ekleme ve arama, kaç kelime saklandığından bağımsız olarak O(m) sürer; m kelimenin uzunluğudur.
- Bir önekle başlayan tüm kelimeleri bulmak, önekə ulaşmak için O(m) artı toplanan eşleşmelerle orantılı zaman alır.
- Trie'ler otomatik tamamlama, yazım denetimi ve yönlendirme tablolarında önek eşleştirme için kullanılır.
- Başlıca maliyet bellektir; radix ağaçları gibi sıkıştırılmış türler bunu azaltır.
Örnek
def insert(node, word):
for char in word: # one step per character: O(m)
node = node.setdefault(char, {})
node["$"] = True # "$" marks the end of a complete word
def has_prefix(node, prefix):
for char in prefix: # also O(m), however many words are stored
if char not in node:
return False
node = node[char]
return True
trie = {}
for word in ["car", "card", "care"]:
insert(trie, word) # all three words share the path c -> a -> r
print(has_prefix(trie, "car"), has_prefix(trie, "cat")) # True FalseSık sorulan sorular
Buna neden trie deniyor?
Ad, retrieval (geri getirme) sözcüğünün ortasından gelir. Adı 1960'ta ortaya atan Edward Fredkin bunu tree gibi telaffuz etmiştir, ancak birçok kişi şimdi tree ile karışmasın diye try der.
Ne zaman hash tablosu yerine trie kullanmalıyım?
Otomatik tamamlama ya da belirli bir metinle başlayan her anahtarı bulmak gibi önek sorgularına ihtiyacınız olduğunda veya anahtarları sıralı listelemek istediğinizde trie kullanın. Düz tam eşleşmeli aramalar için hash tablosu genellikle daha basittir ve daha az bellek kullanır.
Trie'nin zaman karmaşıklığı nedir?
Bir kelimeyi eklemek, silmek ya da aramak, kaç kelime saklandığından bağımsız olarak O(m) sürer; m kelimenin uzunluğudur. Belirli bir önekle başlayan tüm kelimeleri listelemek, önekə ulaşmak için O(m) artı sonuçların boyutuyla orantılı zaman alır.
İlgili sayfalar
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- Hash TablosuVeri Yapıları, s. 18Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
- DizeProgramlamanın Temelleri, s. 14Dize, bir isim, cümle, URL ya da dosya içeriği gibi metni sıralı bir karakter dizisi olarak temsil eden bir veri türüdür.
- Tam Metin AramaVeritabanları, s. 35Tam metin arama, verilen sözcükleri ya da ifadeleri içeren dokümanları bir metin indeksinde arayarak bulan ve sonuçları alaka düzeyine göre sıralayan tekniktir.
- İkili Arama AğacıVeri Yapıları, s. 22İkili arama ağacı, her düğümün sol alt ağacında küçük, sağ alt ağacında büyük değerler bulunan ve hızlı sıralı aramaya olanak tanıyan bir ikili ağaçtır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin