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

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

সূচনা

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

google suggestion

 

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

তোমাকে অনেকগুলি শব্দের অভিধান ( 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” শব্দ গুলি নিয়ে একটি ট্রাই ট্রি বানাই , তাহলে দেখতে এরকম হবে –

trie2খেয়াল করে দেখ, প্রত্যেক টি ভারটেক্স কিন্তু একটি প্রেফিক্স কে নির্দেশ করছে। 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 এ ]

কিউ বেসিক ডাটা স্ট্রাকচার

সামনে বাংলাদেশ প্রিমিয়ার লিগ এর খেলা, ব্যাংক এ টিকেট পাওয়া যাচ্ছে। তুমি সকাল সকাল ব্যাংক এর সামনে গেলে, গিয়ে দেখলে তোমাকে কাউন্টার এর সামনে দাড়াতে হবে। এখন নিয়ম হচ্ছে, কাউন্টার খালি থাকলে তুমি সবার প্রথমে দাঁড়াবে, আর তা না হলে , যারা দাড়িয়ে আছে তাদের একদম পিছনে দাড়াতে হবে। আর কাউন্টার থেকে প্রথমে যে আশবে , তাকে প্রথমে টিকেট দেয়া হবে। যে শেষে আশবে সে সবার শেষে টিকেট পাবে। হুম , আমাদের দৈনন্দিন জীবনে যেভাবে কোন সার্ভিস নেয়ার জন্য লাইনে দাঁড়াই , ব্যাপার টা আসলে তাই। এই লাইনে দাঁড়ানোর ব্যাপার টাই কিউ ডাটা স্ট্রাকচার প্রকাশ করে।

কিউ ডাটা স্ট্রাকচার এর ধর্ম

১। নতুন কোন ডাটা আশলে , পুরাতন ডাটা থাকলে তাদের সবার পিছনে থাকবে।

২। কোন ডাটা কে নিতে হলে, সবার প্রথমে যে ডাটা টি আসছিল তাকেই প্রথমে নিতে হবে, একে বলে First In First Out [FIFO] ।

কিউ এর অপারেশানঃ

১। Push: নতুন কোন ডাটা আনলে সবার শেষে রাখতে হবে।

২। Pop: কোন ডাটা নিতে হলে , সবার প্রথমে যে থাকবে তাকে নিতে হবে।

Human queue

Queue

কিউ এর সিমুলেশন

১। Push(1): ১ কিউ তে ঢুকাতে হবে।

কিউঃ ১

২। Push(2): ২ কিউ তে ঢুকাতে হবে

কিউঃ ১ ২

৩। Push(3): ৩ কিউ তে ঢুকাতে হবে

কিউঃ ১ ২ ৩

৪। Pop(): সবার আগে যে আছে, তাকে বের করে ফেলতে হবে , এক্ষেত্রে ১ বের হবে

কিউঃ ২ ৩

৫। pop(): এবার ও সবার আগে যে আছে, তাকে বের করতে হবে। এক্ষেত্রে ২ বের হবে।

কিউঃ ৩

৬। Push(4): ৪ কিউ তে ঢুকাতে হবে।

কিউঃ ৩ ৪

৭। Pop(): নিজে কর

৮। Push(6): নিজে কর।

অ্যালগোরিদম এনালাইসিস

Push আর Pop , O(1) এ করা যায়।

কিউ এর ব্যাবহার

Breadth First Search (Graph Algorithm) এ কিউ ব্যবহার করতে হয়। Operating System এ কিউ একটি প্রয়োজনীয় ডাটা স্ট্রাকচার

বাইসেকশন মেথড বেসিক টিউটোরিয়াল

বাইসেকশন মেথড

আচ্ছা তোমাকে যদি বলা হয় একটা কম্পিউটার প্রোগ্রাম লিখ, যেটা যেকোনো একটি সংখ্যা x  (x>=0)এর বর্গমূল বের করবে , যেটা কে ইংরেজী তে বলে square root. যারা প্রোগ্রামিং ল্যাঙ্গুয়েজ জানে, তাদের কাছে ব্যাপার টা সোজা। কারন প্রায় সব প্রোগ্রামিং ল্যাঙ্গুয়েজ এই sqrt() নামে ফাংশন আছে , যা সহজেই বর্গমূল বের করে দিবে। কিন্তু এখন যদি বলা হয় যে, cubic root/ ³√x অথবা 4√x  বের করতে হবে, তখন কি করব? হুম… চিন্তার ব্যাপার। কারন এই রকম কোন built in ফাংশন সাধারন প্রোগ্রামিং ল্যাঙ্গুয়েজ এ নাই! তাইলে উপায় ??

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

