Huffman Coding
အသက် ၂၆ နှစ်အရွယ် MIT မှာ ကျောင်းတက်နေတဲ့ David Huffman ဆိုတဲ့ ကောင်လေးတစ်ယောက်က ၁၉၅၂ ခုနှစ်လောက်မှာ Algorithm လေးတစ်ခုကို Assignment တစ်ခုအနေနဲ့ ဖန်တီးခဲ့တယ်။ အဲ့ဒီ Algorithm လေးက ကျွန်တော်တို့ ဒီနေ့ခေတ်အထိအသုံးပြုနေကြတဲ့ Data Compression တွေရဲ့ အခြေခံတစ်ခုလို့ ပြောလို့ရပါလိမ့်မယ်။
Data Compression ဆိုတာကတော့ ကွန်ပျူတာ သတင်းအချက်အလက်တွေကို ရှိရင်းစွဲအရွယ်အစားထပ် ပိုပြီး သေးနိုင်သမျှ သေးသွားအောင် ချုံ့လိုက်တာကိုပြောတာပေါ့။ အဲ့လို သေးအောင် လုပ်လိုက်တဲ့အချိန်မှာ မူရင်း သတင်းအချက်အလက်တွေ ပျောက်ရှသွားနိုင်တဲ့ နည်းလမ်း(Lossy Data Compression) တွေလည်း ရှိသလို၊ အရွယ်အစားသာသေးသွားပြီး အချက်အလက်တွေ မပျောက်မရှပဲ ပြန်ရနိုင်တဲ့ နည်းလမ်း (Lossless Data Compression) လည်း ရှိပါတယ်။
Lossy Data Compression ကတော့ အထူးသဖြင့် အသံဖိုင်၊ ဓာတ်ရှင်ဖိုင်၊ ဓာတ်ပုံဖိုင်တွေမှာ အတွေ့များကြတယ်။ Lossless Data Compression ကတော့ Zip ဖိုင်လိုမျိုးတွေမှာ တွေ့ရတာများတယ်။ David Huffman ရဲ့ Algorithm ကတော့ Lossless Data Compression နည်းလမ်းတစ်ခုပဲဖြစ်ပါတယ်။
Data Compression တွေအကြောင်းကတော့ ဒီလောက်ပဲထားပါတော့ဗျာ။ နောက်ကြုံတော့မှပဲ ထပ်ပြောပြတော့မယ်။ အဓိက ပြောပြချင်တာကတော့ David Huffman က ဖန်တီးလိုက်တဲ့ Huffman Coding လေးကတော့ Compression တွေရဲ့ စတင်ပေါက်ဖွားမှုတွေထဲက တစ်ခုလို့ မှတ်သားဖွယ်ရာရှိပါတယ်။
Huffman Coding
အဲ့တာဆိုရင် Huffman Coding အကြောင်းလေး နည်းနည်းလောက် လေ့လာကြည့်ရအောင်။ အသေးစိတ်အလုပ်လုပ်ပုံကိုတော့ ကျွန်တော် Video လေးနဲ့ ရှင်းပြသွားပါမယ်။ အခုကတော့ Huffman Coding အကြောင်းနည်းနည်းပါးပါးပြောပြမယ်နော်။
Huffman Coding လို့ ခေါ်တာကတော့ David Huffman ကဖန်တီးခဲ့တဲ့အတွက် သူ့နာမည်ကို အစွဲပြုပြီး ခေါ်လိုက်တာပါ။ အရှေ့မှာပြောခဲ့သလိုပဲ သူ့ရဲ့ Algorithm ကတော့ Data တွေကို ဆွဲချုံဖို့အတွက် အသုံးပြုလို့ရတဲ့ Algorithm တစ်ခုပေါ့နော်။
ဒီ Algorithm က အကောင်းဆုံးပဲလား ဆိုရင်တော့ ဟုတ်ချင်မှ ဟုတ်မှာပါ။ ဒါပေမယ့် ဒီနေ့ခေတ်အထိ သူ့ကိုမှီပြီးပဲ အသုံးပြုနေကြတာတွေအများကြီးပါပဲ။ သူ့ကို အခြေခံပြီး ပိုကောင်းအောင် ထပ်လုပ်ထားကြတာတွေလည်း အများကြီးပါပဲ။ ဥပမာ GZip လိုမျိုးပေါ့။ တစ်ထေရာတည်း သုံးချင်မှတော့ သုံးထားလိမ့်မယ်။ ဒါပေမယ့် သူ့ Algo ကတော့ ပါတယ်။
အဲ့တော့ Huffman Coding က Data တွေကို ဘယ်လိုချုံ့လိုက်လဲဆိုတာလေး အကြမ်းလေးဆက်ပြောပြဦးမယ်။
ကျွန်တော်တို့တွေက ဘယ်လိုကွန်ပျူတာအချက်အလက်ကိုမဆို ထိတွေ့တိုင်းကတော့ Binary Code တွေနဲ့ပဲဆိုတာကို အားလုံးသိထားကြမှာပါ။ Binary Code တွေကြောင့် ကွန်ပျူတာ အချက်အလက်တွေကို ပို့ရသယ်ရတာတွေ၊ သိမ်းရဆည်းရတာတွေ၊ တွက်ရချက်ရတာတွေကို ရိုးရိုးရှင်းရှင်း အလုပ်လုပ်နိုင်ခဲ့တာပေါ့နော်။
ဒါပေမယ့် ဒီ Binary Code တွေက သတင်းအချက်အလက်တစ်ခုကို ဖော်ပြတဲ့အခါမှာ တိကျတဲ့ Bit အရွယ်အစားတွေရှိတယ်။ ဆိုလိုတာက 8bit သုံးထားတဲ့ UTF-8 Encoding နဲ့ တည်ဆောက်လိုက်တဲ့ BANANA ဆိုတဲ့စာလေး ရှိမယ်ဆိုပါတော့။ ဒီမှာပါတဲ့ Character တစ်လုံးစီက 8 bit ယူထားတော့ စုစုပေါင်း ဒီ သတင်းအချက်အလက်က 48 bits (6 Byte) ယူသွားတယ်။
Get တစ်သုည’s stories in your inbox
Join Medium for free to get updates from this writer.
အဲ့ဒီ bits အရေအတွက်ကို Huffman Coding နဲ့ ချုံ့လိုက်မယ်ဆိုရင် 9 bits လောက်ပဲကျန်လိမ့်မယ်။ ဘယ်လိုချုံ့လိုက်လဲဆိုတာကို Video ထဲမှာ ရှင်းပြပေးထားပါတယ်နော်။
ဘယ်လိုချုံ့လိုက်လဲဆိုတာကို အကျဉ်းလေးပြောရရင် ဒီသတင်းအချက်အလက်မှာပါတဲ့ Binary Sequence တွေရဲ့ ကြိမ်နှုန်းတွေကို Tree Diagram တစ်ခုနဲ့ တွက်ထုတ်ပြီး ပိုနည်းတဲ့ bits အသစ်တွေ ပြောင်းပေးလိုက်တာပါပဲ။
အဲ့တာကိုမှ ထပ်ခါထပ်ခါပါနေတဲ့ ၊ ၁ ကြိမ်ထပ်မက ပိုပါနေတဲ့ Character တွေ(Binary Sequence) တွေကို bits အနည်းဆုံးဖြစ်အောင် ချုံ့လိုက်တယ်။ BANANA ဆိုတဲ့ စာမှာဆိုရင် A က ၃ ခါပါတယ်။ N က ၂ ခါပါတယ်။ အဲ့လို ထပ်ခါထပ်ခါပါတဲ့ Binary တွေရဲ့ အကြိမ်ရေအလိုက် Tree Diagram မှာ အဆင့်ဆင့် တည်ဆောက်လိုက်တယ်။ အဲ့ကနေမှ Binary Sequence တွေက 8 bit မဖြစ်တော့ပဲ ပိုနည်းတဲ့ bit အရေအတွက်တွေ ပြောင်းသွားတယ်။
အက်ြိမ်ရေ အများဆုံးပါတဲ့ A ရဲ့ မူရင်း Binary က 01000001 ရှိတယ်ဆိုရင် ချုံ့လိုက်တဲ့အခါမှာတော့ 1 တစ်လုံးတည်းပဲ ဖြစ်သွားမှာ။ N ဆိုရင်က 01 ဖြစ်သွားလိမ့်မယ်။ B က 00 ဖြစ်သွားတယ်။ ဘယ်လိုရလဲကို Video ထဲမှာ ပြောပေးမယ်နော်။
ဆိုတော့ပြောချင်တာက Huffman Coding ရဲ့အဓိက အလုပ်က Binary Sequence တွေရဲ့ အကြိမ်ရေကို အသုံးပြုပြီး အကြိမ်ရေပိုများများပါတဲ့ Binary တွေကို ပိုနည်းတဲ့ bits တွေဖြစ်အောင်လုပ်လိုက်ဖို့ပါပဲ။ ဒါပေမယ့် ဒီလိုချုံ့ထားတဲ့ Binary Sequence အသစ်ကို ပြန်ဖြည်ဖို့ကတော့ သူ့ကိုဆောက်ထားတဲ့ Tree Diagram ကိုတော့ သိဖို့လိုတယ်။
အဲ့အတွက်ကြောင့် BANANA လိုမျိုး Data နည်းနည်းလေးပဲပါတဲ့ စာတွေကိုတော့ ချုံ့ဖို့ဆိုတာ မဖြစ်နိုင်တဲ့ အားနည်းချက်တော့ ရှိပါတယ်။ Tree Diagram ပါ ပေးရမှာဆိုတော့ ပိုကြီးသွားနိုင်တာပေါ့။ မယုံရင် BANANA ဆိုတဲ့ စာကို Text File ထဲသိမ်းပြီး အဲ့ဖိုင်ကို Zip ချုံ့ကြည့်ပါ။ မူရင်းထပ် ပိုများနေတာတွေ့ပါလိမ့်မယ်။
ဆိုဒ်ကြီးတာတွေကိုချုံ့ရင်တော့ ပိုသိသာတဲ့ ရလဒ်တစ်ခုတွေ့ရပါလိမ့်မယ်။ အဲ့တာတောင်မှ ပါဝင်တဲ့ ဒေတာပေါ်မူတည်ပြီး ကွဲပါသေးတယ်။ BANANA ဆိုတဲ့ စာကြီးပဲ 1 GB လောက်ရှိအောင် ရိုက်ထားပြီး Zip ချုံ့လိုက်ရင် ဆိုဒ်က တော်တော်သေးသွားမှာပါ။ ဒါပေမယ့် 1GB လောက်ရှိတဲ့ ဝတ္ထုတစ်အုပ်ကို Zip ချုံ့လိုက်ရင်တော့ အများကြီး သေးသွားလိမ့်မယ်လို့ မျှော်လင့်လို့ မရပါဘူး။ အဓိကက ပါဝင်တဲ့ Binary Sequence ရဲ့ အကြိမ်ရေတွေကြောင့်ပါ။
ပြီးတော့ ကျွန်တော်က Huffman Coding နဲ့ ချုံ့တဲ့အခါ စာကို ချုံ့တာကြီး ပြောနေတယ်ဆိုပေမယ့် 8 bit တစ်စုစီပါဝင်တဲ့ မည်သည့် Binary Data မဆို ချုံ့လို့ရပါတယ်နော်။ ဓာတ်ပုံ၊ ရုပ်ရှင်၊ အသံဖိုင်၊ စတာတွေရောပေါ့။ စာကိုပြောတာက UTF-8 English Character တွေက တစ်လုံးကို 8 bit ရှိနေလို့ နမူနာ ပြတဲ့အနေနဲ့ ပြောတာပါ။
ဆိုတော့ကာ Lossless Data Compression အမျိုးအစားထဲက Huffman Coding ရဲ့အကြောင်းလေးကတော့ ဒီလောက်ပါပဲ။ အလုပ်လုပ်ပုံလေးကိုတော့ Video ထဲမှာ ဆက်လက်လေ့လာကြည့်ပေးပါ။
ဖတ်ရှုပေးတဲ့အတွက် ကျေးဇူးအများကြီးတင်ပါတယ်။ အမှားများပါခဲ့တယ်ဆိုရင်လည်း ဝင်ရောက်ထောက်ပြ ဆွေးနွေးအကြံပြုပေးကြပါဦးနော်။ တစ်ခြားသိလိုတာလေးတွေရှိရင်လဲ ကွန်းမန့်မှာ မေးခဲ့လို့ရပါတယ်။ တစ်သုည Facebook Page ကိုလည်း Like and Follow လုပ်ထားလို့ ရပါတယ်။
အခြေခံ ကွန်ပျူတာ သိပ္ပံ အပါအဝင် Programming ကို စလုံးရေးစက လေ့လာချင်တယ်ဆိုရင်လည်း ကျွန်တော် သင်တန်းလေးဖွင့်ထားပါတယ်။ အသေးစိတ်ကို ဒီကနေ စုံစမ်းကြည့်လို့ရပါတယ်နော်။
ကျေးဇူးတင်ပါတယ်ခင်ဗျာ
-တစ်သုည-
