Äèíàìè÷åñêîå ñæàòèå ìåòîäîì Õàôôìàíà

Äàííàÿ ñòàòüÿ ïðåäïîëàãàåò, ÷òî ÷èòàòåëü çíàêîì ñ ïðèíöèïàìè ñæàòèÿ äàííûõ ïðè ïîìîùè àëãîðèòìà Õàôôìàíà. Ñóòü àëãîðèòìà çàêëþ÷àåòñÿ â òîì, ÷òî ñèìâîëû ïî÷òè ëþáîãî àëôàâèòà èìåþò ðàçíóþ âåðîÿòíîñòü ïîÿâëåíèÿ â òåêñòå. Äëÿ ïðèìåðà - â ðóññêîì ÿçûêå áóêâà "À" âñòðå÷àåòñÿ íàìíîãî ÷àùå, ÷åì "Ú". À ó Àëåêñàíäðà Ñåðãååâè÷à Ïóøêèíà - "Ô" - âñòðå÷àåòñÿ âñåãî òðè ðàçà: äâàæäû â "Ñêàçêå î öàðå Ñàëòàíå" è îäèí ðàç â "Ìåäíîì âñàäíèêå". Èòàê, ðàç ðàçíûå ñèìâîëû èìåþò ðàçíûå âåðîÿòíîñòè ïîÿâëåíèÿ, ñëåäîâàòåëüíî, åñëè êîäèðîâàòü èõ íå âñå ïî 8 áèò, êàê îíè õðàíÿòñÿ â ASCII ôîðìàòå, à äëèíó êîäà íàèáîëåå ÷àñòî âñòðå÷àåìûõ óìåíüøèòü çà ñ÷¸ò óâåëè÷åíèÿ äëèíû êîäà ðåäêèõ ñèìâîëîâ - ìîæíî äîâîëüíî íåïëîõî ñæàòü èñõîäíûé òåêñò. Äîêóìåíòàöèè ïî ýòîìó àëãîðèòìó â Èíòåðíåòå öåëîå ìîðå è åù¸ íåáîëüøàÿ ëóæèöà ðàçìåðîì ñ îêåàí÷èê.

Ðàçëè÷èÿ ñòàòè÷åñêîé è äèíàìè÷åñêîé ìîäåëåé

Ïðàêòè÷åñêè âñå ñóùåñòâóþùèå àëãîðèòìû ñæàòèÿ äàííûõ ìîæíî ðåàëèçîâàòü â äâóõ âàðèàíòàõ - ñòàòè÷åñêîì è äèíàìè÷åñêîì. Êàæäûé èç íèõ èìååò ñâî¸ ïðàâî íà æèçíü è, ñîîòâåòñòâåííî, çàíèìàåò îïðåäåë¸ííóþ íèøó, èñïîëüçóÿñü â òåõ ñëó÷àÿõ, êîãäà îí íàèáîëåå óäîáåí. Àëãîðèòì Õàôôìàíà íå ÿâëÿåòñÿ èñêëþ÷åíèåì - ïðèìåíÿÿñü âî ìíîãèõ è ìíîãèõ àðõèâàòîðàõ è ôîðìàòàõ îí èñïîëüçóåòñÿ èíîãäà â ñòàòè÷åñêîì (JPEG, ARJ) èëè â äèíàìè÷åñêîì (óòèëèòà compact äëÿ UNIX, ICE) âàðèàíòàõ.

 ÷¸ì æå çàêëþ÷àåòñÿ ðàçëè÷èå ìåæäó ýòèìè äâóìÿ òèïàìè ðåàëèçàöèé? Òàê êàê àëãîðèòì Õàôôìàíà ñæèìàåò äàííûå çà ñ÷¸ò âåðîÿòíîñòåé ïîÿâëåíèÿ ñèìâîëîâ â èñòî÷íèêå, ñëåäîâàòåëüíî äëÿ òîãî ÷òîá óñïåøíî ÷òî-òî ñæàòü è ðàçæàòü íàì ïîòðåáóåòñÿ çíàòü ýòè ñàìûå âåðîÿòíîñòè äëÿ êàæäîãî ñèìâîëà. Ñòàòè÷åñêèå àëãîðèòìû ñïðàâëÿþòñÿ ñ ýòèì äåëîì íå ìóäðñòâóÿ ëóêàâî - ïåðåä òåì êàê íà÷àòü ñæàòèå ôàéëà ïðîãðàììà áûñòðåíüêî ïðîáåãàåòñÿ ïî ñàìîìó ôàéëó è ïîäñ÷èòûâàåò êàêîé ñèìâîë ñêîëüêî ðàç âñòðå÷àåòñÿ. Çàòåì, â ñîîòâåòñòâèè ñ âåðîÿòíîñòÿìè ïîÿâëåíèé ñèìâîëîâ, ñòðîèòñÿ äâîè÷íîå äåðåâî Õàôôìàíà - îòêóäà èçâëåêàþòñÿ ñîîòâåòñòâóþùèå êàæäîìó ñèìâîëó êîäû ðàçíîé äëèíû. È íà òðåòüåì ýòàïå ñíîâà îñóùåñòâëÿåòñÿ ïðîõîä ïî èñõîäíîìó ôàéëó, êîãäà êàæäûé ñèìâîë çàìåíÿåòñÿ íà ñâîé äðåâåñíûé êîä. Òàêèì îáðàçîì ñòàòè÷åñêîìó àëãîðèòìó òðåáóåòñÿ äâà ïðîõîäà ïî ôàéëó èñòî÷íèêó, ÷òîá çàêîäèðîâàòü äàííûå.

