ট্রিপড়তে ৬ মিনিট লাগবে

ট্রাই (Trie বা Prefix Tree)

শব্দের প্রথম কয়েকটা অক্ষর দিয়ে পুরো শব্দ খোঁজা — চোখের পলকে অটোকারেক্ট বা সাজেশন
insert: O(L)search: O(L)prefix search: O(L)space: O(মোট অক্ষরের সংখ্যা)

একটা ট্রাই (Trie) (উচ্চারণ 'ট্রাই', retrieval শব্দ থেকে এসেছে) হলো এমন একটা গাছের মতো ডেটা স্ট্রাকচার, যার প্রতিটা নোড বা ডালে একটা করে অক্ষর (character) থাকে। গাছের রুট বা শেকড় থেকে শুরু করে একটা নির্দিষ্ট দাগ দেওয়া নোড পর্যন্ত হেঁটে গেলে একটা পুরো শব্দ পাওয়া যায়। সবচেয়ে মজার ব্যাপার হলো, যেসব শব্দের শুরুর দিকের অক্ষরগুলো (prefix) একইরকম, তারা গাছের একই ডাল শেয়ার করে।

আমাদের ডিকশনারির কথা ভাবুন: "ca" দিয়ে শুরু হওয়া সব শব্দ এক জায়গায় থাকে — "cat", "car", "card", "care"। ট্রাই ঠিক এভাবেই ডেটাগুলোকে সুন্দর করে গুছিয়ে রাখে।

স্ট্রাকচার বা গঠন

ট্রাইয়ের প্রতিটা নোডে দুটো জিনিস থাকে:

  • একটা অ্যারে বা ম্যাপ, যেখানে সর্বোচ্চ ২৬টা বাচ্চার জায়গা থাকে (ইংরেজি বর্ণমালার ২৬টা অক্ষরের জন্য)।
  • একটা বুলিয়ান ফ্ল্যাগ বা সিগন্যাল: is_end_of_word — যেটা বলে দেয়, "হ্যাঁ, এখানে এসে একটা পুরো শব্দ শেষ হয়েছে।"
pseudocode
1
2
3
4
class TrieNode:
  def __init__(self):
    self.children = {}  # অক্ষর → TrieNode
    self.is_end = False

রুট বা শেকড়টা একদম খালি থাকে — তার মানে সে কোনো অক্ষর না। রুট থেকে একটা একটা ডাল ধরে নিচে নামলে অক্ষরগুলো মিলে ধীরে ধীরে একটা শব্দ তৈরি হয়।

◈ খালি জায়গায় শব্দ বসানো দেখুন

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

নতুন শব্দ ঢোকানো (Insert)

ধরুন আপনি "cat" শব্দটা বসাতে চান:

  1. রুট থেকে শুরু করুন। রুটের কি 'c' নামে কোনো বাচ্চা আছে? না থাকলে, একটা তৈরি করুন এবং সেখানে যান।
  2. এবার 'c' নোডে আছেন। এর কি 'a' নামে কোনো বাচ্চা আছে? না থাকলে তৈরি করুন।
  3. এবার 'a' নোডে। এর কি 't' নামে কোনো বাচ্চা আছে? না থাকলে তৈরি করুন।
  4. অবশেষে 't' নোডে এসে is_end = True করে দিন।

এখন যদি "cat"-এর পর "car" বসাতে চান: ১ আর ২ নম্বর ধাপ হুবহু মিলে যাবে (কারণ 'c'->'a' রাস্তাটা আগেই বানানো আছে)। 'a'-তে এসে আপনি নতুন একটা ডাল 'r' বানাবেন এবং সেটাকে is_end হিসেবে মার্ক করবেন। এখানে শুরুর অক্ষরগুলো একই রাস্তা ব্যবহার করছে — কোনো ডুপ্লিকেট জায়গা নষ্ট হচ্ছে না!

pseudocode
1
2
3
4
5
6
7
def insert(word):
  node = root
  for char in word:
    if char not in node.children:
      node.children[char] = TrieNode()
    node = node.children[char]
  node.is_end = True

শব্দ খোঁজা (Search)

অক্ষর ধরে ধরে একটার পর একটা এগোতে থাকুন। যদি মাঝপথে কোনো অক্ষর না মেলে → তার মানে শব্দটা ট্রাইয়ের ভেতর নেই। আর যদি শেষ অক্ষর পর্যন্ত পৌঁছে যান, তখন is_end সিগন্যালটা চেক করে দেখুন যে সত্যিই ওখানে কোনো শব্দ শেষ হয়েছে কি না।

pseudocode
1
2
3
4
5
6
def search(word):
  node = root
  for char in word:
    if char not in node.children: return False
    node = node.children[char]
  return node.is_end  # ট্রু হবে যদি এবং কেবল যদি এখানে শব্দটা শেষ হয়

প্রিফিক্স খোঁজা বা অটো-সাজেশন (Prefix search)

