ট্রাই ট্রি ( Trie Tree )

আগে জেনে আসা উচিত : ট্রি, লিঙ্কড লিস্ট, Prefix কাকে বলে

সূচনা

গুগল সার্চ করার সময়ে দেখা যায় কোন কিছু লিখলে গুগল আমাদের কে কিছু সাজেশন দেখায় যেমন লিখলাম, যেমনটি নিচের মতো –

 

এটা কিভাবে করে গুগল ? এই টাকে যদি একটি প্রব্লেম হিশেবে চিন্তা করি , তাহলে সহজভাবে বলা যায় –

তোমাকে অনেকগুলি শব্দের অভিধান ( Dictionary ) দেয়া আছে, এখন তোমাকে আবার কতগুলো শব্দ দেয়া হবে, প্রতিটি শব্দ এর জন্য তোমাকে বলতে হবে যে অই শব্দ টি তোমার অভিধানের কতগুলো শব্দের Prefix ?

ধরো, তোমার অভিধানে এই শব্দ গুলো আছে –

ABBA

ABC

ACCA

ANA

ANACONDA

BAAB

এখন যদি তোমাকে জিজ্ঞাশা করা হয় যে “AB” শব্দটি অভিধানের কতটি শব্দের Prefix ? উত্তর হবে ২, শুধু “A” এর ক্ষেত্রে উত্তর হবে ৫।

এবার এই প্রব্লেম এর সল্যুশন বের করি-

অবশ্যই Brute Force একটি উপায় যার Order হবে প্রায় O(n^3) , কিন্তু যদি আমরা  আরও ভালো উপায় খুজতে চাই তখন কি হতে পারে ? একটি উপায় হতে পারে আমার ডিকশনারির সব গুলো শব্দ কে Lexicographically সাজায়ে বাইনারি সার্চ। কিন্তু সে উপায়ে Order হবে O(nlogn)। এর চেয়ে ভালো উপায় আছে কি ?

হুম… আছে। আরেকটি উপায় হচ্ছে ট্রাই ট্রি ( Trie Tree ). যা O(n) [ আসলে O( given word’s length ) ] এ কাজ করে।

ট্রাই ট্রি কি জিনিশ ?

ট্রাই ট্রি একটি ডাটা স্ট্রাকচার, যার নাম টি এসেছে “Retrieval” শব্দটি থেকে । ট্রাই ট্রি কে প্রেফিক্স ট্রি ও বলা হয়ে থাকে। ট্রাই ট্রি এর বৈশিষ্ট্য হচ্ছে-

১। ট্রাই ট্রি এর প্রতিটি ভারটেক্স একটি সম্পূর্ণ শব্দ বা একটি শব্দের Prefix কে প্রকাশ বা নির্দেশ করে।

২। এই ট্রি এর রুট (Root) একটি Empty String, এবং রুট থেকে তার প্রতিটি সন্তান এর মধ্যে Shortest Path Distance অই দৈর্ঘ্য এর প্রেফিক্স কে নির্দেশ করে। যদি রুট থেকে কোন সন্তান এর মধ্যে সবচেয়ে কাছাকাছি পথ এর দৈর্ঘ্য ২ হয় তার মানে হচ্ছে অই vertex টি কোন এক বা একাধিক শব্দের ২ দৈর্ঘ্য এর prefix কে নির্দেশ করে।

৩। যদি A এবং B ট্রাই ট্রি এর দুটি ভারটেক্স হয়, এবং A যদি B এর সবচেয়ে নিকটবর্তী পিতা হয় তাহলে A অবশ্যই B এর প্রেফিক্স কে নির্দেশ করে।

ট্রাই ট্রি দেখতে কিরকম ?

যদি আমরা “HOME”, “HOUSE”, “HOMEWORKER”, “MOUNTAIN” শব্দ গুলি নিয়ে একটি ট্রাই ট্রি বানাই , তাহলে দেখতে এরকম হবে –

খেয়াল করে দেখ, প্রত্যেক টি ভারটেক্স কিন্তু একটি প্রেফিক্স কে নির্দেশ করছে। HOME, HOUSE দুটি শব্দেরই কিন্তু ২ দৈর্ঘ্য এর প্রেফিক্স সমান, এ কারনে ৩ দীর্ঘের প্রেফিক্স এর সময় দুটি চাইল্ড নোড আসছে। আর প্রত্যেকটি কমলা রঙ করা ভারটেক্স বা নোড একটি সম্পূর্ণ শব্দ কে নির্দেশ করে।

ট্রাই এর কোড

নিচে Reference অংশে কিছু লিঙ্ক দেয়া আছে, ওখান থেকে কোড পাবে।

ট্রাই দিয়ে প্রব্লেম সল্ভিং

যেই প্রব্লেম দিয়ে শুরু করেছিলাম ব্লগটি সেই প্রব্লেম টা এবার ট্রাই দিয়ে সমাধান করি। যদি প্রতিটি ভারটেক্স এ আমরা একটা কাউন্টার রাখি যা আমাদেরকে বলে দিবে যে অই প্রেফিক্স টা কতটি শব্দের প্রেফিক্স , তাহলেই তো হয়ে গেল তাই না। আমরা প্রথমেই অভিধান এর শব্দ গুল ট্রাই ট্রি তে Insert করবো এবং যেইশব নোড দিয়ে যাব তাদের কাউন্টার বাড়াবো, এরপর প্রতিটি Query  করা শব্দের জন্য ট্রাই ট্রি তে দেখবো যেই অই শব্দটার পুরোটাই আমাদের ট্রি তে আছে কিনা , যদি থাকে তাহলে যেই নোড এ গিয়ে শেষ হয়েছে শব্দটা সেই নোড এর কাউন্টার ই তো আমাদের উত্তর।

এখন যদি তোমাকে কোন Query String দিয়ে যদি বলা হয় যে এই String টা তোমার অভিধানে আছে কিনা ? তাহলে কিভাবে ট্রাই দিয়ে বের করবো ? সহজ ব্যাপার, প্রতিটি নোড এ একটি ফ্ল্যাগ রাখবো যা নির্দেশ করবে যেই অই নোড টি কোন শব্দের শেষ কিনা মানে অই নোড এ কোন শব্দ শেষ হয়েছে কিনা। এখন আমরা যখন একেকটি শব্দ অভিধানে Insert করবো তখন যেই নোড এ আমাদের শব্দ টা শেষ হবে সেই নোড এর ফ্ল্যাগ টা 1 করে দিবো। এখন Query String এর জন্য আমরা ট্রাভারস করবো আমাদের ট্রি টা এবং দেখবো যে যেই নোড এ আমাদের query string শেষ হয়েছে তার ফ্ল্যাগ অন কিনা। সোজা না ?

রেফারেন্স

1.  http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries
2.  http://www.toptal.com/java/the-trie-a-neglected-data-structure
3. http://en.wikipedia.org/wiki/Trie

প্রোগ্রামিং প্রব্লেম

1. http://www.lightoj.com/volume_problemcategory.php?category=Trie%20Tree
2. http://www.spoj.com/problems/PHONELST/
3. http://www.spoj.com/problems/SUBXOR/%5B/embed

ধন্যবাদান্তে

সাব্বির ইউসুফ সানি ভাই,যার কাছ থেকে এই ডাটা স্ট্রাকচার শিখেছিলাম।

 

[ কোন কিছু বুঝতে অসুবিধা হলে , এখানে কমেন্ট করতে পারো অথবা ইমেইল করতে পারো faiyaz26 [at] gmail [dot] com এ ]