Äèíàìè÷åñêèé àëãîðèòì ïîçâîëÿåò ðåàëèçîâàòü îäíîïðîõîäíóþ ìîäåëü ñæàòèÿ. Íå çíàÿ ðåàëüíûõ âåðîÿòíîñòåé ïîÿâëåíèé ñèìâîëîâ â èñõîäíîì ôàéëå - ïðîãðàììà ïîñòåïåííî èçìåíÿåò äâîè÷íîå äåðåâî ñ êàæäûì âñòðå÷àåìûì ñèìâîëîì óâåëè÷èâàÿ ÷àñòîòó åãî ïîÿâëåíèÿ â äåðåâå è ïåðåñòðàèâàÿ â ñâÿçè ñ ýòèì ñàìî äåðåâî. Îäíàêî ñòàíîâèòñÿ î÷åâèäíûì, ÷òî âûèãðàâ â êîëè÷åñòâå ïðîõîäîâ ïî èñõîäíîìó ôàéëó - ìû íà÷èíàåì òåðÿòü â êà÷åñòâå ñæàòèÿ, òàê êàê â ñòàòè÷åñêîì àëãîðèòìå ÷àñòîòû âñòðå÷àåìîñòè ñèìâîëîâ áûëè èçâåñòíû ñ ñàìîãî íà÷àëà è äëèíû êîäîâ ýòèõ ñèìâîëîâ áûëè áîëåå áëèçêè ê îïòèìàëüíûì, â òî âðåìÿ êàê äèíàìè÷åñêàÿ ìîäåëü èçó÷àÿ èñòî÷íèê ïîñòåïåííî äîõîäèò äî åãî ðåàëüíûõ ÷àñòîòíûõ õàðàêòåðèñòèê è óçíà¸ò èõ ëèøü ïîëíîñòüþ ïðîéäÿ èñõîäíûé ôàéë. Êîíå÷íî, îáèäíî, íî ñåé íåäîñòàòîê ìîæíî êîìïåíñèðîâàòü äðóãèì ïðåèìóùåñòâîì äèíàìè÷åñêîãî àëãîðèòìà. Òàê êàê äèíàìè÷åñêîå äâîè÷íîå äåðåâî ïîñòîÿííî ìîäèôèöèðóåòñÿ íîâûìè ñèìâîëàìè - íàì íåò íåîáõîäèìîñòè çàïîìèíàòü èõ ÷àñòîòû çàðàíåå - ïðè ðàçàðõèâèðîâàíèè, ïðîãðàììà, ïîëó÷èâ èç àðõèâà êîä ñèìâîëà, òî÷íî òàê æå âîññòàíîâèò äåðåâî, êàê îíà ýòî äåëàëà ïðè ñæàòèè è óâåëè÷èò íà åäèíè÷êó ÷àñòîòó åãî âñòðå÷àåìîñòè. Áîëåå òîãî, íàì íå òðåáóåòñÿ çàïîìèíàòü êàêèå ñèìâîëû â äâîè÷íîì äåðåâå íå âñòðå÷àþòñÿ. Âñå ñèìâîëû êîòîðûå áóäóò äîáàâëÿòüñÿ â äåðåâî è åñòü òå, êîòîðûå íàì ïîòðåáóþòñÿ äëÿ âîññòàíîâëåíèÿ ïåðâîíà÷àëüíûõ äàííûõ.  ñòàòè÷åñêîì àëãîðèòìå ñ ýòèì äåëîì íåìíîãî ñëîæíåå - â ñàìîì íà÷àëå ñæàòîãî ôàéëà òðåáóåòñÿ õðàíèòü èíôîðìàöèþ î âñòðå÷àåìûõ â ôàéëå èñòî÷íèêå ñèìâîëàõ è èõ âåðîÿòíîñòíûõ ÷àñòîòàõ. Ýòî îáóñëîâëåíî òåì, ÷òî åù¸ äî íà÷àëà ðàçàðõèâèðîâàíèÿ íàì íåîáõîäèìî çíàòü êàêèå ñèìâîëû áóäóò âñòðå÷àòüñÿ è êàêîâ áóäåò èõ êîä.

Íèæå ïðåäñòàâëåíû àëãîðèòìû ðàáîòû ñòàòè÷åñêîãî è äèíàìè÷åñêîãî àðõèâàòîðîâ êîäàìè Õàôôìàíà.

