Implement Trie (Prefix Tree)

Q: Neden bir hash kümesi yerine trie kullanılır?

Bir hash kümesi, tam sözcük aramalarını O(L) sürede yanıtlar, ancak her sözcüğü taramadan öneklerle ilgili bir soruyu yanıtlayamaz. Her sözcüğün tüm öneklerini tutan ikinci bir küme ekleyebilirsin, ancak bu durumda 20 harfli bir sözcük, aralarında toplam 210 harf bulunan 20 önek saklar. Bir trie, paylaşılan her öneki yalnızca bir kez saklar ve her iki soruyu da aynı gezinmeyle yanıtlar. Düğüm başına 26 dizi yuvasıyla, bir öneğin altındaki gezinme sözcüklerle harf sırasına göre de karşılaşır; bu, otomatik tamamlamanın ihtiyaç duyduğu şeydir.

OrtaTrie

+10

Trie veya önek ağacı, sözcükleri başlangıçlarıyla ilgili sorgular hızlı olacak şekilde saklar. Küçük harfli sözcükler için üç işlem içeren bir trie oluştur: insert w sözcük w'yi ekler, search w doğrudan w'nin eklenip eklenmediğini belirtir ve startsWith p eklenmiş herhangi bir sözcüğün p ile başlayıp başlamadığını belirtir. Bir sözcük, kendisinin öneki sayılır.

İşlemleri sıralı olarak ops içinde alırsın ve words[i], ops[i] için sözcük veya önektir. İşlemleri boş başlayan tek bir trie üzerinde uygula ve her işlem için bir metin döndür: ekleme için "null", arama veya startsWith için "true" ya da "false".

Fonksiyon

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: işlemler, çalıştırıldıkları sırayla
wordsstring-array: her işlem için sözcük veya önek
Döndürürstring-array: işlem başına metin olarak bir yanıt

Kısıtlar

1 ≤ ops.length ≤ 2000
words.length == ops.length
Her ops[i], insert, search veya startsWith değerlerinden biridir.
1 ≤ words[i].length ≤ 20
words[i] yalnızca küçük harfli İngilizce harfleri içerir.

Örnekler

Girdi: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Çıktı: ["null", "false", "true", "null", "true"]
Açıklama: İlk başta yalnızca card saklanır, bu yüzden car için arama yapmak "false" sonucunu verir: car hiçbir zaman bir sözcük olarak eklenmemiştir. card sözcüğünün başlangıcıdır, bu nedenle startsWith car "true" sonucunu verir. car eklendikten sonra arama onu bulur.

Girdi: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Çıktı: ["null", "null", "true", "false", "false", "true", "true"]
Açıklama: Her iki kelime de te ile başladığından startsWith te sonucu "true" olur, ancak hiçbir kelime tam olarak te olmadığı için arama başarısız olur. Hiçbir kelime tex ile başlamaz. ten eklendi ve tea kendisinin bir öneki olduğundan son iki yanıt "true" olur.

Girdi: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Çıktı: ["false", "false", "null", "true", "false", "true"]
Açıklama: Trie boş başlar, bu nedenle ilk iki yanıt "false" olur. dog eklendikten sonra arama onu bulur, hiçbir kelime dogs ile başlamaz ve do, dog kelimesinin başlangıcıdır.

Gönderirken +16 gizli test

Ek soru

countPrefix p işlemini, p ile başlayan kaç farklı kayıtlı sözcük olduğunu O(L) zamanda döndürecek şekilde nasıl eklersiniz?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir hash set, search sorgusunu anında yanıtlar; ancak startsWith, belirli bir şekilde başlayan her sözcüğü sorar ve bir küme başlangıç kavramına sahip değildir. Bir trie, başlangıçları saklar: her sözcük kökten başlayan bir harf yoludur, aynı şekilde başlayan sözcükler yollarının başlangıç kısmını paylaşır ve bir düğümdeki işaret, saklanan bir sözcüğün nerede bittiğini gösterir. Böylece her iki soru da, kaç sözcük saklanırsa saklansın, en fazla L bağlantı boyunca tek bir yürüyüşte yanıtlanır; burada L, sorgunun uzunluğudur.

Kelimelerin bir listesini tut ve onu tara

Sezgi

