Хьюффман коделеуі: деректерді қысу әдісі

Кіріспе

Деректерді сығыстыру техникасы

Компьютерлік ғылым және ақпарат теориясында Хэффман коды – деректерді жоғалтпай сығыстыру үшін жиі қолданылатын оптималды префикс кодының бір түрі. Мұндай кодты табу немесе қолдану процесі Хэффман кодтау деп аталады, бұл алгоритм Дэвид А. Хэффман MIT-де докторын қорғаған кезінде жасаған және 1952 жылы «Минималдық артықтықтың кодтарын құру әдісі» деген мақаласында жариялаған. Хэффман алгоритмінің нәтижесін бастапқы символдарды (мысалы, файлдағы әріптерді) кодтауға арналған өзгермелі ұзындығы бар код кестесі ретінде қарастыруға болады. Алгоритм бұл кестені бастапқы символдың әрбір мүмкін мәнінің болжамды ықтималдығы немесе жиілігі (салмағы) негізінде құрастырады. Басқа энтропиялық кодтау әдістеріндегідей, жиі кездесетін символдар көбінесе сирек кездесетін символдарға қарағанда аз биттермен бейнеленеді. Хэффман әдісін тиімді жүзеге асыруға болады, егер салмақтар сұрыпталған болса, кіріс салмақтарының санына пропорционал уақытта код табуға болады. Дегенмен, символдарды жеке-жеке кодтау әдістері арасында оптималды болғанымен, Хэффман кодтау барлық сығыстыру әдістерінің арасында әрдайым оптималды болып табылмайды – жақсы сығыстыру қатынасы қажет болған жағдайда, оны арифметикалық кодтау немесе асимметриялық сандық жүйелермен алмастыруға болады.

Тарих

1951 жылы Дэвид А. Хаффман мен оның MIT ақпараттық теориясы бойынша оқысқан сыныптастарына курстық жұмыс жазу немесе қорытынды емтихан тапсыру мүмкіндігі берілді. Профессор Роберт Фану ең тиімді екілік кодты табу мәселесін зерттеу бойынша курстық жұмыс тапсырды. Хаффман, ешқандай кодтың ең тиімді екенін дәлелдей алмағандықтан, емтиханға дайындалуға кіріспей жатып, жиілігі бойынша сұрыпталған екілік ағаш пайдалану идеясын ойлап тапты және бұл әдістің ең тиімді екенін тез дәлелдеді. Осылайша Хаффман, Клод Шеннонмен бірлесіп ұқсас кодты жасаған Фанодан озып кетті. Ағашты төменнен құру Шеннон-Фано кодтамасының жоғарыдан төменге қарайғы тәсілінен өзгеше, оңтайлылықты қамтамасыз етті.

Терминология

Хаффман кодтамасы әрбір символдың бейнеленуі үшін нақты бір әдіс қолданады, нәтижесінде префикс код пайда болады (кейде "префиксі жоқ кодтар" деп те аталады, яғни, қандай да бір символды білдіретін бит тізбегі ешқашан басқа символды білдіретін бит тізбегінің басы болмайды). Хаффман кодтау – префикс кодтарды жасаудың өте кең таралған әдісі, сондықтан "Хаффман коды" термині "префикс код" сөзімен бір мағынада қолданылады, тіпті егер мұндай код Хаффман алгоритмі арқылы жасалмаса да.

Бейресми сипаттама

Символдар жиынтығы және олардың салмақтары берілген (әдетте, ықтималдыққа пропорционалды). Префиксі жоқ екілік кодты (код сөздерінің жиынтығын) ең аз күтілетін код сөз ұзындығымен табыңыз (теңдесінен, тамырдан ең аз салмақталған жол ұзындығына ие ағаш).

Ресми сипаттама

Кіріс. Әліппе, бұл символдар әліппесі, өлшемі .
Тюпл, бұл (оң) символ салмақтарының (әдетте ықтималдықтарға пропорционалды) тізімі, яғни .

Шығыс. Код, бұл (бинарлық) код сөздерінің тізімі, мұнда - символының код сөзі.

Мақсат. Кодтың салмақталған жол ұзындығы болсын .
Шарты: кез келген код үшін .

Декомпрессия