Ñòàòè÷åñêèé àëãîðèòì:
InitTree	' Èíèöèàëèçèðóåì äâîè÷íîå äåðåâî
For i=0 to Ubound(CharCount)
CharCount(i)=0	' Èíèöèàëèçèðóåì ìàññèâ ÷àñòîò ýëåìåíòîâ àëôàâèòà
Next
Do While not EOF(Ôàéë èñòî÷íèê)	' Çàïóñêàåì ïåðâûé ïðîõîä ôàéëà
Get Ôàéë èñòî÷íèê, C	' ×èòàåì òåêóùèé ñèìâîë
CharCount(C)= CharCount(C)+1	' Óâåëè÷èâàåì íà îäèí ÷àñòîòó åãî âñòðå÷àåìîñòè
Loop
ReBuildTree	' Ïî ïîëó÷åííûì ÷àñòîòàì ñòðîèì äâîè÷íîå äåðåâî
WriteTree (Ôàéë ïðè¸ìíèê)	' Çàïèñûâàåì â ôàéë äâîè÷íîå äåðåâî
Do While not EOF(Ôàéë èñòî÷íèê)	' Çàïóñêàåì âòîðîé ïðîõîä ôàéëà
Get Ôàéë èñòî÷íèê, C	' ×èòàåì òåêóùèé ñèìâîë
code=FindCodeInTree(C)	' Íàõîäèì ñîîòâåòñòâóþùèé åìó êîä â äåðåâå
Put Ôàéë ïðè¸ìíèê, code	' Çàïèñûâàåì ïîñëåäîâàòåëüíîñòü áèò â ôàéë
Loop

Ïðîöåäóðà InitTree èíèöèàëèçèðóåò äâîè÷íîå äåðåâî, îáíóëÿÿ çíà÷åíèÿ, âåñà, è óêàçàòåëè íà ðîäèòåëÿ è ïîòîìêîâ òåêóùåãî ëèñòà. Äàëåå âûïîëíÿåòñÿ ïåðâûé ïðîõîä ïî èñòî÷íèêó äàííûõ ñ öåëüþ ïðîâåðêè ÷àñòîòíîñòè ñèìâîëîâ - ðåçóëüòàòû êîòîðîãî çàïîìèíàþòñÿ â ìàññèâ CharCount. Ðàçìåðíîñòü ýòîãî ìàññèâà äîëæíà ðàâíÿòüñÿ êîëè÷åñòâó ýëåìåíòîâ àëôàâèòà èñòî÷íèêà.  îáùåì ñëó÷àå, äëÿ ñæàòèÿ ïðîèçâîëüíîãî êîìïüþòåðíîãî ôàéëà, åãî äëèíà äîëæíà ñîñòàâëÿòü 256 ýëåìåíòîâ. Çàòåì, â ñîîòâåòñòâèè ñ ïîëó÷åííûì íàáîðîì ÷àñòîò ñòðîèì äâîè÷íîå äåðåâî ReBuildTree. Âî âðåìÿ âòîðîãî ïðîõîäà, ïåðåêîäèðóåì èñòî÷íèê â ñîîòâåòñòâèè ñ äåðåâîì è çàïèñûâàåì ïîëó÷àåìûå ïîñëåäîâàòåëüíîñòè áèò â ñæàòûé ôàéë. Äëÿ òîãî, ÷òîá ïîòîì âîçìîæíî áûëî âîññòàíîâèòü ñæàòûå äàííûå - íåîáõîäèìî, òàêæå, â ïîëó÷åííûé ôàéë, ñîõðàíèòü êîïèþ äâîè÷íîãî äåðåâà WriteTree.

Äèíàìè÷åñêèé àëãîðèòì:
InitTree	' Èíèöèàëèçèðóåì äâîè÷íîå äåðåâî
For i=0 to Ubound(CharCount)
CharCount(i)=0	' Èíèöèàëèçèðóåì ìàññèâ ÷àñòîò ýëåìåíòîâ àëôàâèòà
Next
Do While not EOF(Ôàéë èñòî÷íèê)	' Çàïóñêàåì ïðîõîä ôàéëà
Get Ôàéë èñòî÷íèê, C	' ×èòàåì òåêóùèé ñèìâîë
If C íåò â äåðåâå then	' Ïðîâåðÿåì âñòðå÷àëñÿ ëè òåêóùèé ñèìâîë ðàíüøå
code=Êîä "ïóñòîãî" ñèìâîëà & Asc(C)	' Åñëè íåò, òî çàïîìèíàåì êîä ïóñòîãî ëèñòà è ASCII êîä òåêóùåãî ñèìâîëà
else
code=Êîä C	' Èíà÷å çàïîìèíàåì êîä òåêóùåãî ñèìâîëà
End if
Put Ôàéë ïðè¸ìíèê, code	' Çàïèñûâàåì ïîñëåäîâàòåëüíîñòü áèò â ôàéë
ReBuildTree(Ñ)	' Îáíîâëÿåì äâîè÷íîå äåðåâî ñèìâîëîì
Loop