Eklenen her sözcüğü bir listede tut. search w için w ile saklanan her sözcüğü karşılaştır. startsWith p için saklanan sözcüklerden herhangi birinin p ile başlayıp başlamadığını kontrol et. İkinci örnekte startsWith te, önce tea sözcüğüne bakar ve orada durur; startsWith tex ise "false" yanıtını vermeden önce her iki sözcüğe de bakmak zorundadır.

Bu doğrudur ve buradaki sınırlar içinde tamamlanır, ancak her sorgu saklanan her sözcüğün maliyetini getirir. Saklanan n sözcük varsa, bir sorgu her biri en fazla L harften oluşan en fazla n karşılaştırmaya mal olur. Saklanan 1.000 sözcük ve 1.000 sorgu, bir milyon dize karşılaştırması demektir ve sözlük büyüdükçe iş miktarı da artmaya devam eder. Hiçbir şey ortak da kullanılmaz: tea ve ten sözcüklerinin her biri kendi t ve e harflerini saklar.

Algoritma

Boş bir sözcük listesiyle başla.
insert w için: w'yi listeye ekle.
search w için: saklanan sözcüklerden herhangi birinin w'ye eşit olup olmadığını döndür.
startsWith p için: saklanan sözcüklerden herhangi birinin p ile başlayıp başlamadığını döndür.
Her yanıtı metin olarak kaydet ve listeyi döndür.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Bir trie: çocuk bağlantıları ve bir bitiş bayrağı

Sezgi

Bir trie'nin her düğümü bir öneki temsil eder: kökten o düğüme kadar olan yoldaki harfleri. Kök, boş öneki temsil eder. Bir düğüm iki şey tutar: sıradaki her harf için bir çocuk bağlantısı (26 yuvalı bir dizi veya harften düğüme eşleme) ve saklanan bir sözcüğün tam olarak bu düğümde bitip bitmediğini belirten isEnd bayrağı.

insert, sözcük boyunca kökten başlayarak ilerler. Her harfte çocuk bağlantısını izler; bağlantı eksikse önce düğümü oluşturur ve son harfte isEnd değerini ayarlar. İkinci örnekte, tea eklemek t, te ve tea düğümlerini oluşturur ve tea düğümünü işaretler. ten eklemek t ve te düğümlerini yeniden kullanır ve yalnızca ten düğümünü ekler. İki sözcük te için olan yolu paylaşır; önek ağacı adının kaynağı da budur.

search ve startsWith hiçbir şey oluşturmadan aynı yolu izler. Bir bağlantı eksikse, saklanan hiçbir sözcük bu harflerle başlamaz; bu nedenle ikisi de false yanıtını verir: tex, te düğümünde durur; bu düğümde x bağlantısı yoktur. Yolun sonuna ulaşılırsa üzerinde durulan düğüm, hakkında sorduğunuz önektir. startsWith true yanıtını verir; search ise o düğümün bayrağını yanıt olarak verir. te düğümü vardır, ancak bayrağı kapalıdır; çünkü bu düğümden geçen sözcükler daha aşağıda biter. Bu nedenle startsWith te true, search te ise false yanıtını verir.

Bir sözcüğü önekten ayıran şey bayraktır. İlk örnekte, card eklendikten sonra c, a, r yolu vardır. Bayrak olmasaydı, search car yanlış biçimde true yanıtını verirdi. Daha sonra car eklemek hiçbir düğüm oluşturmaz; yalnızca bayrağı açar.

Her işlem en fazla L bağlantıyı izler; burada L, sözcüğün uzunluğudur. Bu nedenle saklanan sözcük sayısından bağımsız olarak maliyeti O(L) olur. Trie, farklı her önek için bir düğüm tutar; bu sayı eklenen toplam harf sayısını hiçbir zaman aşmaz.

Algoritma

Çocuk bağlantıları (26 yuva veya bir eşleme) ve bir isEnd bayrağı olan bir düğüm tanımlayın ve boş bir kök oluşturun.
insert w için: kökten başlayarak, w sözcüğünün her harfi için ilgili bağlantıyı izleyin; bağlantı yoksa düğümü oluşturun. Son düğümde isEnd değerini ayarlayın.
Bir yardımcı find(p) işlevi yazın: kökten başlayarak, p sözcüğünün her harfi için ilgili bağlantıyı izleyin ve bağlantılardan biri eksikse hemen vazgeçin. Ulaşılan düğümü döndürün.
search w için: find(w), isEnd ayarlanmış bir düğüme ulaştığında true yanıtını verin.
startsWith p için: find(p) bir düğüme ulaştığında true yanıtını verin.
İşlemleri sırayla çalıştırın ve her biri için "null", "true" veya "false" kaydedin.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Tuzaklar ve uç durumlar

