Trie, radix tree ve autocomplete

Trie bir anahtarın karakterlerini/bitlerini adım adım dallara dönüştürür. Kelime sonu işareti önemlidir: “car” prefix'i bulunması onun kayıtlı tam kelime olduğunu göstermez. Autocomplete önce prefix düğümünü bulur, sonra alt ağacı gezer. Sonuç sayısı ve toplam çıktı uzunluğu maliyete dahildir.

Her düğümde bütün alfabe için dizi tutmak hızlı ama seyrek veride pahalıdır; dictionary çocukları daha esnek olabilir. Radix/Patricia tree tek çocuklu yolları kenar etiketlerinde sıkıştırır. Silme kelime sonunu kaldırır ve başka kelimeye ait olmayan düğümleri budar.

Unicode'da karakter, code point ve grapheme aynı değildir; case folding ve normalization sözleşmesi belirle. “İ” ve “i” dil farkıyla eşleşir. En popüler önerileri bulmak için sadece alfabetik DFS yetmez: frekans metadata, top-k cache veya priority structure gerekir. Trie ile hash map maliyetini anahtar uzunluğu L üzerinden karşılaştır.

END = object()
root = {}
for word in ["car", "cart", "cat"]:
    node = root
    for c in word: node = node.setdefault(c, {})
    node[END] = True

def contains(word):
    node = root
    for c in word:
        if c not in node: return False
        node = node[c]
    return END in node
assert contains("car") and not contains("ca")