Succinct data structure
কম্পিউটার বিজ্ঞানে, একটি সংক্ষিপ্ত তথ্য কাঠামো হল একটি তথ্য কাঠামো যা তথ্য-তাত্ত্বিক নিম্ন সীমার "কাছাকাছি" পরিমাণ স্থান ব্যবহার করে, তবে (অন্যান্য সংকুচিত উপস্থাপনাগুলির বিপরীতে) এখনও দক্ষ অনুসন্ধান ক্রিয়াকলাপের অনুমতি দেয়। ধারণাটি মূলত জ্যাকবসন দ্বারা বিট ভেক্টর, (লেবেলবিহীন) গাছ এবং প্ল্যানার গ্রাফগুলি এনকোড করার জন্য চালু করা হয়েছিল। সাধারণ ক্ষতিহীন ডেটা কম্প্রেশন অ্যালগরিদমের বিপরীতে, সংক্ষিপ্ত ডেটা স্ট্রাকচারগুলি প্রথমে ডিকম্প্রেস না করে তাদের জায়গায় ব্যবহার করার ক্ষমতা বজায় রাখে। একটি সম্পর্কিত ধারণা হল একটি সংকুচিত তথ্য কাঠামো, যেখানে সংরক্ষিত বা এনকোড করা তথ্যের আকার একইভাবে তথ্যের নির্দিষ্ট বিষয়বস্তুর উপর নির্ভর করে। ধরুন এটি কিছু তথ্য সংরক্ষণের জন্য প্রয়োজনীয় বিটের তথ্য-তাত্ত্বিক সর্বোত্তম সংখ্যা। এই তথ্যের উপস্থাপনাকে বলা হয়ঃ যদি এটি কিছুটা জায়গা নেয় তবে অন্তর্নিহিত, যদি এটি কিছুটা জায়গা নেয় তবে সংক্ষিপ্ত এবং যদি এটি কিছুটা জায়গা নেয় তবে সংক্ষিপ্ত। উদাহরণস্বরূপ, একটি ডেটা স্ট্রাকচার যা বিট অফ স্টোরেজ ব্যবহার করে তা কম্প্যাক্ট, বিট সংক্ষিপ্ত, বিটও সংক্ষিপ্ত এবং বিট অন্তর্নিহিত। এইভাবে অন্তর্নিহিত কাঠামোগুলি সাধারণত ইনপুট ডেটার কিছু বিন্যাস ব্যবহার করে তথ্য সংরক্ষণের জন্য হ্রাস করা হয়; এর সবচেয়ে সুপরিচিত উদাহরণ হ 'ল স্তূপ। সুনির্দিষ্ট সূচকযোগ্য অভিধান, যাকে র্যাঙ্ক/নির্বাচিত অভিধানও বলা হয়, বাইনারি ট্রি,-এরি ট্রি এবং মাল্টিসেট, পাশাপাশি প্রত্যয় ট্রি এবং অ্যারে সহ বেশ কয়েকটি সংক্ষিপ্ত উপস্থাপনা কৌশলের ভিত্তি গঠন করে। মূল সমস্যা হল একটি মহাবিশ্বের একটি উপসেট সংরক্ষণ করা, যা সাধারণত একটি বিট অ্যারে হিসাবে উপস্থাপিত হয় যেখানে একটি সূচকযোগ্য অভিধান অভিধানের সাধারণ পদ্ধতিগুলিকে (প্রশ্ন, এবং গতিশীল ক্ষেত্রে সন্নিবেশ/মুছে ফেলা) পাশাপাশি নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থন করেঃ অন্য কথায়, অবস্থানের সমান উপাদানের সংখ্যা প্রদান করে যখন-তম ঘটনার অবস্থান প্রদান করে। একটি সহজ উপস্থাপনা রয়েছে যা স্টোরেজ স্পেসের বিট (মূল বিট অ্যারে এবং একটি সহায়ক কাঠামো) ব্যবহার করে এবং স্থির সময়ে র্যাঙ্ক এবং নির্বাচনকে সমর্থন করে। এটি পরিসীমা-ন্যূনতম প্রশ্নের জন্য অনুরূপ একটি ধারণা ব্যবহার করে; সীমিত আকারের একটি উপ-সমস্যায় থামার আগে ক্রমাগত সংখ্যক পুনরাবৃত্তি হয়। বিট অ্যারেটি বড় আকারের বিট এবং ছোট আকারের বিটগুলিতে বিভক্ত করা হয়। প্রতিটি বড় ব্লকের জন্য, এর প্রথম বিটের র্যাঙ্ক একটি পৃথক টেবিলে সংরক্ষণ করা হয়; এই ধরনের প্রতিটি এন্ট্রি মোট বিটের জন্য বিট নেয়। একটি বড় ব্লকের মধ্যে, অন্য একটি ডিরেক্টরি প্রতিটি ছোট ব্লকের র্যাঙ্ক সংরক্ষণ করে। এখানে পার্থক্য হল যে এটির প্রতিটি এন্ট্রির জন্য শুধুমাত্র বিটের প্রয়োজন, যেহেতু শুধুমাত্র ধারণকারী বড় ব্লকের প্রথম বিটের র্যাঙ্কের পার্থক্যগুলি সংরক্ষণ করা প্রয়োজন। সুতরাং, এই টেবিলটি মোট বিট নেয়। তারপরে একটি লুকআপ টেবিল ব্যবহার করা যেতে পারে যা প্রতিটি সম্ভাব্য র্যাঙ্ক প্রশ্নের উত্তরকে দৈর্ঘ্যের একটি বিট স্ট্রিং-এ সংরক্ষণ করে; এর জন্য কিছুটা সঞ্চয় স্থান প্রয়োজন। সুতরাং, যেহেতু এই সহায়ক টেবিলগুলির প্রতিটি স্থান নেয়, তাই এই তথ্য কাঠামো সময় এবং জায়গার অংশে র্যাঙ্কের প্রশ্নগুলিকে সমর্থন করে। স্থির সময়ের মধ্যে একটি প্রশ্নের উত্তর দেওয়ার জন্য, একটি ধ্রুবক সময় অ্যালগরিদম গণনা করেঃ বাস্তবে, সন্ধান টেবিলটি বিটওয়াইজ অপারেশন এবং ছোট টেবিল দ্বারা প্রতিস্থাপিত করা যেতে পারে যা ছোট ব্লকে সেট করা বিটের সংখ্যা খুঁজে পেতে ব্যবহার করা যেতে পারে। এটি প্রায়শই উপকারী, যেহেতু সংক্ষিপ্ত ডেটা স্ট্রাকচারগুলি বড় ডেটা সেটগুলিতে তাদের ব্যবহার খুঁজে পায়, এই ক্ষেত্রে ক্যাশে মিসগুলি অনেক বেশি ঘন ঘন হয়ে যায় এবং কাছাকাছি সিপিইউ ক্যাশে থেকে লুকআপ টেবিলটি উচ্ছেদ হওয়ার সম্ভাবনা বেশি হয়ে যায়। নির্বাচিত প্রশ্নগুলি র্যাঙ্কের জন্য ব্যবহৃত একই সহায়ক কাঠামোর উপর বাইনারি অনুসন্ধান করে সহজেই সমর্থন করা যেতে পারে; তবে, সবচেয়ে খারাপ ক্ষেত্রে এটি সময় নেয়। অতিরিক্ত সঞ্চয়ের বিট ব্যবহার করে একটি আরও জটিল কাঠামো স্থির সময়ে নির্বাচনকে সমর্থন করতে ব্যবহার করা যেতে পারে। বাস্তবে, এই সমাধানগুলির মধ্যে অনেকগুলির স্বরলিপিতে লুকানো ধ্রুবক রয়েছে যা কোনও অ্যাসিম্পটোটিক সুবিধা স্পষ্ট হওয়ার আগে আধিপত্য বিস্তার করে; ব্রডওয়ার্ড অপারেশন এবং শব্দ-সংযুক্ত ব্লক ব্যবহার করে বাস্তবায়নগুলি প্রায়শই অনুশীলনে আরও ভাল কাজ করে। এনট্রপি-কম্প্রেসড সলিউশন স্পেস পদ্ধতির উন্নতি করা যেতে পারে এই বলে যে এর স্বতন্ত্র-সাবসেট রয়েছে (বা ঠিক 1 এর সাথে দৈর্ঘ্যের বাইনারি স্ট্রিং), এবং এইভাবে এটি সংরক্ষণের জন্য প্রয়োজনীয় বিটের সংখ্যার উপর একটি তথ্য তাত্ত্বিক নিম্ন আবদ্ধ। একটি সংক্ষিপ্ত (স্থির) অভিধান রয়েছে যা স্থান ব্যবহার করে এই সীমা অর্জন করে। এই কাঠামোটি র্যাঙ্ক সমর্থন করতে এবং প্রশ্ন নির্বাচন করতে প্রসারিত করা যেতে পারে এবং স্থান নেয়। এই কাঠামোর সঠিক র্যাঙ্কের প্রশ্নগুলি সেটে থাকা উপাদানগুলির মধ্যে সীমাবদ্ধ, যা ন্যূনতম নিখুঁত হ্যাশিং ফাংশনগুলি কীভাবে কাজ করে তার অনুরূপ। অভিধানের সঞ্চয়স্থানকে সময়সাপেক্ষ প্রশ্নের মধ্যে কমিয়ে দিয়ে এই সীমাটিকে একটি স্থান/সময়ের বিনিময়ে হ্রাস করা যেতে পারে। একটি সূচকযোগ্য অভিধান তৈরি করাও সম্ভব যা র্যাঙ্ককে সমর্থন করে (তবে নির্বাচন করে না) যা বিটের চেয়ে কম ব্যবহার করে। এই ধরনের অভিধানকে বলা হয় মনোটোন মিনিমাল পারফেক্ট হ্যাশ ফাংশন, এবং অল্প সংখ্যক বিট ব্যবহার করে প্রয়োগ করা যেতে পারে। একটি সংক্ষিপ্ত হ্যাশ টেবিল, যা একটি সংক্ষিপ্ত ক্রমহীন অভিধান নামেও পরিচিত, একটি ডেটা স্ট্রাকচার যা স্পেস বিট ব্যবহার করে একটি মহাবিশ্বের কীগুলি সঞ্চয় করে এবং ধ্রুবক প্রত্যাশিত সময়ে সদস্যতার প্রশ্নগুলিকে সমর্থন করে। যদি একটি সংক্ষিপ্ত হ্যাশ টেবিল স্থির প্রত্যাশিত সময়ে সন্নিবেশ এবং মুছে ফেলাকেও সমর্থন করে, তবে এটিকে গতিশীল হিসাবে উল্লেখ করা হয় এবং অন্যথায় এটিকে স্থির হিসাবে উল্লেখ করা হয়। প্রথম গতিশীল সংক্ষিপ্ত হ্যাশ টেবিলটি 2003 সালে রমন এবং রাওয়ের কারণে হয়েছিল। যেখানে, তাদের সমাধান স্পেস বিট ব্যবহার করে। পরবর্তীকালে, এটি দেখানো হয়েছিল যে এই স্থান সীমাটি যে কোনও ধ্রুবক সংখ্যক লগারিদমের জন্য বিটগুলিতে উন্নত করা যেতে পারে। পরের সমাধানটি উচ্চ সম্ভাবনার সাথে সবচেয়ে খারাপ-ক্ষেত্রে ধ্রুবক সময়ে সমস্ত ক্রিয়াকলাপকে সমর্থন করে। প্রথম স্থির সংক্ষিপ্ত হ্যাশ টেবিল 1999 সালে পাঘের কারণে ছিল। যেখানে, তাদের সমাধান স্পেস বিট ব্যবহার করে এবং সবচেয়ে খারাপ-কেস ধ্রুবক-সময়ের প্রশ্নগুলিকে সমর্থন করে। এই সীমাটি পরবর্তীকালে বিট এবং তারপর বিটগুলিতে উন্নত করা হয়েছিল। যেখানে প্রথম দুটি সমাধান সবচেয়ে খারাপ-ক্ষেত্রে ধ্রুবক-সময়ের প্রশ্নগুলিকে সমর্থন করে, শেষটি ধ্রুবক প্রত্যাশিত-সময়ের প্রশ্নগুলিকে সমর্থন করে। চূড়ান্ত সমাধানের জন্য আকারের একটি সন্ধান টেবিলের অ্যাক্সেসও প্রয়োজন, তবে এই সন্ধান টেবিলটি সংরক্ষণ করা উপাদানগুলির সেট থেকে স্বাধীন। অন্যান্য উদাহরণ স্বেচ্ছাচারী দৈর্ঘ্যের (প্যাসকেল স্ট্রিং) একটি স্ট্রিং জেড + লগ (জেড) স্থান নেয় এবং এইভাবে সংক্ষিপ্ত হয়। যদি সর্বাধিক দৈর্ঘ্য থাকে-যা বাস্তবে প্রযোজ্য, যেহেতু 232 = 4 গিগাবাইট ডেটা একটি খুব দীর্ঘ স্ট্রিং, এবং 264 = 16 ইআইবি ডেটা অনুশীলনে যে কোনও স্ট্রিংয়ের চেয়ে বড়-তবে দৈর্ঘ্যের একটি স্ট্রিংও অন্তর্নিহিত, জেড + কে স্থান গ্রহণ করে, যেখানে কে হল সর্বাধিক দৈর্ঘ্যের প্রতিনিধিত্ব করার জন্য ডেটার সংখ্যা (যেমন, 64 বিট)। যখন পরিবর্তনশীল-দৈর্ঘ্যের আইটেমগুলির একটি ক্রম (যেমন স্ট্রিং) এনকোড করার প্রয়োজন হয়, তখন বিভিন্ন সম্ভাবনা থাকে। একটি সরাসরি পদ্ধতি হল প্রতিটি রেকর্ডে একটি দৈর্ঘ্য এবং একটি আইটেম সংরক্ষণ করা-এগুলি তারপর একের পর এক স্থাপন করা যেতে পারে। এটি পরবর্তী কার্যকারিতার অনুমতি দেয়, কিন্তু kth আইটেমটি খুঁজে পায় না। একটি বিকল্প হল একটি ডিলিমিটার (যেমন, নাল-টার্মিনেটেড স্ট্রিং) দিয়ে আইটেমগুলিকে সাজানো। এটি দৈর্ঘ্যের পরিবর্তে একটি ডিলিমিটার ব্যবহার করে এবং এটি যথেষ্ট ধীর, কারণ সম্পূর্ণ ক্রমটি ডিলিমিটারের জন্য স্ক্যান করা আবশ্যক। এই দুটিই স্থান-দক্ষ। একটি বিকল্প পদ্ধতি হল আউট-অফ-ব্যান্ড পৃথকীকরণঃ কোনও সীমানা ছাড়াই জিনিসগুলি একের পর এক স্থাপন করা যেতে পারে। আইটেম সীমানা তারপর দৈর্ঘ্যের ক্রম হিসাবে সংরক্ষণ করা যেতে পারে, বা আরও ভাল, এই ক্রমের মধ্যে অফসেট। বিকল্পভাবে, একটি পৃথক বাইনারি স্ট্রিং যেখানে একটি আইটেম শুরু হয় সেখানে 1s নিয়ে গঠিত এবং অন্য সর্বত্র 0s এর সাথে এনকোড করা হয়। এই স্ট্রিংটি দেওয়া হলে, ফাংশনটি দ্রুত নির্ধারণ করতে পারে যে প্রতিটি আইটেম কোথায় শুরু হয়, তার সূচক দেওয়া। এটি সংক্ষিপ্ত কিন্তু সংক্ষিপ্ত নয়, কারণ এটি 2Z স্থান নেয়, যা হল O (Z)। আরেকটি উদাহরণ হল একটি বাইনারি ট্রি-র উপস্থাপনাঃ যে কোনও নোডে বিভিন্ন ক্রিয়াকলাপকে সমর্থন করার সময় নোডের উপর একটি নির্বিচারে বাইনারি ট্রি বিটগুলিতে প্রতিনিধিত্ব করা যেতে পারে, যার মধ্যে রয়েছে তার প্যারেন্ট, তার বাম এবং ডান চাইল্ড খুঁজে বের করা এবং তার সাবট্রির আকার ফিরিয়ে দেওয়া, প্রতিটি স্থির সময়ে। নোডের উপর বিভিন্ন বাইনারি গাছের সংখ্যা হল। বড় ক্ষেত্রে, এটি প্রায়; সুতরাং এটি এনকোড করার জন্য আমাদের কমপক্ষে প্রায় বিট প্রয়োজন। একটি সংক্ষিপ্ত বাইনারি ট্রি তাই প্রতি নোডে শুধুমাত্র বিট দখল করবে। আরও দেখুন মিনিমাল পারফেক্ট হ্যাশ ফাংশন সুসিঙ্ক নন-ইন্টারেক্টিভ আর্গুমেন্টস অফ নলেজ রেফারেন্স