İçeriğe geç

Prefix arama

Ders 2 / 4 · 5 dk

Prefix arama

Adım 1/9

Üç kelime saklı. Kullanıcı henüz bir şey yazmadı, yani hepsi hâlâ aday.

Fikir

Otomatik tamamlama (autocomplete), "bu bir kelime mi?" sorusundan farklı bir şey sorar. Sorduğu şu: "bununla ne başlıyor?"

Prefix (önek) boyunca bir kez in; bunun maliyeti yazılan karakter başına bir adım. Vardığın düğüm (node), tam olarak o prefix'e sahip kelimeleri tutan bir alt ağacın köküdür; bu yüzden önerileri toplarken sözlüğün geri kalanına hiç dokunmazsın.

Gerçek hayattan örnek

Üç harften sonra kelime öneren bir telefon klavyesi düşün. Tuş vuruşları arasında 200.000 kelimeyi baştan tarayamaz; bu yüzden "cat" için ulaştığı konumu tutar ve sonraki tuşta baştan başlamak yerine bir adım daha atar.

Kod

Sıra sende

Boşluğu doldur.

trie = {"a": {"t": {"$": 1}}}
node = trie
for ch in "ax":
  node = node.get(ch)
  if node ___ None:
      break
print(node)   # None

Mini quiz

1 / 3

P uzunluğundaki bir prefix'in düğümüne ulaşmak ne kadar sürer?