২ ৪ ৫ ১১ ১৫ ২০

এখন তোমাকে বলা হল যে, এই সংখ্যা গুলোর মধ্যে ৪ আছে কিনা বলতে হবে। এই সমস্যা সমাধান এর দুইটা উপায়ে আছে,

১। যতোগুলা সংখ্যা দেয়া আছে, সবগুলা একটা একটা করে দেখা যে সংখ্যা টি ৪ কিনা।

২। বাইনারী সার্চ করা

প্রথম উপায়ে টা আসলে সবসময়েই কাজ করে, কিন্তু আমাকে যদি ১০০০০০০ টা সংখ্যা দেয়া হয়, তাহলে এই পদ্ধতি টা অনেক ধীর গতির হবে। সবচেয়ে খারাপ ক্ষেত্রে আমাকে পুরো ১০০০০০০ টা সংখ্যাই দেখতে হবে। Big Oh notation এ যদি ব্যাপার টাকে বলা হয়, তাহলে order হবে O(N) [যেখানে N হচ্ছে কতগুলো সংখ্যা দেয়া হল]।

এইতো গেল প্রথম উপায়।

এইবার আসি, দ্বিতীয় উপায়ে…

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

২ ৪ ৫ ১১ ১৫ ২০

এখন আমাকে ৪ খুজতে হবে। আমাকে ৬ টা সংখ্যা দেয়া হয়েছে। এখন প্রথম মধ্যমা টা নির্ধারণ করি। মধ্যমা ১= (১+৬)/২=৩.৫=৩ [স্বাভাবিক সংখ্যায়ে প্রকাশ করা হোল] , প্রথম মধ্যমা টা হচ্ছে ৩য় সংখ্যা টি অর্থাৎ ৫। এখন আমরা চাচ্ছি ৪, পেলাম ৫। হোল না । তাহলে আমাকে আবার সার্চ করতে হবে। কিনতু এখন একটা ব্যাপার দেখ, ৫ > ৪। তাহলে ৫ এর পরে যত সংখ্যা আছে  সবই তাহলে ৪ এর থেকে বড় , কেননা সংখ্যা গুলো ছোট থেকে বড় এভাবে সাজানো। তাহলে আমরা একটা কাজ করতে পারি না! ৫ এর পর যারা আছে তাদের কে আমরা হিশাব থেকে বাদ দিতে পারি না? হুম… অবশ্যই পারি। আমরা এখন দেখব ১ম থেকে ৩য় সংখ্যা এর মাঝে ৪ আছে কিনা। আবার মধ্যমা নির্ধারণ করি। মধ্যমা ২= (১+৩)/২=২। অর্থাৎ ২য় সংখ্যাটি। আর সেটা হচ্ছে ৪। আরি… আমরা ৪ পেয়ে গেছি।

মাত্র ২ ধাপে আমরা ফলাফল পেয়ে গেছি , তাই না? একারনে বাইনারি সার্চ এর অর্ডার O(logn)। উম… ১ম উপায়েও তো ২ ধাপেই ফলাফল পেতাম, তাইলে লাভ টা কি হল? বলছি… তোমাকে যদি ১১ খুজতে দেয়া হয়, তাহলে তুমি কয় ধাপে ফলাফল পাবা ? ৫ ধাপে। কিন্তু বাইনারি সার্চ দিয়ে ২ ধাপেই পেয়ে যাবা। কিভাবে? নিজেই চেষ্টা করে দেখ।

এতক্ষন খালি বাইনারি সার্চ নিয়া বয়ান আর গুনগান ছারলাম। কিন্তু আমার মেইন টপিক তো বাইসেকশন !! সেটার কি হবে? আসছি তাতে……

