কিভাবে লসলেস ডেটা কম্প্রেশন কাজ করে | কোয়ান্টা ম্যাগাজিন

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

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

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

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

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

ফ্যানো সমস্যার এই অংশটি সমাধান করেছিল। তিনি বুঝতে পেরেছিলেন যে তিনি ব্যয়বহুল স্পেস ছাড়াই বিভিন্ন দৈর্ঘ্যের কোড ব্যবহার করতে পারেন, যতক্ষণ না তিনি সম্পূর্ণ কোড এবং অন্য কোডের শুরু উভয়ের মতো অঙ্কের একই প্যাটার্ন ব্যবহার করেননি। উদাহরণস্বরূপ, যদি একটি নির্দিষ্ট বার্তায় S অক্ষরটি এতটাই সাধারণ ছিল যে Fano এটিকে অত্যন্ত সংক্ষিপ্ত কোড 01 বরাদ্দ করেছে, তাহলে সেই বার্তার অন্য কোনও অক্ষর 01 থেকে শুরু হওয়া কোনও কিছুর সাথে এনকোড করা হবে না; 010, 011 বা 0101 এর মতো কোড সবই নিষিদ্ধ। ফলস্বরূপ, কোডেড বার্তাটি কোনও অস্পষ্টতা ছাড়াই বাম থেকে ডানে পড়া যেতে পারে। উদাহরণ স্বরূপ, 01 বরাদ্দকৃত S অক্ষর, A অক্ষরটি 000, অক্ষরটি 001 বরাদ্দ করা এবং L অক্ষরটি 1 বরাদ্দ করা হয়েছে, হঠাৎ 0100100011 বার্তাটি অবিলম্বে "ছোট" শব্দে অনুবাদ করা যেতে পারে যদিও L একটি দ্বারা প্রতিনিধিত্ব করা হয়। ডিজিট, দুই ডিজিট দ্বারা S, এবং অন্য অক্ষর তিনটি করে প্রতিটি।

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

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

ফলাফল উল্লেখযোগ্যভাবে কার্যকর কম্প্রেশন ছিল. কিন্তু এটা ছিল শুধুমাত্র একটি অনুমান; একটি ভাল কম্প্রেশন কৌশল বিদ্যমান ছিল. তাই ফ্যানো তার ছাত্রদের এটি খুঁজে বের করার জন্য চ্যালেঞ্জ করেছিল।

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

এমন একটি বার্তা বিবেচনা করুন যেখানে ফ্যানো পদ্ধতিটি ব্যর্থ হয়। "স্কুলরুমে," O চারবার প্রদর্শিত হয়, এবং S/C/H/L/R/M প্রতিটি একবার প্রদর্শিত হয়। ফ্যানোর ভারসাম্য বজায় রাখার পদ্ধতিটি বাম শাখায় O এবং অন্য একটি অক্ষর বরাদ্দ করে শুরু হয়, সেই অক্ষরের মোট পাঁচটি ব্যবহার বাকি অক্ষরের পাঁচটি উপস্থিতির ভারসাম্য বজায় রাখে। ফলস্বরূপ বার্তার জন্য 27 বিট প্রয়োজন।

হাফম্যান, বিপরীতে, দুটি অস্বাভাবিক অক্ষর দিয়ে শুরু করে — বলুন, R এবং M — এবং তাদের একত্রিত করে, জোড়াটিকে একটি একক অক্ষরের মতো আচরণ করে।

তার আপডেট করা ফ্রিকোয়েন্সি চার্ট তাকে চারটি পছন্দের প্রস্তাব দেয়: O যেটি চারবার প্রদর্শিত হয়, নতুন সম্মিলিত RM নোড যা কার্যকরীভাবে দুইবার ব্যবহার করা হয় এবং একক অক্ষর S, C, H এবং L. হাফম্যান আবার দুটি সর্বনিম্ন সাধারণ বিকল্প বেছে নেয়, মিলে যায় (বলো) H এর সাথে L

চার্ট আবার আপডেট হয়: O এর এখনও ওজন 4, RM এবং HL এখন প্রতিটির ওজন 2, এবং অক্ষর S এবং C একা দাঁড়িয়েছে। হাফম্যান সেখান থেকে চলতে থাকে, প্রতিটি ধাপে দুটি সর্বনিম্ন ঘন ঘন বিকল্পগুলিকে গোষ্ঠীবদ্ধ করে এবং তারপর ট্রি এবং ফ্রিকোয়েন্সি চার্ট উভয়ই আপডেট করে।

পরিশেষে, ফ্যানো টপ-ডাউন পদ্ধতির থেকে কিছুটা শেভ করে, "স্কুলরুম" হয়ে যায় 11101111110000110110000101।

এক বিট খুব বেশি শোনাতে পারে না, কিন্তু বিলিয়ন গিগাবাইট দ্বারা স্কেল করা হলে ছোট সঞ্চয়ও প্রচুর পরিমাণে বৃদ্ধি পায়।

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

একটি প্রকল্পের জন্য খারাপ নয় যা মূলত একজন স্নাতক ছাত্রের চূড়ান্ত পরীক্ষা এড়িয়ে যাওয়ার ইচ্ছা দ্বারা অনুপ্রাণিত হয়।