Trie — শব্দ আর prefix খোঁজার tree

১ · সমস্যা — ফোন কীভাবে আপনার শব্দ আগেই আন্দাজ করে

ফোনে মেসেজ লিখছেন। “ca” টাইপ করতেই কিবোর্ডের ওপরে ভেসে উঠল: car, card, cat. ফোনবুকে “Ra” লিখলেই চলে এল রহিম, রাকিব, রাশেদ। Google বা দারাজের সার্চ বক্সে দুই অক্ষর লিখতেই দশটি পরামর্শ। প্রতিটি ক্ষেত্রে প্রশ্নটি একই: “এই শুরু দিয়ে কোন কোন শব্দ আছে?” আর উত্তর দিতে হবে প্রতিটি অক্ষর চাপার সাথে সাথে, চোখের পলকে।

এই শুরুর অংশকে বলে prefix — যেমন “car”, “ca” আর “c” তিনটিই “card”-এর prefix. আর ব্যবহারকারী পুরো শব্দ লেখার আগেই সম্ভাব্য শব্দ দেখানোর সুবিধার নাম autocomplete. এর সাথে আরও দুটি কাছাকাছি প্রশ্ন আসে: বানান-যাচাইয়ে “এই শব্দটি কি অভিধানে আছে?”, আর পরিসংখ্যানে “কতগুলো শব্দ ‘pre’ দিয়ে শুরু?”

আগের পর্বগুলোর অস্ত্র দিয়ে চেষ্টা করি। ধরুন অভিধানে n টি শব্দ, প্রশ্নের prefix-এর দৈর্ঘ্য L.

সাজানো অ্যারে কিন্তু খারাপ নয় — পর্ব ১৮-এর lower bound দিয়ে “ca”-র প্রথম শব্দ আর “cb”-র প্রথম শব্দের অবস্থান খুঁজে বিয়োগ করলেই “ca” দিয়ে কয়টি শব্দ, তা বের হয়। প্রতিটি তুলনা দুটি string-এর, তাই খরচ O(L log n). কিন্তু প্রতিটি নতুন শব্দ ঢোকাতে বাকিদের সরাতে হয়। Hash table-এর অবস্থা আরও খারাপ: hash function ইচ্ছা করেই কাছাকাছি key-গুলোকে দূরে দূরে ছড়িয়ে দেয়, তাই prefix-এর তথ্য পুরো হারিয়ে যায়।

২ · Trie-এর গঠন — প্রতিটি edge একটি অক্ষর

Trie একটি rooted tree. এর নিয়ম মাত্র তিনটি:

• প্রতিটি edge-এ একটি অক্ষর. কোনো node থেকে একই অক্ষরের দুটি edge বের হয় না।
• প্রতিটি node একটি prefix. Root থেকে কোনো node পর্যন্ত পথের অক্ষরগুলো পরপর পড়লে যে string হয়, সেই node সেটিকেই বোঝায়। Root নিজে খালি string “”. লক্ষ করুন, অক্ষর আসলে node-এর ভেতরে লেখা থাকে না — থাকে parent থেকে আসা edge-এ; ছবিতে সুবিধার জন্য অক্ষরটি node-এর গায়ে লেখা হয়।
• শব্দের শেষে একটি চিহ্ন. যে node-এ কোনো রাখা শব্দ শেষ হয়েছে, সেখানে একটি end-of-word marker (একটি bool বা counter) থাকে। এটি ছাড়া “car” রাখলে “ca”-ও আছে বলে মনে হতো — কারণ “ca”-র node-ও তো tree-তে আছে।

এখান থেকেই trie-র আরেক নাম prefix tree, আর পুরোনো বইয়ে digital tree বা digital search tree. প্রতিটি node-এর সন্তান সর্বোচ্চ σ (সিগমা) টি, যেখানে σ হলো alphabet size — ছোট হাতের ইংরেজি অক্ষরে ২৬, বাইটে ২৫৬, DNA-তে ৪ (A, C, G, T), আর bit-এ ২। নিচে খালি trie-তে পরপর “car”, “cat”, “card” আর “do” ঢোকানো দেখুন। * চিহ্ন মানে এখানে একটি শব্দ শেষ।

দুটি তথ্য মনে রাখুন। প্রথমত, trie-র আকার রাখা শব্দগুলোর ওপর নির্ভর করে, ঢোকানোর ক্রমের ওপর নয় — যে ক্রমেই car, cat, card, do ঢোকান, ঠিক এই tree-ই হবে। BST-র (পর্ব ২৭) মতো কোনো ক্রমে tree একপাশে ঝুলে পড়ার ভয় নেই, তাই ভারসাম্য রাখার কোনো ঝামেলাও নেই। দ্বিতীয়ত, node-এর সংখ্যা সর্বোচ্চ N + 1, যেখানে N = সব শব্দের দৈর্ঘ্যের যোগফল — প্রতিটি অক্ষর বড়জোর একটি নতুন node বানায়। শব্দগুলো যত বেশি prefix ভাগ করে, node তত কম।

৩ · Insert, search আর startsWith — O(L), n যত বড়ই হোক

তিনটি কাজের কঙ্কাল একই: root থেকে শুরু করে শব্দের প্রতিটি অক্ষরের edge ধরে এক ধাপ নামা। পার্থক্য শুধু পথ না পেলে কী করবেন, আর শেষে কী দেখবেন।

Pseudocode — trie over a..z (0-based letters: c = ch - 'a')

node: child[0..25]  (NIL = no child),  isEnd = false

insert(w):
    v = root
    for each ch in w:
        if v.child[ch] == NIL: v.child[ch] = new node     // only here does the trie grow
        v = v.child[ch]
    v.isEnd = true