Äèíàìè÷åñêîå ñæàòèå èñïîëüçóåò áîëåå ãèáêèé ïîäõîä. Ïåðâîíà÷àëüíî äâîè÷íîå äåðåâî êîäîâ ÿâëÿåòñÿ ïóñòûì è ïðîöåäóðà InitTree çàïèñûâàåò òîëüêî ëèñò ñîäåðæàùèé "ïóñòîé" ñèìâîë. Çàòåì êîäèðóåòñÿ è çàïèñûâàåòñÿ â ñæàòûé ôàéë ïîñòóïèâøèé íà âõîä òåêóùèé ñèìâîë. Ïðîöåäóðà ReBuildTree îáíîâëÿåò äåðåâî â ñîîòâåòñòâèè ñ ýòèì ñèìâîëîì. Ñèìâîëû äîáàâëÿþòñÿ â ñëîâàðü òîëüêî ïî ìåðå èõ ïîÿâëåíèÿ â ôàéëå èñòî÷íèêå. Åñëè ïîÿâèâøèéñÿ ñèìâîë ðàíüøå íå âñòðå÷àëñÿ, òî âûâîäèì â ïîòîê êîä "ïóñòîãî" ñèìâîëà, òî åñòü ñèìâîëà, êîòîðûé ðàíüøå íå âñòðå÷àëñÿ, à çàòåì ASCII êîä ñàìîãî ñèìâîëà, êîòîðûé ãàðàíòèðóåò íàì, ÷òî ïðè ðàçàðõèâèðîâàíèè âîññòàíàâëèâàåìàÿ èíôîðìàöèÿ íå ñìîæåò äâîÿêî òðàêòîâàòüñÿ.

Äèíàìè÷åñêèé àëãîðèòì ñæàòèÿ Õàôôìàíà

Äèíàìè÷åñêîå ñæàòèå ìåòîäîì Õàôôìàíà áûëî ïðåäëîæåíî íåçàâèñèìî Ôîëëåðîì [1973] è Ãàëëàãåðîì [1978].  1985 Äîíàëüä Êíóò ðàçðàáîòàë îêîí÷àòåëüíûé óñîâåðøåíñòâîâàííûé âàðèàíò àëãîðèòìà - âñëåäñòâèå ÷åãî àëãîðèòì ïîëó÷èë íàçâàíèå FGK (Faller, Gallager, Knuth) àëãîðèòìà. Îñíîâíûì ïðèíöèïîì FGK àëãîðèòìà - ÿâëÿåòñÿ ñâîéñòâî "áðàòñòâà". Äâîè÷íîå äåðåâî îáëàäàåò äàííûì ñâîéñòâîì, åñëè êàæäûé åãî óçåë (çà èñêëþ÷åíèåì êîðíåâîãî) èìååò â äåðåâå óçëà "áðàòà" è, ïðè ðàñïîëîæåíèè âñåõ óçëîâ â ñïèñêå, â ïîðÿäêå íåóâåëè÷åíèÿ èõ âåñîâ, óçëû "áðàòüÿ" íàõîäÿòñÿ ïî ñîñåäñòâó. "Áðàòüÿìè" íàçîâ¸ì äâà óçëà, êîòîðûå èìåþò îáùåãî ðîäèòåëÿ.

Íàïðèìåð, äëÿ óêàçàííîãî äåðåâà, ïðè âûïèñûâàíèè óçëîâ â òðåáóåìûé ñïèñîê - ïîëó÷àåì:

Óç3	Óç2	Óç1	Ã	Â	Á	À
9	5	4	3	2	2	2

Ãäå âåðõíèé ðÿä îçíà÷àåò óçåë äåðåâà, à íèæíèé åãî âåñ. Òàêèì îáðàçîì âûÿñíÿåì, ÷òî äàííîå äåðåâî îáëàäàåò ñâîéñòâîì "áðàòñòâà", òàê êàê êàæäûé, êðîìå êîðíåâîãî, óçåë èìååò "áðàòà" è âñå óçëû "áðàòüÿ" íàõîäÿòñÿ â ñïèñêå ïî ñîñåäñòâó { À - Á }, {  - à }, { Óç1 - Óç2 }. Ëèñòüÿ òàêîãî äåðåâà ïðåäñòàâëÿþò ñîáîé ñèìâîëû èçâëåêàåìûå èç èñõîäíîãî ôàéëà, à âåñà ëèñòüåâ - êîëè÷åñòâî ïîÿâëåíèé ýòèõ ñèìâîëîâ â èñõîäíîì ôàéëå. Ïî ìåðå ïðîõîæäåíèÿ àëãîðèòìà ÷åðåç ôàéë âåñà ëèñòüåâ ìîãóò ëèáî óâåëè÷èâàòüñÿ, ëèáî îñòàâàòüñÿ áåç èçìåíåíèé.

