একটি ফাইলকে কি অনির্দিষ্টকাল ধরে সংকুচিত বা কমপ্রেস করা সম্ভব? কোনো একটি বই, ভিডিও বা ডিএনএ সিকোয়েন্সকে একটি অক্ষরও না হারিয়ে সংরক্ষণ করতে সর্বনিম্ন কত বিট প্রয়োজন? ক্লদ শ্যাননের পূর্বে বিজ্ঞানীদের কাছে ডেটা কম্প্রেশনের কোনো তাত্ত্বিক মাপকাঠি ছিল না। ১৯৪৮ সালে শ্যানন প্রমাণ করেন ঐতিহাসিক সোর্স কোডিং উপপাদ্য (Source Coding Theorem)। তিনি দেখান যে কোনো তথ্য উৎসের শ্যানন এনট্রপি $H(X)$-ই হলো লসলেস ডেটা কম্প্রেশনের পরম অভেদ্য ভৌত প্রাচীর। এনট্রপির নিচে কোনো ফাইলকে সংকুচিত করলে তথ্য বিলুপ্তি নিশ্চিত, আর এনট্রপির সমপরিমাণ বিটে সংকুচিত করলে শতভাগ তথ্য পুনরুদ্ধার সম্ভব।
১. অ্যাসিম্পটোটিক ইকুইপার্টিশন প্রোপার্টি (AEP) ও টিপিক্যাল সেট
সোর্স কোডিং উপপাদ্যের মূল গাণিতিক চালিকাশক্তি হলো অ্যাসিম্পটোটিক ইকুইপার্টিশন প্রোপার্টি (AEP), যা বৃহৎ সংখ্যার দুর্বল নিয়মের (Weak Law of Large Numbers) তথ্য-তাত্ত্বিক প্রকাশ।
ধরা যাক একটি উৎস থেকে $n$ দৈর্ঘ্যের প্রতীক সিকোয়েন্স তৈরি হচ্ছে। বৃহৎ $n$-এর ক্ষেত্রে প্রায় সকল সম্ভাব্যতা একটি ক্ষুদ্র উপসেটে কেন্দ্রীভূত হয়, যাকে বলা হয় টিপিক্যাল সেট (Typical Set) $A_epsilon^{(n)}$। এর তিনটি মূল বৈশিষ্ট্য:
- বাস্তব ক্ষেত্রে যেকোনো উৎপাদিত সিকোয়েন্সের এই টিপিক্যাল সেটের অন্তর্ভুক্ত হওয়ার সম্ভাবনা প্রায় ১০০%: $mathbb{P}(x^n in A_epsilon^{(n)}) to 1$।
- টিপিক্যাল সেটের প্রতিটি সিকোয়েন্সের সম্ভাবনা প্রায় সমান: $p(x^n) approx 2^{-n H(X)}$।
- মোট টিপিক্যাল সিকোয়েন্সের সংখ্যা হলো প্রায় $2^{n H(X)}$।
যদিও মোট তাত্ত্বিক সিকোয়েন্সের সংখ্যা $2^n$, প্রকৃতি কেবল $2^{n H(X)}$ টি সিকোয়েন্স তৈরি করে। ফলে কেবল এই সিকোয়েন্সগুলোকে সূচীবদ্ধ করতে আমাদের ঠিক $n H(X)$ সংখ্যক বিট প্রয়োজন হয়!
২. প্রিফিক্স কোড ও ক্রাফ্ট অসমতা
একটি কোডকে কোনো বিরতি চিহ্ন ছাড়াই তাৎক্ষণিকভাবে ডিকোডযোগ্য হতে হলে তাকে প্রিফিক্স কোড হতে হয় (যেখানে কোনো কোডওয়ার্ড অন্য কোনো কোডওয়ার্ডের শুরুর অংশ হতে পারে না)। লিওন ক্রাফ্ট প্রমাণ করেন যে কোডওয়ার্ডের দৈর্ঘ্য $l_1, dots, l_m$ হলে প্রিফিক্স কোডের অস্তিত্বের প্রয়োজনীয় ও পর্যাপ্ত শর্ত হলো:
[
sum_{i=1}^m 2^{-l_i} le 1
]
৩. শ্যাননের সোর্স কোডিং উপপাদ্য
ল্যাগ্রাঞ্জ গুণক ব্যবহার করে গড় কোড দৈর্ঘ্য $L = sum p_i l_i$ সর্বনিম্ন করলে দেখা যায় অনুকূল দৈর্ঘ্য $l_i^* = -log_2 p_i$। পূর্ণসংখ্যায় রূপান্তর করলে ক্রাফট অসমতা বজায় রেখে পাওয়া যায় ঐতিহাসিক উপপাদ্য:
[
H(X) le L < H(X) + 1 quad text{bits/symbol}
]
$n$ প্রতীকের ব্লক কোডিং করলে গড় বিট রেট নিখুঁতভাবে এনট্রপির সমান হয়:
[
lim_{n to infty} frac{L_n}{n} = H(X)
]
শ্যাননের অকাট্য সিদ্ধান্ত: এনট্রপি $H(X)$ হলো লসলেস কম্প্রেশনের চরম সীমা। কোনো অ্যালগরিদম কখনোই এর চেয়ে বেশি সংকুচিত করতে পারে না।
৪. হাফম্যান ও এরিথমেটিক কোডিং
১৯৫২ সালে ডেভিড হাফম্যান উদ্ভাবন করেন বিখ্যাত গ্রিডি হাফম্যান কোডিং ট্রি, যা প্রতিটি প্রতীকের জন্য অপটিমাল প্রিফিক্স কোড তৈরি করে। তবে কোনো প্রতীকের সম্ভাবনা ৫০%-এর বেশি হলে হাফম্যান কোড ভগ্নাংশ বিট দিতে পারে না বিধায় আধুনিক ভিডিও (H.264/H.265) ও ফাইল কম্প্রেশনে (Zstandard) ব্যবহূত হয় এরিথমেটিক কোডিং এবং অ্যাসিমেট্রিক নিউমেরাল সিস্টেমস (ANS), যা সম্পূর্ণ শ্যানন সীমার কাছাকাছি কম্প্রেশন সক্ষমতা অর্জন করে।
