কোড সংকোচন

যখন আমরা কোন তথ্যকে প্রকাশ করি, যেমন কোন একটা চিত্রের মাধ্যমে, ডিজিটালরূপে, তার মানে আমরা সেই তথ্যকে নিশ্চয়ই কয়েকভাবে ভাগ করে নিয়েছি। এর ফলে আমরা একটা চিত্রকে অনেকগুলো রঙের সংকেতের ক্রম হিসেবে পাঠাতে পারি আর এই প্রত্যেকটি রং, কিছু কোড ব্যবহারের মাধ্যমে প্রত্যেক সংখ্যাকে প্রকাশ করে থাকে নিচের ব্যাপারটা মন দিয়ে খেয়াল করি। এলিস আর বব বাইনারি তথ্য আদান-প্রদান করতে পারে। (মোর্স কোড) এপদ্ধতি ব্যবহার করতে তারা গ্রাহকদের কাছ থেকে ১ পেনি করে মূল্য গ্রহণ করে। একজন গ্রাহক আসেন যিনি একটা বার্তা পাঠাতে চান, এবং তার বার্তাটিতে ১০০০টা প্রতীক আছে। এই বার্তার কী অর্থ দাঁড়ায় সেটা আমরা এখনো জানি না। সাধারণত, এই ধরনের বার্তা আদর্শ ২-বিট কোডের মাধ্যমে পাঠিয়ে থাকি, অর্থাৎ গ্রাহককে ২০০০ বিটের মূল্য দিতে হবে। এলিস আর বব তাদের এই গ্রাহকের বিষয়ে আগেই আলোচনা করেছে এবং তারা একটা জিনিস বুঝতে পেরেছে যে এই বার্তায় প্রত্যেক প্রতীকের ব্যবহারের সম্ভাব্যতা ভিন্ন। তাহলে তারা কী এই জানা সম্ভাব্যতা ব্যবহার করে প্রেরণকে কি সংকোচন করা যাবে কিংবা এতে তাদের কোন লাভ হবে? তাহলে অপটিমাল কোডের কৌশল কী হবে? এই অপটিমাল কোডের কৌশল সমাধান করেছেন ডেভিড হফম্যান, যেটি প্রকাশিত হয় ১৯৫২ সালে। এবং একটা বাইনারি ট্রি গড়ার ভিত্তিতে এই অপটিমাল কোডের কৌশল তৈরি হয়েছিল। শুরু করার জন্য, আমরা সবগুলো প্রতীকের একটা তালিকা করব যেগুলোর নাম হল নোডস। এরপর, আমাদের দুটো লঘিষ্ঠ সম্ভাব্য নোডস নির্ণয় বের করতে হবে। ধরে নেই, এই ক্ষেত্রে সেটা হল বি এবং সি, এবং তারপর এদুটো নোডকে একত্রে যুক্ত করে, সেই সাথে এদের সম্ভাব্যতাকে যোগ করতে হবে। এরপর আবার পরের দুইটি লঘিষ্ট নোডের ক্ষেত্রেও একই কাজ করতে হবে, এবং ততক্ষণ পর্যন্ত যুক্ত করতে হবে যতক্ষণ পর্যন্ত না আমরা একটা মাত্র নোডে পৌঁছাবো। অবশেষে, এর প্রান্তগুলোকে আমরা ০ বা ১ দ্বারা যেকোন ক্রমে চিহ্নিত করব। তাহলে এখন যেকোন বর্ণের কোড হল এর একদম শীর্ষ থেকে বর্ণের আগ পর্যন্ত। তাহলে "এ"-এর জন্য, এখানে মাত্র একটি প্রান্ত আছে, বা ১ এটাই হফম্যান কোডিং নামে সবার কাছে পরিচিত, উল্লেখিত ধরণের উদাহরণগুলো বেশ কঠিন। শুর করা যাক! ধরে নেই, ডি এর কোড ছোট করে 0 লিখা হয়েছে, তাহলে একটা মেসেজ ০১১ মানে হতে পারে ডিএএ, অথবা শুধু বি। এ্রর জন্য বার্তার মধ্যকার বর্ণের ব্যবধান নির্ণয় করতে হবে, কারণ তথ্য প্রেরণের সময় আপনা-আপনি এই ব্যবধানগুলো চলে যায়। এখন মূল বার্তা ২০০০ বিটের তুলনায় এখানে এই বার্তাটিকে কতটুকু সংকোচন করা হয়েছে? তো, আমাদের শুধু নির্ণয় করতে হবে যে প্রত্যেক বর্ণে গড়ে কয়টি করে বিট আছে। তাহলে এখানে আমরা প্রত্যেক কোডের দৈর্ঘ্যকে ঘটনার সম্ভাব্যতা সংখ্যা দিয়ে গুণ করে এবং পরে সবগুলোকে একত্রে যোগ করলে আমরা প্রত্যেক সংকেতের গড় দৈর্ঘ্য পাব, যেমন এই ক্ষেত্রে সেটা হল ১.৭৫ বিট। এর মানে হল এই হফম্যান কোডিং এর সাহায্যে ২০০০ বিটের বার্তাকে ১৭৫০ বিটে সংকোচন করা যেতে পারে। এবং ক্লড শ্যানন হলেন সেই ব্যক্তি যিনি প্রথম বলেন যে এই সংকোচনের সীমা সবসময়ই এই বার্তার উৎসের এনট্রপি। যেহেতু এর উৎসের এনট্রপি অথবা অনির্দিষ্টতার জানা পরিসংখ্যানের কারণে কমে তাই সংকোচনের ক্ষমতা বৃদ্ধি পায়। (মোর্স কোড) আবার কোনভাবে যদি এনট্রপি বেড়ে যায় তাহলে সংকোচনের ক্ষমতা কমে যেতে পারে। (মোর্স কোড) আমরা যদি এনট্রপির উর্ধে উঠে সংকোচন করতে চাই, সেক্ষেত্রে আমাদের বার্তার যে মূল বক্তব্যকে আছে সেটি বাদ দিয়ে দিতে হবে।