Project: Trie နဲ့ Autocomplete ဆောက်ခြင်း

နားလည်ထားရမယ့် အချက်

Trie တစ်ခုက word set တစ်ခုကို common prefix တွေ root ကနေ path အနေနဲ့ share ခြင်းအားဖြင့် သိမ်းတယ်: node တစ်ခုစီက character တစ်လုံးကို ကိုယ်စားပြုတယ်၊ insert လုပ်ထားတဲ့ word တိုင်းက root ကနေ 'end of word' လို့ mark လုပ်ထားတဲ့ node ဆီ path တစ်ခုနဲ့ ကိုက်ညီတယ်။ autocomplete အတွက် naive alternative က tutorial title အားလုံးရဲ့ flat list တစ်ခုကို scan လုပ်ပြီး တစ်ခုချင်းစီမှာ `.startswith(prefix)` စစ်တာပါပဲ—မှန်ကန်ပေမယ့် keystroke တိုင်းမှာ stored word အရေအတွက်နဲ့ O(n) ဖြစ်နေတယ်၊ catalog ကြီးလာလေ နှေးလာလေဖြစ်ပြီး typed prefix နဲ့ ဘာမှ မတူတဲ့ word တွေကိုတောင် အကြိမ်ကြိမ် ပြန်စစ်နေတာက အလဟဿ ဖြစ်တယ်။ Trie ကတော့ matching word အားလုံး ပါတဲ့ subtree ဆီ ရောက်ဖို့ `len(prefix)` node ကိုပဲ လျှောက်ပြီး၊ ဒီ subtree ထဲကနေပဲ result တွေ စုတယ်—cost က prefix length ပေါင်း match အရေအတွက်နဲ့ ပြောင်းလဲတယ်၊ vocabulary size စုစုပေါင်းနဲ့ မဟုတ်ဘူး။ ဒါကြောင့်ပဲ search-autocomplete system တွေက flat list filter မလုပ်ဘဲ Trie (ဒါမှမဟုတ် radix tree လို compressed variant) သုံးတာပါ: shared-prefix structure ကြောင့် stem တူတဲ့ word တွေကြားမှာ work ဘယ်တော့မှ ထပ်ခါထပ်ခါ မလုပ်ရဘူး၊ word set က ထောင်ချီ scale ဖြစ်လာလည်း lookup က မြန်နေဆဲပါ။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

ဒီ project က analogy တစ်ခုမျှသာ မဟုတ်ဘူး — Tutorial Platform ရဲ့ တကယ့် `/api/search-suggest` endpoint ကို တိုက်ရိုက် model လုပ်တာပါ။ ဒီ endpoint က ဒီမေးခွန်းကိုပဲ ဖြေတယ်: user က ဒီအထိ ရိုက်ထားတဲ့စာ ('post', 'prompt') ကို base ပြု၍ `search-index.json` ထဲက ဘယ် tutorial slug/title တွေက ဒီ prefix နဲ့ စတယ်လဲ? `search-index.json` ထဲက entry တိုင်းကနေ တစ်ကြိမ်တည်း ဆောက်ထားတဲ့ Trie (lesson/tutorial title တစ်ခုစီကို word အနေနဲ့ insert လုပ်ထားတာ) က keystroke တစ်ခုစီရဲ့ suggestion lookup ကို request တိုင်းမှာ index file တစ်ခုလုံး re-scan မလုပ်ဘဲ O(prefix length) walk တစ်ခုအဖြစ် ပြောင်းပေးတယ်။ `search-index.json` ကို deploy မလုပ်ခင် `pnpm build-search-index` နဲ့ ပြန်ဆောက်ရမှာ ဖြစ်နေပြီးသားမို့၊ ဒီ Trie ကို server startup မှာ ဒါမှမဟုတ် build time မှာ ဆောက်ပြီး process တစ်ခုလုံးရဲ့ သက်တမ်းအတွက် memory ထဲ cache ထားတာက သဘာဝကျတဲ့ နေရာပါပဲ။

• Trie က common prefix ရှိတဲ့ word တွေ path ကို share လုပ်ပြီး O(prefix length + matches) နဲ့ ရှာနိုင်တယ်
• Flat list scan (`.startswith`) က keystroke တိုင်းမှာ O(n) ဖြစ်နေလို့ catalog ကြီးလာလေ နှေးလာလေဖြစ်တယ်
• ဒီ Trie က site ရဲ့ တကယ့် `/api/search-suggest` endpoint နဲ့ `search-index.json` ကို တိုက်ရိုက် model လုပ်တာပါ

အတူတူ စမ်းရေးကြည့်မယ်

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

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

    def insert(self, word: str):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _collect(self, node, prefix, results):
        if node.is_end:
            results.append(prefix)
        for ch, child in node.children.items():
            self._collect(child, prefix + ch, results)

    def autocomplete(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []  # no word in the index starts with this prefix
            node = node.children[ch]
        results = []
        self._collect(node, prefix, results)
        return sorted(results)

# Simulates entries loaded from search-index.json
tutorial_slugs = ["python", "postgresql", "prompt-engineering", "playwright", "rust"]

trie = Trie()
for slug in tutorial_slugs:
    trie.insert(slug)

print(trie.autocomplete("p"))
print(trie.autocomplete("post"))

`['playwright', 'postgresql', 'prompt-engineering', 'python']` ကို print ထုတ်ပြီး၊ ဒုတိယအကြိမ် `['postgresql']` ကို print ထုတ်တယ်။

Wikipedia — Trie — Data Structures & Algorithms