walk(p):                                                // the node for prefix p, or NIL
    v = root
    for each ch in p:
        v = v.child[ch]
        if v == NIL: return NIL                         // some word would need this edge
    return v

search(w):      v = walk(w);  return v != NIL and v.isEnd
startsWith(p):  return walk(p) != NIL

কেন এটি ঠিক — invariant. insert আর walk-এর লুপে i টি অক্ষর পার হওয়ার পর একটি কথা সব সময় সত্য: “v হলো সেই node, root থেকে যার পথের অক্ষরগুলো ঠিক w-এর প্রথম i টি অক্ষর।” শুরুতে i = 0, v = root, পথ খালি — সত্য। প্রতিটি ধাপে আমরা অক্ষর w[i]-এর edge ধরে নামি, তাই পথে ঠিক w[i] যোগ হয় — সত্য থাকে। কোনো node থেকে একই অক্ষরের দুটি edge নেই, তাই প্রতিটি prefix-এর node একটিই. এখন search-এর শুদ্ধতা: w আগে ঢোকানো হয়ে থাকলে তার পথ তৈরি হয়েছিল আর শেষ node-এ isEnd বসেছিল — তাই search হ্যাঁ বলবে। উল্টো দিকে, isEnd শুধু insert-এর শেষ লাইনই বসায়, আর সেটি বসে ঠিক ঢোকানো শব্দের node-এ — তাই কোনো না-ঢোকানো শব্দে search হ্যাঁ বলতে পারে না। startsWith(p) হ্যাঁ ⇔ p-এর node আছে ⇔ কোনো ঢোকানো শব্দের পথ এই node দিয়ে গেছে ⇔ কোনো শব্দ p দিয়ে শুরু। এটি পর্ব ০৩-এর loop invariant পদ্ধতির সরল প্রয়োগ।

বিশ্লেষণ. প্রতিটি অক্ষরে একটি সন্তান খোঁজা আর বড়জোর একটি node বানানো। সন্তান যদি array-তে থাকে, খোঁজা O(1) — তাই insert, search আর startsWith তিনটিই Θ(L) সময় (শব্দ না থাকলে আরও আগে থামতে পারে, তাই search-এর worst case O(L)). লক্ষ করুন n কোথাও নেই! দশ শব্দের অভিধান আর দশ লাখ শব্দের অভিধানে “card” খুঁজতে একই ৪টি ধাপ। বাড়তি জায়গা: search আর startsWith O(1), insert বড়জোর L টি নতুন node — প্রতিটি σ আকারের array নিলে O(L·σ). পুরো trie-র জায়গা O(N·σ), N = মোট অক্ষর।

৪ · সন্তান কোথায় রাখবেন — array[26], hash map, না sorted vector

Pseudocode-এ লিখেছি child[0..25]. কিন্তু এটিই একমাত্র উপায় নয়, আর বড় trie-তে এই সিদ্ধান্তই ঠিক করে দেয় প্রোগ্রাম মেমরিতে ধরবে কি না। তিনটি প্রচলিত উপায় পাশাপাশি দেখুন (σ = alphabet size, d = node-টির আসল সন্তানের সংখ্যা):

সংখ্যা দিয়ে ভাবি। ধরুন একটি ইংরেজি অভিধানের trie-তে ২০ লাখ node. int next[26] (প্রতি ঘর ৪ byte) মানে প্রতি node-এ ১০৪ byte — মোট প্রায় ২০৮ MB. Pointer রাখলে (৬৪-bit মেশিনে ৮ byte) দ্বিগুণ, প্রায় ৪১৬ MB. অথচ বাস্তব অভিধানের trie-তে গভীরের বেশিরভাগ node-এর সন্তান মাত্র একটি বা শূন্য — অর্থাৎ ২৬টি ঘরের প্রায় ২৫টিই খালি পড়ে থাকে। Sorted vector-এ তখন প্রতি সন্তানে মাত্র কয়েক byte, সাথে vector-এর নিজের সামান্য খরচ।

লক্ষ করুন, “মোট জায়গা” কলামে nodes ≤ N + 1. অর্থাৎ array-র সংস্করণে জায়গা O(N·σ), বাকিগুলোতে O(N). আরেকটি বাস্তব কৌশল: প্রতিটি node-এর জন্য আলাদা new না করে সব node একটি বড় অ্যারেতে রাখুন আর pointer-এর বদলে int index ব্যবহার করুন (এই পর্বের কোড ঠিক তাই করে)। এতে মেমরি অর্ধেক হয়, allocation-এর খরচ যায়, আর node-গুলো পাশাপাশি থাকায় cache locality ভালো হয়। কনটেস্টে প্রায়ই আগে থেকে হিসাব করে নেওয়া হয়: মোট অক্ষর সর্বোচ্চ ১০^৬ হলে node-এর অ্যারে ১০^৬ + ১ আকারের।

৫ · Prefix গোনা, শব্দের frequency আর delete

শুধু একটি bool-এর বদলে প্রতিটি node-এ দুটি counter রাখুন: pass[v] — কতগুলো ঢোকানো শব্দের পথ v দিয়ে গেছে, আর end[v] — কতগুলো শব্দ ঠিক v-তে শেষ হয়েছে। Insert-এর সময় পথের প্রতিটি node-এ (root-সহ) pass এক বাড়ান, আর শেষ node-এ end এক বাড়ান। এই ছোট পরিবর্তনে তিনটি নতুন প্রশ্নের উত্তর মেলে, প্রত্যেকটি O(L)-এ:

