হাফম্যান কোড: উদাহরণ, অ্যাপ্লিকেশন

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

অ্যালগরিদম ইতিহাস

ইলেকট্রনিক তথ্য দক্ষ কোডিং জন্য খুব প্রথম অ্যালগরিদম হাফম্যান দ্বারা প্রস্তাবিত বিংশ শতাব্দীর মাঝখানে কোড, যথা 1952 সালে। এটি বর্তমানে তথ্য সংবহন করতে নির্মিত বেশিরভাগ প্রোগ্রামের মূল মূল উপাদান। এই মুহূর্তে, এই কোড ব্যবহার করে সবচেয়ে জনপ্রিয় সূত্র এক, জিপ, ARJ, RAR এবং অন্যান্য অনেক আর্কাইভ হয়। এই Huffman অ্যালগরিদম এছাড়াও JPEG চিত্র এবং অন্যান্য গ্রাফিক বস্তু কম্প্রেস করতে ব্যবহৃত হয়। ওয়েল এবং সমস্ত আধুনিক ফ্যাক্স কোডিং ব্যবহার করে, 1952 সালে উদ্ভাবিত। যেহেতু কোডটি এতদিন ধরে তৈরি হয়েছে তাই আজ পর্যন্ত এটি নতুন শেলগুলিতে এবং প্রাচীন এবং আধুনিক ধরনের সরঞ্জামগুলিতে ব্যবহৃত হয়।

দক্ষ কোডিং এর নীতি

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

হাফম্যানের কোড, উদাহরণ

আলগোরিদিমকে চিত্রিত করার জন্য, আসুন একটি কোড ট্রি তৈরি করার একটি গ্রাফিকাল রূপ নিতে। এই পদ্ধতিটি ব্যবহার করা কার্যকর ছিল, এই পদ্ধতির ধারণার জন্য প্রয়োজনীয় কিছু মানগুলির সংজ্ঞা ব্যাখ্যা করা উপযুক্ত। নোড থেকে নোড থেকে নির্দেশিত আর্ক এবং নোডের সেট সাধারণত একটি গ্রাফ বলা হয়। গাছ নিজেই নির্দিষ্ট বৈশিষ্ট্য একটি সেট সঙ্গে একটি গ্রাফ হয়:

• প্রতিটি নোডের মধ্যে কোনও একটি অ্যারের প্রবেশ করতে পারেন;
• নোডগুলির মধ্যে একটি গাছের মূল হতে হবে, অর্থাৎ, এতে কোনও চাপ থাকবে না;
• যদি root থেকে arcs বরাবর চলতে আরম্ভ থেকে, এই প্রক্রিয়া সম্পূর্ণরূপে কোনও নোডের মধ্যে পেতে অনুমতি দেওয়া উচিত।

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

হফম্যান অনুযায়ী একটি গাছ নির্মাণের জন্য অ্যালগরিদম

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

কম্প্রেশন দক্ষতা উন্নতি

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

কম্প্রেশন প্রক্রিয়া প্রসার

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

উপসংহার

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