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

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

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

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

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

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

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

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

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

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

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

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

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

ব্রিজঃ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

উত্তরঃ

১। হ্যাঁ

২। হ্যাঁ

৩। না,

৪। 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

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

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

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

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

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

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

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

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

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 এ কিউ একটি প্রয়োজনীয় ডাটা স্ট্রাকচার

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

ডাটা স্ট্রাকচার কি জিনিশ ?

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

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

ডাটা স্ট্রাকচার অনেক অ্যালগোরিদম কে সুন্দর ভাবে এবং আরও দক্ষ ভাবে প্রকাশ করতে সাহায্য করে।

স্ট্যাক

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

• নতুন কোন ডাটা রাখতে হলে, সবার উপরে রাখতে হবে। তাতে কষ্ট কম হবে।
• কোন ডাটা কে নিতে চাইলে, তার উপরের সব গুলো ডাটাকে কে সরাতে হবে। মানে যাকে সবার শেষে রাখা হয়েছে, তাকে সবার আগে বের করে নিতে হবে । এটাকে বলে LIFO [Last in First Out ].
• খুব সহজেই বলতে পারবো যে কোন ডাটা টি সবার শেষে নেয়া হয়েছে।

এই ভাবে আমরা যদি ডাটা উপস্থাপন করি , তাহলে তাকে বলে স্ট্যাক।

এখন স্ট্যাক এর দুইটি অপারেশন বা প্রক্রিয়া আছে-

১। Push

২। Pop

Push হচ্ছে আমরা যে নতুন ডাটা পেলে তা একদম উপরে রাখছি, এটাই ।

আবার Pop হচ্ছে স্ট্যাক থেকে ডাটা নিতে হলে সবার উপর থেকে নিচ্ছি এই প্রক্রিয়া টিই।

তাহলে এবার আমরা হাতে হাতে করে দেখি স্ট্যাক এ কোন অপারেশন এর জন্য কি হয়।

১। Push(1) : প্রথমে স্ট্যাক টি খালি ছিল, তাহলে স্ট্যাক এ ১ ঢুকাই।

স্ট্যাক : 1

২। Pop(): স্ট্যাক এর সব চেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে । আর কোন সংখ্যা স্ট্যাক এ নাই বলে স্ট্যাক টি আবার খালি হয়ে যাবে

স্ট্যাক:

৩। Push(2): স্ট্যাক টি এখন খালি বিধায়ে ২ স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2

৪। Push(3): 3 স্ট্যাক এ ঢুকাই। তাহলে স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৫। Push(4): 4 স্ট্যাক এ ঢুকাই। স্ট্যাক টির বর্তমান অবস্থা –

স্ট্যাক: 2 3 4

৬। Pop(): স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 4. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৭। Pop(): আবারো স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 3. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2

৮। Push(5): 5 স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2 5

৯। Push(1): এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5 1

১০। Pop():এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5

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

প্রতি Push বা Pop করতে O(1) সময়ে লাগে

স্ট্যাক এর ব্যবহার

স্ট্যাক অনেক দরকারি এবং খুবি সোজা একটি ডাটা স্ট্রাকচার। এটি ব্যবহার করে Depth First Search (Graph Algorithm) কাজ করে। স্ট্যাক দিয়ে expression evaluation(postfix-infix) করা যায় । এছাড়া Compiler বানাতে স্ট্যাক অত্যাবশ্যক একটি ডাটা স্ট্রাকচার।

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

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

আচ্ছা তোমাকে যদি বলা হয় একটা কম্পিউটার প্রোগ্রাম লিখ, যেটা যেকোনো একটি সংখ্যা x  (x>=0)এর বর্গমূল বের করবে , যেটা কে ইংরেজী তে বলে square root. যারা প্রোগ্রামিং ল্যাঙ্গুয়েজ জানে, তাদের কাছে ব্যাপার টা সোজা। কারন প্রায় সব প্রোগ্রামিং ল্যাঙ্গুয়েজ এই sqrt() নামে ফাংশন আছে , যা সহজেই বর্গমূল বের করে দিবে। কিন্তু এখন যদি বলা হয় যে, cubic root/ ³√x অথবা ⁴√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 এ ]