• countPrefix(p) = pass[walk(p)] — কতগুলো শব্দ p দিয়ে শুরু। কোনো DFS লাগে না, উত্তর node-এই লেখা আছে। এটিই prefix count.
• frequency(w) = end[walk(w)] — একই শব্দ বারবার ঢোকালে কতবার এসেছে। এক কোটি সার্চের log থেকে প্রতিটি সার্চ-বাক্য কতবার খোঁজা হয়েছে, তা গোনার একটি স্বাভাবিক উপায়।
• erase(w) — আগে search করে নিশ্চিত হোন w আছে, তারপর পথ ধরে প্রতিটি pass এক কমান আর শেষে end এক কমান। যে node-এর pass শূন্য হলো, তার নিচে আর কোনো শব্দ নেই — সেটি কেটে ফেলা যায়।

নিচে car, card, care আর cat রাখা trie থেকে “card” মুছে ফেলা দেখুন। প্রতিটি node-এর পাশে লেখা আছে [pass, end].

Counter ছাড়া, শুধু bool দিয়েও delete করা যায় — recursion দিয়ে: শব্দের শেষ node-এ isEnd = false করুন, তারপর ফেরার পথে প্রতিটি node দেখুন — তার কোনো সন্তান নেই আর সে নিজে কোনো শব্দের শেষ নয়? তাহলে তাকে মুছে parent-এর ঘর NIL করুন। প্রথম যে node-এ শর্তটি মেলে না (যেমন উপরের r, যেটি “car”-এর শেষ), সেখানেই থামুন। প্রচলিত ভুল হলো শর্ত না দেখেই পুরো পথ মুছে ফেলা — তাতে “card” মুছতে গিয়ে “car” আর “care”-ও হারিয়ে যায়।

৬ · Autocomplete — DFS দিয়ে অভিধানের ক্রমে সব শব্দ

“ca” টাইপ করা হয়েছে। আগে walk("ca") দিয়ে prefix-এর node খুঁজুন — O(L). তারপর সেই node-এর subtree-তে যত শব্দ আছে, সবই “ca” দিয়ে শুরু, আর বাইরে একটিও নেই। তাই উত্তর = subtree-র সব end-চিহ্নিত node. এদের বের করতে DFS চালান, সাথে বর্তমান string-টি নিয়ে: নামার সময় অক্ষর যোগ, ফেরার সময় বাদ। প্রতিটি node-এ আগে নিজের শব্দটি (যদি থাকে) লিখুন, তারপর সন্তানদের a থেকে z ক্রমে ঘুরুন — এটিই preorder traversal (পর্ব ২৬).

কেন ক্রমটি lexicographic — প্রমাণ. দুটি আলাদা রাখা শব্দ u আর w নিন, যেখানে lexicographic order-এ u < w. দুটি ক্ষেত্র। (ক) u হলো w-এর prefix (যেমন car আর card): তাহলে u-র node w-এর পথের ওপরে, পূর্বপুরুষ; preorder-এ node নিজে তার সব বংশধরের আগে আসে, তাই u আগে লেখা হয়। (খ) নইলে প্রথম যে index-এ দুটি আলাদা, সেখানে u-র অক্ষর ছোট (যেমন card আর care-এ d < e): দুটির পথ সেই পর্যন্ত এক, তারপর একই node থেকে দুটি আলাদা সন্তানে ভাগ হয় — আর আমরা ছোট অক্ষরের সন্তানের পুরো subtree শেষ করে তারপর বড়টিতে যাই। তাই u আগে আসে। দুই ক্ষেত্রেই DFS-এর ক্রম = lexicographic ক্রম। ∎ (এই কারণে n টি শব্দ trie-তে ঢুকিয়ে পুরো DFS করলেই সাজানো list পাওয়া যায় — O(N·σ) সময়ের এক ধরনের radix sort.)

খরচ. prefix-এ হাঁটা O(L). তারপর DFS subtree-র প্রতিটি node একবার দেখে; array[σ] হলে প্রতিটি node-এ σ টি ঘর পরীক্ষা, তাই O(L + σ·S + K), যেখানে S = subtree-র node-সংখ্যা আর K = আউটপুটের মোট দৈর্ঘ্য (প্রতিটি শব্দ লিখতে তার দৈর্ঘ্যের সমান সময় লাগে)। ফোনের কিবোর্ড কিন্তু সব শব্দ দেখায় না, দেখায় সবচেয়ে বেশি ব্যবহৃত তিনটি — এ নিয়ে অংশটির শেষে।

এবার সব একসাথে কোডে: insert, search, startsWith, countPrefix, frequency আর autocomplete. C++ সংস্করণে সন্তান array<int, 26>-এ, সব node একটি vector-এ, আর index 0 একই সাথে root আর “সন্তান নেই”-এর চিহ্ন (root কখনো কারও সন্তান হয় না, তাই গোলমাল হয় না)। Python সংস্করণে সন্তান dict-এ — অংশ ৪-এর hash map উপায়।