Жалпы алғанда, декомпрессия процесі – префикс кодтары ағынын жеке байт мәндеріне аудару ғана, әдетте кіріс ағынынан әр бит оқылғанда Хэффман ағашының түйінін түйінмен кесіп өту арқылы (жапырақ түйініне жету сол байт мәнін іздеуді міндетті түрде тоқтатады). Бірақ, бұған дейін Хэффман ағашын қалпына келтіру қажет. Ең қарапайым жағдайда, егер символдардың жиілігі болжамды болса, ағаш алдын ала құрастырылуы мүмкін (тіпті әрбір сығылу циклында статистикалық түрде түзетілуі мүмкін) және осылайша әрқашан қайта қолданылуы мүмкін, бірақ сығылу тиімділігінің белгілі бір деңгейінен айырылуы мүмкін. Әйтпесе, ағашты қалпына келтіру үшін қажетті ақпарат алдын ала жіберілуі керек. Наive тәсіл – әр символдың жиілік санын сығылу ағынына қосу. Алайда, мұндай жағдайда қосымша шығын бірнеше килобайтқа жете алады, сондықтан бұл әдіс іс жүзінде пайдалы емес. Егер деректер канондық кодтау арқылы сығылса, сығылу моделін ақпараттың тек бірнеше битімен дәл қалпына келтіруге болады (мұнда B – символға шаққандағы биттер саны). Тағы бір әдіс – Хэффман ағашын біртіндеп, биттен бітке, шығыс ағынына қосу. Мысалы, егер 0 мәні ата-ана түйінді, ал 1 – жапырақ түйінді білдірсе, соңғысы кездескенде ағаш құрастыру процедурасы келесі 8 битті оқып, сол жапырақтың символдік мәнін анықтайды. Бұл процесс соңғы жапырақ түйініне жеткенге дейін рекурсивті түрде жалғасады; сол кезде Хэффман ағашы адал түрде қалпына келтіріледі. Мұндай әдіс қолданылғандағы қосымша шығын шамамен 2-ден 320 байтқа дейін болуы мүмкін (8 биттік әліпбиді ескере отырып). Тағы да көптеген техникалар бар. Қалай болғанда да, сығылған деректерде пайдаланылмаған "қалдық биттер" болуы мүмкін болғандықтан, декомпрессор шығаруды қашан тоқтату керектігін анықтай білуі керек. Бұл сығылу моделімен бірге декомпрессияланған деректердің ұзындығын беру арқылы немесе енгізудің соңына жеткенін білдіретін арнайы кодтық символді анықтау арқылы жүзеге асырылуы мүмкін (бірақ соңғы әдіс код ұзындығының оптималдығына кері әсер етуі мүмкін).

Generally speaking, the process of decompression is simply a matter of translating the stream of prefix codes to individual byte values, usually by traversing the Huffman tree node by node as each bit is read from the input stream (reaching a leaf node necessarily terminates the search for that particular byte value). Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori. A naive approach might be to prepend the frequency count of each character to the compression stream. Unfortunately, the overhead in such a case could amount to several kilobytes, so this method has little practical use. If the data is compressed using canonical encoding, the compression model can be precisely reconstructed with just bits of information (where B is the number of bits per symbol). Another method is to simply prepend the Huffman tree, bit by bit, to the output stream. For example, assuming that the value of 0 represents a parent node and 1 a leaf node, whenever the latter is encountered the tree building routine simply reads the next 8 bits to determine the character value of that particular leaf. The process continues recursively until the last leaf node is reached; at that point, the Huffman tree will thus be faithfully reconstructed. The overhead using such a method ranges from roughly 2 to 320 bytes (assuming an 8 bit alphabet). Many other techniques are possible as well. In any case, since the compressed data can include unused "trailing bits" the decompressor must be able to determine when to stop producing output. This can be accomplished by either transmitting the length of the decompressed data along with the compression model or by defining a special code symbol to signify the end of input (the latter method can adversely affect code length optimality, however).

Негізгі қасиеттері

