ഹഫ്‌മാൻ കോഡിങ്

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Huffman_coding

ഇൻഫർമേഷൻ തിയറിയിൽ ഉള്ളടക്കം നഷ്ടപ്പെടാതെ വിവരത്തെ ചുരുക്കുന്നതിനുപയോഗിക്കുന്ന ഒരു രീതിയാണ് ഹഫ്‌മാൻ കോഡിങ്. എം.ഐ.ടിയിൽ Sc.D.(Doctor of science) വിദ്യാർത്ഥിയായിരുന്ന കാലഘട്ടത്തിൽ ഡേവിഡ് ഹഫ്‌മാനാണ് ഈ രീതി ആവിഷ്കരിക്കുകയും, "എ മെത്തേഡ് ഫോർ കൺസ്ട്രക്ഷൻ ഓഫ് മിനിമം-റിഡൻഡൻസി കോഡ്സ്" എന്ന പ്രബന്ധത്തിലൂടെ പ്രസിദ്ധീകരിക്കുകയും ചെയ്തത്.^[1] ഒരു അസ്ഥിരമായ കോഡിങ് രീതിയായ ഇതിൽ ഓരോ അക്ഷരത്തിനും അതിന്റെ സംഭാവ്യസാധ്യത അനുസരിച്ചുള്ള വലിപ്പത്തിലെ കോഡ് ആയിരിക്കും നൽകുന്നത്. വാക്യത്തിൽ ഏറ്റവുമധികം വരുന്ന അക്ഷരത്തിനു ഏറ്റവും ചെറിയ കോഡ്‌വേഡും, ഏറ്റവും കുറവു വരാൻ സാധ്യതയുള്ളതിനു ഏറ്റവും വലിയ കോഡ്‌വേഡും നൽകുന്നു. ഹഫ്‌മാൻ ട്രീ എന്ന പേരിലെ ഒരു ട്രീ ഡാറ്റാ സ്ട്രക്ചർ ഇതിന്റെ കോഡിങ്-ഡോകോഡിങ് പ്രക്രിയയിലുടനീളം ഉപയോഗിക്കുന്നു.

ഒരു സോഴ്സ് സിംബൽ എൻകോഡ് ചെയ്യുന്നതിനുള്ള വേരിയബിൾ-ലെങ്ത് കോഡ് ടേബിളായി ഹഫ്മാന്റെ അൽഗോരിതത്തിൽ നിന്നുള്ള ഔട്ട്പുട്ട് കാണാൻ കഴിയും (ഒരു ഫയലിലെ സിമ്പൽ പോലെ). സോഴ്സ് ചിഹ്നത്തിന്റെ സാധ്യമായ ഓരോ മൂല്യത്തിനും വേണ്ടി കണക്കാക്കിയ പ്രോബബിലിറ്റിയിൽ നിന്നോ ഫ്രിക്വൻസി ഓഫ് ഒക്കറൻസിൽ (ഭാരം) നിന്നോ അൽഗോരിതം ഈ പട്ടിക ഉണ്ടാക്കുന്നു. മറ്റ് എൻട്രോപ്പി എൻകോഡിംഗ് രീതികളിലെന്നപോലെ, സാധാരണ ചിഹ്നങ്ങളേക്കാൾ കുറച്ച് ബിറ്റുകൾ ഉപയോഗിച്ചാണ് സാധാരണയായി പ്രതിനിധീകരിക്കുന്നത്. ഈ ഭാരങ്ങൾ അടുക്കിയാൽ ഇൻപുട്ട് വെയ്റ്റുകളുടെ എണ്ണത്തിന് ലീനിയർ കോഡ് കണ്ടെത്തുന്നതിലൂടെ ഹഫ്മാന്റെ രീതി കാര്യക്ഷമമായി നടപ്പിലാക്കാൻ കഴിയും.^[2]

നിർവ്വചനം

ഇൻഫോർമൽ നിർവചനം

നൽകിയിരിക്കുന്നത്: ഒരു കൂട്ടം അക്ഷരങ്ങളും അവയുടെ സാധ്യതകളും (പ്രോബബിലിറ്റി)
കണ്ടെത്തേണ്ടത്: ഒരു ഹഫ്‌മാൻ ട്രീ. ഇതിൽ ലീഫിനടുത്തുള്ള അക്ഷരങ്ങൾക്ക് സാധ്യത ഏറ്റവും വിരളവും, റൂട്ടിനടുത്തേക്കു പോകുമ്പോൾ കൂടിയും വരണം

ഫോർമൽ നിർവചനം

ഇൻപുട്ട്.
അക്ഷരമാല $A=\left\{a_{1},a_{2},\cdots ,a_{n}\right\}$ , n, വലിപ്പമുള്ള ഗണം
$W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}$ , അക്ഷരമാല ഗണത്തിലെ അക്ഷരങ്ങൾക്കുള്ള സാധ്യതകൾ, i.e. $w_{i}=\mathrm {weight} \left(a_{i}\right),1\leq i\leq n$ .

Output.
Code $C\left(A,W\right)=(c_{1},c_{2},\cdots ,c_{n})$ , $c_{i}$ കോഡ് വേഡാകുമ്പോൾ തതുല്യ ടൂപിളുകളുടെ ഗണം $a_{i},1\leq i\leq n$ .

Goal.
Let $L\left(C\right)=\sum _{i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}$ be the weighted path length of code $C$ . Condition: $L\left(C\right)\leq L\left(T\right)$ for any code $T\left(A,W\right)$ .