হাফম্যান কোড
একটি হাফম্যান কোডকে নির্দিষ্ট ধরনের সর্বোত্তম উপসর্গ কোড হিসাবে সংজ্ঞায়িত করা হয় যা সাধারণত ক্ষতিহীন ডেটা কম্প্রেশনের জন্য ব্যবহৃত হয়।
এই ধরনের একটি কোড খুঁজে বের করার বা বাস্তবায়ন করার প্রক্রিয়া হাফম্যান কোডিং এর মাধ্যমে এগিয়ে যায়, একটি অ্যালগরিদম যা ডেভিড এ. হাফম্যান যখন এসসি.ডি. এমআইটি-তে ছাত্র, এবং 1952 সালের গবেষণাপত্র "অ্যা মেথড ফর দ্য কনস্ট্রাকশন অফ মিনিমাম-রিডানডেন্সি কোড"-এ প্রকাশিত।
Huffman এর অ্যালগরিদম থেকে আউটপুট একটি উৎস প্রতীক এনকোড করার জন্য একটি পরিবর্তনশীল-দৈর্ঘ্য কোড টেবিল হিসাবে প্রদর্শিত হতে পারে (যেমন একটি ফাইলের একটি অক্ষর)। অ্যালগরিদম উৎস প্রতীকের প্রতিটি সম্ভাব্য মানের জন্য আনুমানিক সম্ভাব্যতা বা সংঘটনের ফ্রিকোয়েন্সি (ওজন) থেকে এই টেবিলটি তৈরি করে। অন্যান্য এনট্রপি এনকোডিং পদ্ধতির মতো, আরও সাধারণ চিহ্নগুলি সাধারণত কম সাধারণ প্রতীকের চেয়ে কম বিট প্রয়োগ করে উপস্থাপন করা হয়। হাফম্যানের পদ্ধতিটি দক্ষতার সাথে প্রয়োগ করা যেতে পারে, যদি এই ওজনগুলি সাজানো হয় তবে ইনপুট ওজনের সংখ্যার সাথে রৈখিক একটি কোড খুঁজে পাওয়া যায়৷
এনট্রপি
তথ্য তত্ত্বে, শ্যাননের সোর্স কোডিং উপপাদ্য (বা শব্দহীন কোডিং উপপাদ্য) সম্ভাব্য ডেটা কম্প্রেশনের সীমা এবং শ্যানন এনট্রপির কার্যকরী অর্থ স্থাপন করতে সক্ষম।
সোর্স কোডিং উপপাদ্যটি দেখায় যে (সীমার মধ্যে, স্বাধীন এবং অভিন্নভাবে বিতরণ করা র্যান্ডম ভেরিয়েবলের (আই.আই.ডি.) ডেটার দৈর্ঘ্য যেমন অসীমের দিকে থাকে) ডেটাকে সংকুচিত করা সম্ভব নয় যাতে কোড হার (গড় সংখ্যা বিট প্রতি প্রতীক) উৎসের শ্যানন এনট্রপির চেয়ে ছোট, এটি কার্যত নিশ্চিত না হয়ে তথ্য হারিয়ে যাবে। যাইহোক, ক্ষতির নগণ্য সম্ভাবনা সহ, শ্যানন এনট্রপির কাছাকাছি নির্বিচারে কোড রেট পাওয়া সম্ভব।
তথ্য এনট্রপি গড় হার হিসাবে সংজ্ঞায়িত করা হয় যেখানে তথ্যের একটি স্টোকাস্টিক উৎস দ্বারা তথ্য উত্পাদিত হয়।
একটি র্যান্ডম ভেরিয়েবলের জন্য এনট্রপি গণনা করুন
এলোমেলো ভেরিয়েবলে কত তথ্য আছে তাও আমরা গণনা করতে পারি।
উদাহরণস্বরূপ, যদি আমরা সম্ভাব্যতা বন্টন p সহ একটি র্যান্ডম ভেরিয়েবল X-এর জন্য তথ্য গণনা করতে চাই তবে এটি একটি ফাংশন H() হিসাবে লেখা হতে পারে; যেমন:H(X)
প্রকৃতপক্ষে, র্যান্ডম ভেরিয়েবলের জন্য তথ্য গণনা করা র্যান্ডম ভেরিয়েবলের জন্য ইভেন্টের সম্ভাব্যতা বণ্টনের জন্য তথ্য গণনার অনুরূপ।
একটি এলোমেলো ভেরিয়েবলের জন্য তথ্য গণনা করা হয় "তথ্য এনট্রপি", "শ্যানন এনট্রপি" বা সহজভাবে "এনট্রপি"।
এটি সাদৃশ্য দ্বারা পদার্থবিদ্যা থেকে এনট্রপির ধারণার সাথে সম্পর্কিত, যে উভয়ই অনিশ্চয়তা শব্দের সাথে সম্পর্কিত।
এনট্রপির অন্তর্দৃষ্টি হল র্যান্ডম ভেরিয়েবলের সম্ভাব্যতা বন্টন থেকে অঙ্কিত একটি ইভেন্টকে প্রতিনিধিত্ব করতে বা প্রেরণ করার জন্য প্রয়োজনীয় বিটের গড় সংখ্যা হিসাবে সংজ্ঞায়িত করা হয়৷
একটি ডিস্ট্রিবিউশনের শ্যানন এনট্রপিকে সেই ডিস্ট্রিবিউশন থেকে প্রাপ্ত ইভেন্টে প্রত্যাশিত তথ্যের পরিমাণ হিসাবে সংজ্ঞায়িত করা হয়।
এটি একটি ডিস্ট্রিবিউশন P থেকে অঙ্কিত চিহ্নগুলিকে এনকোড করার জন্য গড়ে প্রয়োজনীয় বিটের সংখ্যার একটি নিম্ন সীমা প্রদান করে।
এনট্রপি একটি র্যান্ডম ভেরিয়েবল X-এর জন্য K এর সাথে K বিযুক্ত অবস্থায় নিম্নরূপ গণনা করা যেতে পারে
H(X) = -sum(each k in K p(k) * log(p(k)))
তার মানে প্রতিটি ঘটনার সম্ভাব্যতার যোগফলের নেতিবাচককে প্রতিটি ইভেন্টের সম্ভাব্যতার লগ দ্বারা গুণ করা হয়।
তথ্যের মতো, log() ফাংশন বেস-2 প্রয়োগ করে এবং ইউনিটগুলি বিট। পরিবর্তে একটি প্রাকৃতিক লগারিদম প্রয়োগ করা যেতে পারে।
সর্বনিম্ন এনট্রপি একটি র্যান্ডম ভেরিয়েবলের জন্য গণনা করা হয় যার একটি একক ইভেন্ট আছে যার সম্ভাব্যতা 1.0, একটি নিশ্চিততা। একটি র্যান্ডম ভেরিয়েবলের জন্য সবচেয়ে বড় এনট্রপি সম্ভব হবে যদি সমস্ত ঘটনা সমানভাবে সম্পাদিত হয়।