Қолданылатын ықтималдықтар қолданыс саласы үшін орташа тәжірибеге негізделген жалпылама ықтималдықтар немесе сығылатын мәтінде табылған нақты жиіліктер болуы мүмкін. Бұл жағдайда жиілік кестесі сығылған мәтінмен бірге сақталуы тиіс. Осы мақсатта қолданылатын әртүрлі техникалар туралы толық ақпаратты жоғарыдағы «Декомпрессия» бөлімінен қараңыз.

Оптималдылық

Хаффманның бастапқы алгоритмі белгілі кіріс ықтималдық үлестірімімен символ бойынша кодтау үшін оңтайлы, яғни осындай дерек ағынында байланыссыз символдарды жеке-жеке кодтау. Дегенмен, символ бойынша кодтау шектеуі алынса немесе ықтималдық массалық функциялары белгісіз болса, ол оңтайлы емес. Сондай-ақ, егер символдар тәуелсіз және бірдей таралмаса, бір код оптималдық үшін жеткіліксіз болуы мүмкін. Арифметикалық кодтау сияқты басқа әдістер көбінесе жақсы қысу мүмкіндігіне ие. Жоғарыда аталған екі әдіс те тиімді кодтау үшін кез келген символдар санын біріктіре алады және әдетте нақты кіріс статистикасына бейімделеді, арифметикалық кодтау оны есептеу немесе алгоритмдік күрделілігін айтарлықтай арттырмай жасайды (дегенмен, ең қарапайым нұсқасы Хаффман кодтауынан баяу және күрделірек болуы мүмкін). Мұндай икемділік, әсіресе, кіріс ықтималдығы нақты белгісіз болғанда немесе ағын ішінде айтарлықтай өзгергенде пайдалы. Бірақ Хаффман кодтамасы көбінесе жылдамырақ болады және арифметикалық кодтама тарихи түрде патенттік мәселелерге байланысты алаңдаушылық тудырды. Сондықтан көптеген технологиялар тарихи түрде арифметикалық кодтамадан бас тартып, Хаффман және басқа префикс кодтау техникаларын пайдаланды. 2010 жылдың ортасына қарай, Хаффман кодтамасына балама ретінде қолданылатын ең көп қолданылатын әдістер алғашқы патенттердің мерзімі өткендіктен, жалпыға қолжетімді болды. Біркелкі ықтималдық үлестірімі бар және саны екінің дәрежесіне тең символдар жиыны үшін Хаффман кодтамасы қарапайым бинарлық блок кодтамасына, мысалы, ASCII кодтамасына тең. Бұл мұндай кіріспен қысу мүмкін емес екенін көрсетеді, қысу әдісіне қарамастан, яғни деректерге ешқандай өзгеріс енгізбеу – ең оңтайлы нәрсе. Хаффман кодтамасы барлық жағдайларда, әрбір кіріс символы белгілі тәуелсіз және бірдей таратылған кездейсоқ айнымалы болып табылатын жағдайда, барлық әдістердің арасында оңтайлы болып табылады, оның ықтималдығы екілік болады. Префикс кодтары, соның ішінде Хаффман кодтамасы, кіші алфавиттерде тиімсіз болуға бейім, онда ықтималдықтар көбінесе осы оңтайлы (екілік) мәндердің арасында орналасады. Хаффман кодтамасының ең нашар жағдайы ең ықтимал символдың ықтималдығы 2−1 = 0,5-тен әлдеқайда асып кеткенде туындайды, бұл тиімсіздіктің жоғарғы шегін шектемейді. Бұл тиімсіздікті жою үшін, әлі де Хаффман кодтамасын қолдана отырып, екі байланысты тәсіл бар. Белгілі бір санды символдарды біріктіру («блоктау») көбінесе (әзірге азайта алмай) қысуды арттырады. Блоктың көлемі шексіздікке жақындағанда, Хаффман кодтамасы теориялық тұрғыдан энтропия шегіне, яғни оңтайлы қысуға жақындайды. Дегенмен, символдардың өте үлкен топтарын блоктау практикалық емес, өйткені Хаффман кодінің күрделілігі кодталуға тиіс мүмкіндіктер санына пропорционалды, ал бұл сан блоктың өлшеміне қарай экспоненциалды түрде өседі. Бұл іс жүзінде қолданылатын блоктау мөлшерін шектейді. Көптеген жағдайларда қолданылатын практикалық балама – орындалу ұзындығы кодтау. Бұл техника энтропиялық кодтаудан бұрын бір қадам қосады, атап айтқанда қайталанатын символдарды санау (жұғу), содан кейін оларды кодтау. Бернулли процестерінің қарапайым жағдайы үшін Голомб кодтамасы орындалу ұзындығын кодтау үшін префикс кодтарының арасында оңтайлы болып табылады, бұл факт Хаффман кодтамасының әдістері арқылы дәлелденген. Осыған ұқсас тәсілді модификацияланған Хаффман кодтамасын пайдаланатын факс машиналары қолданады. Алайда, орындалу ұзындығы кодтау басқа қысу технологиялары сияқты көптеген кіріс түрлеріне бейімделмейді.

