সার্চ পদ্ধতি সমূহ

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

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

সাধারণ সার্চ টেকনিক সমূহ

এই সার্চ টেকনিকগুলো সম্পর্কে জানা ও বোঝার জন্য array, relational operator, logical operator এবং C প্রোগ্রাম কন্ট্রোল স্টেটমেন্ট সমূহ সম্পর্কে জ্ঞান থাকতে হবে।

n সংখ্যক তথ্য বিশিষ্ট একটি তালিকার কথা কল্পনা করি যেখানে প্রত্যেকটি তথ্যই একটি key হতে পারে। আমাদের লক্ষ্য হবে এই তালিকা থেকে যে কোন একটি নির্দিষ্ট key কে যতটা কম সম্ভব সময়ের মধ্যে খুজে বের করা। একটি তালিকা থেকে এভাবে খুঁজে বের করার জন্য আমাদের সতর্কতার সাথে লক্ষ্য করতে হবে যে, তালিকাটিতে ডেটা কিভাবে সাজানো রয়েছে, অর্থাৎ কোন ধরনের ডেটা স্ট্রাকচার ব্যবহার করা হয়েছে। প্রাথমিক ভাবে আমাদের সবার পরিচিত array ডেটা স্ট্রাকচারে তথ্য রাখা হয়েছে বলেই ধরে নিই। array তে কোন তথ্য দুইভাবে সাজানো থাকতে পারে। সুবিন্যস্ত  (sorted) এবং অবিন্যস্ত (unsorted)। আমরা প্রথমে এই দুই ক্ষেত্রে কিভাবে সার্চ করা হবে সেটা দেখবো। সাজানোর পদ্ধতি বা সর্টিং টেকনিক সম্পর্কে আলোচনার জন্য এইখানে দেখুন।

লিনিয়ার সার্চ ও বাইনারী সার্চ

১. লিনিয়ার সার্চ বা সিকোয়েন্সিয়াল সার্চ

এই সার্চ পদ্ধতি একেবারেই সরল ও সোজাসুজি পদ্ধতি। একটি array এর প্রথম ইন্ডেক্স থেকে সার্চ শুরু করবো এবং যতক্ষন পর্যন্ত key এর সাথে মিল পাওয়া না যাবে ততক্ষণ সার্চ চালিয়ে যাবো। এই ক্ষেত্রে সর্বোচ্চ শেষ ইন্ডেক্স পর্যন্ত সার্চ করার প্রয়োজন হতে পারে, যদি key টি শেষ ইন্ডেক্সে থাকে অথবা key টি আদৌ array তে না থেকে থাকে।

বর্ণনা থেকেই বোঝা যাচ্ছে যে বড় ডেটার ক্ষেত্রে এটি মন্থর গতির সার্চ। তবে সময় সাপেক্ষ হলেও অবিন্যস্ত  array এর ক্ষেত্রে এটিই একমাত্র সরাসরি সার্চ টেকনিক। এই বিষয়ে বিস্তারিত জানার জন্য এখানে দেখুন।

২. বাইনারি সার্চ

সুবিন্যস্ত array এর ক্ষেত্রে এই সার্চ টেকনিক ব্যবহার করা যায়। ধরা যাক একটি array এর সকল তথ্য ঊর্ধ্বক্রমে সাজানো আছে। অর্থাৎ প্রথম ইন্ডেক্সে সবচে ছোট আর শেষ ইন্ডেক্সে সবচে বড় মানের তথ্যটি আছে। এইখানে সার্চ শুরু করা হয় array এর মধ্য ইন্ডেক্স থেকে। যদি মধ্য ইন্ডেক্সের তথ্যের মান key এর চেয়ে কম হয় তাহলে সার্চ করা হয় array এর ডান পাশের অর্ধেকের মধ্য ইন্ডেক্সটি। আর যদি মান key এর চেয়ে বেশি হয় তাহলে সার্চ করা হয় array এর বাম পাশের অর্ধেকের মধ্য ইন্ডেক্সটি।

এভাবে প্রতিবারে array এর সার্চ এলাকা অর্ধেক হতে থাকে। তাই এটি লিনিয়ার সার্চ অপেক্ষা দ্রুতগতির। তবে এটি কেবলমাত্র সুবিন্যস্ত তথ্যের ক্ষেত্রে কাজ করে। অবিন্যস্ত তথ্যের উপর বাইনারি সার্চ চালানোর জন্য তাকে প্রথমে বিন্যস্ত করে বা সর্ট করে নেবার দরকার পরে। বিস্তারিত জানার জন্যে এখানে দেখুন।

কিছু উচ্চতর সার্চ টেকনিক

নিম্নবর্ণিত সার্চ টেকনিক দুটি array অপেক্ষা জটিল ও উচ্চতর ডেটা স্ট্রাকচারে সার্চিং এর জন্য ব্যবহার করা হয়। এইগুলো ব্যবহারের পূর্বে হ্যাশ টেবিল, ট্রি, কিউ ইত্যাদি ডেটা স্ট্রাকচার সম্পর্কে সুস্পষ্ট ধারনা গ্রহন আবশ্যক।

৩. হ্যাশ সার্চ

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

বিস্তারিত জানার জন্য এখানে দেখুন।

৪. বাইনারি ট্রি সার্চ

বাইনারি ট্রি সার্চও হ্যাশ সার্চের মতই তবে এটি সাধারণত তুলনামূলক ভাবে মন্থর, বিশেষ করে যদি ট্রি এর সজ্জা ঠিকমতো ব্যালেন্স করা না থাকে।

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

বিস্তারিত জানার জন্য এখানে দেখুন।