Ïåðâîíà÷àëüíî äåðåâî ñîñòîèò èç îäíîãî "ïóñòîãî" óçëà. Ýòîò óçåë ÿâëÿåòñÿ åäèíñòâåííûì ëèñòîì, êîòîðûé íå ñîäåðæèò íèêàêîãî ñèìâîëà è èìååò íóëåâîé âåñ. Îí ïðåäíàçíà÷àåòñÿ äëÿ êîäèðîâàíèÿ òåõ ñèìâîëîâ, êîòîðûå ðàíåå íå ïîïàäàëè âî âõîäíîé ïîòîê. Äàëåå, ïî ìåðå ïîñòóïëåíèÿ íà âõîä ïðîãðàììû àðõèâàòîðà ñèìâîëîâ èç èñõîäíîãî ôàéëà, ïðîâåðÿåòñÿ, åñòü ëè óæå òàêîé ñèìâîë â äåðåâå èëè íåò. Åñëè ñèìâîë ïðèñóòñòâóåò - åãî êîä ïåðåäà¸òñÿ ñæàòîìó ôàéëó, çàòåì åãî (è âñåõ åãî ðîäèòåëåé) âåñ èíêðåìåíòèðóåòñÿ è äåðåâî ïåðåñ÷èòûâàåòñÿ ïî íîâîé. Ïðè îòñóòñòâèè ñèìâîëà â äåðåâå - â ñæàòûé ôàéë ïåðåäà¸òñÿ êîä "ïóñòîãî" ñèìâîëà, ñëåäóþùèå çà êîòîðûì áèòû ñîäåðæàò èíôîðìàöèþ îäíîçíà÷íî îïðåäåëÿþùèé íîâûé ñèìâîë (÷àùå âñåãî ýòî ASCII êîä). Ïîñëå ÷åãî â äåðåâî äîáàâëÿåòñÿ åù¸ îäèí ëèñò, êîòîðûé ñîäåðæèò íîâûé ñèìâîë è èìååò âåñ 1. Èíêðåìåíòèðóþòñÿ âåñà âñåõ ðîäèòåëåé íîâîèñïå÷¸ííîãî óçëà. Ñíîâà ïåðåñ÷èòûâàåì äåðåâî.

Òàê êàê "ïóñòîé" óçåë èìååò âåñ 0, òî ïðè ïåðåñ÷¸òå äåðåâà îí âñåãäà áóäåò èìåòü ñàìûé äëèííûé êîä. Ñëåäîâàòåëüíî, êàæäûé ïîÿâèâøèéñÿ íîâûé ñèìâîë áóäåò èìåòü êîä ðàâíûé ïî äëèíå êîäó "ïóñòîãî" óçëà èëè ìåíüøèé åãî íà 1 áèò. Áëàãîäàðÿ ÷åìó ñàìûå ðåäêîâñòðå÷àåìûå ñèìâîëû, êîòîðûå áóäóò, ñîîòâåòñòâåííî, ïîçæå ïîÿâëÿòüñÿ - áóäóò èìåòü ñàìûå äëèííûå êîäû - ÷òî ïîëíîñòüþ ñîîòâåòñòâóåò ïðèíöèïàì àëãîðèòìà ñæàòèÿ Õàôôìàíà.

Ïðèíöèïû ïîñòðîåíèÿ îñíîâíûõ ïðîöåäóð

 ñîîòâåòñòâèè ñ îïèñàííûì âûøå àëãîðèòìîì ñæàòèÿ ìåòîäîì Õàôôìàíà ìîæíî âûäåëèòü òðè îñíîâíûå ïðîöåäóðû îò àëãîðèòìîâ ðåàëèçàöèè êîòîðûõ çàâèñÿò õàðàêòåðèñòèêè (ïðîèçâîäèòåëüíîñòü, êîýôôèöèåíò ñæàòèÿ è ò.ä.) ïðîãðàììû ñæàòèÿ. Ïðîöåäóðà InitTree - èíèöèàëèçèðóþùàÿ äâîè÷íîå äåðåâî, ïðîöåäóðà äîáàâëåíèÿ íîâîãî ñèìâîëà â äåðåâî è ïðîöåäóðà ReBuildTree - ìîäèôèöèðóþùàÿ òåêóùåå äåðåâî â ñîîòâåòñòâèè ñ íîâîé ïîñòóïèâøåé èíôîðìàöèåé. Ðàññìîòðèì ïðèíöèïû èõ ðåàëèçàöèè â îáðàòíîì ïîðÿäêå.

Îò ïðîöåäóðû ReBuildTree âî ìíîãîì çàâèñèò áûñòðîäåéñòâèå ïðîãðàììû àðõèâàòîðà, òàê êàê èìåííî îíà äîëæíà ïîñëå êàæäîãî ïîñòóïèâøåãî ñèìâîëà çàíîâî ïåðåñòðàèâàòü äâîè÷íîå äåðåâî êîäîâ. Ñàìûé ïðîñòîé è íàä¸æíûé ñïîñîá - êîíå÷íî æå ïîëíîå ïîñòðîåíèå äåðåâà - îäíàêî â ýòîì ñëó÷àå àëãîðèòì áóäåò íàñòîëüêî ìåäëåííûì, ÷òî ïðè àðõèâàöèè äàæå ñàìîãî ìàëåíüêîãî ôàéëà ìîæíî áóäåò óñïåòü âûïèòü ïàðó ÷àøåê êîôå è íåìíîæêî âçäðåìíóòü. Ïîëíîå ïîñòðîåíèå äâîè÷íîãî äåðåâà - äîâîëüíî áîëüøàÿ è íåë¸ãêàÿ ðàáîòà äàæå äëÿ ñîâðåìåííûõ êîìïüþòåðîâ. Íî âûõîä âñ¸-òàêè åñòü! Âñïîìíèì, ÷òî ìû ïîëüçóåìñÿ äëÿ ñæàòèÿ äàííûõ FGK àëãîðèòìîì, êîòîðûé îáëàäàåò ñâîéñòâîì "áðàòñòâà". Ñîãëàñíî ïðàâèëàì, ïðè ðàñïîëîæåíèè âñåõ óçëîâ â ñïèñêå, â ïîðÿäêå íåóâåëè÷åíèÿ èõ âåñîâ, óçëû "áðàòüÿ" íàõîäÿòñÿ ïî ñîñåäñòâó. Îòêóäà ñëåäóåò, ÷òî âìåñòî òîãî, ÷òîá ïîñòîÿííî ïîëíîñòüþ ìîäèôèöèðîâàòü âñ¸ äåðåâî ìîæíî õðàíèòü åãî â âèäå óïîðÿäî÷åííîãî ñïèñêà è èçìåíÿòü òîëüêî òå ýëåìåíòû ñïèñêà, êîòîðûå òðåáóþò èçìåíåíèÿ.