#include <array>
#include <initializer_list>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Trie {
    vector<array<int, 26>> nxt = vector<array<int, 26>>(1);  // node 0 = root; 0 also means "no child"
    vector<int> pass{0}, ends{0};          // words passing through v / words ending at v
    void insert(const string& w) {
        int v = 0; ++pass[v];
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = (int)nxt.size(); nxt.push_back({}); pass.push_back(0); ends.push_back(0); }
            v = nxt[v][c]; ++pass[v];
        }
        ++ends[v];
    }
    int walk(const string& p) const {      // node of prefix p, or -1
        int v = 0;
        for (char ch : p) if (!(v = nxt[v][ch - 'a'])) return -1;
        return v;
    }
    bool search(const string& w) const { int v = walk(w); return v >= 0 && ends[v] > 0; }
    int countPrefix(const string& p) const { int v = walk(p); return v < 0 ? 0 : pass[v]; }
    void dfs(int v, string& cur, string& out) const {          // preorder, children a..z
        if (ends[v]) out += (out.empty() ? "" : " ") + cur;
        for (int c = 0; c < 26; ++c)
            if (int u = nxt[v][c]) { cur += char('a' + c); dfs(u, cur, out); cur.pop_back(); }
    }
    string complete(string p) const { string out; if (int v = walk(p); v >= 0) dfs(v, p, out); return out; }
};
int main() {
    Trie t;
    for (const char* w : {"car", "card", "care", "cart", "cat", "do", "dog", "dot", "deal", "dog"}) t.insert(w);
    auto yn = [](bool b) { return b ? "yes" : "no"; };
    cout << "nodes: " << t.nxt.size() << "  words: " << t.countPrefix("") << '\n';
    cout << "search car: " << yn(t.search("car")) << "  search ca: " << yn(t.search("ca"))
         << "  startsWith ca: " << yn(t.countPrefix("ca") > 0) << '\n';
    cout << "prefix car: " << t.countPrefix("car") << "  prefix do: " << t.countPrefix("do")
         << "  freq dog: " << t.ends[t.walk("dog")] << '\n';
    cout << "complete ca: " << t.complete("ca") << "\ncomplete d : " << t.complete("d") << '\n';
}

nodes: 15  words: 10
search car: yes  search ca: no  startsWith ca: yes
prefix car: 4  prefix do: 4  freq dog: 2
complete ca: car card care cart cat
complete d : deal do dog dot

class Trie:
    def __init__(self):
        self.kids = [{}]                     # node 0 = root; kids[v]: dict letter -> child id
        self.passes, self.ends = [0], [0]    # words through v / words ending at v
    def insert(self, w):
        v = 0
        self.passes[0] += 1
        for ch in w:
            if ch not in self.kids[v]:
                self.kids[v][ch] = len(self.kids)
                self.kids.append({}); self.passes.append(0); self.ends.append(0)
            v = self.kids[v][ch]
            self.passes[v] += 1
        self.ends[v] += 1
    def walk(self, p):                       # node of prefix p, or -1
        v = 0
        for ch in p:
            v = self.kids[v].get(ch, -1)
            if v < 0: return -1
        return v
    def search(self, w):
        v = self.walk(w); return v >= 0 and self.ends[v] > 0
    def count_prefix(self, p):
        v = self.walk(p); return 0 if v < 0 else self.passes[v]
    def complete(self, p):                   # stored words starting with p, a..z order
        out = []
        def dfs(v, cur):
            if self.ends[v]: out.append(cur)
            for ch in sorted(self.kids[v]):  # a dict keeps insertion order: sort the keys
                dfs(self.kids[v][ch], cur + ch)
        v = self.walk(p)
        if v >= 0: dfs(v, p)
        return " ".join(out)

t = Trie()
for w in ["car", "card", "care", "cart", "cat", "do", "dog", "dot", "deal", "dog"]: t.insert(w)
yn = lambda b: "yes" if b else "no"
print("nodes:", len(t.kids), " words:", t.count_prefix(""))
print("search car:", yn(t.search("car")), " search ca:", yn(t.search("ca")), " startsWith ca:", yn(t.count_prefix("ca") > 0))
print("prefix car:", t.count_prefix("car"), " prefix do:", t.count_prefix("do"), " freq dog:", t.ends[t.walk("dog")])
print("complete ca:", t.complete("ca"))
print("complete d :", t.complete("d"))

nodes: 15  words: 10
search car: yes  search ca: no  startsWith ca: yes
prefix car: 4  prefix do: 4  freq dog: 2
complete ca: car card care cart cat
complete d : deal do dog dot

নিজে চালিয়ে দেখুন — trie visualiser

নিচের টুলে “চালিয়ে দেখুন” চাপুন। বাক্সে একটি শব্দ লিখে যোগ করুন চাপলে সেটি trie-তে ঢুকবে, আর যে node-গুলোর মধ্য দিয়ে গেছে সেগুলো লাল হবে। মোটা দুই-দাগের বর্ডার মানে সেখানে একটি শব্দ শেষ। একটি prefix লিখে পরামর্শ চাপলে prefix-এর পথ জ্বলবে, আর নিচে আসবে সব completion. এই সংস্করণ সন্তান রাখে Map-এ আর অক্ষর ধরে for…of লুপে — তাই “কলম”, “কমল”, “কলা”-র মতো বাংলা শব্দও দিয়ে দেখুন (অংশ ৭).

const kids = [new Map()], endw = [false];     // node 0 = root; kids[v]: letter -> child id
const $ = id => document.getElementById(id);
let hot = new Set();
function addWord(w) {
  let v = 0, made = 0; hot = new Set([0]);
  for (const ch of w) {                        // for..of walks code points, so Bangla works too
    if (!kids[v].has(ch)) { kids[v].set(ch, kids.length); kids.push(new Map()); endw.push(false); made++; }
    v = kids[v].get(ch); hot.add(v);
  }
  endw[v] = true;
  return made;
}
function words(v, cur, out) {                  // preorder DFS, children in sorted order
  if (endw[v]) out.push(cur);
  for (const ch of [...kids[v].keys()].sort()) words(kids[v].get(ch), cur + ch, out);
  return out;
}
function tree(v) {
  const ks = [...kids[v].keys()].sort();
  if (!ks.length) return "";
  return "<ul>" + ks.map(ch => { const c = kids[v].get(ch);
    return `<li><span class="nd${hot.has(c) ? " hl" : ""}${endw[c] ? " end" : ""}">${ch}</span>${tree(c)}</li>`; }).join("") + "</ul>";
}
function draw(msg) {
  $("tr").innerHTML = '<span class="nd hl">root</span>' + tree(0);
  $("msg").textContent = msg; console.log(msg);
}
function insertWord(w) {
  w = w.trim().toLowerCase(); if (!w) return;
  const m = addWord(w); draw(`insert ${w}: +${m} nodes, total ${kids.length}`);
}
function suggest(p) {
  p = p.trim().toLowerCase(); let v = 0; hot = new Set([0]);
  for (const ch of p) { v = kids[v].get(ch); if (v === undefined) { hot = new Set(); return draw(`prefix ${p}: no words`); } hot.add(v); }
  draw(`prefix ${p}: ` + words(v, p, []).join(" "));
}
$("bi").onclick = () => insertWord($("wv").value);
$("bs").onclick = () => suggest($("wv").value);
$("br").onclick = () => { kids.length = 1; kids[0] = new Map(); endw.length = 1; endw[0] = false; hot = new Set(); draw("empty trie"); };
for (const w of ["car", "cat", "card", "do", "dog"]) insertWord(w);
suggest("ca");