Huffman's original algorithm is optimal for a symbol by symbol coding with a known input probability distribution, i. e., separately encoding unrelated symbols in such a data stream. However, it is not optimal when the symbol by symbol restriction is dropped, or when the probability mass functions are unknown. Also, if symbols are not independent and identically distributed, a single code may be insufficient for optimality. Other methods such as arithmetic coding often have better compression capability. Although both aforementioned methods can combine an arbitrary number of symbols for more efficient coding and generally adapt to the actual input statistics, arithmetic coding does so without significantly increasing its computational or algorithmic complexities (though the simplest version is slower and more complex than Huffman coding). Such flexibility is especially useful when input probabilities are not precisely known or vary significantly within the stream. However, Huffman coding is usually faster and arithmetic coding was historically a subject of some concern over patent issues. Thus many technologies have historically avoided arithmetic coding in favor of Huffman and other prefix coding techniques. As of mid 2010, the most commonly used techniques for this alternative to Huffman coding have passed into the public domain as the early patents have expired. For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding, e. g., ASCII coding. This reflects the fact that compression is not possible with such an input, no matter what the compression method, i. e., doing nothing to the data is the optimal thing to do. Huffman coding is optimal among all methods in any case where each input symbol is a known independent and identically distributed random variable having a probability that is dyadic. Prefix codes, and thus Huffman coding in particular, tend to have inefficiency on small alphabets, where probabilities often fall between these optimal (dyadic) points. The worst case for Huffman coding can happen when the probability of the most likely symbol far exceeds 2−1 = 0.5, making the upper limit of inefficiency unbounded. There are two related approaches for getting around this particular inefficiency while still using Huffman coding. Combining a fixed number of symbols together ("blocking") often increases (and never decreases) compression. As the size of the block approaches infinity, Huffman coding theoretically approaches the entropy limit, i. e., optimal compression. However, blocking arbitrarily large groups of symbols is impractical, as the complexity of a Huffman code is linear in the number of possibilities to be encoded, a number that is exponential in the size of a block. This limits the amount of blocking that is done in practice. A practical alternative, in widespread use, is run length encoding. This technique adds one step in advance of entropy coding, specifically counting (runs) of repeated symbols, which are then encoded. For the simple case of Bernoulli processes, Golomb coding is optimal among prefix codes for coding run length, a fact proved via the techniques of Huffman coding. A similar approach is taken by fax machines using modified Huffman coding. However, run length coding is not as adaptable to as many input types as other compression technologies.

Вариациялар

Хаффман кодтамасының көптеген түрлері бар, олардың кейбіреулері Хаффманға ұқсас алгоритмді пайдаланады, ал басқалары оңтайлы префикс кодтарын анықтайды (мысалы, нәтижеге түрлі шектеулер қойып). Аталған екінші жағдайда, әдіс міндетті түрде Хаффманға ұқсас болуы керек емес, тіпті полиномиалды уақытта жұмыс істеуі де міндетті емес.

n-ary Хэффман коды