Äëÿ ðàññìîòðåííîãî âûøå äåðåâà óïîðÿäî÷åííûé ñïèñîê ïðåäñòàâëÿë ñîáîé:

Óç3	Óç2	Óç1	Ã	Â	Á	À
9	5	4	3	2	2	2

Òåïåðü, åñëè î÷åðåäíûì ñèìâîëîì âî âõîäÿùåì ïîòîêå áóäåò ñèìâîë "Ã", òîãäà óâåëè÷èâàåì åãî âåñ íà 1. Î÷åâèäíî, ÷òî âåñ ðîäèòåëÿ Óç2 òåïåðü íå ñîîòâåòñòâóåò ñóììå âåñîâ ïîòîìêîâ, ïîýòîìó åãî òîæå ñëåäóåò èíêðåìåíòèðîâàòü. Óâåëè÷èâ âåñ óçëà Óç2 - ïåðåõîäèì ê åãî ðîäèòåëþ - êîðíþ äåðåâà Óç3, âåñ êîòîðîãî òàê æå óâåëè÷èâàåòñÿ íà 1. Íîâûé ñïèñîê òåïåðü áóäåò èìåòü âèä:

Óç3	Óç2	Óç1	Ã	Â	Á	À
10	6	4	4	2	2	2

À äåðåâî ñîîòâåòñòâåííî ñòàíåò:

Íàì ïîòðåáîâàëîñü âñåãî òðè äåéñòâèÿ, ÷òîá èçìåíèòü äåðåâî.  îáùåì ñëó÷àå íåîáõîäèìî óâåëè÷èòü íà 1 âåñ ëèñòà ïîñòóïèâøåãî íà âõîä ñèìâîëà, à çàòåì èíêðåìåíòèðîâàòü âåñà âñåõ åãî ðîäèòåëåé âïëîòü äî êîðíÿ äåðåâà. Òî åñòü ñðåäíåå ÷èñëî îïåðàöèé áóäåò ðàâíÿòüñÿ ñðåäíåìó êîëè÷åñòâó áèòîâ (èëè ñðåäíåé äëèíå ïóòè îò ëèñòà ê êîðíþ äåðåâà), íåîáõîäèìûõ äëÿ òîãî, ÷òîá çàêîäèðîâàòü ñèìâîë.

Îäíàêî âîçìîæåí âàðèàíò, êîãäà óïîðÿäî÷åííîñòü ñïèñêà íàðóøàåòñÿ. Íàïðèìåð, åñëè äëÿ ïîëó÷åííîãî äåðåâà ñëåäóþùèé ñèìâîë ñíîâà áóäåò "Ã", è ìû ïðîñòî óâåëè÷èì âåñà, òîãäà ïîñëå èõ êîäèðîâàíèÿ ñïèñîê ïðèìåò âèä:

Óç3	Óç2	Óç1	Ã	Â	Á	À
11	7	4	5	2	2	2

Êàê âèäíî ñâîéñòâî óïîðÿäî÷åííîñòè íàðóøåíî. Ñèìâîë "Ã" âåñ êîòîðîãî áîëüøå ÷åì âåñ Óç1 ñòîèò ðàíüøå íåãî â ñïèñêå.  òàêîì ñëó÷àå íåîáõîäèìî ïðîèçâåñòè îïåðàöèþ óïîðÿäî÷èâàíèÿ ñïèñêà. Äëÿ ýòîãî ïîñëå èíêðåìåíòàöèè âåñà ñèìâîëà íà÷èíàåì äâèãàòüñÿ ïî ñïèñêó, â ñòîðîíó óâåëè÷åíèÿ âåñà, äî òåõ ïîð ïîêà íå íàéäåì ïîñëåäíèé óçåë ñ ìåíüøèì âåñîì ÷åì òåêóùèé. Çàòåì ïåðåñòàâëÿåì òåêóùèé è íàéäåííûé óçëû âîññòàíàâëèâàÿ òàêèì îáðàçîì ïîðÿäîê â ñïèñêå. Ïðè ýòîì ðîäèòåëè îáîèõ óçëîâ òîæå èçìåíÿþòñÿ. Ðîäèòåëåì òåêóùåãî óçëà ñòàíîâèòñÿ ðîäèòåëü íàéäåííîãî è íàîáîðîò. Äàëüøå óâåëè÷èâàåòñÿ âåñ íîâîãî ðîäèòåëÿ è òàê äàëåå, äî ñàìîãî êîðíÿ äåðåâà. Íîâûé ñïèñîê óæå áóäåò âûãëÿäåòü ñëåäóþùèì îáðàçîì:

