[পরিদর্শক (58.214.*.*)]উত্তর [চীনা ] | সময় :2022-12-17 | গত শতাব্দীর পঞ্চাশের দশকের গোড়ার দিকে হাফম্যান যখন এই এনকোডিংয়ের প্রস্তাব দিয়েছিলেন, তখন তিনি অক্ষরের উপস্থিতির সম্ভাবনার উপর ভিত্তি করে সংক্ষিপ্ততম গড় দৈর্ঘ্যের সাথে সংক্ষিপ্ততম এনকোডিং তৈরি করেছিলেন। এটি একটি ভেরিয়েবল-লেংথ এনকোডিং। এনকোডিং-এ, যদি প্রতিটি কোডওয়ার্ডের দৈর্ঘ্য কঠোরভাবে কোডওয়ার্ডের সাথে সম্পর্কিত প্রতীকের উপস্থিতির সম্ভাবনার বিপরীত ক্রমে সাজানো হয়, তবে এনকোডিংয়ের গড় দৈর্ঘ্য সবচেয়ে ছোট.(দ্রষ্টব্য: কোডওয়ার্ডটি হ'ল হাফম্যান দ্বারা প্রতীকটি এনকোড করার পরে প্রাপ্ত কোড, এবং প্রতীকটি উপস্থিত হওয়ার সম্ভাবনার উপর নির্ভর করে এর দৈর্ঘ্য ভিন্ন, তাই হাফম্যান কোডটি একটি ভেরিয়েবল-দৈর্ঘ্যের এনকোডিং। এবং হাফম্যান কোডিং পিতার সাবট্রি অনুযায়ী, যখন তার পড়ার কোডটি সম্পূর্ণ বিপরীত।.. স্ট্যাটিক এনকোডিং এই এনকোডিং পদ্ধতিটি স্ট্যাটিক হাফম্যান এনকোডিং, যা দুবার এনকোড করার জন্য ডেটা স্ক্যান করে: প্রথম পাসটি মূল ডেটাতে প্রতিটি অক্ষরের ফ্রিকোয়েন্সি গণনা করে, হাফম্যান গাছ তৈরি করতে প্রাপ্ত ফ্রিকোয়েন্সি মান ব্যবহার করে এবং গাছের তথ্য সংরক্ষণ করতে হবে, অর্থাৎ, অক্ষর 0-255 (2^8 = 256) এর ফ্রিকোয়েন্সি মান 2-4 BYTES এর দৈর্ঘ্য ক্রমে সংরক্ষণ করা হয়, (ফ্রিকোয়েন্সি মানটি 4 বাইটসের দৈর্ঘ্যে সংরক্ষণ করা হয়),ফ্রিকোয়েন্সি মানটি 0--2^ 32-1 এর পরিসরে উপস্থাপন করা হয়, যা বড় ফাইলগুলিতে অক্ষরগুলির সংঘটনের ফ্রিকোয়েন্সি নির্দেশ করার জন্য যথেষ্ট) যাতে ডিকম্প্রেস করার সময় ডিকম্প্রেশনের জন্য একই হাফম্যান ট্রি তৈরি করা হয়; দ্বিতীয় পাসটি প্রথম স্ক্যান থেকে প্রাপ্ত হাফম্যান গাছকে এনকোড করে এবং এনকোডকরা কোডওয়ার্ডগুলি সংরক্ষণ করে,স্ট্যাটিক হাফম্যান এনকোডিং পদ্ধতির কিছু অসুবিধা রয়েছে: প্রথমত, খুব ছোট ফাইলগুলি এনকোড করা খুব কম তাত্পর্যপূর্ণ, কারণ 4 বাইট দৈর্ঘ্যে হাফম্যান গাছের তথ্য সংরক্ষণ ের জন্য 1024বাইট স্টোরেজ স্পেস প্রয়োজন; দ্বিতীয়ত, যখন হাফম্যান কোডিং করা হয়, এনকোড করা তথ্য সংরক্ষণ করার সময়, যদি এটি যোগাযোগ নেটওয়ার্কের সাথে ব্যবহার করা হয় তবে এটি একটি বড় বিলম্বের কারণ হবে; তৃতীয়ত, বড় ফাইল এনকোড করার সময়,ঘন ঘন ডিস্ক পড়া এবং লেখার অ্যাক্সেসগুলি ডেটা এনকোডিংকে ধীর করে দেয়,ডায়নামিক এনকোডিং অতএব, একটি গতিশীল হাফম্যান কোডিং পদ্ধতি পরে প্রস্তাব করা হয়েছিল.ডাইনামিক হাফম্যান এনকোডিং একটি গতিশীলভাবে পরিবর্তিত হাফম্যান গাছ ব্যবহার করে, t 1 অক্ষরের এনকোডিং মূল ডেটাতে প্রথম টি অক্ষর দ্বারা প্রাপ্ত হাফম্যান গাছের উপর ভিত্তি করে, এনকোডিং এবং ডিকোডিং একই প্রাথমিক হাফম্যান গাছ ব্যবহার করে এবং প্রতিটি অক্ষর প্রক্রিয়াজাত, এনকোডিং এবং ডিকোডিং হাফম্যান ট্রি সংশোধন করার জন্য একই পদ্ধতি ব্যবহার করে,সুতরাং ডিকোডিংয়ের জন্য হাফম্যান গাছের তথ্য সংরক্ষণ করার দরকার নেই,একটি অক্ষর এনকোড এবং ডিকোড করতে যে সময় লাগে তা সেই অক্ষরের এনকোডিং দৈর্ঘ্যের সমানুপাতিক, তাই গতিশীল হাফম্যান এনকোডিং রিয়েল টাইমে করা যেতে পারে। ডায়নামিক হাফম্যান কোডিং স্ট্যাটিক হাফম্যান কোডিংয়ের চেয়ে অনেক বেশি জটিল, এবং আগ্রহী পাঠকরা ডেটা স্ট্রাকচার এবং অ্যালগরিদমের বইগুলি উল্লেখ করতে পারেন।.. . উপরোক্ত JPEG হাফম্যান এনকোডিং ব্যবহার করে, এমন নয় যে JPEG শুধুমাত্র হাফম্যান এনকোডিং ব্যবহার করে, তবে এর মানগুলির তালিকা পাওয়ার জন্য একাধিক পদক্ষেপের পরে একটি ছবি, এই মানগুলি হফম্যান স্টোরেজ বা ট্রান্সমিশনের জন্য এনকোড করা হয়.হাফম্যান এনকোডিং পদ্ধতিটি বোঝা অপেক্ষাকৃত সহজ, এবং আপনি তার এনকোডিং পদ্ধতি অনুসারে হাফম্যান এনকোডিং এবং ডিকোডিং প্রোগ্রামটি লিখতে পারেন।.. হাফম্যান গাছ নির্মাণের জন্য অ্যালগরিদম।
const maxvalue = 10000; {সর্বাধিক ওজন সংজ্ঞায়িত করুন}
Maxleat=30; {একটি হাফম্যান গাছে পাতা নোডের সংখ্যা সংজ্ঞায়িত করুন}
maxnode=maxleaf*2-1;
HnodeType=record টাইপ করুন
ওজন: পূর্ণসংখ্যা;
পিতা-মাতা: পূর্ণসংখ্যা;
lchild: পূর্ণসংখ্যা;
rchild: পূর্ণসংখ্যা;
শেষ;
HuffArr:array[0..maxnode] HnodeType এর;
var ......
পদ্ধতি CreatHaffmanTree (var HuffNode: HuffArr); {Huffman tree construction algorithm}
var i, j, m1, m2,x1,x2,n: পূর্ণসংখ্যা;
আরম্ভ
readln(n); {পাতা নোডের সংখ্যা লিখুন} i:=0 থেকে 2*n-1 করুন {অ্যারে হাফনোড[] সূচনা}
আরম্ভ
HuffNode.weight=0;
HuffNode.parent=-1;
HuffNode.lchild=-1;
HuffNode.rchild=-1;
শেষ;
i এর জন্য: = 0 থেকে n-1 পড়ুন (HuffNode.weight); {n পাতার নোডের ওজন লিখুন}
i:=0 থেকে n-1 এর জন্য {একটি হাফম্যান গাছ তৈরি করুন}
আরম্ভ
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
j এর জন্য:=0 থেকে n i-1 do
যদি (HuffNode[j].weight<m1) এবং (HuffNode[j].parent=-1) তাহলে
শুরু করুন m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
শেষ
অন্যথায় যদি (HuffNode[j].weight<m2) এবং (HuffNode[j].parent=-1) তাহলে শুরু m2:=HuffNode[j].weight; x2:=j; শেষ;
{একটি সাবট্রিতে চিহ্নিত দুটি সাবট্রি মার্জ করুন}
হাফনোড[x1].পিতামাতা:=n i; হাফনোড[x2].পিতামাতা:=n i;
HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;
হাফনোড[n i].lchild:=x1; হাফনোড[n i].rchild:=x2;
শেষ;
শেষ; |
|