insert car: +3 nodes, total 4
insert cat: +1 nodes, total 5
insert card: +1 nodes, total 6
insert do: +2 nodes, total 8
insert dog: +1 nodes, total 9
prefix ca: car card cat

বেশি ব্যবহৃত শব্দ আগে, আর longest common prefix

বাস্তবের কিবোর্ড অভিধানের ক্রমে সব শব্দ দেখায় না, দেখায় সবচেয়ে সম্ভাব্য তিনটি। এখানে end[v] হয় শব্দের frequency — কতবার ব্যবহার হয়েছে। সরল উপায়: subtree-র সব শব্দ বের করে (frequency, শব্দ) ধরে পর্ব ২৩-এর top-k heap চালানো — O(L + σ·S + S log k). কিন্তু “a” টাইপ করলে subtree প্রায় অর্ধেক অভিধান! তাই বড় সিস্টেম আগে থেকে হিসাব করে রাখে: প্রতিটি node-এ তার subtree-র সেরা k টি শব্দের একটি ছোট list. প্রশ্ন তখন O(L + k), কিন্তু প্রতিটি node-এ k টি বাড়তি তথ্য, আর frequency বদলালে পথের সব node-এর list হালনাগাদ করতে হয় — আবারও সময় আর জায়গার বিনিময়।

একটি ক্লাসিক ইন্টারভিউ প্রশ্ন: কয়েকটি শব্দের longest common prefix (LCP) কী? পর্ব ১১-এ দুটি সরল পদ্ধতি দেখেছেন। Trie দিয়ে উত্তরটি চোখে দেখা যায়: সব শব্দ ঢোকান, তারপর root থেকে নামুন যতক্ষণ বর্তমান node-এর ঠিক একটি সন্তান আছে আর বর্তমান node নিজে কোনো শব্দের শেষ নয়। যেমন {flower, flow, flight}: f → l পর্যন্ত একটিই পথ, তারপর l-এর দুটি সন্তান (o আর i) — LCP “fl”. আর {interview, internet, in}-এ “in”-এর n-এ শব্দ শেষ, তাই সেখানেই থামতে হবে: LCP “in”. খরচ ঢোকাতে O(N), নামতে O(LCP-র দৈর্ঘ্য). শুধু একবারের প্রশ্নে সাজিয়ে প্রথম আর শেষ শব্দ মেলানো সহজতর, কিন্তু শব্দ যোগ হতে থাকলে trie প্রতিবার নতুন উত্তর সস্তায় দেয়।

৭ · বাংলা আর Unicode-এর trie — code point না byte?

ইংরেজির ২৬টি অক্ষরের হিসাব সরল। কিন্তু বাংলায় সার্চ-পরামর্শ, বাংলা বানান-যাচাই বা ফোনবুকে বাংলা নাম খুঁজতে কী হবে? পর্ব ১১-এ দেখেছেন, কম্পিউটারে প্রতিটি অক্ষর একটি সংখ্যা: Unicode-এ প্রতিটি অক্ষরের একটি code point (বাংলার জন্য U+0980 থেকে U+09FF — ১২৮টি ঘরের একটি block), আর ফাইলে বা মেমরিতে তা সাধারণত UTF-8 encoding-এ — প্রতিটি বাংলা অক্ষর ৩টি byte. “কলম” আর “কমল” নিয়ে দুই উপায় দেখুন:

Byte-trie-এর সেই একা-সন্তানের শিকল ঠিক পরের অংশের radix tree জুড়ে ফেলে, তাই বাস্তবে অনেক লাইব্রেরি byte-এর ওপর compressed trie বানায়। আর byte-এর ক্রম আর code point-এর ক্রম UTF-8-এ একই — UTF-8-এর একটি পরিকল্পিত গুণ — তাই দুই উপায়েই DFS একই lexicographic ক্রম দেয়।

কিন্তু সেই “lexicographic” ক্রম বাংলা বর্ণমালার ক্রম কি না, সেটি আলাদা প্রশ্ন। বেশিরভাগ ক্ষেত্রে কাছাকাছি — ক (U+0995) খ-এর (U+0996) আগে — কিন্তু ং (U+0982) আর ঃ (U+0983) আছে অ-এর (U+0985) আগে, আর য় (U+09DF) বসেছে হ-এর (U+09B9) অনেক পরে। অভিধানের মতো ক্রম চাইলে আলাদা collation নিয়ম লাগে (পর্ব ২৫).

৮ · Radix tree, Patricia আর trie-র পরিবার

একা-সন্তানের শিকল জুড়ে ফেলা — compressed trie