Óç3	Óç2	Ã	Óç1	Â	Á	À
10	6	5	4	2	2	2

À äåðåâî ñîîòâåòñòâåííî:

Èç ïðèâåä¸ííîãî ïðèìåðà âèäíî, ÷òî ÷åì ÷àùå âñòðå÷àåòñÿ òîò ëèáî èíîé ñèìâîë, òåì áëèæå îí íàõîäèòñÿ ê íà÷àëó ñïèñêà è êîðî÷å êîä èìååò.  ïîñëåäíåì äâîè÷íîì äåðåâå ñàìûé ÷àñòî âñòðå÷àåìûé ñèìâîë "Ã" èìååò ñàìûé êîðîòêèé êîä - 1 áèò.

 îáùåì âèäå àëãîðèòì ìîäèôèêàöèè äåðåâà ìîæíî çàïèñàòü òàê:

Public Sub ReBuildTree (Ñèìâîë as Byte)
ÒåêóùèéÓçåë = ËèñòÑîîòâåòñòâóþùèé(Ñèìâîë)	' Íàõîäèì â äåðåâå ëèñò ñîîòâåòñòâóþùèé ñèìâîëó
Do While True
ÒåêóùèéÓçåë.Âåñ=ÒåêóùèéÓçåë.Âåñ + 1	' Óâåëè÷èâàåì åãî âåñ íà 1
If ÒåêóùèéÓçåë=ÊîðåíüÄåðåâà then	' ßâëÿåòñÿ ëè òåêóùèé óçåë êîðíåì äåðåâà
Exit Do	' Åñëè äà, òî çàêàí÷èâàåì ïðîöåäóðó îáíîâëåíèÿ
else
if ÒåêóùèéÓçåë.Âåñ > (ÒåêóùèéÓçåë+1).Âåñ	' Ïðîâåðÿåì íå íàðóøåíà ëè óïîðÿäî÷åííîñòü
i=1
Do WhileÒåêóùèéÓçåë.Âåñ > (ÒåêóùèéÓçåë+i).Âåñ
i=i+1
Loop
Ïåðåñòàíîâêà ÒåêóùèéÓçåë, ÒåêóùèéÓçåë+i	' Åñëè óïîðÿäî÷åííîñòü íàðóøåíà, òî âîññòàíàâëèâàåì å¸ ïóò¸ì îáìåíà óçëîâ
End if
ÒåêóùèéÓçåë = ÒåêóùèéÓçåë.Ðîäèòåëü	' Ïåðåõîäèì ê ðîäèòåëþ òåêóùåãî óçëà
End if
Loop
End sub

Òåïåðü, ïîñëå òîãî êàê ñòàëè ÿñíû ïðèíöèïû ïîñòðîåíèÿ è ìîäèôèêàöèè äâîè÷íîãî äåðåâà, âîçíèêàåò âîïðîñ î äîáàâëåíèè â äåðåâî íîâîãî ñèìâîëà. Ñîãëàñíî àëãîðèòìó, ïðè ïîÿâëåíèè âî âõîäíîì ïîòîêå íîâîãî ñèìâîëà â ôàéë àðõèâ âûäà¸òñÿ êîä "ïóñòîãî" ñèìâîëà, à çàòåì ïîñëåäîâàòåëüíîñòü áèò îäíîçíà÷íî èäåíòèôèöèðóþùèõ íîâûé ñèìâîë.

Ïðîöåäóðà äîáàâëåíèÿ íîâîãî ñèìâîëà ñîñòîèò â òîì, ÷òî â õâîñò óïîðÿäî÷åííîãî ñïèñêà, êîèì ÿâëÿåòñÿ íàøå äåðåâî êîäîâ, äîáàâëÿþòñÿ äâà íîâûõ ýëåìåíòà - ïåðâûé èç íèõ ñòàíîâèòñÿ ëèñòîì äëÿ íîâîãî ñèìâîëà, à âòîðîé äîïîëíèòåëüíûì óçëîì. Òîëüêî ÷òî ñîçäàííûé äîïîëíèòåëüíûé óçåë áåð¸ò íà ñåáÿ ðîäèòåëÿ "ïóñòîãî" ñèìâîëà è ñàì ñòàíîâèòñÿ ðîäèòåëåì äëÿ íîâîãî è "ïóñòîãî" ñèìâîëîâ. Äîïîëíèòåëüíûé óçåë íåîáõîäèì, òàê êàê îáùåå êîëè÷åñòâî óçëîâ äåðåâà äîëæíî áûòü ðàâíûì êîëè÷åñòâó ëèñòüåâ -1.

