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

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.

ഇൻഫർമേഷൻ തിയറിയിൽ ഉള്ളടക്കം നഷ്ടപ്പെടാതെ വിവരത്തെ ചുരുക്കുന്നതിനുപയോഗിക്കുന്ന ഒരു രീതിയാണ് ഹഫ്‌മാൻ കോഡിങ്. എം.ഐ.ടിയിൽ പി.എച്.ഡി. വിദ്യാർത്ഥിയായിരുന്ന കാലഘട്ടത്തിൽ ഡേവിഡ് ഹഫ്‌മാനാണ് ഈ രീതി ആവിഷ്കരിക്കുകയും, "A Method for the Construction of Minimum-Redundancy Codes" എന്ന പ്രബന്ധത്തിലൂടെ പ്രസിദ്ധീകരിക്കുകയും ചെയ്തത്. ഒരു അസ്ഥിരമായ കോഡിങ് രീതിയായ ഇതിൽ ഓരോ അക്ഷരത്തിനും അതിന്റെ സംഭാവ്യസാധ്യത അനുസരിച്ചുള്ള വലിപ്പത്തിലെ കോഡ് ആയിരിക്കും നൽകുന്നത്. വാക്യത്തിൽ ഏറ്റവുമധികം വരുന്ന അക്ഷരത്തിനു ഏറ്റവും ചെറിയ കോഡ്‌വേഡും, ഏറ്റവും കുറവു വരാൻ സാധ്യതയുള്ളതിനു ഏറ്റവും വലിയ കോഡ്‌വേഡും നൽകുന്നു. ഹഫ്‌മാൻ ട്രീ എന്ന പേരിലെ ഒരു ട്രീ ഡാറ്റാ സ്ട്രക്ചർ ഇതിന്റെ കോഡിങ്-ഡോകോഡിങ് പ്രക്രിയയിലുടനീളം ഉപയോഗിക്കുന്നു.

നിർവ്വചനം[തിരുത്തുക]

ഹഫ്‌മാൻ ട്രീയുടെ നിർമ്മാണം

ഇൻഫോർമൽ നിർവചനം[തിരുത്തുക]

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

ഫോർമൽ നിർവചനം[തിരുത്തുക]

ഇൻപുട്ട്.
അക്ഷരമാല , n, വലിപ്പമുള്ള ഗണം
, അക്ഷരമാല ഗണത്തിലെ അക്ഷരങ്ങൾക്കുള്ള സാധ്യതകൾ, i.e. .

Output.
Code , കോഡ് വേഡാകുമ്പോൾ തതുല്യ ടൂപിളുകളുടെ ഗണം .

Goal.
Let be the weighted path length of code . Condition: for any code .


Char Freq Code
space 7 111
a 4 010
e 4 000
f 3 1101
h 2 1010
i 2 1000
m 2 0111
n 2 0010
s 2 1011
t 2 0110
l 1 11001
o 1 00110
p 1 10011
r 1 11000
u 1 00111
x 1 10010
"https://ml.wikipedia.org/w/index.php?title=ഹഫ്‌മാൻ_കോഡിങ്&oldid=2362273" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്