“internationalization” একা একটি শব্দ trie-তে রাখলে ২০টি node, প্রতিটির একটি মাত্র সন্তান — আর array[26] নিলে প্রতিটিতে ২৫টি খালি ঘর। সমাধান: যে node-এর ঠিক একটি সন্তান আর যে নিজে শব্দের শেষ নয়, তাকে তার সন্তানের সাথে জুড়ে দিন। তখন একটি edge-এ একটি অক্ষর নয়, একটি পুরো string. এর নাম radix tree বা compressed trie.

সাধারণ trie — romane, romanus, romulus, rubens (root ছাড়া ১৭টি node)

r ─┬─ o ─ m ─┬─ a ─ n ─┬─ e*
   │         │         └─ u ─ s*
   │         └─ u ─ l ─ u ─ s*
   └─ u ─ b ─ e ─ n ─ s*

radix tree — একই চারটি শব্দ (root ছাড়া ৭টি node)

r ─┬─ om ─┬─ an ─┬─ e*
   │      │      └─ us*
   │      └─ ulus*
   └─ ubens*

কেন জায়গা নিশ্চিতভাবে কমে? Radix tree-তে প্রতিটি internal node হয় একটি শব্দের শেষ, নয়তো তার অন্তত দুটি সন্তান। n টি শব্দ মানে বড়জোর n টি leaf, আর অন্তত দুই-সন্তানের internal node সর্বোচ্চ n − 1 টি — তাই মোট node O(n), শব্দগুলো যত লম্বাই হোক। খোঁজা এখনও O(L): edge-এর label-এর অক্ষরগুলো একে একে মেলাতে হয়।

১৯৬৮ সালে Donald R. Morrison Journal of the ACM-এ প্রকাশ করেন PATRICIA — “Practical Algorithm To Retrieve Information Coded In Alphanumeric”. এটি key-কে bit-এর সারি হিসেবে দেখে (σ = ২), আর প্রতিটি node-এ শুধু লেখা থাকে “এবার কোন bit-টি দেখতে হবে” — মাঝের যেসব bit-এ কোনো শাখা নেই, সেগুলো সরাসরি লাফিয়ে পার হয়। শেষে পৌঁছে পুরো key একবার মিলিয়ে নিতে হয়, কারণ লাফানো bit-গুলো দেখা হয়নি। আজ “Patricia trie” আর “radix tree” নাম দুটি প্রায়ই একই অর্থে ব্যবহার হয়।

যেখানে radix tree রোজ চলে

IP routing — longest prefix match. আপনার bKash অ্যাপের প্রতিটি অনুরোধ ইন্টারনেটে অসংখ্য router পার হয়। প্রতিটি router-এর routing table-এ IP address-এর prefix আর “কোন দিকে পাঠাতে হবে” লেখা থাকে, যেমন:

গন্তব্য 10.1.2.3 হলে তিনটি নিয়মই মেলে, কিন্তু নিতে হবে সবচেয়ে লম্বা (সবচেয়ে নির্দিষ্ট) মেলা prefix-টি — B. এর নাম longest prefix match. 10.2.3.4 যাবে A-তে, 8.8.8.8 যাবে C-তে। Hash table এখানে সরাসরি কাজ করে না, কারণ জানা নেই কত bit-এর prefix খুঁজতে হবে। Trie-তে কাজটি স্বাভাবিক: address-এর ৩২টি bit ধরে নামুন, আর পথে শেষ যে node-এ একটি নিয়ম পেয়েছেন সেটি মনে রাখুন — O(W), W = address-এর bit (IPv4-এ ৩২, IPv6-এ ১২৮). BSD ঘরানার অপারেটিং সিস্টেমে বহু বছর ধরে radix tree দিয়ে routing table রাখা হয়েছে, আর Linux kernel IPv4-এর জন্য একটি level-compressed trie (LC-trie) ব্যবহার করে। বড় হার্ডওয়্যার router কাজটি আরও দ্রুত করতে বিশেষ মেমরি-চিপ (TCAM) ব্যবহার করে।

Web server-এর URL router. একটি API-তে হাজারো পথ থাকতে পারে: /users, /users/:id, /users/:id/orders, /products… প্রতিটি অনুরোধের URL কোন handler-এ যাবে? Go-র জনপ্রিয় httprouter লাইব্রেরি আর তার ওপর বানানো Gin framework এই কাজে radix tree ব্যবহার করে — খরচ URL-এর দৈর্ঘ্যের সমানুপাতিক, route-এর সংখ্যার নয়। Redis-এর stream-এর ভেতরেও একটি radix tree (rax) আছে, আর Ethereum তার state রাখে “Merkle Patricia Trie”-তে।

Ternary search tree আর suffix trie — দুই আত্মীয়

Ternary search tree (TST; Jon Bentley আর Robert Sedgewick, ১৯৯৭) array-র মেমরি সমস্যার আরেকটি সমাধান: প্রতিটি node-এ একটি অক্ষর আর তিনটি সন্তান — ছোট (<), সমান (=), বড় (>). অক্ষর মিললে “সমান” দিয়ে শব্দের পরের অক্ষরে যান; না মিললে BST-র মতো বাঁয়ে বা ডানে, একই অক্ষর-অবস্থানে। প্রতিটি node-এ মাত্র তিনটি pointer, আর prefix-খোঁজা ও ক্রমে ঘোরা সবই চলে। খরচ মোটামুটি L আর একটি BST-র গভীরতার যোগফল — এলোমেলো ক্রমে ঢোকালে গড়ে O(L + log n).

