Package-merge algorithm
প্যাকেজ-মার্জ অ্যালগরিদম হল একটি ও (এনএল)-টাইম অ্যালগরিদম যা একটি প্রদত্ত দৈর্ঘ্য-সীমিত হাফম্যান কোড খুঁজে বের করার জন্য একটি প্রদত্ত বর্ণমালার আকার এন-এর উপর, যেখানে কোনও কোড শব্দ এল-এর চেয়ে দীর্ঘ নয়। এটি একটি লোভী অ্যালগরিদম, এবং হাফম্যানের মূল অ্যালগরিদমের একটি সাধারণীকরণ। প্যাকেজ-মার্জ কোড নির্মাণের সমস্যাকে বাইনারি মুদ্রা সংগ্রাহকের সমস্যায় হ্রাস করে কাজ করে। মুদ্রা সংগ্রাহকের সমস্যা ধরুন একজন মুদ্রা সংগ্রাহকের কাছে বিভিন্ন মূল্যমানের বেশ কয়েকটি মুদ্রা রয়েছে, যার প্রত্যেকটির মুদ্রাতাত্ত্বিক মান তার মূল্যমানের সাথে সম্পর্কিত নয়। মুদ্রা সংগ্রাহক অর্থ শেষ করে ফেলেছে এবং তার মুদ্রা সংগ্রহের কিছু অংশ ব্যবহার করে এন মূল্যের কিছু কিনতে চায়। সে তার ন্যূনতম মুদ্রাতাত্ত্বিক মূল্যের সংগ্রহ থেকে মুদ্রার একটি উপসেট নির্বাচন করতে চায় যার মূল্যমান মোট এন। এই সমস্যার বাইনারি সংস্করণটি হল যে সমস্ত মূল্যমান 2, অর্থাৎ 1,1/2,1/4, ইত্যাদির শক্তি। ডলার। প্যাকেজ-মার্জ অ্যালগরিদমের বিবরণ ধরে নিন যে বৃহত্তম মূল্য 1 ডলার, এবং এন একটি পূর্ণসংখ্যা। (অ্যালগরিদম কাজ করে যদিও এই অনুমানগুলি ধরে রাখে না, তুচ্ছ পরিবর্তন দ্বারা।) মুদ্রা সংগ্রাহক প্রথমে তার মুদ্রাগুলিকে তালিকায় বিভক্ত করেন, প্রতিটি মূল্যমানের জন্য একটি করে, মুদ্রাতাত্ত্বিক মান অনুসারে সাজানো হয়। তারপরে তিনি জোড়ায় জোড়ায় ক্ষুদ্রতম মূল্যমানের মুদ্রা প্যাকেজ করেন, যা ক্ষুদ্রতম মোট মুদ্রাতাত্ত্বিক মানের জোড়া থেকে শুরু হয়। যদি একটি মুদ্রা অবশিষ্ট থাকে, তবে এটি সেই মূল্যমানের সর্বোচ্চ মুদ্রাতাত্ত্বিক মূল্যের মুদ্রা হবে এবং এটি আলাদা করে রাখা হবে এবং এখন থেকে উপেক্ষা করা হবে। এই প্যাকেজগুলি আবার মুদ্রাতাত্ত্বিক মানের ক্রমে পরবর্তী ক্ষুদ্রতম মূল্যমানের মুদ্রার তালিকায় একত্রিত করা হয়। সেই তালিকার আইটেমগুলি তারপর জোড়ায় প্যাক করা হয়, এবং পরবর্তী ক্ষুদ্রতম তালিকায় একত্রিত করা হয়, ইত্যাদি। পরিশেষে, জিনিসপত্রের একটি তালিকা রয়েছে, যার প্রতিটি হল 1 ডলারের মুদ্রা বা একটি প্যাকেজ যা দুই বা ততোধিক ছোট মুদ্রার সমন্বয়ে গঠিত যার মূল্যমান মোট 1 ডলার। এগুলি মুদ্রাতাত্ত্বিক মানের ক্রমেও সাজানো হয়। মুদ্রা সংগ্রাহক তারপর তাদের মধ্যে সর্বনিম্ন মান এন নির্বাচন করে। লক্ষ্য করুন যে অ্যালগরিদমের সময় মুদ্রার সংখ্যায় রৈখিক। মুদ্রা সংগ্রাহকের সমস্যায় দৈর্ঘ্য-সীমিত হাফম্যান কোডিং হ্রাস করা যাক যে কোনও কোড শব্দের সর্বোচ্চ দৈর্ঘ্য এল হতে পারে। ধরা যাক p1,., pn হল এনকোড করা বর্ণমালার প্রতীকগুলির ফ্রিকোয়েন্সি। আমরা প্রথমে চিহ্নগুলিকে এমনভাবে সাজাই যাতে পাই ≤ পাই + 1 হয়। প্রতিটি প্রতীকের জন্য 2−1,., 2−এল মূল্যমানের এল মুদ্রা তৈরি করুন, যার প্রত্যেকটির মুদ্রাতাত্ত্বিক মান পাই। ন্যূনতম মুদ্রাতাত্ত্বিক মানের মুদ্রার সেট নির্বাচন করতে প্যাকেজ-মার্জ অ্যালগরিদম ব্যবহার করুন যার মূল্যমান মোট n−1। ধরা যাক নির্বাচিত মুদ্রাতাত্ত্বিক মানের মুদ্রার সংখ্যা। সর্বোত্তম দৈর্ঘ্য-সীমিত হাফম্যান কোডটি দৈর্ঘ্যের একটি বিট স্ট্রিং সহ প্রতীক i কে এনকোড করবে। ক্যানোনিকাল হাফম্যান কোডটি সহজেই একটি সহজ বটম-আপ লোভী পদ্ধতি দ্বারা তৈরি করা যেতে পারে, যেহেতু হাই পরিচিত, এবং এটি দ্রুত ডেটা সংকোচনের ভিত্তি হতে পারে। কর্মক্ষমতার উন্নতি এবং সাধারণীকরণ এই হ্রাসের সাথে, অ্যালগরিদমটি হল ও (এনএল)-সময় এবং ও (এনএল)-স্থান। যাইহোক, মূল কাগজ, "সর্বোত্তম দৈর্ঘ্য-সীমিত হাফম্যান কোডের জন্য একটি দ্রুত অ্যালগরিদম", দেখায় যে কীভাবে এটি ও (এনএল)-সময় এবং ও (এন)-স্পেসে উন্নত করা যেতে পারে। ধারণাটি হল অ্যালগরিদমটি প্রথমবার চালানো, শুধুমাত্র দুটি সমতুল্য উপ-সমস্যা নির্ধারণ করতে সক্ষম হওয়ার জন্য পর্যাপ্ত তথ্য রাখা যা মূল সমস্যার অর্ধেক আকারের যোগফল। এটি পুনরাবৃত্তিমূলকভাবে করা হয়, যার ফলে একটি অ্যালগরিদম তৈরি হয় যা প্রায় দ্বিগুণ সময় নেয় তবে কেবল রৈখিক স্থানের প্রয়োজন হয়। গুণনীয়ক ধ্রুবক হ্রাস করতে এবং বিশেষ ক্ষেত্রে এটি দ্রুততর করার জন্য প্যাকেজ-মার্জ অ্যালগরিদমের আরও অনেক উন্নতি করা হয়েছে, যেমন পুনরাবৃত্ত পিস থাকা সমস্যাগুলি। প্যাকেজ-মার্জ পদ্ধতিটি বর্ণানুক্রমিক কোডিংয়ের মতো সম্পর্কিত সমস্যাগুলির সাথেও খাপ খাইয়ে নেওয়া হয়েছে। গ্রাফ তত্ত্বের সাথে জড়িত পদ্ধতিগুলিতে প্যাকেজ-মার্জ অ্যালগরিদমের তুলনায় ভাল অ্যাসিম্পটোটিক স্থান জটিলতা দেখানো হয়েছে, তবে এগুলি ততটা ব্যবহারিক প্রয়োগ দেখেনি। তথ্যসূত্র বাহ্যিক সংযোগ প্যাকেজ-মার্জ অ্যালগরিদমের একটি বাস্তবায়ন "" একটি দ্রুত এনট্রপি কোডার যা প্যাকেজ-মার্জ অ্যালগরিদম লসলেস কম্প্রেশন অ্যালগরিদম কোডিং তত্ত্ব ব্যবহার করে।