N-арлық Хаффман алгоритмі хабарды кодтау және n-арлық ағаш құру үшін {0, 1, …, n − 1} алфавитін пайдаланады. Бұл тәсілді Хаффман өзінің түпкілікті мақаласында қарастырған. Бинарлық кодтарға қолданылатын алгоритмнің өзі қолданылады, тек ең аз ықтимал n символдары ең аз ықтимал 2 символдың орнына бірге алынады. n 2-ден үлкен болған жағдайда, бастапқы сөздердің барлық жиынтығы Хаффман кодтау үшін n-арлық ағашты дұрыс құра алмайды. Мұндай жағдайларда, қосымша 0 ықтималдығы бар орны толтырушылар қосылуы керек. Себебі ағаш n-ден 1-ге дейінгі қысқартушы болуы керек; бинарлық кодтау үшін бұл 2-ден 1-ге дейінгі қысқартушы, ал кез келген өлшемдегі жиын мұндай қысқартушыны құра алады. Егер бастапқы сөздердің саны n-1 модулі бойынша 1-ге конгруэнтті болса, онда бастапқы сөздердің жиынтығы дұрыс Хаффман ағашын құрайды.

Адаптациялық Хаффман коды

Адаптивті Хаффман кодтамасы деп аталатын түрі, бастапқы символдар тізбегіндегі соңғы нақты жиіліктерге сүйене отырып, ықтималдықтарды динамикалық түрде есептеуді және жаңартылған ықтималдық бағалауларына сай кодтау ағашының құрылымын өзгертуді қамтиды. Ол практикада сирек қолданылады, себебі ағашты жаңартуға кететін шығын, оны жақсырақ қысылатын және икемдірек оптимизацияланған адаптивті арифметикалық кодтамадан баяу жасайды.

Хаффман үлгі алгоритмі

Көбінесе Хаффман кодтауын іске асыруда қолданылатын салмақтар сандық ықтималдықтарды көрсетеді, бірақ жоғарыда келтірілген алгоритм мұны қажет етпейді; ол салмақтардың толық реттелген коммутативтік моноидты құрауын ғана талап етеді, яғни салмақтарды салыстыру және оларды қосу мүмкіндігін. Хаффман алгоритмінің негізгі үлгісі кез келген салмақты (құн, жиілік, салмақтар жұбы, сандық емес салмақтар) және әртүрлі біріктіру әдістерін (тек қосу ғана емес) қолдануға болады. Мұндай алгоритмдер басқа да минимумдау мәселелерін шеше алады, мысалы, схемаларды жобалауда алғаш рет қолданылған мәселені.

Ұзындығы шектеулі Хэффман коды/минималды ауытқу Хэффман коды

Ұзындығы шектеулі Хаффман кодировкасы – мақсаты әлі де ең аз салмақталған жол ұзындығына қол жеткізу болып табылады, бірақ әрбір код сөзінің ұзындығы белгілі бір тұрақтыдан кем болуы керек деген қосымша шектеу бар. Пакеттерді біріктіру алгоритмі бұл мәселені Хаффман алгоритміне өте ұқсас қарапайым ашкөз тәсілмен шешеді. Оның уақыт күрделілігі O(n log n), мұнда n – код сөзінің ең үлкен ұзындығы. Алдын ала сұрыпталған және сұрыпталмаған дәстүрлі Хаффман мәселелерінен айырмашылығы, бұл мәселені O(n) немесе O(n log n) уақытында шешетін ешқандай алгоритм белгілі емес.

Хат шығыны тең емес Хэфман кодтамасы

Стандартты Хаффман кодтау мәселесінде код сөздерін құрайтын жиынтықтағы әрбір символдың тарату құны бірдей деп есептеледі: N цифрлы код сөздің құны әрқашан N болады, бұл цифрлардың нешесі 0, нешесі 1 және т.б. Бұл ереже бойынша жұмыс істегенде, хабарламаның жалпы құнын азайту және цифрлардың жалпы санын азайту бірдей мақсатқа жетеді. Әріптердің құны әртүрлі Хаффман кодтау – бұл ережеден бас тартатын жалпылау: кодтау әліпбиінің әріптері тарату ортасының ерекшеліктеріне байланысты әртүрлі ұзындықта болуы мүмкін. Мысалы, Морзе кодтау әліпбиінде "сызықша" "нүктеден" ұзақ уақытқа созылады, сондықтан тарату кезіндегі "сызықшаның" құны жоғары. Мақсат әлі де орташа салмақталған код сөздерінің ұзындығын азайту болып табылады, бірақ хабарламада қолданылатын символдар санын ғана азайту жеткіліксіз. Оны дәстүрлі Хаффман кодтау сияқты бірдей әдіспен немесе тиімділікпен шешетін алгоритм әзірленбеген, бірақ оны Карп шешкен, ал оның шешімі Голин тарапынан бүтін санмен өлшенетін құн үшін жақсартылған.