একটি লেখা T-এর (দৈর্ঘ্য m) সব suffix একটি trie-তে ঢোকালে পাওয়া যায় suffix trie. T-এর যেকোনো substring কোনো না কোনো suffix-এর prefix — তাই “P কি T-এর ভেতরে আছে?” প্রশ্নের উত্তর O(|P|)-এ, T যত বড়ই হোক। সমস্যা আকারে: m টি suffix-এর মোট দৈর্ঘ্য m(m+1)/2, তাই worst case-এ Θ(m²) node. Radix-এর মতো জুড়ে ফেললে আসে suffix tree — O(m) node (Peter Weiner, ১৯৭৩; পরে Esko Ukkonen ১৯৯৫ সালে বাঁ থেকে ডানে এক পাসে বানানোর পদ্ধতি দেন)। আর সব suffix-কে শুধু তাদের শুরুর index দিয়ে সাজিয়ে রাখলে পাওয়া যায় আরও কম জায়গার suffix array (Udi Manber আর Gene Myers, ১৯৯০) — যা আসলে suffix tree-র leaf-গুলোকে lexicographic DFS-এর ক্রমে পড়া। অনেকগুলো pattern একসাথে খোঁজার Aho-Corasick অ্যালগরিদমও একটি trie-র ওপর বানানো। এসব বিস্তারিত পর্ব ৫৯-এ।

৯ · Binary trie আর maximum XOR pair — কনটেস্টের প্রিয় কৌশল

সমস্যা: n টি অঋণাত্মক পূর্ণসংখ্যার মধ্যে এমন দুটি বাছুন, যাদের XOR সবচেয়ে বড়। সব জোড়া দেখলে O(n²) — n = ২ লাখ হলে প্রায় ২০০০ কোটি জোড়া, কনটেস্টের সময়সীমায় অসম্ভব। কৌশল: সংখ্যাগুলোকে B bit-এর string হিসেবে দেখুন (সবচেয়ে বড় bit আগে), আর σ = ২-এর একটি trie-তে রাখুন — binary trie.

মূল পর্যবেক্ষণ greedy, কিন্তু প্রমাণযোগ্য: XOR-এর মান ঠিক করে সবচেয়ে বাঁয়ের যে bit 1. 2^b > 2^b−1 + … + 2 + 1, তাই bit b-তে 1 পাওয়া নিচের সব bit মিলিয়ে যা পাওয়া যায় তার চেয়ে বেশি দামি। তাই একটি সংখ্যা x-এর সেরা সঙ্গী y খুঁজতে root থেকে নামুন, সবচেয়ে বড় bit আগে: প্রতিটি ধাপে x-এর bit-এর উল্টো bit-এর সন্তান থাকলে সেদিকে যান (ফলের এই bit = 1); না থাকলে বাধ্য হয়ে একই bit-এর দিকে (ফলের bit = 0). পুরো উত্তর: সংখ্যাগুলো একে একে নিন — প্রতিটির জন্য আগে ঢোকানো সংখ্যাদের মধ্যে সেরা সঙ্গী খুঁজুন, তারপর সেটি নিজে ঢোকান। এভাবেই প্রতিটি জোড়া (i < j) একবার বিবেচিত হয় — maximum XOR pair.

প্রমাণ (exchange-এর ধাঁচে). ধরুন greedy পথ প্রথম যে bit b-তে সত্যিকারের সেরা সঙ্গী y* থেকে আলাদা হলো। তার আগের সব bit-এ দুটির পথ এক, তাই ফলের ওপরের bit-গুলোও এক। bit b-তে greedy উল্টো bit নিয়েছে (ফলে 1) — নিশ্চয়ই y*-এর পথে ছিল একই bit (ফলে 0), কারণ greedy শুধু উল্টোটি না থাকলেই একই bit নেয়, আর সেক্ষেত্রে y*-ও সেই পথেই থাকত। তাহলে greedy-র ফল bit b-তে 1, y*-এর 0, ওপরে সমান — তাই greedy-র ফল কঠোরভাবে বড়, যা y* সেরা হওয়ার সাথে বিরোধ। অতএব greedy-ই সেরা। নিচে a = [3, 10, 5, 25, 2, 8]-এ (B = 5 bit) x = 25-এর পালা দেখুন, যখন trie-তে আগের তিনটি সংখ্যা {3, 10, 5} আছে।

বিশ্লেষণ. প্রতিটি insert আর প্রতিটি query ঠিক B ধাপ, তাই মোট সময় Θ(n·B); trie-তে সর্বোচ্চ n·B + 1 টি node, প্রতিটিতে দুটি int — জায়গা O(n·B). মান ১০^৯ পর্যন্ত হলে B = ৩০ (কারণ 2³⁰ > ১০^৯), তাই n = ২ লাখে insert আর query মিলিয়ে প্রায় ১ কোটি ২০ লাখ ধাপ — চোখের পলকে। নিচের কোড এই উদাহরণ চালায়, তারপর ৩০০টি এলোমেলো অ্যারেতে উত্তরটি সরল O(n²) brute force-এর সাথে মিলিয়ে দেখে — এটিই stress testing.