Hataların çoğu, "bir kelimenin burada bitmesi" ile "bir kelimenin buradan geçmesi" kavramlarını karıştırmaktan kaynaklanır.

Yol var olduğunda search işlevinin true döndürmesine izin vermek. card eklendikten sonra car için yol vardır, ancak car hiç eklenmemiştir.
isEnd değerini yalnızca yeni oluşturulan düğümlerde ayarlamak. cards sözcüğünden sonra card eklemek hiçbir şey oluşturmaz, ancak son düğümün yine de bayrağa ihtiyacı vardır.
Bağlantı zaten varken yeni bir çocuk oluşturmak. Bu, altında depolanan her şeyi kesip atar: yeni bir t düğümüyle ten eklemek, tea sözcüğünü kaybettirir.
Bir sözcüğün kendisinin de kendi öneki olduğunu unutmak. tea eklendikten sonra startsWith tea true olur.
Yolun sonunu geçerek okumak. Yalnızca sun kayıtlıyken sunny gibi tüm sözcüklerden daha uzun bir önek, ilk eksik bağlantıda durmalı ve false döndürmelidir.
Boolean değerler döndürmek veya ekleme işlemlerini yanıttan çıkarmak. Ekleme işlemleri için "null" da dahil olmak üzere, her işlem bir dize alır.

Sıkça sorulan sorular4

Bir trie'nin zaman karmaşıklığı nedir?

Insert, search ve startsWith, bağımsız değişkenlerindeki her harf için bir bağlantıyı izler; bu nedenle uzunluğu L olan bir sözcük için her biri O(L) zaman alır ve bu süre depolanan sözcük sayısından bağımsızdır. Trie, eklenen her harf için en fazla bir düğüm barındırır; bu nedenle toplamda eklenen T harf için alan kullanımı O(T) düğümdür ve her düğüm en fazla 26 çocuk bağlantısı depolar.

Neden bir hash kümesi yerine trie kullanılır?

Bir hash kümesi, tam sözcük aramalarını O(L) sürede yanıtlar, ancak her sözcüğü taramadan öneklerle ilgili bir soruyu yanıtlayamaz. Her sözcüğün tüm öneklerini tutan ikinci bir küme ekleyebilirsin, ancak bu durumda 20 harfli bir sözcük, aralarında toplam 210 harf bulunan 20 önek saklar. Bir trie, paylaşılan her öneki yalnızca bir kez saklar ve her iki soruyu da aynı gezinmeyle yanıtlar. Düğüm başına 26 dizi yuvasıyla, bir öneğin altındaki gezinme sözcüklerle harf sırasına göre de karşılaşır; bu, otomatik tamamlamanın ihtiyaç duyduğu şeydir.

Bir trie düğümü 26 bağlantıdan oluşan bir dizi mi yoksa bir hash haritası mı kullanmalı?

Dizi, her harf için bir indeks kullanarak çocuk düğümlere en hızlı erişimi sağlar; ancak yalnızca bir çocuk kullansa bile her düğüm 26 yuva için bellek ayırır. Bir eşlem, yalnızca var olan çocukları saklar ve her alfabe için çalışır; bunun karşılığında her harf için bir karma hesaplama adımı gerekir. Küçük harfli İngilizce sözcükler için ikisi de uygundur; Unicode metinlerde veya seyrek trie’lerde ise eşlem çok fazla bellek tasarrufu sağlar.

Trie'ler pratikte nerelerde kullanılır?

Otomatik tamamlama ve arama önerileri, yazılan öneke kadar bir trie'ı izler ve altındaki sözcükleri listeler. Yazım denetleyicileri, sözlükteki sözcükleri bulmak için bir tahtayı tarayan kelime oyunları ve en uzun eşleşen adres önekini bulan yönlendiriciler aynı yapıyı kullanır. Çok sayıda dizge aynı başlangıcı paylaşıyorsa ve başlangıca göre sorgulama yapıyorsanız trie uygundur.

Python

def trieOps(ops, words):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Beklenen

["null", "false", "true", "null", "true"]