Адаптивті Хаффман кодилеуі: FGK және Vitter алгоритмдері
Adaptive Huffman coding
Адаптивті Хаффман коделеуі – деректерді қысудың тиімді әдісі. Бұл онлайн кодирование техникасы деректерді жылдам өңдеуге, өзгерістерге бейімделуге мүмкіндік береді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Деректерді сығыстыру техникасы. Адаптациялық Хаффман коды (Динамикалық Хаффман коды деп те аталады) – Хаффман кодына негізделген адаптивті кодтау техникасы. Ол символдар беріліп жатқанда кодты құруға мүмкіндік береді, дереккөз таралуы туралы алдын ала білімді қажет етпейді, соның арқасында деректерді бір рет өте кодтап, өзгеріп отыратын жағдайларға бейімделуге болады. Бір реттік процедураның артықшылығы – дереккөзді нақты уақытта кодтау мүмкіндігі, алайда ол беріліс қателерге өте сезімтал, себебі бір ғана қате бүкіл кодты жояды, сондықтан қателерді анықтау және түзету қажет болады.
Data compression technique
Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one pass encoding and adaptation to changing conditions in data. The benefit of one pass procedure is that the source can be encoded in real time, though it becomes more sensitive to transmission errors, since just a single loss ruins the whole code, requiring error detection and correction.
Алгоритмдер
Бұл әдістің бірнеше іске асырылуы бар, олардың ең белгілілері FGK (Faller Gallager Knuth) және Виттер алгоритмі.
There are a number of implementations of this method, the most notable are FGK (Faller Gallager Knuth) and Vitter algorithm.
FGK алгоритмі
Бұл Хаффман кодтамасына негізделген онлайн кодтау техникасы. Кездесу жиіліктері туралы алдын ала білімі болмағандықтан, деректерді беру кезінде Хаффман ағашын динамикалық түрде реттеуге мүмкіндік береді. FGK Хаффман ағашында 0 түйіні деп аталатын арнайы сыртқы түйін, жаңадан келетін символді анықтау үшін қолданылады. Яғни, жаңа деректер кездескен кезде, 0 түйініне дейінгі жол шығарылып, содан кейін деректер шығарылады. Бұрыннан келіп түскен символ үшін, ағымдағы Хаффман ағашындағы деректердің жолы ғана шығарылады. Ең маңыздысы, қажет болған жағдайда FGK Хаффман ағашын түзетуіміз керек, соңында тиісті түйіндердің жиілігін жаңартуымыз керек. Деректердің жиілігі артқан сайын, Хаффман ағашының бауырлас қасиеті бұзылуы мүмкін. Осы себепті түзету іске қосылады. Бұл түйіндерді, кіші ағаштарды немесе олардың екеуін де тізбектей алмастыру арқылы жүзеге асырылады. Деректер түйіні, Хаффман ағашындағы (немесе ең жоғары реттелген түйінде тамырланған кіші ағаштағы) бірдей жиіліктегі ең жоғары реттелген түйінмен ауыстырылады. Түйіннің барлық аталық түйіндері де осылай өңделуі керек. FGK алгоритмінің түйін немесе кіші ағашты алмастыруға қатысты кемшіліктері болғандықтан, Виттер оны жақсарту үшін басқа алгоритм ұсынды.
It is an online coding technique based on Huffman coding. Having no initial knowledge of occurrence frequencies, it permits dynamically adjusting the Huffman's tree as data are being transmitted. In a FGK Huffman tree, a special external node, called 0 node, is used to identify a newly coming character. That is, whenever new data is encountered, output the path to the 0 node followed by the data. For a past coming character, just output the path of the data in the current Huffman's tree. Most importantly, we have to adjust the FGK Huffman tree if necessary, and finally update the frequency of related nodes. As the frequency of a datum is increased, the sibling property of the Huffman's tree may be broken. The adjustment is triggered for this reason. It is accomplished by consecutive swappings of nodes, subtrees, or both. The data node is swapped with the highest ordered node of the same frequency in the Huffman's tree, (or the subtree rooted at the highest ordered node). All ancestor nodes of the node should also be processed in the same manner. Since the FGK Algorithm has some drawbacks about the node or subtree swapping, Vitter proposed another algorithm to improve it.