Оптималды әліпбилік екілік ағаштар (HuTucker кодтамасы)

Стандартты Хаффман кодтау мәселесінде кез келген код сөзі кез келген кіріс символына сәйкес келуі мүмкін деп есептеледі. Әліпбилік нұсқасында кіріс және шығыс символының әліпбилік реті толықтай сәйкес болуы керек. Осылайша, мысалы, символға код тағайындауға болмайды, оның орнына немесе кодтары тағайындалуы тиіс. Бұл мәселе Т.С. Ху мен Алан Такердің есімімен аталады, олар осы оңтайлы екілік әліпбилік мәселені алғаш рет шешкен. Бұл алгоритмнің өзгеруі емес, бірақ Хаффман алгоритмімен кейбір ұқсастықтары бар. Кейінірек Адриано Гарсия мен Мишель Л. Вахс (1977) жасаған Гарсия-Вахс алгоритмі, сол уақыт шегінде сол салыстыруларды жасау үшін қарапайым логика қолданады. Бұл оңтайлы әліпбилік екілік ағаштар көбінесе екілік іздеу ағаштары ретінде пайдаланылады.

Каноникалық Хаффман коды

Егер әліпбилік ретпен берілген кірістерге сәйкес келетін салмақтар сандық ретпен орналасса, Хэффман коды оңтайлы әліпбилік кодтың ұзындығымен бірдей болады, оны осы ұзындықтарды есептеу арқылы табуға болады, бұл Hu-Tucker кодтауын қажетсіз етеді. Сандық (қайта) реттелген кірістен алынған код кейде канондық Хэффман коды деп аталады және оңай кодтау/декодтау мүмкіндігіне байланысты практикада жиі қолданылады. Бұл кодты табу әдісі кейде Хэффман-Шеннон-Фано кодтау деп аталады, себебі ол Хэффман кодтау сияқты оңтайлы, бірақ салмақ бойынша ықтималдыққа қатысты әліпбилік, Шеннон-Фано кодтау сияқты. Мысалға сәйкес Хэффман-Шеннон-Фано коды - , ол бастапқы шешіммен бірдей код сөздерінің ұзындығына ие, демек оңтайлы. Бірақ канондық Хэффман кодында нәтиже .

Қолданбалар

Арифметикалық кодтау және Хаффман кодтау тең нәтиже береді – энтропияға қол жеткізу – әрбір символдың 1/2k ықтималдығы болған кезде. Басқа жағдайларда арифметикалық кодтау Хаффман кодтаудан жақсы қысу мүмкіндігін ұсынады, себебі интуитивті түрде оның "код сөздері" іс жүзінде бүтін емес бит ұзындығына ие болуы мүмкін, ал Хаффман кодтары сияқты префикс кодтарындағы код сөздері тек толық бит санына ие болуы мүмкін. Сондықтан, ұзындығы k код сөз 1/2k ықтималдығы бар символға ғана оңтайлы сәйкес келеді, ал басқа ықтималдықтар оңтайлы көрсетілмейді; ал арифметикалық кодтауда код сөз ұзындығы символдың нақты ықтималдығымен дәл сәйкес келуі мүмкін. Бұл айырмашылық әсіресе кішкентай алфавиттер үшін айқын байқалады. Дегенмен, префикс кодтары қарапайымдылығы, жоғары жылдамдығы және патенттік қорғаудың болмауы себепті кеңінен қолданылады. Олар көбінесе басқа қысу әдістерінің "соңғы бөлігі" ретінде қолданылады. Deflate (PKZIP алгоритмі) және JPEG және MP3 сияқты мультимедиялық кодектерде алдыңғы модель және кванттаудан кейін префикс кодтары қолданылады; олар көбінесе "Хаффман кодтары" деп аталады, бірақ көптеген қолданбалар Хаффман алгоритмімен жасалған кодтардың орнына алдын ала анықталған өзгермелі ұзындығы бар кодтарды пайдаланады.