ট্রাই ট্রি ( 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 এ ]

বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট [ থিওরি ]

আগে জেনে আসা উচিত:    বেসিক গ্রাফ থিওরি , গ্রাফ কানেক্টিভিটি , DFS

এই পোস্ট এ আমরা থিওরি জানবো , পরে আরেকটি পোস্ট এ আমরা বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট বের করার অ্যালগোরিদম নিয়ে আলোচনা করব।

ধরো, তোমার একজন বন্ধুর নাম সাফওয়াত। তুমি এখন তার বাসায়ে যাবে, এখন তুমি একটা ম্যাপ বের করলে যেখানে তুমি থাকো 0 নং নোডে , এবং তোমার বন্ধু থাকে ৬ নং নোডে। নিচের গ্রাফ টি দেখঃ

bcc1

এখন খেয়াল কর , তুমি ০ থেকে ৫ নং নোডে ২ ধরনের রাস্তা ব্যবহার করতে পার। সেগুলো হচ্ছে-

১। ০ – > ১ – >৪ – > ৫

২। ০ -> ২ -> ৩ -> ৫

দুটো পথের কোন টাই কিন্তু কেউ কারো উপর দিয়ে যাচ্ছে না, তাই না ? কিন্তু যদি আমি ৬ নং নোডে যেতে চাই, তাহলেও দুটি পথ আছে,

১। ০ -> ১ -> ৪-> ৫-> ৬

২। ০ -> ২ -> ৩ -> ৫ ->৬

এখন দেখ, আমাকে ৫->৬ এই খানে দুটি পথ এক হয়ে গেছে। এক হয়ে গেছে তো কি হয়েছে ? একটা সমস্যা হয়ে যাচ্ছে, ধরো তুমি বন্ধুর বাসায়ে যাচ্ছ , ১ নং পথ ধরে, হঠাত ভুমিকম্প হল, আর ৪ থেকে ৫ এ যাওয়ার রাস্তা গেল ভেঙ্গে , তুমি গিয়ে দেখলে ৪ নং নোড থেকে ৫ নং  এ যাওয়া যাচ্ছে না, কিন্তু তোমাকে তো ৫ এ যেতেই হবে , নাইলে ৬ নং নোড এ যাওয়া যাবে না !

bcc9

কিন্তু তোমার কাছে তো ম্যাপ আছে, এবং তুমি দেখলে যে আরেক টা রাস্তা আছে , যেই টা ব্যবহার করে ৫ নং নোড এ যাওয়া যায়, তো তুমি ঘুরে আবার তোমার বাসায় এসে, ২য় পথ ধরে তুমি তোমার বন্ধুর বাসায় পৌছাইলা।

ব্রিজঃ

সাধারণ মানুষ হইলে , তুমি বন্ধুর বাসায় গিয়ে আড্ডা মেরে সুন্দর মত নিজের বাসায়ে চলে যাইতা! সমস্যা হইল তুমি একজন প্রব্লেম সল্ভার , তোমার মাথায়ে সবসময় চিন্তা আসে যে যদি এইটা হইত তাহলে কি হইত, অইটা কেন হইত না…..

একি কারনে তোমার মাথায়ে চিন্তা আসল যে যদি ভুমিকম্পে ৫->৬ এর রাস্তা টা নস্ট হয়ে যাইত, তাহলে কি করতা ? তাহলে কি আর কোন পথ ছিল বন্ধুর বাসায় যাওয়ার ? না, আর কোন পথ থাকত না । 😦

আমি যদি গ্রাফ এর ৫ থেকে ৬ নং নোড এ যাওয়ার রাস্তা  টাকে বাদ দেই, তাহলে গ্রাফ টা দাড়ায় এরকম – 

bcc2

bcc8

তুমি এখন নিজেকেই প্রশ্ন করলা যে, যদি ভুমিকম্পে শুধুমাত্র একটি রাস্তা নষ্ট হয়, তারপরেও তোমার বাসা থেকে কোন কোন নোড এ যাওয়া যাবে এবং রাস্তা যেটাই নষ্ট হোক না কেন তুমি সবসময়ে অই নোড গুলা তে যেতে পারবে ? যেমন ধরো, যখন ৪ থেকে ৫ এর রাস্তা টা নষ্ট হইল , তখন কিন্তু তুমি ৬ নং নোড এ যেতে পারসো। কিন্তু যদি ৫ থেকে ৬ এর রাস্তা নষ্ট হইত , তাইলে কিন্তু ৬ নং নোড এ যেতে পারতা না। তারমানে যেকোনো একটি রাস্তা নষ্ট হলেও, সবসময়  তোমার বাসা থেকে  ৬ নং নোড এ যেতে পারবে না। তাহলে কোন কোন নোড এ যেতে পারবা ? গ্রাফ টার দিকে ভালো করে খেয়াল কর, নিজেই বের করতে পারো কিনা দেখ।

উত্তরঃ ১, ২, ৩, ৪, ৫ এই নোড গুলা তে যাইতে পারবা।