ট্রাইয়ের সবচেয়ে মারাত্মক ফিচারটা হলো: একটা নির্দিষ্ট 'প্রিফিক্স' (prefix বা শব্দের শুরুর অংশ) দিয়ে শুরু হওয়া সব শব্দ আপনি O(L) সময়ে (L হলো ওই প্রিফিক্সের সাইজ) খুঁজে পেতে পারেন। ওই প্রিফিক্সের রাস্তা ধরে হেঁটে শেষ মাথায় পৌঁছান; এরপর সেখান থেকে নিচের দিকে যত রাস্তা বা ডাল আছে, তার সবগুলোই হলো আপনার অটো-সাজেশনের রেজাল্ট বা সম্ভাব্য শব্দ।

pseudocode
1
2
3
4
5
6
def starts_with(prefix):
  node = root
  for char in prefix:
    if char not in node.children: return False
    node = node.children[char]
  return True  # হ্যাঁ, এই প্রিফিক্স দিয়ে শব্দ আছে

কোথায় কাজে লাগে?

  • অটোকমপ্লিট (Autocomplete) — গুগল বা ইউটিউবের সার্চ বার, কোড লেখার এডিটর, বা মোবাইলের কিবোর্ডের সাজেশন।
  • বানান ভুল চেক করা — পুরো ডিকশনারি সেভ করে রাখা এবং চোখের পলকে বা O(L) স্পিডে শব্দ খোঁজা।
  • আইপি রাউটিং (IP routing) — নেটওয়ার্কের সবচেয়ে লম্বা প্রিফিক্স মেলানোর কাজে।
  • শব্দের গেম বা পাজল — একটা নির্দিষ্ট অক্ষর দিয়ে শুরু হওয়া সব শব্দ জাদুকরী স্পিডে খুঁজে বের করতে।

মেমোরি বা স্পেসের হিসাব

প্রতিটা নোডের ভেতরে ২৬টা বাচ্চার জায়গা বরাদ্দ থাকতে পারে (যদি শুধু ছোট হাতের ইংরেজি অক্ষর হয়)। তবে খুব একটা দরকার না হলেও ২৬টা জায়গা নষ্ট না করে সাধারণ হ্যাশ ম্যাপ ব্যবহার করাই ভালো। এখানে মোট মেমোরি লাগে ট্রাইয়ে ঢোকানো সবগুলো শব্দের মোট অক্ষরের সংখ্যা সমান।

দ্রষ্টব্য: ১০ হাজার ইংরেজি শব্দের একটা ট্রাইয়ে মোটামুটি ৫০ হাজার থেকে ২ লাখের মতো নোড লাগে, কারণ অনেক শব্দের শুরুর অক্ষরগুলো সেম বা শেয়ারড থাকে। একই শব্দগুলো যদি সাধারণ হ্যাশ সেটে রাখা হতো, তাহলে ১০ হাজার এন্ট্রিই হয়ে যেত, কিন্তু তখন আবার ওই সার্চ বারের অটো-সাজেশন বা প্রিফিক্স খোঁজার কাজটা করা যেত না। এটা হলো স্পিড বাড়ানোর জন্য একটু বেশি জায়গা খরচ করার একটা বুদ্ধি বা ট্রেডঅফ।

Complexity

L সাইজের শব্দ বসানো
প্রতিটা অক্ষরের জন্য এক ধাপ — অন্য শব্দের সাথে কোনো তুলনা করতে হয় না
অত্যন্ত ফাস্ট O(L)
হুবহু শব্দটা খোঁজা
L-টা অক্ষর ধরে হেঁটে গিয়ে শুধু is_end ফ্ল্যাগটা চেক করা
অত্যন্ত ফাস্ট O(L)
প্রিফিক্স বা শুরুর অংশ খোঁজা
প্রিফিক্স ধরে আগানো — এরপর যে ডালগুলো আছে সেটাই অটো-সাজেশন
অত্যন্ত ফাস্ট O(L)
শব্দ ডিলিট করা
is_end ফ্ল্যাগটা অফ করে দেওয়া; চাইলে অব্যবহৃত ডাল কেটেও দেওয়া যায়
অত্যন্ত ফাস্ট O(L)
জায়গা (Space)
শেয়ার করা প্রিফিক্সের কারণে অনেকগুলো শব্দ আলাদা রাখলেও জায়গা বেঁচে যায়
অক্ষরের সমানুপাতিক O(মোট অক্ষর)
Challenge

ছোট কুইজ

একটা ট্রাইয়ের ভেতরে "app", "আম", আর "application" — এই তিনটা শব্দ আছে। "appl" এই প্রিফিক্সটা বা শুরুর অংশটা তিনটা শব্দের মধ্যে মোট কয়টা নোড বা ঘর শেয়ার করবে?

পড়া চালিয়ে যান

বাইনারি ট্রি (Binary Trees)
এমন একটা ফ্যামিলি ট্রি, যেখানে বাবা-মায়ের সর্বোচ্চ দুজন করেই সন্তান থাকতে পারে
→
বাইনারি সার্চ ট্রি (Binary Search Tree)
সাজানেন-গোছানো গাছ — বাঁয়ে ছোটরা, ডানে বড়রা
→
সাফিক্স অ্যারে এবং এলসিপি অ্যারে (Suffix Array & LCP Array)
কোনো শব্দের সবগুলো সাফিক্স বা শেষাংশকে সাজিয়ে রাখা — স্ট্রিং খোঁজার দুনিয়ার এক জাদুকরী হাতিয়ার
→
Strings & FormattingPython
Slice, format, and play with text
→