#include <algorithm>
#include <array>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
const int B = 20;                                  // values are in [0, 2^20)
int maxXorTrie(const vector<int>& a) {
    vector<array<int, 2>> ch(1);                   // node 0 = root; ch[v][bit] = child, 0 = none
    auto add = [&](int x) {
        int v = 0;
        for (int b = B - 1; b >= 0; --b) {
            int bit = (x >> b) & 1;
            if (!ch[v][bit]) { ch[v][bit] = (int)ch.size(); ch.push_back({}); }
            v = ch[v][bit];
        }
    };
    auto best = [&](int x) {                       // max of x ^ y over every y already inserted
        int v = 0, r = 0;
        for (int b = B - 1; b >= 0; --b) {
            int want = ((x >> b) & 1) ^ 1;         // the opposite bit puts a 1 here
            if (ch[v][want]) { r |= 1 << b; v = ch[v][want]; } else v = ch[v][want ^ 1];
        }
        return r;
    };
    int ans = 0; add(a[0]);
    for (size_t i = 1; i < a.size(); ++i) { ans = max(ans, best(a[i])); add(a[i]); }
    return ans;
}
int maxXorBrute(const vector<int>& a) {
    int r = 0;
    for (size_t i = 0; i < a.size(); ++i) for (size_t j = i + 1; j < a.size(); ++j) r = max(r, a[i] ^ a[j]);
    return r;
}
int main() {
    vector<int> a{3, 10, 5, 25, 2, 8};
    cout << "trie: " << maxXorTrie(a) << ", brute force: " << maxXorBrute(a) << '\n';
    mt19937 rng(2026); int ok = 0;
    for (int t = 0; t < 300; ++t) {
        vector<int> v(2 + rng() % 60);
        for (int& x : v) x = int(rng() % (1u << B));
        ok += maxXorTrie(v) == maxXorBrute(v);
    }
    cout << "random tests passed: " << ok << " / 300\n";
}

trie: 28, brute force: 28
random tests passed: 300 / 300

import random
B = 20                                   # values are in [0, 2**20)

def max_xor_trie(a):
    ch = [[0, 0]]                        # node 0 = root; ch[v][bit] = child id, 0 = none
    def add(x):
        v = 0
        for b in range(B - 1, -1, -1):
            bit = (x >> b) & 1
            if not ch[v][bit]:
                ch[v][bit] = len(ch); ch.append([0, 0])
            v = ch[v][bit]
    def best(x):                         # max of x ^ y over every y already in the trie
        v = r = 0
        for b in range(B - 1, -1, -1):
            want = ((x >> b) & 1) ^ 1    # the opposite bit puts a 1 here
            if ch[v][want]: r |= 1 << b; v = ch[v][want]
            else: v = ch[v][want ^ 1]
        return r
    ans = 0; add(a[0])
    for x in a[1:]:
        ans = max(ans, best(x)); add(x)
    return ans

def max_xor_brute(a):
    return max(a[i] ^ a[j] for i in range(len(a)) for j in range(i + 1, len(a)))

a = [3, 10, 5, 25, 2, 8]
print(f"trie: {max_xor_trie(a)}, brute force: {max_xor_brute(a)}")
random.seed(2026); ok = 0
for _ in range(300):
    v = [random.randrange(1 << B) for _ in range(random.randint(2, 61))]
    ok += max_xor_trie(v) == max_xor_brute(v)
print(f"random tests passed: {ok} / 300")

trie: 28, brute force: 28
random tests passed: 300 / 300

একই binary trie আরও অনেক সমস্যার চাবি। Prefix XOR (পর্ব ১৭) p[i] রাখলে যেকোনো subarray-র XOR = p[r] XOR p[l − 1] — তাই “সবচেয়ে বড় XOR-এর subarray” আসলে prefix XOR-গুলোর মধ্যে maximum XOR pair. প্রতিটি node-এ subtree-র সংখ্যা গুনে রাখলে “x-এর সাথে XOR k-এর কম এমন কয়টি সংখ্যা” বা “k-তম ছোট XOR”-এর মতো প্রশ্নও O(B)-এ। আর সংখ্যা মুছতে হলে অংশ ৫-এর pass-counter কৌশল হুবহু কাজ করে: counter শূন্য হলে সেই শাখায় নামবেন না।

১০ · AI-এর যুগে trie — কোড ছোট, ফাঁদ সূক্ষ্ম

“একটি Trie class লিখে দাও insert, search, startsWith সহ” — যেকোনো AI কয়েক সেকেন্ডে এটি লিখবে, আর প্রায় সবসময় ঠিকও লিখবে, কারণ এটি সবচেয়ে বেশি অনুশীলিত ইন্টারভিউ প্রশ্নগুলোর একটি। ভুল লুকোয় একটু বাইরের অংশে: delete-এ ভাগাভাগি করা node মুছে ফেলা, autocomplete-এ hash map-এর এলোমেলো ক্রম, বড় ইনপুটে মেমরি সীমা পার হওয়া, বা XOR-এর প্রশ্নে bit-এর ভুল সীমা। আর complexity জিজ্ঞেস করলে AI প্রায়ই trie-র search-কে “O(log n)” বা জায়গাকে শুধু “O(N)” বলে দেয়, σ-এর গুণটি বাদ দিয়ে।

Trie-এর কোডে AI সাধারণত যেসব ভুল করে

Trie-এর কোড যাচাইয়ের চেকলিস্ট

• search আর startsWith আলাদা করে পরীক্ষা করেছি: রাখা শব্দ, শুধু prefix, আর একেবারে না-থাকা শব্দ
• Edge case চালিয়েছি: খালি string, একই শব্দ দুবার, একটি শব্দ আরেকটির prefix (car / card), খালি trie-তে খোঁজা
• autocomplete-এর ফল একই শব্দগুলো list-এ রেখে filter আর sort করা brute force-এর সাথে মিলিয়েছি
• হাজারটি এলোমেলো insert/erase/countPrefix-এর পর counter-গুলো একটি সরল গণনার সাথে মেলে কি না — stress test করেছি
• ইনপুটের অক্ষর-সীমা যাচাই করেছি (শুধু a–z? বড় হাতের? Unicode?), আর মেমরি হাতে হিসাব করেছি
• XOR-এর প্রশ্নে B-কে সবচেয়ে বড় মানের bit-সংখ্যার সাথে মিলিয়েছি, আর brute force-এর সাথে এলোমেলো পরীক্ষা চালিয়েছি