Óç1	À
1	1	0

Íàïðèìåð, ïðè èìåþùåìñÿ äâîè÷íîì äåðåâå ñ îäíèì ñèìâîëîì "À" è íóëåâûì óçëîì, åñëè ñëåäóþùèì ñèìâîëîì ïîñòóïàþùèì èç ôàéëà èñòî÷íèêà ÿâëÿåòñÿ "Á" íåîáõîäèìî äîáàâèòü åãî â ñïèñîê.

Óç1	À	Óç2	Á
2	1	1	1	0

Ïåðâîíà÷àëüíî âåñà íîâîãî ñèìâîëà è åãî ðîäèòåëüñêîãî óçëà óñòàíàâëèâàþòñÿ ðàâíûìè 0, îäíàêî â êîíöå ïðîöåäóðû äîáàâëåíèÿ ñèìâîëà èä¸ò îáðàùåíèå ê ïðîöåäóðå ïîñòðîåíèÿ äåðåâà ReBuildTree, ãäå óêàçûâàåòñÿ òîëüêî ÷òî ñîçäàííûé ñèìâîë. ReBuildTree óâåëè÷èâàåò íà îäèí âåñ ñèìâîëà, à òàê æå åãî ðîäèòåëåé â äåðåâå è ïåðåìåùàåò èõ (åñëè ýòî íåîáõîäèìî) ñîãëàñíî àëãîðèòìó ïî ñïèñêó òàê, ÷òîá ñîõðàíÿëèñü ïðèíöèïû óïîðÿäî÷åííîñòè ñïèñêà, è íå íàðóøàëîñü ïîñòðîåíèå äâîè÷íîãî äåðåâà.

Public Sub AddNode (Ñèìâîë as Byte)
Ñîçäàòü(ÍîâûéÓçåë)	' Ñîçäà¸ì íîâûé óçåë äåðåâà
Ñîçäàòü(ÍîâûéËèñò)	' Ñîçäà¸ì íîâûé ëèñò äåðåâà (äëÿ ñèìâîëà)
ÍîâûéÓçåë.Ðîäèòåëü=ÏóñòîéËèñò.Ðîäèòåëü	' Ðîäèòåëåì íîâîãî óçëà äåëàåì ðîäèòåëÿ ïóñòîãî ñèìâîëà
ÏóñòîéËèñò.Ðîäèòåëü=ÍîâûéÓçåë	' Äåëàåì íîâûé óçåë ðîäèòåëåì ïóñòîãî
ÍîâûéËèñò.Ðîäèòåëü=ÍîâûéÓçåë	' Äåëàåì íîâûé óçåë ðîäèòåëåì íîâîãî ëèñòà
ÍîâûéÓçåë.Âåñ=0	' Ïðèñâàèâàåì íîâîìó óçëó íóëåâîé âåñ
ÍîâûéËèñò.Âåñ=0	' Ïðèñâàèâàåì íîâîìó ëèñòó íóëåâîé âåñ
ÍîâûéËèñò.Ñèìâîë=Ñèìâîë	' Çàïîìèíàåì â ëèñòå ñèìâîë, ðàäè êîòîðîãî åãî ñîçäàâàëè
ReBuildTree(Ñèìâîë)	' Îáíîâëÿåì äâîè÷íîå äåðåâî
End Sub

Èíèöèàëèçàöèÿ äåðåâà, ïðîöåäóðà InitTree, ïðåäñòàâëÿåò ñîáîé íè ÷òî èíîå, êàê ïðîñòî ñîçäàíèå "ïóñòîãî" ñèìâîëà.  ñàìîì íà÷àëå óïîðÿäî÷åííîãî ñïèñêà. Òàê êàê ïðè íà÷àëå êîäèðîâàíèÿ äåðåâî íå ñîäåðæèò íè îäíîãî ñèìâîëà, òî "ïóñòîé" ñèìâîë íå ñìîòðÿ íà ñâîé íóëåâîé âåñ áóäåò ïåðâûì è åäèíñòâåííûì è ïðè îáðàùåíèè ê íåìó âûäàñò â ïîòîê îäíîáèòíûé êîä 0.

Çàêëþ÷åíèå

Ñòàòè÷åñêîå êîäèðîâàíèå Õàôôìàíà äîâîëüíî øèðîêî ïðèìåíÿåòñÿ â ñîâðåìåííûõ àëãîðèòìàõ ñæàòèÿ, íî íå â ÷èñòîì âèäå, à êàê îäíà èç ñòóïåíåé ñæàòèÿ â áîëåå ñëîæíûõ àëãîðèòìàõ. Äèíàìè÷åñêèé æå âàðèàíò àëãîðèòìà íà ïðàêòèêå, â ïîñëåäíåå âðåìÿ, óñòóïèë áîëåå ãèáêèì è ñêîðîñòíûì àëãîðèòìàì è ïðèìåíÿåòñÿ â îñíîâíîì òîëüêî â ýêñïåðèìåíòàëüíûõ öåëÿõ.

ßíêîâîé Ìèõàèë, 2004