তাহলে দেখ যদি আমরা ৫ থেকে ৬ এ যাওয়ার রাস্তা গ্রাফ থেকে সরায়ে দেই, তাহলে গ্রাফ থিউরি এর ভাষায়ে গ্রাফ টা কিন্তু কানেক্টেড না। যেই রাস্তাকে [ edge ] বাদ দিলে পুরো গ্রাফ টি ডিস্কানেক্টেড হয়ে যাবে মানে সব নোড থেকে সব নোডে যাওয়া যাবে না,  অই রাস্তা বা edge কে বলা হয় ব্রিজ [Bridge] , আমাদের পদ্মা ব্রিজ এর কথা চিন্তা করতে পার। 🙂

ফরমাল ভাষায় বললে, যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

আরটিকুলেশন পয়েন্টঃ

এতক্ষন ০, ১, ২ এইগুলাকে নোড বললাম, ধরো এই গুলা একেক টা শহর, এখন ধরো, ৩ নং শহরে কারফিউ জারি করা হইল, তার মানে তুমি কারফিউ এর সময় অই শহর দিয়ে যেতে পারবা না। তাহলে ধরা যায় যে, ৩ নং নোড টা গ্রাফেই নাই ।

bcc4

bcc5

তাহলে দেখ এর পরেও কিন্তু তুমি সব নোড থেকে সব নোড এ  যেতে পারছ তাই না ? মানে তারা এখনও কানেক্টেড।

কিন্তু যদি ৫ নং নোড / শহরে কারফিউ জারি করা থাকতো , তখন গ্রাফ টা কেমন হইত ?

bcc6

bcc7

এই খানে দেখ, সব নোড থেকে সব নোড এ যাওয়া যাচ্ছে না। তারমানে গ্রাফ টা ডিসকানেক্টেড হয়ে যাচ্ছে। এই রকম অবস্থায় অই কারফিউ জারি করা নোড টা কে বলা হয় আরটিকুলেশন পয়েন্ট [ Articulation Point ] ।

ফরমাল ভাষায় বললে, যদি কোন নোড কে গ্রাফ থেকে বাদ দেয়া হয় , এর ফলে যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই নোড টা কে বলা হবে আরটিকুলেশন পয়েন্ট।

এতক্ষন তো Articulation Point এবং Bridge নিয়া বললাম কিন্তু বাইকানেক্টেড কম্পোনেন্ট টা কি ? 

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

bcc11

নিচের দুইটা গ্রাফ এর পুরোটা কিন্তু বাইকানেক্টেড না , কেন ? কারন গ্রাফ গুলো তে আরটিকুলেশন পয়েন্ট আছে – 

bcc10

বরং তাদের সাব গ্রাফ গুলো একেকটা বাইকানেক্টেড কম্পোনেন্ট , যেমন –

bcc13

লাল রঙ এর নোড গুলো কিন্তু বামের নীল এবং সবুজ দুই রঙের বাইকানেক্টেড কম্পোনেন্ট এর ই অংশ, কিন্তু পুরো গ্রাফ টা বাইকানেক্টেড কম্পোনেন্ট না, কারন লাল রঙের নোড টা একটি আরটিকুলেশন পয়েন্ট।

সব সংজ্ঞা এক সাথে:

 ব্রিজ: যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

আরটিকুলেশন পয়েন্ট: যদি কোন নোড কে গ্রাফ থেকে বাদ দেয়া হয় , এর ফলে যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই নোড টা কে বলা হবে আরটিকুলেশন পয়েন্ট।

 বাইকানেক্টেড কম্পোনেন্ট: যদি একটি গ্রাফে কোন আরটিকুলেশন পয়েন্ট না থাকে, তাহলে অই গ্রাফ টি একটি বাইকানেক্টেড কম্পোনেন্ট।

নিচে কয়েকটি গ্রাফ দেয়া হবে উত্তর বের করে মিলাও, উত্তর মিললে বুঝা যাবে যে , হ্যাঁ তুমি BCC, Bridge, Articulation point কি বুঝেছ।

১। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

২। নিচের গ্রাফ টা কি বাইকানেক্টেড ? 

bcc6

৩। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

৪। নিচের গ্রাফে কোন গুলো আরটিকুলেশন পয়েন্ট এবং কোন কোন সাব গ্রাফ বাইকানেক্টেড কম্পোনেন্ট?

 

৫। নিচের গ্রাফ এ কয়টি ব্রিজ এবং আরটিকুলেশন পয়েন্ট আছে ?

 

উত্তরঃ

১। হ্যাঁ

২। হ্যাঁ

৩। না,

৪। A, H, G, J এরা হচ্ছে AP, আর বাইকানেক্টেড কম্পোনেন্ট গুলো হচ্ছে – 

{A, C, G, D, E, F}, {G, J, L, B।}, B, H, I, K

৫। ৩ টা Bridge, ২ টা AP.

আরও জানতে:

১। http://en.wikipedia.org/wiki/Biconnected_component

২। http://www.ics.uci.edu/~dan/class/161/notes/8/Bicomps.html

৩। http://www.scribd.com/doc/56802813/Bridge-Algorithm