হাফম্যানের অ্যালগরিদম ডেটা সংকুচিত বা এনকোড করতে ব্যবহৃত হয়। সাধারণত, একটি টেক্সট ফাইলের প্রতিটি অক্ষর আট বিট (সংখ্যা, 0 অথবা 1) হিসাবে সংরক্ষণ করা হয় যা ASCII নামক একটি এনকোডিং ব্যবহার করে সেই অক্ষরের সাথে মানচিত্র করে। একটি হাফম্যান-এনকোডেড ফাইল অনমনীয় 8-বিট কাঠামোকে ভেঙে দেয় যাতে সর্বাধিক ব্যবহৃত অক্ষরগুলি কয়েকটি বিটে সংরক্ষণ করা হয় ('a' ASCII এর পরিবর্তে "10" বা "1000" হতে পারে, যা "01100001")। সর্বনিম্ন সাধারণ অক্ষরগুলি প্রায়শই 8 বিটেরও বেশি সময় নেয় ('z' "00100011010" হতে পারে), কিন্তু সেগুলি খুব কমই ঘটে বলে, হাফম্যান এনকোডিং, সম্পূর্ণভাবে, মূলের চেয়ে অনেক ছোট ফাইল তৈরি করে।
ধাপ
2 এর অংশ 1: এনকোডিং
ধাপ 1. এনকোড করা ফাইলের প্রতিটি অক্ষরের ফ্রিকোয়েন্সি গণনা করুন।
ফাইলের শেষ চিহ্নিত করতে একটি ডামি অক্ষর অন্তর্ভুক্ত করুন - এটি পরে গুরুত্বপূর্ণ হবে। আপাতত, এটিকে EOF (ফাইলের শেষ) বলুন এবং এটিকে 1 এর ফ্রিকোয়েন্সি হিসাবে চিহ্নিত করুন।
উদাহরণস্বরূপ, যদি আপনি "ab ab cab" পড়ার একটি টেক্সট ফাইল এনকোড করতে চান, তাহলে আপনার ফ্রিকোয়েন্সি 3 সহ 'a', ফ্রিকোয়েন্সি 3 সহ 'b', ফ্রিকোয়েন্সি 2 সহ 'স্পেস', ফ্রিকোয়েন্সি 1 সহ 'c' থাকবে, এবং ফ্রিকোয়েন্সি 1 সহ EOF।
ধাপ 2. অক্ষরগুলিকে ট্রি নোড হিসাবে সংরক্ষণ করুন এবং সেগুলিকে অগ্রাধিকার সারিতে রাখুন।
আপনি প্রতিটি অক্ষরকে একটি পাতার মতো একটি বড় বাইনারি গাছ তৈরি করবেন, তাই আপনার অক্ষরগুলিকে এমন একটি বিন্যাসে সংরক্ষণ করা উচিত যাতে তারা গাছের নোড হতে পারে। এই নোডগুলিকে অগ্রাধিকার সারিতে রাখুন প্রতিটি চরিত্রের ফ্রিকোয়েন্সি তার নোডের অগ্রাধিকার হিসাবে।
- একটি বাইনারি ট্রি হল একটি ডেটা ফরম্যাট যেখানে প্রতিটি টুকরো ডাটা একটি নোড যা একটি পিতা -মাতা এবং দুটি সন্তান পর্যন্ত থাকতে পারে। এটি প্রায়শই একটি শাখা গাছ হিসাবে আঁকা হয়, তাই নামটি।
- একটি সারি একটি যথাযথ নামযুক্ত তথ্য সংগ্রহ যেখানে সারিতে প্রবেশ করার প্রথম জিনিসটিও প্রথম জিনিস (যেমন লাইনে অপেক্ষা করা)। একটি অগ্রাধিকার সারিতে, তথ্যগুলি তাদের অগ্রাধিকার অনুসারে সংরক্ষণ করা হয়, যাতে প্রথম জিনিসটি সবচেয়ে জরুরী জিনিস হয়, প্রথম জিনিসের পরিবর্তে সবচেয়ে ছোট অগ্রাধিকারযুক্ত জিনিসটি।
- "Ab ab cab" উদাহরণে, আপনার অগ্রাধিকার সারি এই রকম হবে: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
ধাপ 3. আপনার গাছ নির্মাণ শুরু করুন।
অগ্রাধিকার সারি থেকে দুটি সবচেয়ে জরুরী জিনিস সরান (বা ডিকিউ)। এই দুটি নোডের অভিভাবক হওয়ার জন্য একটি নতুন ট্রি নোড তৈরি করুন, প্রথম নোডটি তার বাম সন্তান হিসেবে এবং দ্বিতীয়টি তার ডান সন্তান হিসেবে সংরক্ষণ করুন। নতুন নোডের অগ্রাধিকার তার সন্তানের অগ্রাধিকারগুলির সমষ্টি হওয়া উচিত। তারপর অগ্রাধিকার কাতারে এই নতুন নোড এনকিউ।
অগ্রাধিকার সারি এখন এইরকম দেখাচ্ছে: {'': 2, নতুন নোড: 2, 'a': 3, 'b': 3}
ধাপ 4. আপনার গাছ নির্মাণ শেষ করুন:
সারিতে শুধুমাত্র একটি নোড না হওয়া পর্যন্ত উপরের ধাপটি পুনরাবৃত্তি করুন। লক্ষ্য করুন যে আপনি অক্ষর এবং তাদের ফ্রিকোয়েন্সিগুলির জন্য তৈরি নোডগুলি ছাড়াও, আপনি ডিকিউইং, গাছগুলিতে পরিণত হবেন এবং প্যারেন্ট নোড, নোডগুলি যা ইতিমধ্যে নিজেরাই গাছ।
- যখন আপনি শেষ করেন, সারির শেষ নোডটি এনকোডিং গাছের মূল হবে, অন্য সব নোডগুলি এর থেকে শাখা ছাড়বে।
- সর্বাধিক ব্যবহৃত অক্ষর হবে গাছের চূড়ার কাছাকাছি পাতা, যখন খুব কমই ব্যবহৃত অক্ষরগুলি মূল থেকে অনেক দূরে গাছের নীচে অবস্থান করবে।
পদক্ষেপ 5. একটি এনকোডিং মানচিত্র তৈরি করুন। প্রতিটি অক্ষরে পৌঁছানোর জন্য গাছের মধ্য দিয়ে হাঁটুন। প্রতিবার যখন আপনি একটি নোডের বাম সন্তান পরিদর্শন করেন, এটি একটি '0'। প্রতিবার যখন আপনি একটি নোডের ডান শিশু পরিদর্শন করেন, এটি একটি '1'। যখন আপনি একটি অক্ষর পেতে, অক্ষর 0s এবং 1s ক্রম যে এটি পেতে লাগে সঙ্গে সংরক্ষণ করুন। সংকলিত ফাইলের মতো অক্ষরটি এনকোড করা হবে। একটি মানচিত্রে অক্ষর এবং তাদের ক্রম সংরক্ষণ করুন।
- উদাহরণস্বরূপ, মূল থেকে শুরু করুন। মূলের বাম সন্তানের সাথে দেখা করুন, এবং তারপর সেই নোডের বাম শিশুটি দেখুন। যেহেতু আপনি এখন যে নোডটিতে আছেন তার কোন সন্তান নেই, তাই আপনি একটি চরিত্রে পৌঁছেছেন। এই ' '. যেহেতু আপনি এখানে দুবার বামদিকে হেঁটেছেন, তাই '' এর জন্য এনকোডিং হল "00"।
- এই গাছের জন্য, মানচিত্রটি এইরকম দেখাবে: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}।
ধাপ 6. আউটপুট ফাইলে, হেডার হিসেবে এনকোডিং মানচিত্র অন্তর্ভুক্ত করুন।
এটি ফাইলটিকে ডিকোড করার অনুমতি দেবে।
ধাপ 7. ফাইল এনকোড করুন।
ফাইলের প্রতিটি অক্ষর এনকোড করার জন্য, আপনি মানচিত্রে সংরক্ষিত বাইনারি ক্রম লিখুন। একবার আপনি ফাইল এনকোডিং শেষ করলে, শেষ পর্যন্ত EOF যোগ করতে ভুলবেন না।
- "Ab ab cab" ফাইলের জন্য, এনকোডেড ফাইলটি এইরকম দেখাবে: "1011001011000101011011"।
- ফাইলগুলি বাইট (8 বিট, বা 8 বাইনারি ডিজিট) হিসাবে সংরক্ষণ করা হয়। যেহেতু হাফম্যান এনকোডিং অ্যালগরিদম 8-বিট ফরম্যাট ব্যবহার করে না, তাই এনকোডেড ফাইলগুলির দৈর্ঘ্য প্রায় 8 এর গুণিতক হবে না। এই ক্ষেত্রে, ফাইলের শেষে দুটি 0 যোগ করা হবে, যা অন্য স্পেসের মতো দেখায়। এটি একটি সমস্যা হতে পারে: কীভাবে ডিকোডার জানতে পারবে কখন পড়া বন্ধ করতে হবে? যাইহোক, যেহেতু আমরা একটি ফাইলের শেষ অক্ষর অন্তর্ভুক্ত করেছি, ডিকোডার এটিতে পৌঁছাবে এবং তারপরে যোগ করা অন্য কিছু উপেক্ষা করে থামবে।
2 এর 2 অংশ: ডিকোডিং
পদক্ষেপ 1. একটি হাফম্যান-এনকোডেড ফাইলে পড়ুন।
প্রথমে হেডার পড়ুন, যা এনকোডিং ম্যাপ হওয়া উচিত। ডিকোডিং ট্রি তৈরির জন্য এটি ব্যবহার করুন যেভাবে আপনি ফাইলটি এনকোড করতে ব্যবহার করেছেন সেই গাছটি তৈরি করেছেন। দুটি গাছ অভিন্ন হওয়া উচিত।
ধাপ 2. বাইনারিতে একবারে এক অঙ্কে পড়ুন।
আপনি পড়ার সময় গাছটি অতিক্রম করুন: যদি আপনি '0' তে পড়েন, আপনি যে নোডে আছেন তার বাম সন্তানের কাছে যান এবং যদি আপনি '1' এ পড়েন তবে ডান সন্তানের কাছে যান। যখন আপনি একটি পাতায় (কোন শিশু ছাড়া একটি নোড) পৌঁছান, আপনি একটি চরিত্রের কাছে এসেছেন। ডিকোডেড ফাইলে অক্ষরটি লিখুন।
যেভাবে অক্ষরগুলি গাছের মধ্যে সংরক্ষণ করা হয় তার কারণে, প্রতিটি অক্ষরের কোডগুলির একটি উপসর্গ সম্পত্তি থাকে, যাতে অন্য চরিত্রের এনকোডিংয়ের শুরুতে কোনও চরিত্রের বাইনারি এনকোডিং কখনও ঘটতে পারে না। প্রতিটি চরিত্রের এনকোডিং সম্পূর্ণ অনন্য। এটি ডিকোডিং অনেক সহজ করে তোলে।
ধাপ Re. পুনরাবৃত্তি করুন যতক্ষণ না আপনি EOF এ পৌঁছান।
অভিনন্দন! আপনি ফাইল ডিকোড করেছেন।