বাইসেকশন আসলে বাইনারি সার্চ এর ই এক ভাই। বাইনারি সার্চ sorted  sequence এ খুজে বের করে, আর বাইসেকশন সমীকরণ এর মধ্যে খুজে বের করে। তবে এর ও একটা শর্ত আছে, সেটা হচ্ছে সমীকরণ টিকে x এর সাপেক্ষে ঊর্ধ্বমুখী অথবা নিম্নমুখি হতে হবে। যেমনঃ y=x, y=x*x ইত্যাদি। এখানে x এর মান যত বারাচ্ছি y এর মান তত বারতেছে অথবা এর উল্টো টা । এরকম ক্ষেত্রে বাইসেকশন করা যাবে। কারন দেখ যে,  ব্যাপার টা কিন্তু ছোট থেকে বড় ভাবে সাজানো সংখ্যা এর মতোই, তাই না?

আমরা তো বাইনারি সার্চ কি তা জানি, এখন একি ভাবে বাইসেকশন এ কি হয় তা দেখব। ধরো আমরা বের করতে চাই ১৬ এর বর্গ মুল । বর্গমূল এর সাধারন সমীকরণ কি? y=root(x) . এখানে x=16 বসালে আমরা y এর মান ৪ পাবো। এই সমীকরণ টা কিন্তু ঊর্ধ্বমুখী [increasing] । তুমি যথাক্রমে, x=4, x=9, x=16 বসাও । দেখবে y এর মান বেড়ে যাচ্ছে।

যাই হোক, এখন আমরা  এই সমীকরণ টাকে এভাবে লিখতে পারি

y=x*x

কিভাবে, আমি যদি x=4 বসাই তাহলে কি পাচ্ছি y=16. তাহলে ব্যাপার টা একি দাঁড়াচ্ছে। শুধু চলক গুলো [variable] পরিবর্তন করলাম এই যা।

এখন আমরা বাইসেকশন করার জন্য লিমিট ঠিক করব। আগে বাইনারি সার্চ করার জন্য আমাদের লিমিট ছিল ১ থেকে যতোটি সংখ্যা দেয়া হয়েছে। এবার লিমিট হচ্ছে ০ থেকে আমাদের কে যতো সংখ্যা এর বর্গমূল বের করতে হবে।

তো শুরু করা যাক, আগের মত করে মধ্যমা বের করি প্রথমে,

মধ্যমা ১= (০+১৬)/২=৮। এখন ৮ টাকে আমাদের সমীকরণ টাতে বসাই, y=64 পাই যা ১৬ থেকে অনেক বড়। তাহলে আমাদের লিমিট আরেকটু কমাইতে হবে। নতুন লিমিট ০ থেকে ৮। নতুন মধ্যমা বের করি, মধ্যমা ২= (০+৮)/২=৪ ।  সমীকরণ টাতে ৪ বসাই, কি পাচ্ছি ? y=16 তাই না ? যা আমরা যেই সংখ্যা এর বর্গমূল চেয়েছিলাম সেটাই। তাহলে ১৬ এর বর্গমূল ৪। কাজ শেষ। সহজ জিনিশ তাই না ? এখন  বদলে তুমি  যদি x*x*x , x*x*x*x*x বসাও তাহলে কিন্তু তুমি  ও বের করে ফেলতে পারবে। ACM Programming Contest, Programming/ Algorithmic Problem solving এ বাইনারি সার্চ আর বাইসেকশন অনেক কাজে লাগে। পরে সেটা নিয়ে আলোচনা করব আরেক দিন [যদি আপনাদের এই লেখা ভালো লাগে 😉 ]। এবার বাইনারি সার্চ এবং বাইসেকশন এর c++ code দেখবো। নিচের লিঙ্ক গুলোতে ক্লিক করো।

বাইনারি সার্চ : http://ideone.com/iza80 , http://pastie.org/8427581

বাইসেকশন: http://ideone.com/oQEap , http://pastie.org/8427578

প্রব্লেমঃ UVA 10341 (http://uva.onlinejudge.org/external/103/10341.html)

[ নোট : বাইসেকশন কোড এ দশমিক সংখ্যা নিয়ে কাজ করার জন্য কিছু কাজ করা হয়েছে, না বুঝে থাকলে অবশ্যই জিজ্ঞাশা করতে হবে J ]

[ নোট : যদি কোন কিছু বুঝতে সমস্যা হয় তবে, মন্তব্য এর স্থানে জিজ্ঞাসা করুন, অথবা আমাকে মেইল করুনঃ faiyaz26 [at] gmail [dot] com এ ]