Ìåòîäû Õàôôìàíà è Øåííîíà-Ôàíî >>
ÕÀÔÔÌÀÍ Â ÏËÀÍÅ ÌÈÍÈÌÈÇÀÖÈÈ ÏÐÎÃÐÀÌÌÛ
Äîìàøíÿÿ ñòðàíèöà
1. Çíàêîìñòâî ñ Õàôôìàíîì
2. Îïòèìàëåí ëè Õàôôìàí?
3. Âû÷èñëåíèå äëèí áèòîâûõ ïðåäñòàâëåíèé ñèìâîëîâ
4. Áèòîâûå ïðåäñòàâëåíèÿ ñèìâîëîâ
5. Ðàñøèôðîâêà ñæàòîãî òåêñòà
6. Ïðèìåð ïðîãðàììû â öåëîì
7. Ëèñòèíãè
• ÂÛ×ÈÑËÅÍÈÅ ÄËÈÍ ÏÐÅÄÑÒÀÂËÅÍÈÉ
• ÂÛ×ÈÑËÅÍÈÅ ÏÐÅÄÑÒÀÂËÅÍÈÉ
• ÄÅÊÎÄÈÐÎÂÙÈÊ
8. Çàêëþ÷åíèå
Îáû÷íî óëó÷øåíèå îäíèõ õàðàêòåðèñòèê ïðîãðàììû äîñòèãàåòñÿ â
óùåðá äðóãèì. Îäíàêî îòñå÷åíèå ëèøíåãî â ïðîãðàììå, íàïðèìåð, ïðè
êîíêðåòíûõ òðåáîâàíèÿõ ê ñêîðîñòè, íåðåäêî ïîçâîëÿåò âûäåëèòü
ñóùåñòâåííûå ÷àñòè àëãîðèòìà, âûÿâèòü áîëåå ãëóáîêèå çàêîíîìåðíîñòè
è äîáèòüñÿ óëó÷øåíèÿ ïðîãðàììû ñðàçó ïî ðÿäó ïîêàçàòåëåé.
1. Çíàêîìñòâî ñ Õàôôìàíîì
Âîçüìåì íàáîð ñèìâîëîâ
1111111111222222222333333334444444555555 ,
â êîòîðîì íàõîäÿòñÿ 10 ñèìâîëîâ "1", 9 - "2", 8 - "3", 7 - "4", 6 - "5".
Åñëè êàæäûé ñèìâîë ïðåäñòàâëÿåòñÿ âîñåìüþ áèòàìè, íàïðèìåð,
"1" - 00110000, "2" - 0011001 è ò.ä., òî âçÿòûé íàáîð ïîòÿíåò íà 320
áèòîâ.
Ñíà÷àëà Õàôôìàí ðåêîìåíäóåò âûáðàòü äâà ñèìâîëà, íàèáîëåå
ðåäêèõ â òåêñòå, è ïðèïèñàòü îäíîìó áèò=0, à äðóãîìó - áèò=1. Â
ïîñëåäñòâèè ýòè áèòû îêàæóòñÿ ïîñëåäíèìè â ïðåäñòàâëåíèè ýòèõ äâóõ
âûáðàííûõ ñèìâîëîâ. Òàêèì îáðàçîì, ïîêà ïðîÿñíèëîñü íåìíîãî:
"1" - ...
"2" - ...
"3" - ...
"4" - ... 0
"5" - ... 1
Äàæå äëèíà ïðåäñòàâëåíèé ïîêà íå èçâåñòíà.
Äàëåå ïðåäëàãàåòñÿ âìåñòî ïÿòè èñõîäíûõ ñèìâîëîâ ðàáîòàòü
ñ ÷åòûðüìÿ: "1" , "2", "3" è íåêèì âñïîìîãàòåëüíûì ñèìâîëîì "Z"
(îáîçíà÷åíèå îñîáîé ðîëè íå èãðàåò), äëÿ êîòîðîãî ñóììèðóþòñÿ êîëè÷åñòâà
âõîæäåíèé ñèìâîëîâ "4" è "5". Ò.å. äàëåå èìååì äåëî ñ êîëè÷åñòâàìè:
"1" - 10, "2" - 9, "3" - 8, "Z" - 13.
Òåïåðü îïÿòü íàäî âûáðàòü äâà íàèìåíåå óïîòðåáèòåëüíûõ
ñèìâîëà (ýòî áóäóò "2" è "3") è òàêæå ïðèïèñàòü èì 0 è 1, à çàòåì
ñîáðàòü îáîáùåííûé ñèìâîë "Y":
"1" - ...
"2" - ... 0
"3" - ... 1
"Z" - ...
Êîëè÷åñòâà: "1" - 10, "Y" - 17, "Z" - 13.
Äàëåå "1" è "Z" îáðàçóþò "X" . Îñòàëîñü âñåãî 2 ñèìâîëà:
"Y" è "Z". Îäíîìó ïðèñâàèâàåì áèò = 0 , äðóãîìó áèò = 1.
Ðèñ.1. Äåðåâî Õàôôìàíà
Âîçâðàùàÿñü ïî ïîñòðîåííîìó äåðåâó ê åãî ëèñòî÷êàì, ñîáèðàåì öåïî÷êè
áèòîâ è ïîëó÷àåì ïðåäñòàâëåíèÿ:
"1" - 11
"2" - 00
"3" - 01
"4" - 100
"5" - 101
 òàêîì ñëó÷àå èñõîäíûé òåêñò ïåðåâîäèòñÿ â 93 áèòà.
2. Îïòèìàëåí ëè Õàôôìàí?
 ðàññìîòðåííîì ïðèìåðå 320 áèòîâ óæàòü äî 93. Íî íå èëëþçîðíà
ëè âûãîäà?
Ïîñêîëüêó èçáðàííàÿ â ïðèìåðå êîäèðîâêà íå îáùåóïîòðåáèòåëüíà,
òî ê 93 áèòàì äîáàâèòñÿ ñóùåñòâåííàÿ íàãðóçêà: òàáëèöà ñîîòâåòñòâèÿ.
Ôîðìàëüíî íà êàæäûé ñèìâîë ïîòðåáóåòñÿ:
à) îáùåóïîòðåáèòåëüíîå ïðåäñòàâëåíèå, íàïðèìåð, 8-áèòîâîå,
á) êîëè÷åñòâî áèòîâ â ïîñòðîåííîì ïðåäñòàâëåíèè (äëÿ êîòîðîãî
ïîòðåáóåòñÿ åùå 2 áèòà, ÷òîáû îõâàòèòü ðàññìàòðèâàåìûé ïðèìåð),
â) ñîáñòâåííî íîâîå ïðåäñòàâëåíèå.
Èòîãî â ïàññèâå: 62 áèòà.
Âìåñòî ñòîëü ãðîìîçäêîé òàáëèöû ìîæíî õðàíèòü ñàìî äåðåâî,
îïèñàííîå âûøå, íàïðèìåð, â ôîðìå, îïèñàííîé íèæå (ìàññèâ èç ïàð,
îòðàæàþùèõ ñëèÿíèå, â ðàçäåëå 3). Òîãäà ìîæíî ëèáî ðàçâåðíóòü òàáëèöó
ïåðåä äåøèôðîâêîé, ëèáî áîëåå äëèòåëüíîé ïðîöåäóðîé ïîëçàíèÿ ïî äåðåâó
âñÿêèé ðàç ïî çàäàííûì áèòàì íàõîäèòü íà ýòîì äåðåâå íóæíûé ëèñòîê. Íî
è ýòî êðàéíå îáúåìíî, íå ãîâîðÿ óæå î íåîïðàâäàííûõ ïîòåðÿõ âðåìåíè íà
ðàñøèôðîâêó, êîòîðûå âî ìíîãèõ ñëó÷àÿõ ìîãóò îêàçàòüñÿ íåïðèåìëåìûìè.
Êðîìå òîãî, ÷òîáû íåêàÿ ïðîãðàììà ìîãëà ðàñøèôðîâûâàòü íå òîëüêî
îäèí òåêñò, à åùå õîòÿ áû íåñêîëüêî, äëÿ ýòîãî ïåðåä òàáëèöåé ñîîòâåòñòâèÿ
íàäî óêàçàòü äëèíó òàáëèöû è äëèíó ñæàòîãî òåêñòà, à òàêæå, âîçìîæíî,
íåêèå ïàðàìåòðû òàáëèöû. Ïðàâäà, äëÿ äëèííûõ òåêñòîâ èçäåðæêè íà òàáëèöó
ñòàíîâÿòñÿ îòíîñèòåëüíî ìàëûìè.
Ãîðàçäî áîëüøèå íåïðèÿòíîñòè îæèäàþò íàñ ïðè àíàëèçå äðóãîãî
÷èñëà: 320.
Øèðîêî ðàñïðîñòðàíåííîå 8-áèòîâîå ïðåäñòàâëåíèå ñèìâîëîâ,
îõâàòûâàþùåå öèôðû, áîëüøèå ì ìàëûå áóêâû ðóññêîãî è ëàòèíñêîãî
àëôàâèòà, - äàëåêî íå åäèíñòâåííî ñ òåîðåòè÷åñêîé òî÷êè çðåíèÿ.
Âî ìíîãèõ ïðîãðàììàõ â õîäó óæå 16-áèòîâîå ïðåäñòàâëåíèå. Ñ äðóãîé
ñòîðîíû, äëÿ ïðåäñòàâëåíèÿ äåñÿòè÷íûõ öèôð äîñòàòî÷íî 4 áèòîâ.
À â àçáóêå Ìîðçå âîîáùå íåò åäèíîé äëèíû: íàèáîëåå óïîòðåáèòåëüíûå
ñèìâîëû çàïèñûâàþòñÿ êîðîòêèìè öåïî÷êàìè òî÷åê è òèðå (ýêâèâàëåíòíî:
íóëåé è åäèíèö), ìåíåå óïîòðåáèòåëüíûå - äëèííûìè öåïî÷êàìè.
Äëÿ ðàññìîòðåííîãî ïðèìåðà ãîäèòñÿ ñòàíäàðòíàÿ 4-áèòîâàÿ
êîäèðîâêà öèôð: "0" = 0000 , "1" = 0001 , "2"= 0010 è ò.ä. Òîãäà
èñõîäíûé íàáîð ïîòÿíåò íå íà 320, à íà 160 áèòîâ, è âûãîäû îò "ñæàòèÿ"
êàê íå áûâàëî. Âïðî÷åì, òåêñòû òîëüêî èç öèôð âñòðå÷àþòñÿ íå òàê óæ
÷àñòî. À íåóòåøèòåëüíûé èòîã äëÿ ðàññìîòðåííîãî ïðèìåðà ãîâîðèò ëèøü
î òîì, ÷òî ìåòîä Õàôôìàíà (êàê è ëþáîé ìåòîä ñæàòèÿ èíôîðìàöèè)
íå âñåñèëåí. Íà ëþáîé èç íèõ íåòðóäíî ïîäîáðàòü ïðèìåð, íà êîòîðîì
ìåòîä ïàñóåò. À åñëè êàêîé-òî òåêñò óæå ÿâëÿåòñÿ ðåçóëüòàòîì
õîðîøåãî ñæàòèÿ, òî îí, êàê ïðàâèëî, ñòàíîâèòñÿ êðåïêèì îðåøêîì äëÿ
ëþáîãî ìåòîäà.
Íî äàæå ïðè ñîâåðøåííî îïðåäåëåííîé äëèíå èñõîäíûõ ñèìâîëîâ,
áóäü òî õîòü 8 áèòîâ, õîòü 16, íèêòî íå çàïðåùàåò çàïóñòèòü àëãîðèòì
Õàôôìàíà, íàïðèìåð, äëÿ 4-áèòîâûõ ÷àñòåé ýòèõ ñèìâîëîâ. Ýòî íåâàæíî, ÷òî
â èñõîäíîì òåêñòå âðîäå áû ñòàíåò áîëüøå ñèìâîëîâ. Çàòî êàæäûé èç íèõ
ïîëó÷èò áîëåå êîðîòêîå íîâîå ïðåäñòàâëåíèå, ìíîãîêðàòíî ñîêðàòèòñÿ
òàáëèöà ñîîòâåòñòâèÿ è ïðî÷åå. Ïî áîëüøîìó ñ÷åòó, äëÿ çàïóñêà àëãîðèòìà
íåâàæíî, èìååì ëè ìû äåëî ñ îñìûñëåííûì òåêñòîì èëè äàæå âîîáùå ñ
ñèìâîëàìè.
Èñõîäíûé òåêñò - ýòî ïðîñòî óïîðÿäî÷åííûé íàáîð íóëåé è åäèíèö.
Åãî ìîæíî ðàçáèòü íà êóñî÷êè ïî 2 áèòà, ìîæíî ïî 3 è ò.ä. Ìîæíî îäèí
è òîò æå òåêñò ðàçáèòü íà ýëåìåíòû ðàçíîé äëèíû. È âñÿêèé ðàç áóäóò
ïîëó÷àòüñÿ, âîîáùå ãîâîðÿ, ñóùåñòâåííî îòëè÷àþùèåñÿ îáúåìû ñæàòîãî
òåêñòà. Íàïðèìåð, ÷òîáû ñæàòü òåêñò, ïîñòóïèâøèé ïî àçáóêå ìîðçå,
íàäî ðàçðåçàòü ïîòîê òî÷åê è òèðå íà êóñêè ðàçíîé äëèíû, ñîîòâåòñòâóþùèå
áóêâàì.
Êàêîé ñïîñîá ëó÷øå - çàâèñèò îò êîíêðåòíîãî òåêñòà. È âûáîð
íàèëó÷øåãî ñïîñîáà - ýòî îòäåëüíàÿ ñëîæíàÿ çàäà÷à, êîòîðîé ìû çäåñü
íå êàñàåìñÿ. Íî ïîëåçíî çàìåòèòü, ÷òî ôîðìóëà
ÒÅÊÑÒ + ÕÀÔÔÌÀÍ =
äàëåêî íå âåäåò ê îäíîçíà÷íîìó ðåçóëüòàòó äàæå äëÿ îáúåìà ñæàòîãî
òåêñòà, èëè âî âñÿêîì ñëó÷àå îïòèìóì çäåñü ðåàëüíî íàéòè ëèøü â
î÷åíü ïðîñòûõ ñèòóàöèÿõ.
×òîáû íå óòîíóòü â îïèñàííûõ ñëó÷àÿõ, äàëåå ìû îãðàíè÷èâàåìñÿ
ðàçáèåíèåì èñõîäíîãî òåêñòà òîëüêî íà 8-áèòîâûå êóñî÷êè. Òåì íå ìåíåå,
èçáðàííûé ñïîñîá - íå ïðîñòî îäèí èç ðàâíûõ. Åñëè â îñíîâå ÝÂÌ ëåæèò
áàéòîâàÿ ñòðóêòóðà, ïî áàéòàì ñòðîÿòñÿ àäðåñà, çíà÷åíèÿ ÷èñåë, ìàøèííûå
êîìàíäû è ïð., òî è ñâîéñòâà èíôîðìàöèè, óäîáíûå äëÿ åå àðõèâàöèè, ëåæàò,
êàê ïðàâèëî, íà óðîâíå áàéòîâ.
Êðîìå òîãî, êîìïàêòíîñòü ìîæåò äîñòèãàòüñÿ ìíîãèìè ñïîñîáàìè, à
îòíþäü íå òîëüêî êîäèðîâêîé îòäåëüíûõ ñèìâîëîâ. Íåòðóäíî äîãàäàòüñÿ,
÷òî çàïèñü
10(1),9(2),8(3),7(4),6(5)
îòâå÷àåò òîìó æå âçÿòîìó ïðèìåðó.
Åñòü î÷åíü ñèëüíûå ìåòîäû ñæàòèÿ òåêñòà, åñëè â íåì íåîäíîêðàòíî
âñòðå÷àþòñÿ íåêîòîðûå ñî÷åòàíèÿ ñèìâîëîâ. Òàêîâû òåêñòû íà ðàçíûõ ÿçûêàõ,
ôàéëû â áàçàõ äàííûõ, çàãðóçî÷íûå ìîäóëè. Òîãäà, íàïðèìåð, âìåñòî î÷åðåäíîãî
ñî÷åòàíèÿ äîñòàòî÷íî óêàçàòü àäðåñ (åùå ëó÷øå ðàçíèöó àäðåñîâ) è äëèíó
ïðåäûäóùåãî àíàëîãè÷íîãî ñî÷åòàíèÿ.
Íî åñòü íåìàëî ñëó÷àåâ, êîãäà ñèìâîëû ïåðåìåøàíû, è òîëüêî íà
îñíîâå èõ ÷àñòîò ìîæíî êàê-òî óæàòü òåêñò. Äëÿ ýòîãî è ïðåäíàçíà÷åí
àëãîðèòì Õàôôìàíà, êîòîðûé ñ ÷àñòîòàìè, ò.å. íà ñâîåì ïîëå, ñïðàâëÿåòñÿ
áëåñòÿùå.
Âîîáùå ãîâîðÿ, ëó÷øåå ñæàòèå òðåáóåò è áîëüøåãî âðåìåíè.
È ñ ðîñòîì îáúåìà èñõîäíîãî òåêñòà ýòî âðåìÿ ìîæåò êàòàñòðîôè÷åñêè
ðàñòè. Íî àëãîðèòì Õàôôìàíà - îäèí èç íåìíîãèõ, êòî ìàëî÷óâñòâèòåëåí ê
îáúåìó òåêñòà.  çàâèñèìîñòè îò îáúåìà âñåãî ëèøü ëîãàðèôìè÷åñêè
ðàñòåò äëèíà ïðåäñòàâëåíèé ñèìâîëîâ (äà è òî íå âñåõ), è âðåìÿ íà ïîèñê
ïðåäñòàâëåíèé ñòàíîâèòñÿ èñ÷åçàþùå ìàëûì ïî ñðàâíåíèþ ñ çàòðàòàìè
íà ÷òåíèå-çàïèñü ôàéëîâ è íà ïðî÷èå ïåðåìåùåíèÿ èíôîðìàöèè,
íåîáõîäèìûå äëÿ ëþáîãî ìåòîäà.
Íàîáîðîò, áîëåå ìîùíûå àëãîðèòìû ñæàòèÿ áåðóòñÿ çà ïåðåáîð
ñî÷åòàíèé, ÷èñëî êîòîðûõ ðàñòåò, âîîáùå ãîâîðÿ, êâàäðàòè÷íî. À ñïîñîáû
óñêîðåíèÿ ïåðåáîðà òðåáóþò áîëüøîé îïåðàòèâíîé ïàìÿòè. (Ïðè äåøèôðîâêå
àíàëîãè÷íî Õàôôìàíó íóæíà òîëüêî òàáëèöà ñîîòâåòñòâèÿ. Äðóãèå
çíàìåíèòûå ìåòîäû òðåáóþò õðàíåíèÿ â ïàìÿòè áîëüøîãî ñëîâàðÿ èëè
äëèííîé ÷àñòè ðàñøèôðîâàííîãî òåêñòà.)
Òàêèì îáðàçîì, âîïðîñ îá îïòèìàëüíîñòè ñæàòèÿ ìåòîäîì Õàôôìàíà,
ñòðîãî ãîâîðÿ, íåêîððåêòåí, òàê æå êàê, íàïðèìåð, âîïðîñ îá îïòèìàëüíîñòè
ïðèâû÷íîé òàáëèöû óìíîæåíèÿ. Ñêàæåì, äëÿ óìíîæåíèÿ äâîè÷íûõ ÷èñåë òàáëèöà
íå íóæíà. Íî àëãîðèòì Õàôôìàíà, êàê è òàáëèöà óìíîæåíèÿ, â ñâîåì ðîäå
òî÷åí, ýôôåêòèâåí è ÿâëÿåòñÿ âûäàþùèìñÿ íàó÷íûì äîñòèæåíèåì.
3. Âû÷èñëåíèå äëèí áèòîâûõ ïðåäñòàâëåíèé ñèìâîëîâ
Äàëåå äëÿ îïðåäåëåííîñòè îãðàíè÷èìñÿ òåêñòàìè äî 64 ÊÁ
è 256 ñèìâîëàìè, çà êàæäûì èç êîòîðûõ ñòîèò åãî íîìåð îò 0 äî 255,
ò.å. íåêîå 8-áèòîâîå äâîè÷íîå ÷èñëî. Áîëåå äëèííûå òåêñòû â ïðèíöèïå
ìîæíî êîäèðîâàòü ïî ÷àñòÿì. Êðîìå òîãî, êàê îòìå÷àëîñü, Õàôôìàí íå
áîèòñÿ áîëüøèõ îáúåìîâ.
Ïî ìåòîäó Õàôôìàíà íåâàæíî, êàêîé èç äâóõ âåòâåé äåðåâà
íàçíà÷èòü 0, à êàêîé 1. Ïîýòîìó ðåçóëüòàò íåîäíîçíà÷åí â ñìûñëå
êîíêðåòíîé êîäèðîâêè. Íî îí îäíîçíà÷åí (ïðè èçáðàííîì âûøå äåëåíèè
òåêñòà íà 8-áèòîâûå êóñî÷êè) â ñìûñëå îáúåìà ñæàòîãî òåêñòà. È ýòîò
îáúåì ïîëíîñòüþ îïðåäåëÿåòñÿ äëèíàìè ïðåäñòàâëåíèé ñèìâîëîâ. Ñ äðóãîé
ñòîðîíû, çíàÿ äëèíû ïðåäñòàâëåíèé, óæå íåòðóäíî (êàê áóäåò ïîêàçàíî)
ïîñòðîèòü ñîáñòâåííî ïðåäñòàâëåíèÿ. Ïîýòîìó íàéòè äëèíû íîâûõ
ïðåäñòàâëåíèé ñèìâîëîâ - ýòî ðåøàþùèé, êëþ÷åâîé øàã, ïîñëå êîòîðîãî
íå âûéòè íà îïòèìàëüíîå ñæàòèå (îïòèìàëüíîå ïî ÷àñòîòàì) ìîæíî
òîëüêî â ðåçóëüòàòå ãðóáåéøèõ îøèáîê.
Òàêèì îáðàçîì, çàäà÷ó ìîæíî ðàçäåëèòü íà äâå îòíîñèòåëüíî
íåçàâèñèìûå ÷àñòè: à) âû÷èñëåíèå äëèí ïðåäñòàâëåíèé, á) âû÷èñëåíèå
çíà÷åíèé ïðåäñòàâëåíèé ñèìâîëîâ.
Àëãîðèòì Õàôôìàíà ïðèìå÷àòåëåí òåì, ÷òî â íåì íåò ôîðìóë
è ïðàêòè÷åñêè íåò âû÷èñëåíèé, åñëè äàæå ñðàâíèâàòü ñ äðóãèìè
ìåòîäàìè àðõèâàöèè, îáû÷íî íàïè÷êàííûìè ñëîæíûìè ðàñ÷åòàìè è òîíêèìè
îöåíêàìè. Òåì íå ìåíåå, åñëè ïîïûòàòüñÿ çàïðîãðàììèðîâàòü àëãîðèòì
Õàôôìàíà ìàêñèìàëüíî áëèçêî ê åãî ëàêîíè÷íûì ôðàçàì, òî âîçíèêíóò ïðîáëåìû,
ñïîñîáíûå ïîñòàâèòü â òóïèê äàæå îïûòíîãî ñïåöèàëèñòà. È ïî íåèçìåííîìó
äåðåâó ëàçèòü íåïðîñòî, à òóò ìîæåò ïîíàäîáèòüñÿ 255 ðàçíûõ ñîñòîÿíèé
äåðåâà, ïðè÷åì îíè ïîÿâëÿþòñÿ òîëüêî â ïðîöåññå ðàñ÷åòà, çàðàíåå î íèõ
íåëüçÿ ñêàçàòü ïî÷òè íè÷åãî. Óæå ìàÿ÷èò ìåãàáàéòíûé ìàññèâ è ìíîæåñòâî
ïåðåòàñîâîê, ãðîçÿùèõ ïîñòàâèòü êðåñò íà áûñòðîäåéñòâèè.
Îäíàêî ïîñëå îòñå÷åíèÿ ëèøíåãî îêàçûâàåòñÿ, ÷òî äëÿ âû÷èñëåíèÿ
äëèí ïî çàäàííûì ÷àñòîòàì âõîæäåíèÿ ñèìâîëîâ äîñòàòî÷íî 1 ÊÁ îïåðàòèâíîé
ïàìÿòè è 0.09 ÊÁ ìàøèííîãî êîäà (íà IBM PC), ò.å. äåñÿòêà ñòðîê íà
õîðîøåì ÿçûêå ïðîãðàììèðîâàíèÿ.
0.5 ÊÁ ïðèäåòñÿ ïîòðàòèòü íà êîëè÷åñòâà âõîæäåíèé ñèìâîëîâ â
òåêñò. (Ýòî - äëÿ èñõîäíîãî òåêñòà äî 64 ÊÁ. Èñõîäíûé òåêñò â 16 ÌÁ
ïîòðåáîâàë áû ìàññèâ äëÿ âõîæäåíèé îáúåìîì 0.75 ÊÁ è ò.ä.) Ñîîòâåòñòâèå
ñèìâîëàì - ïîçèöèîííîå, ò.å. íîìåð ñèìâîëà = íîìåð ïîçèöèè â ìàññèâå.
À ñîáñòâåííî äëÿ ðàáîòû ïîíàäîáèòñÿ åùå äî 0.5 ÊÁ äëÿ ïàð íîìåðîâ ñèìâîëîâ.
Êàæäàÿ ïàðà îòðàæàåò îáðàçîâàíèå î÷åðåäíîãî âñïîìîãàòåëüíîãî ñèìâîëà ïî
äâóì ñèìâîëàì ñ ìèíèìàëüíîé ÷àñòîòîé.
ÀËÃÎÐÈÒÌ ÂÛ×ÈÑËÅÍÈß ÄËÈÍ.
Ýòàï 1: çàïîëíåíèå ðàáî÷åãî ìàññèâà.
Âûáèðàåì ïàðó ñèìâîëîâ ñ íàèìåíüøèìè íåíóëåâûìè êîëè÷åñòâàìè
âõîæäåíèé Ê1 è Ê2. Åñëè òàêèõ íå íàøëîñü òî ïåðåõîäèì íà ýòàï 2.
Çàñûëàåì â ðàáî÷èé ìàññèâ íîìåðà âûáðàííûõ ñèìâîëîâ. Çàòåì ê ÿ÷åéêå ñ Ê2
äîáàâëÿåì Ê1, à ÿ÷åéêó ñ Ê1 îáíóëÿåì. Ïîâòîðÿåì ýòàï 1.
Ýòàï 2: ïîäñ÷åò äëèí.
Äëÿ êàæäîãî ñèìâîëà S äåëàåì ñëåäóþùåå. Ïîëàãàåì ðàáî÷åå çíà÷åíèå
R=S è îáíóëÿåì îäíîáàéòîâûé ñ÷åò÷èê. Åñëè â 1-é ïàðå èç ðàáî÷åãî ìàññèâà
åñòü R, òî ïîëàãàåì R ðàâíûì 2-ìó ÷èñëó èç ýòîé ïàðû è óâåëè÷èâàåì ñ÷åòêèê
íà 1. Ïåðåõîäèì êî 2-é ïàðå è ò.ä.
 èòîãå â ñ÷åò÷èêå íàõîäèòñÿ èñêîìàÿ äëèíà, òàê êàê îíà ðàâíà
êîëè÷åñòâó ñëèÿíèé, â êîòîðûõ ó÷àñòâîâàë ñèìâîë S è åãî ïîñëåäîâàòåëè.
ÊÎÍÅÖ àëãîðèòìà.
 îòëè÷èå îò ñëîâåñíîãî èçëîæåíèÿ çäåñü íå ïîíàäîáèëèñü
âñïîìîãàòåëüíûå ñèìâîëû Z, Y, X, ... è ñîîòâåòñòâóþùèå ÿ÷åéêè ïàìÿòè.
Ìîæíî ñêàçàòü, ÷òî âñïîìîãàòåëüíûé ñèìâîë íàñëåäóåò èìÿ îäíîãî èç
ðîäèòåëåé.
Èç èçëîæåííîãî àëãîðèòìà íåòðóäíî èçâëå÷ü è ñîáñòâåííî áèòîâûå
ïðåäñòàâëåíèÿ. Äîñòàòî÷íî íà ýòàïå 2 îòìå÷àòü, êàêèì ýëåìåíòîì ïàðû
îêàçàëîñü R. Åñëè ïåðâûì, òî êëàäåì 0, èíà÷å 1, ýòî è áóäåò áèòîâîå
ïðåäñòàâëåíèå ñèìâîëà S, ïðàâäà, â îáðàòíîì ïîðÿäêå. Òàê ÷òî ôîðìàëüíî
àëãîðèòì èñ÷åðïûâàåò ìåòîä Õàôôìàíà. Ê ñîæàëåíèþ, ïîëó÷åííûå áèòîâûå
ïðåäñòàâëåíèÿ - ýòî ñîâñåì íå òå, êîòîðûå ìèíèìèçèðóþò òàáëèöó
ñîîòâåòñòâèÿ è, ñòðîãî ãîâîðÿ, îáúåì ñæàòîãî òåêñòà, åñëè åãî ìûñëèòü
âìåñòå ñ êëþ÷îì äëÿ ðàñøèôðîâêè. Áîëåå òîãî, íèêàêèìè ïðîñòûìè
ïîïðàâêàìè íå óäàåòñÿ âûâåñòè àëãîðèòì Õàôôìàíà íà ëó÷øåå âî âñåõ
îòíîøåíèÿõ ïðåäñòàâëåíèå ñèìâîëîâ. Åãî ïðîùå íà÷àòü ñòðîèòü ïî äðóãîìó
ïðèíöèïó, èñõîäÿ òîëüêî èç äëèí.
Âû÷èñëÿåìûå äëèíû ìîæíî ïîìåùàòü â ìàññèâ, ãäå ðàíüøå áûëè
êîëè÷åñòâà âõîæäåíèé. Òàê ÷òî äîïîëíèòåëüíîé ïàìÿòè äëÿ äëèí íå
òðåáóåòñÿ.
Ïîäñ÷åò äëèí íà ýòàïå 2 ìîæíî óñêîðèòü íà 2 ïîðÿäêà ïóòåì
îäíîêðàòíîãî (à íå 256-êðàòíîãî, êàê ó íàñ) ïðîõîäà ðàáî÷åãî ìàññèâà
è îäíîâðåìåííîãî çàïîëíåíèÿ 256 ñ÷åò÷èêîâ.  òàêîì ñëó÷àå ôîðìàëüíî
íå ïîíàäîáèòñÿ è ðàáî÷èé ìàññèâ èç 0.5 ÊÁ, òàê êàê ïàðû ìîæíî çàñóíóòü
â ñòåê. (Ïðàâäà, ÷èòàòü åãî ïðèäåòñÿ íåñòàíäàðòíûì îáðàçîì.) Îäíàêî
èç-çà íåçíà÷èòåëüíîãî îáúåìà ðàáî÷åãî ìàññèâà îáùèé ýôôåêò îò òàêîãî
óñêîðåíèÿ ìàëîçàìåòåí.
Äëÿ íå ôîðìàëüíîãî ñîêðàùåíèÿ ðàáî÷åãî ìàññèâà, à ïî ñóùåñòâó,
ìîæíî èñïîëüçîâàòü òîò ôàêò, ÷òî ïî ìåðå çàïîëíåíèÿ ðàáî÷åãî ìàññèâà
ñ òîé æå ñêîðîñòüþ, íàîáîðîò, îñâîáîæäàåòñÿ ìàññèâ ñ êîëè÷åñòâàìè
âõîæäåíèé. Ïîýòîìó çàïèñûâàòü ïàðû ìîæíî íà îñâîáîäèâøååñÿ ìåñòî.
Íî òîãäà äëÿ êàæäîãî äâóáàéòîâîãî ñëîâà íàäî ââåñòè îäíîáèòîâûé
ïðèçíàê, êîòîðûé áóäåò óêàçûâàòü, ÷òî õðàíèòñÿ â ñëîâå: òî ëè âñå åùå
êîëè÷åñòâî, òî ëè óæå ïàðà, îòðàæàþùàÿ ñëèÿíèå. Ïðè çàïèñè î÷åðåäíîé
ïàðû äðóãèå (âñå èëè ÷àñòè÷íî) ïàðû ïðèäåòñÿ äâèãàòü, ÷òîáû ñîõðàíèòü
ïîðÿäîê ïàð. Óñëîæíèòñÿ è àëãîðèòì â öåëîì. Âî âñÿêîì ñëó÷àå ýêîíîìèÿ
480 áàéòîâ ïàìÿòè â íåñêîëüêî ðàç ïðåâîñõîäèò óáûòêè îò ðîñòà
çàãðóçî÷íîãî ìîäóëÿ. 32 áàéòà, çàíÿòûå ïðèçíàêàìè, óæå ìîæíî
ðàçìåñòèòü â ðåãèñòðàõ (íàïðèìåð, ñ ëèõâîé õâàòàåò ðåãèñòðîâ
ñîïðîöåññîðà, èñïîëüçîâàòü êîòîðûé ðàíåå íå áûëî íèêàêîé íàäîáíîñòè).
Ïðè ïîäñ÷åòå äëèí òàêæå íåòðóäíî äîáèòüñÿ, ÷òîáû ïàðà çà ïàðîé
ñòàíîâèëèñü èçëèøíèìè, òîãäà íà îñâîáîäèâøååñÿ ìåñòî ìîæíî ïèñàòü
äëèíû, àíàëîãè÷íî èñïîëüçóÿ 256 îäíîáèòîâûõ ïðèçíàêîâ. Ïîýòîìó íàëèöî
âàðèàíò àëãîðèòìà, êîòîðûé âîîáùå íå òðåáóåò ðàáî÷èõ ìàññèâîâ â
îïåðàòèâíîé ïàìÿòè (åñëè, êîíå÷íî, íå ñ÷èòàòü èñõîäíûõ äàííûõ).
Íåòðóäíî âèäåòü, ÷òî åñëè îäèí ñèìâîë âñòðå÷àåòñÿ â òåêñòå
â 2 ðàçà ÷àùå äðóãîãî ñèìâîëà, òî ïåðâûé, âîîáùå ãîâîðÿ, äîëæåí
ïîëó÷èòü äëèíó ïðåäñòàâëåíèÿ íà îäèí áèò êîðî÷å, ÷åì äëèíà äëÿ 2-ãî
ñèìâîëà. Åñëè ñèìâîë âñòðå÷àåòñÿ Ê ðàç, à îáúåì èñõîäíîãî òåêñòà
(÷èñëî âñåõ ñèìâîëîâ) N, òî îïòèìàëüíàÿ äëèíà ïðåäñòàâëåíèÿ ñèìâîëà
äîëæíà îêàçàòüñÿ âîçëå äâîè÷íîãî ëîãàðèôìà îò N/Ê . Âîïðîñ ñ äëèíàìè
ïðåäñòàâëåíèé ëåãêî ðåøàëñÿ áû, åñëè âñå çíà÷åíèÿ òàêèõ ëîãàðèôìîâ
îêàçàëèñü öåëûìè. Íàïðèìåð, åñëè â òåêñòå èç 64 ñèìâîëîâ îêàçàëîñü
16 áóêâ À, 16 áóêâ Á, 16 áóêâ Â, 8 áóêâ Ä, 4 áóêâû Å è 4 áóêâû Æ,
òî áóêâû À, Á,  ïîëó÷èëè áû 2 áèòîâûå ïðåäñòàâëåíèÿ, Ä - 3-áèòîâîå,
Å è Æ - 4-áèòîâûå.
Ïëîõà èäåÿ ïðîñòî îêðóãëÿòü çíà÷åíèÿ ëîãàðèôìîâ äî áëèæàéøåãî
öåëîãî. Ìîæåò îêàçàòüñÿ, ÷òî áóäóò èñïîëüçîâàíû íå âñå áèòîâûå
ñî÷åòàíèÿ è äëèíà ñæàòîãî òåêñòà íå ñòàíåò ìèíèìàëüíîé. Íî åùå õóæå
áóäåò, åñëè íåêîòîðûì ñèìâîëàì íå õâàòèò âîçìîæíûõ ñî÷åòàíèé áèòîâ.
Ïî äëèíàì L1, L2, ... Ln ëåãêî îïðåäåëèòü, õâàòèò ëè ñî÷åòàíèé.
Äëÿ êàæäîé Li íàäî âçÿòü 1/2 â ñòåïåíè Li è ïðîñóììèðîâàòü ïî i îò 1
äî n. Åñëè ñóììà ïðåâûñèëà åäèíèöó, òî òàêîé íàáîð äëèí âîîáùå íå
ãîäèòñÿ. Åñëè ñóììà ìåíüøå 1, òî ñæàòèå íå áóäåò îïòèìàëüíûì.
(Ïîëåçíî çàìåòèòü, ÷òî äëÿ ñîâïàäåíèÿ ñ åäèíèöåé êîëè÷åñòâî ñèìâîëîâ
ñ ìàêñèìàëüíîé äëèíîé äîëæíî áûòü ÷åòíî.)
Ìîæíî îêðóãëÿòü âñÿêèé ðàç â òàêóþ ñòîðîíó, ÷òîáû ðàáî÷åå
çíà÷åíèå óêàçàííîé ñóììû îñòàâàëîñü ìåíüøå åäèíèöû. Òîãäà íàäî áûòü
ãîòîâûì, ÷òî èíîãäà ïðèäåòñÿ îêðóãëÿòü íå äî áëèæàéøåãî öåëîãî, à
ïåðåñêàêèâàòü åùå íà íåñêîëüêî åäèíèö. Íî è ýòîò ïîäõîä, êàê ïðàâèëî,
íå âåäåò ê îïòèìóìó, õîòÿ è äàåò ïðèåìëåìûå ðåçóëüòàòû.
Èäåþ îêðóãëåíèé ìîæíî ðàçâèòü, îðãàíèçîâàâ ïåðåáîð ðàçëè÷íûõ
ñïîñîáîâ îêðóãëåíèé, è â èòîãå äîáðàòüñÿ äî ïðåäåëüíîãî ïî Õàôôìàíó
ñæàòèÿ èñõîäíîãî òåêñòà. Íî â èòîãå ïîëó÷àåòñÿ ãðîìîçäêèé è ìåäëåííûé
àëãîðèòì.
Óïîìÿíåì åùå îäèí ïîëåçíûé ìåòîä âû÷èñëåíèÿ äëèí. Ñíà÷àëà
íàçíà÷àåì âñåì ñèìâîëàì 8-áèòîâûå äëèíû. Åñëè óïîìÿíóòàÿ â ïðåäûäóùåì
ìåòîäå ñóììà ìåíüøå åäèíèöû, òî íàèáîëåå óïîòðåáèòåëüíûì ñèìâîëàì
äàåì 7-áèòîâûå äëèíû, ïîêà òà æå ñóììà îñòàåòñÿ íå áîëåå 1.
Åñëè è çäåñü íå äîñòèãíóòà 1, òî àíàëîãè÷íî íàçíà÷àåì 6-áèòîâûå
äëèíû è ò.ä. Çàòåì ïåðåáèðàåì âñå èìåþùèåñÿ çíà÷åíèÿ äëèí, íà÷èíàÿ
ñ ìåíüøèõ. Åñëè ñ äëèíîé L åñòü ãðóïïà ïî êðàéíåé ìåðå èç 3 ñèìâîëîâ,
òî ïðîáóåì äëèíó äëÿ íàèáîëåå óïîòðåáèòåëüíîãî ñèìâîëà èç ýòîé ãðóïïû
óìåíüøèòü íà åäèíèöó, à äëèíû äëÿ äâóõ íàèìåíåå óïîòðåáèòåëüíûõ -
óâåëè÷èòü íà åäèíèöó. Ëåãêî ïîäñ÷èòàòü, êàê ïðè ýòîì äîëæåí èçìåíèòüñÿ
îáúåì èòîãîâîãî òåêñòà. Åñëè îáúåì óìåíüøèëñÿ, òî âíîâü ðåæåì ãðóïïó
ñ äëèíàìè L, èíà÷å ïåðåõîäèì ê L+1.
Ýòîò àëãîðèòì áûñòð, êîìïàêòåí (0.07 ÊÁ ìàøèííîãî êîäà),
åìó äîñòàòî÷åí ìàññèâ â 0.625 ÊÁ (0.5 ÊÁ íà çàäàííûå êîëè÷åñòâà
âõîæäåíèé è 0.125 ÊÁ íà äëèíû). Íî ïðè áîëüøîì ðàçáðîñå ÷àñòîò
(è ñîîòâåòñòâåííî êîðîòêèõ ãðóïïàõ äëÿ êàæäîé äëèíû L) àëãîðèòì
íå âûâîäèò íà ïðåäåëüíîå ñæàòèå. Äëÿ òàêîãî âûõîäà íóæíû áîëåå
ñëîæíûå ïðîáû, íàïðèìåð, óäëèíÿòü ïðåäñòàâëåíèÿ íå ïàðû ñèìâîëîâ
èç ãðóïïû L, à òîëüêî îäíîãî ñèìâîëà è ïàðû èç ãðóïïû L+1 è ò.ï.
Äîâîäêà ýòîé èäåè âåäåò ê óñëîæíåíèþ è çàìåäëåíèþ àëãîðèòìà, ò.å.
ê óòðàòå åãî ïðåèìóùåñòâ. Èìååò ñìûñë ïðèìåíÿòü åãî èìåííî â
óïðîùåííîì âèäå, êîãäà ðàçáðîñ ÷àñòîò íåâåëèê, ëèáî ïðåäåëüíîå
ñæàòèå íå àêòóàëüíî.
4. Áèòîâûå ïðåäñòàâëåíèÿ ñèìâîëîâ
Ïî çàäàííûì äëèíàì ïðåäñòàâëåíèé ìîæíî ïîëó÷èòü ìíîãî
âàðèàíòîâ êîíêðåòíûõ ïðåäñòàâëåíèé ñèìâîëîâ, íî ñðåäè íèõ åñòü
íåìíîãèå, êîòîðûå ìèíèìèçèðóþò òàáëèöó äåêîäèðîâêè.
 îáû÷íîé äâîè÷íîé çàïèñè ÷èñëà êàæäàÿ åäèíè÷êà èìååò âåñ
ñîãëàñíî ñâîåé ïîçèöèè. Ñàìàÿ ìëàäøàÿ âåñèò 1, ñëåäóþùàÿ 2 è ò.ä.
 èòîãå ñàìî ÷èñëî ðàâíî ñóììå âåñîâ åäèíè÷åê â åãî çàïèñè.
Àíàëîãè÷íî ìîæíî íàçíà÷èòü âåñà â êîäèðîâêå ïî Õàôôìàíó.
Íî ïðè ïåðåõîäå ê î÷åðåäíîé ïîçèöèè âåñ íå îáÿçàí âîçðàñòàòü
âäâîå, îí ìîæåò äàæå óìåíüøèòüñÿ.
Ðèñ.2. Ïðèíöèïèàëüíîå ðàçëè÷èå òàáëèö âåñîâ
äëÿ ñòàíäàðòíîãî è ñïåöèàëüíîãî ïðåäñòàâëåíèé
Äëÿ ïðèìåðà, ñ êîòîðîãî íà÷àòî äàííîå ñî÷èíåíèå, äàëåå ñèìâîëû
ïðîíóìåðîâàíû (íà÷èíàÿ ñ 0) â ïîðÿäêå óáûâàíèÿ è ïðèâåäåíû èñêîìûå
ïðåäñòàâëåíèÿ:
0) "1" - 00
1) "2" - 10
2) "3" - 01
3) "4" - 110
4) "5" - 111
Êðàéíÿÿ ëåâàÿ åäèíè÷êà õàôôìàíîâñêîãî ïðåäñòàâëåíèÿ âåñèò 1 (è ýòî
åäèíñòâåííî âîçìîæíîå çíà÷åíèå äëÿ ëþáûõ òåêñòîâ è ëþáûõ íàáîðîâ
äëèí). Ñëåäóþùàÿ âåñèò 2, ïîñëåäíÿÿ âåñèò 1. Íåòðóäíî ïðîâåðèòü, ÷òî
íîìåð ëþáîãî ñèìâîëà ðàâåí ñóììå âåñîâ â ïðåäñòàâëåíèè ýòîãî ñèìâîëà.
Îòñþäà ñðàçó âèäíî ïðåèìóùåñòâî: â äåêîäèðîâùèêå íå íóæíî
äëÿ êàæäîãî ñèìâîëà õðàíèòü åãî áèòîâîå ïðåäñòàâëåíèå. Ïðè ñ÷èòûâàíèè
áèòîâ ñæàòîãî òåêñòà íîìåð ñèìâîëà áóäåò íåïîñðåäñòâåííî âû÷èñëÿòüñÿ,
è äîñòàòî÷íî õðàíèòü òîëüêî âåñà (íå áîëåå 16 áàéòîâ, îáùèõ äëÿ âñåõ
ñèìâîëîâ èñõîäíîãî òåêñòà) è 256-áàéòîâóþ òàáëèöó ñîîòâåòñòâèÿ ñèìâîëîâ
è èõ âíóòðåííèõ íîìåðîâ (îáðàçîâàííûõ ñîãðàñíî óáûâàíèþ ÷àñòîò).
Ïðàâäà, ïðè ðàñøèôðîâêå ñæàòîãî òåêñòà íàäî åùå âîâðåìÿ ïîíÿòü,
÷òî íîìåð î÷åðåäíîãî ñèìâîëà ñôîðìèðîâàí, íî äëÿ ýòîãî, êàê áóäåò
âèäíî, äîïîëíèòåëüíîé èíôîðìàöèè íå òðåáóåòñÿ.
Äëÿ ñâåäåíèÿ ïðèâåäåì àëãîðèòì, êîòîðûé áåç õèòðîñòåé ïåðåáîðîì
âû÷èñëÿåò áèòîâûå ïðåäñòàâëåíèÿ. Îí õîðîø ïî îáúåìó (0.04 ÊÁ), íî íå
ëó÷øèé ïî ñêîðîñòè, õîòÿ è îíà èçìåðÿåòñÿ â ñîòûõ äîëÿõ ñåêóíäû, è
îòíîñèòåëüíàÿ íåñïåøíîñòü âûÿâëÿåòñÿ òîëüêî ñïåöèàëüíûìè ýêñïåðèìåíòàìè.
Îí ïîìîæåò ïîíÿòü ñóòü áîëåå ìîùíîãî àëãîðèòìà, êîòîðûé áóäåò èçëîæåí
ïîçæå. Èòàê, äëÿ êàæäîãî ñèìâîëà, âñòðå÷àþùåãîñÿ â èñõîäíîì òåêñòå,
çàäàíà äëèíà áèòîâîãî ïðåäñòàâëåíèÿ.
1. Ïîëàãàåì ðàáî÷åå äâóáàéòîâîå çíà÷åíèå R = 0.
2. Áåðåì ñèìâîë S ñ ìèíèìàëüíîé äëèíîé ïðåäñòàâëåíèÿ L èç
òåõ ñèìâîëîâ, ÷òî åùå íå ïîëó÷èëè ïðåäñòàâëåíèå. Åñëè òàêîãî íåò,
òî ïðîöåññ çàâåðøåí.
3. Îò R â êà÷åñòâå ïðåäñòàâëåíèÿ äëÿ S áåðåì L ìëàäøèõ áèòîâ.
4. Óâåëè÷èâàåì R íà 1. Åñëè ñðåäè îáñëóæåííûõ åñòü ñèìâîë
ñ íåêîé äëèíîé M, ÷üå ïðåäñòàâëåíèå ñîâïàäàåò ñ M ìëàäøèìè áèòàìè
ïðåäñòàâëåíèÿ S, òî ïåðåõîäèì íà ï.3., èíà÷å íà ï.2.
Ïîïóòíî ìîæíî âû÷èñëèòü âåñà áèòîâ, åñëè çàìåòèòü, ÷òî âåñ
ñòàðøåé åäèíè÷êè â ïðåäñòàâëåíèè î÷åðåäíîãî ñèìâîëà S ðàâåí âíóòðåííåìó
íîìåðó ñèìâîëà S ìèíóñ âåñà ïðåäûäóùèõ åäèíè÷åê â åãî ïðåäñòàâëåíèè.
(Ïîëåçíî çàìåòèòü, ÷òî ïðè ôîðìèðîâàíèè áèòîâîãî ïðåäñòàâëåíèÿ
ñèìâîëà îò R îòêèäûâàþòñÿ òîëüêî íóëåâûå áèòû. Åñëè âäðóã ýòî íå
òàê, òî äëèíû çàäàíû íåâåðíî, è íèêàêîé êîäèðîâêè íå ïîëó÷èòñÿ.)
Ïåðåéäåì ê îñíîâíîìó àëãîðèòìó äàííîãî ðàçäåëà. Êàê è ñ
ñóäüáîíîñíîé èäååé Õàôôìàíà, íà÷íåì ñî ñëîâåñíîãî îïèñàíèÿ, êîòîðîå
äîñòàòî÷íî ëàêîíè÷íî è ñðàçó ìíîãîå ïðîÿñíÿåò.
Ïóñòü ñèìâîëû óïîðÿäî÷åíû ïî íåóáûâàíèþ äëèí ïðåäñòàâëåíèé.
Âîçüìåì ñèìâîëû ñ ìàêñèìàëüíîé äëèíîé ïðåäñòàâëåíèé.
Èõ îáÿçàòåëüíî îêàæåòñÿ ÷åòíîå ÷èñëî. Ïåðâîé ïîëîâèíå âûáðàííûõ
ñèìâîëîâ íàçíà÷èì â ñòàðøèé ðàçðÿä 0, îñòàëüíûì 1. Ýòèì ðàçðÿäîì
â èòîãå è áóäóò îòëè÷àòüñÿ îáå ïîëîâèíû. Ïîýòîìó ïðî âòîðóþ èç
íèõ ìîæíî âðåìåííî çàáûòü, êàê è ïðî ñòàðøèé, óæå íàçíà÷åííûé áèò.
à ïåðâàÿ ïîëîâèíà åñòåñòâåííî ïðèñîåäèíèòñÿ ê ãðóïïå ñèìâîëîâ ñ
ìåíüøåé íà åäèíèöó ðàçðÿäíîñòüþ.  ðåçóëüòàòå ïîëó÷àåì ñèòóàöèþ,
èäåíòè÷íóþ èñõîäíîé, íî ñ ìåíüøèì êîëè÷åñòâîì ñèìâîëîâ è ìåíüøåé
ìàêñèìàëüíîé äëèíîé. Ïîâòîðÿåì óêàçàííóþ ïðîöåäóðó äî òåõ ïîð,
ïîêà íå îñòàíóòñÿ 2 ñèìâîëà. Íàçíà÷àåì ïåðâîìó áèò = 0 , âòîðîìó 1.
Çàòåì âîçâðàùàåìñÿ ïî ïðîéäåííîìó ïóòè, çàïîëíÿÿ ïðîáåëû ïðîñòûì
äóáëèðîâàíèåì.
Ðèñ.3. Õàðàêòåðíûå ôðàãìåíòû ñïåöèàëüíîãî
ïðåäñòàâëåíèÿ ñèìâîëîâ
Áûñòðûé àëãîðèòì ïîïóòíî è ëåãêî âûäàåò òàáëèöó âåñîâ. Âåñ
ñòàðøåãî èç èñïîëüçóåìûõ ðàçðÿäîâ ðàâåí ïîëîâèíå ÷èñëà ñèìâîëîâ ñ
ìàêñèìàëüíîé äëèíîé ïðåäñòàâëåíèé. È äàëåå - ñîãëàñíî îïèñàííûì
èäåíòè÷íûì ñèòóàöèÿì.
Ìû íå ïðîâîäèì îòäåëüíîãî òåîðåòè÷åñêîãî èññëåäîâàíèÿ
çàòðîíóòûõ âîïðîñîâ, íî âñå íåîáõîäèìûå èíñòðóìåíòû çäåñü äàíû.
Òàê, óïðîùåííûé âàðèàíò àëãîðèòìà âû÷èñëåíèÿ ïðåäñòàâëåíèé
ïðîÿñíÿåò, êàê óñòðîåíû ñïåöèàëüíûå ïðåäñòàâëåíèÿ, è ôàêòè÷åñêè
äîêàçûâàåò èõ åäèíñòâåííîñòü (åñëè íå ñ÷èòàòü, êîíå÷íî, ÷òî
ñèìâîëû ñ îäèíàêîâîé äëèíîé â ïðèíöèïå ìîãóò ïîìåíÿòüñÿ ñâîèìè
ïðåäñòàâëåíèÿìè). Ýòèì ñòðîåíèåì ïîëüçóåòñÿ âòîðîé âàðèàíò
àëãîðèòìà. Âòîðîé âàðèàíò â ñâîþ î÷åðåäü îáîñíîâûâàåò çàêîííîñòü
ïîíÿòèÿ âåñîâ è äàåò îäèí èç ñïîñîáîâ èõ âû÷èñëåíèÿ, êîòîðûé
âîîáùå ìîæåò áûòü ïðèíÿò çà îïðåäåëåíèå ïîíÿòèÿ âåñîâ.
Êàê îáû÷íî, îò õîðîøåãî ïðèíöèïèàëüíîãî îïèñàíèÿ åùå äàëåêî
äî ïðîãðàììû. Ïîýòîìó ñåé÷àñ ïðèâåäåì áîëåå äåòàëüíóþ ðåäàêöèþ
òîãî æå àëãîðèòìà.  íåé íàçíà÷åíèÿ ïðîèçâîäÿòñÿ çà îäèí ïðîõîä.
Ïåðâîìó ñèìâîëó íàçíà÷àåì â ìëàäøèé ðàçðÿä 0, âòîðîìó 1.
Äàëåå âñÿêèé ðàç èìååì ñèòóàöèþ: çàïîëíåíî L áèòîâ äëÿ êàæäîãî èç
N ñèìâîëîâ. Èç ýòèõ N òîëüêî K ïîñëåäíèõ ñèìâîëîâ (âîçìîæíî è
ñîâïàäåíèå K=N) èìåþò äëèíó ïðåäñòàâëåíèé áîëüøå L. Íàçíà÷àåì
0 â L+1 -é ðàçðÿä êàæäîìó èç N òåõ æå ñèìâîëîâ, è 1 ñëåäóþùèì çà
íèìè K ñèìâîëàì. Ìàòðèöó çíà÷åíèé ðàçðÿäîâ ñ 1 ïî L -é äëÿ ñèìâîëîâ
ñ N-K+1 -ãî ïî N -é äóáëèðóåì äëÿ àíàëîãè÷íûõ ðàçðÿäîâ ñèìâîëîâ
ñ N+1 -ãî ïî N+K -é. Êîíåö ïî ïðèçíàêó K=0.
K - ýòî è åñòü âåñ î÷åðåäíîãî ðàçðÿäà.
Ïîëåçíîå ñëåäñòâèå: ñèìâîë ñ ìàêñèìàëüíûì âíóòðåííèì íîìåðîì
ñïëîøü èçîáðàæàåòñÿ åäèíèöàìè.
Ïîÿñíèì, ÷òî àëãîðèòì íàçíà÷àåò íåêîòîðûì ñèìâîëàì áîëüøå
ðàçðÿäîâ, ÷åì íàäî (è òîãäà îíè íóëåâûå). Íî ýòî íå áåäà, òàê êàê
äëèíû ïðåäñòàâëåíèé èçâåñòíû.
Ïåðåéäåì ê îêîí÷àòåëüíîìó âàðèàíòó àëãîðèòìà. (Åãî îáúåì
â êîäàõ ìåíåå 0.05 ÊÁ). Êðîìå òîãî, ÷òî ñèìâîëû óïîðÿäî÷åíû ïî
íåóáûâàíèþ çàäàííûõ äëèí ïðåäñòàâëåíèé, åùå áóäåì ïðåäïîëàãàòü,
÷òî íà ìåñòå êàæäîãî èç èñêîìûõ ïðåäñòàâëåíèé óæå ëåæàò 16 íóëåâûõ
áèòîâ, ò.å. ìàññèâ ïðåäñòàâëåíèé M(i) îáíóëåí. Ýòî ïîçâîëèò íå äåëàòü
â îáùåì-òî èçëèøíèå (íî ìíîãî÷èñëåííûå) îïåðàöèè ïî íàçíà÷åíèþ íóëåé
â îòäåëüíûå áèòû.
ÀËÃÎÐÈÒÌ ÂÛ×ÈÑËÅÍÈß ÁÈÒÎÂÛÕ ÏÐÅÄÑÒÀÂËÅÍÈÉ ÑÈÌÂÎËÎÂ
1. Ïîëàãàåì Z=2, N=2, L=1, M(2)=1.
2. Âû÷èñëÿåì K - êîëè÷åñòâî ñèìâîëîâ èç ïåðâûõ N øòóê, ÷üè
ïðåäñòàâëåíèÿ â èòîãå äîëæíû áûòü áîëüøå L. Åñëè K=0, òî êîíåö àëãîðèòìà.
3. Ïîëàãàåì M(i) = M(i-K)+Z äëÿ i îò N+1 ïî N+K .
4. Óâåëè÷èâàåì N íà K, óâåëè÷èâàåì L íà 1, à Z óäâàèâàåì.
Ïåðåõîä íà ï.2. ÊÎÍÅÖ àëãîðèòìà.
Íàïîìíèì, ÷òî ïîëó÷àåìûå ïî õîäó àëãîðèòìà âåëè÷èíû K - ýòî
âàæíûå äëÿ ïîñëåäóþùèõ äåéñòâèé âåñà ðàçðÿäîâ, èõ íàäî çàïàñòè â
íåêîòîðûé ìàññèâ. Ïàìÿòè òåïåðü ïîíàäîáèòñÿ ÷óòü áîëüøå, ÷åì íà ýòàïå
âû÷èñëåíèÿ äëèí. Õîòÿ èñõîäíûå äàííûå ìîæíî ïîìåñòèòü â 128 áàéòîâ,
íî íà âûõîäå âñå ðàâíî æåëàòåëüíî èìåòü òå æå 128 áàéòîâ ñ äëèíàìè
è 512 áàéòîâ ñ ïðåäñòàâëåíèÿìè ñèìâîëîâ (ïî 2 áàéòà íà êàæäûé èç 256
ñèìâîëîâ), ÷òîáû áåç ëèøíèõ õëîïîò çàêîäèðîâàòü èñõîäíûé òåêñò.
Ïðè ýòîì òàêæå ìîæíî èñïîëüçîâàòü ìàññèâ, â êîòîðîì ðàíåå ïîñòóïèëè
íåíóæíûå òåïåðü êîëè÷åñòâà âõîæäåíèé ñèìâîëîâ. Ìîæíî ïîáîðîòüñÿ è
çäåñü çà ýêîíîìèþ ïàìÿòè, íî äëÿ äàííîãî ñî÷èíåíèÿ ýòî íå
ïåðâîî÷åðåäíàÿ çàäà÷à. Ê òîìó æå ïî ñðàâíåíèþ ñ íå õàôôìàíîâñêèìè
ìåòîäàìè, èñïîëüçóåìàÿ ïàìÿòü ìèêðîñêîïè÷åñêè ìàëà.
5. Ðàñøèôðîâêà ñæàòîãî òåêñòà
Ñëåäóþùèé àëãîðèòì äåøèôðîâêè ìîæåò áûòü ðàçìåùåí â 0.04 ÊÁ
ìàøèííîãî êîäà. Îí ïðåäïîëàãàåò çàäàííûìè: àäðåñ ñæàòîãî òåêñòà,
àäðåñ âûâîäà, àäðåñ òàáëèöû ñîîòâåòñòâèÿ, àäðåñ âåñîâ. Â òàáëèöå
ñîîòâåòñòâèÿ íå áîëåå 256 áàéòîâ. Ñ åå ïîìîùüþ ïî ôîðìèðóåìîìó â
ïðîöåññå ðàñ÷åòà íàøåìó âíóòðåííåìó íîìåðó â íóæíîé ïîçèöèè ìû
íàéäåì îáùåïðèíÿòîå 8-áèòîâîå ïðåäñòàâëåíèå ñèìâîëà. Â òàáëèöå âåñîâ
íå áîëåå 17 áàéòîâ, çäåñü óêàçàíû âåñà, íà÷èíàÿ ñ ìëàäøèõ ðàçðÿäîâ,
òàáëèöà äîëæíà çàâåðøàòüñÿ íóëåì. Ìîæíî ñêàçàòü, ÷òî óêàçàí è âåñ
ïåðâîãî èç íåèñïîëüçóåìûõ áèòîâ. (Èñõîäíûé òåêñò â 16 ÌÁ ìîæåò
óâåëè÷èòü òàáëèöó âåñîâ íà 8 áàéòîâ è ò.ä.)
Åùå, âîîáùå ãîâîðÿ, íóæåí îáúåì ñæàòîãî èëè ðàçâåðíóòîãî
òåêñòà, ÷òîáû âîâðåìÿ çàâåðøèòü ïðîöåññ. Íî èíîãäà (ñêàæåì, ïðè
ðàçâåðòûâàíèè çàãðóçî÷íîãî ìîäóëÿ â îïåðàòèâíîé ïàìÿòè) çäåñü ìîæíî
íåìíîãî âûãàäàòü, åñëè, íàïðèìåð, ðàçìåñòèòü òàáëèöó ñîîòâåòñòâèÿ
ñðàçó çà ñæàòûì òåêñòîì. Òîãäà ìû áóäåì çíàòü è àäðåñ êîíöà òåêñòà.
ÀËÃÎÐÈÒÌ ÐÀÑØÈÔÐÎÂÊÈ.
1. Óñòàíîâèì ðàáî÷èé àäðåñ A íà íà÷àëî òàáëèöû âåñîâ è
îáíóëèì îäíîáàéòîâûå ñ÷åò÷èêè P è R (áåççíàêîâûå ÷èñëà îò 0 äî 255).
2. ×èòàåì âåñ V ïî àäðåñó A, óâåëè÷èâàåì A íà 1,
÷èòàåì âåñ W ïî àäðåñó A.
Ñ÷èòûâàåì î÷åðåäíîé áèò ñæàòîãî òåêñòà. Åñëè îí íå 0, òî
óâåëè÷èâàåì P íà V. Óâåëè÷èâàåì R íà V.
3. Åñëè W+P > R , òî ïåðåõîä íà ï.2.
4. P - ýòî è åñòü èñêîìûé âíóòðåííèé íîìåð ñèìâîëà.
Âûâîäèì ñèìâîë ñîãëàñíî òàáëèöå ñîîòâåòñòâèÿ. Ïåðåõîäèì íà ï.1
äëÿ ðàñøèôðîâêè î÷åðåäíîãî ñèìâîëà. ÊÎÍÅÖ àëãîðèòìà.
Ïîÿñíèì, ÷òî àëãîðèòì íå òðåáóåò ïðîâåðîê íà èñ÷åðïàíèå
òàáëèöû âåñîâ ïðè ïîäñ÷åòå âíóòðåííåãî íîìåðà î÷åðåäíîãî ñèìâîëà.
Íàîáîðîò, äëÿ áîëüøèíñòâà ñèìâîëîâ ÷òåíèå íå äîõîäèò äî êîíöà ýòîé
òàáëèöû. Íî åñëè óæ àëãîðèòì äîáðàëñÿ äî êîíöà òàáëèöû, òî óñëîâèå
W+P > R çàâåäîìî îêàæåòñÿ íåâûïîëíåííûì, ïîñêîëüêó â ýòîì ñëó÷àå
W=0, â R ïðîñóììèðîâàíû âñå âåñà, à â P - òîëüêî ÷àñòü èç íèõ
(äëÿ ñèìâîëà ñ ìàêñèìàëüíûì âíóòðåííèì íîìåðîì îêàæåòñÿ P=R).
Îòñþäà, â ÷àñòíîñòè, ñëåäóåò, ÷òî ñóììà W+P â ïðîöåññå
âû÷èñëåíèé íèêîãäà íå ìîæåò ïðåâçîéòè 255 è äàæå ìàêñèìàëüíîãî
èç âíóòðåííèõ íîìåðîâ ñèìâîëîâ (òîãäà äëÿ íåå òîæå äîñòàòî÷íî
îäíîáàéòîâîé ÿ÷åéêè).
Ñîîòíîøåíèå W+P > R ïîëó÷àåòñÿ èç äëèííûõ òåîðåòè÷åñêèõ
âûêëàäîê, íî åãî ìîæíî ïîÿñíèòü âåñüìà ïðîñòî. Åñëè W+P íå
ïðåâîñõîäèò R, òî î÷åðåäíàÿ (åùå íå ïðî÷èòàííàÿ) åäèíè÷êà äàëà áû
äâîéíîå ïðåäñòàâëåíèå ñèìâîëà ñ íîìåðîì W+P , ïîýòîìó äëÿ íàáðàííîãî
P ÷òåíèå ñæàòîãî òåêñòà íåîáõîäèìî ïðåêðàòèòü. Ïðè W+P > R ìû,
íàîáîðîò, óçíàåì î ñóùåñòâîâàíèè ñèìâîëà ñ âíóòðåííèì íîìåðîì W+P ,
êîòîðûé íå óêëàäûâàåòñÿ â ïðî÷èòàííîå êîëè÷åñòâî ðàçðÿäîâ, äàæå åñëè
âñå èõ çàïîëíèòü åäèíè÷êàìè.  ýòîì ñëó÷àå ÷òåíèå íàäî ïðîäîëæèòü,
òàê êàê èíà÷å ìû çàâåäîìî íå îõâàòèì âñå ñèìâîëû èñõîäíîãî òåêñòà,
à íå ñ÷èòàííûé âîâðåìÿ ðàçðÿä áåçíàäåæíî èñïîðòèò ðåçóëüòàò.
256-áàéòîâàÿ òàáëèöà ñîîòâåòñòâèÿ äîïóñêàåò ðàçëè÷íûå ñæàòèÿ
è ìîæåò ðàçâîðà÷èâàòüñÿ òîëüêî â îïåðàòèâíîé ïàìÿòè íåïîñðåäñòâåííî
ïåðåä ðàñøèôðîâêîé ñæàòîãî òåêñòà. Â ïåðâûå 4 áèòà ïîëîæèì äëèíó
áèòîâîãî ïðåäñòàâëåíèÿ òîãî ñèìâîëà, êîòîðûé â îáùåïðèíÿòîì 8-áèòîâîì
ïðåäñòàâëåíèè èìååò íîìåð 0. Â ñëåäóþùèå 4 áèòà ïîëîæèì äëèíó ñèìâîëà
íîìåð 1 è ò.ä. Òàáëèöà ñîæìåòñÿ äî 128 áàéòîâ.
Íàïîìíèì, ÷òî ìû îãðàíè÷èëèñü òåêñòàìè äî 64 ÊÁ. Òàê ÷òî
÷åòûðåõ áèòîâ âïîëíå äîñòàòî÷íî äëÿ èçîáðàæåíèÿ âñåõ âîçìîæíûõ äëèí.
À áîëüøèíñòâî ðåàëüíûõ ñëó÷àåâ îõâàòûâàåòñÿ äèàïàçîíîì äëèí îò 5 äî
12, ÷òî ïîçâîëÿåò óæàòü òàáëèöó äî 96 áàéòîâ.  ðÿäå ñïåöèôè÷åñêèõ
îáëàñòåé äîñòàòî÷íî åùå âäâîå ìåíüøåãî äèàïàçîíà, ÷òî äîâîäèò
ðåçóëüòàò äî 64 áàéòîâ.
Ïîíÿòíî, ÷òî ðàçâåðòûâàíèå òàáëèöû ïîòðåáóåò äîïîëíèòåëüíîãî
âðåìåíè è óñëîæíåíèÿ äåêîäèðîâùèêà. Íî ðàçâåðòûâàíèå ïðîèçâîäèòñÿ
îäíîêðàòíî è çàíèìàåò íåçíà÷èòåëüíóþ ÷àñòü îáùåãî âðåìåíè ðàñøèôðîâêè.
À êîìàíäû ðàçâåðòûâàíèÿ óìåùàþòñÿ â 0.04 ÊÁ, ÷òî äåëàåò âûãîäíîé òàêóþ
äîáàâêó, äàæå åñëè åå âñòàâëÿòü â ñàìîðàñïàêîâûâàþùèåñÿ ôàéëû.
Òàáëèöà âåñîâ òîæå äîïóñêàåò áîëåå êîìïàêòíûå ôîðìû. Ìîæíî
èñïîëüçîâàòü òîò ôàêò, ÷òî âåñà ìëàäøèõ ðàçðÿäîâ îáû÷íî ãåîìåòðè÷åñêóþ
ïðîãðåññèþ, íàïðèìåð: 1, 2, 4, 8, 6, 2. Òîãäà ïî îñòàâøåéñÿ ÷àñòè
òàáëèöû, íà÷èíàþùåéñÿ ñ ïîñëåäíåãî ÷ëåíà ïðîãðåññèè (â äàííîì ïðèìåðå
ïî çàïèñè 8, 6, 2) ëåãêî âîññòàíîâèòü íåäîñòàþùóþ ÷àñòü òàáëèöû.
Îäíàêî â îòëè÷èå îò òàáëèöû ñîîòâåòñòâèÿ çäåñü äîáàâêà ìàøèííûõ êîäîâ,
êàê ïðàâèëî, ïðåâîñõîäèò âûãîäó îò ñîêðàùåíèÿ òàáëèöû âåñîâ. Ïîýòîìó
äîáàâêà âïîëíå óìåñòíà â äåçàðõèâàòîðå, ÿâëÿþùåìñÿ îòäåëüíîé ïðîãðàììîé,
íî îíà íå ãîäèòñÿ äëÿ ñàìîðàñïàêîâûâàþùèõñÿ ïðîãðàìì (åñëè, ðàçóìååòñÿ,
îíè íå âûçûâàþò ïðîãðàìì äåøèôðîâêè èçâíå).
Îïèñàííûå ñèòóàöèè ïîêàçûâàþò, ÷òî íåðåäêî èìåííî ìèíèìèçàöèÿ
ìàøèííîãî êîäà, ñòðîÿùàÿñÿ íå òîëüêî íà îñíîâå àáñòðàêòíîé ìàòåìàòèêè,
íî è íà îñíîâå îñîáåííîñòåé ÝÂÌ, â êîíå÷íîì ñ÷åòå ðåøàåò âîïðîñ î
ïðèãîäíîñòè òîãî èëè èíîãî àëãîðèòìà.
6. Ïðèìåð ïðîãðàììû â öåëîì
Ïðèëàãàåòñÿ ïðîãðàììà H.COM îáúåìîì ìåíåå 0.5 ÊÁ , ñæèìàþùàÿ
ôàéëû ïî ìåòîäó Õàôôìàíà. Ïðîöåññîð: 386 è âûøå. Îãðàíè÷åíèå íà îáúåì
ôàéëà: 64 ÊÁ. Ïî èñõîäíîìó ôàéëó, íàïðèìåð, ñ èìåíåì NAME, îíà âûäàåò
çàãðóçî÷íûé ìîäóëü NAME.COM, êîòîðûé ïðè çàïóñêå ðàçâîðà÷èâàåò
íàõîäÿùèéñÿ â íåì ñæàòûé òåêñò è òàêèì îáðàçîì ñîçäàåò êîïèþ
èñõîäíîãî ôàéëà. Ïðèìåð çàïóñêà:
H.COM NAME
Ñîçäàñòñÿ NAME.COM . Çàïóñòèòå åãî, óêàçàâ â ïàðàìåòðàõ
èìÿ íîâîãî ôàéëà. Íàïðèìåð:
NAME.COM Z
Òîãäà ôàéëû NAME è Z îêàæóòñÿ òîæäåñòâåííû ïî ñîäåðæèìîìó.
H.COM â óêàçàííîì ïîðÿäêå ðàçìåùàåò â âûõîäíîì ôàéëå:
1) ìàøèííûå êîäû (69 áàéòîâ),
2) ñæàòûé òåêñò,
3) òàáëèöó ñîîòâåòñòâèÿ (íå áîëåå 256 áàéòîâ),
4) òàáëèöó âåñîâ (íå áîëåå 17 áàéòîâ).
Èç ìàøèííûõ êîäîâ 34 áàéòà èäåò ÷èñòî íà äåêîäèðîâùèê,
îñòàëüíîå - íà ôàéëîâûå îïåðàöèè, íà íà÷àëüíûå óñòàíîâêè ïàðàìåòðîâ è
àäðåñîâ äðóãèõ êîìïîíåíòîâ, íà ïðî÷èå òåõíè÷åñêèå äåòàëè.
Åñëè âûõîäíîé ôàéë íå âïèñûâàåòñÿ â ïðåäåëüíûé äëÿ COM-ôàéëîâ
îáúåì, òî ïðîãðàììà âûäàåò ôàéë íóëåâîãî îáúåìà. À åñëè âåëèê èñõîäíûé
ôàéë, òî H.COM áåðåò èç íåãî ïåðâûå 65535 áàéòîâ.
Åñëè ôàéë íå ìîæåò áûòü ñæàò (òàêîâû, íàïðèìåð, ôàéëû, óæå
ñæàòûå íåêîòîðûì àðõèâàòîðîì), òî H.COM âñå ðàâíî àêêóðàòíî äîáàâëÿåò
íåíóæíóþ çäåñü òàáëèöó ñîîòâåòñòâèÿ è ïðî÷åå.  ðåçóëüòàòå ÿêîáû
ñæàòûé ôàéë ïîëó÷àåòñÿ áîëüøå èñõîäíîãî. Ãðàìîòíûå àðõèâàòîðû â òàêîì
ñëó÷àå îáû÷íî ïîìåùàþò â íà÷àëå âûõîäíîãî ôàéëà ïðèçíàê (äîñòàòî÷íî
îäíîãî áèòà), óêàçûâàþùèé, ñæàò ôàéë èëè îñòàâëåí íåèçìåííûì. Çäåñü
ýòî íå äåëàåòñÿ, òàê êàê ñòàâèòñÿ öåëü ïðîäåìîíñòðèðîâàòü ìåòîä
Õàôôìàíà, à íå ñåðâèñ àðõèâàòîðîâ.
Õîòÿ çäåñü áîðüáà øëà â ïåðâóþ î÷åðåäü çà ìèíèìèçàöèþ
ïðîãðàììû, à íå çà áûñòðîäåéñòâèå, íî ñêîðîñòü îòíþäü íå ïîñòðàäàëà.
(Â óùåðá ñêîðîñòè ìîæíî äîáèòüñÿ è ìåíüøåãî îáúåìà, íåæåëè çäåñü
äîñòèãíóò.) Ïî ñðàâíåíèþ ñ ìîùíûìè àðõèâàòîðàìè (õîòÿ ñîïîñòàâëåíèå
íå ñîâñåì êîððåêòíîå, ïîñêîëüêó îíè âîîðóæåíû ìíîãèìè ìåòîäàìè è
äàþò ëó÷øåå ñæàòèå) âðåìÿ ðàáîòû H.COM â 4-6 ðàç ìåíüøå è äëÿ ôàéëîâ
ìàêñèìàëüíîãî îáúåìà íà ñàìûõ ñòàðûõ Pentium ðàâíî 0.06 ñåê. Èç íèõ
2/3 óõîäèò íà ÷òåíèå è çàïèñü ôàéëîâ. È òîëüêî 0.01 ñåê. òðàòèòñÿ
íà îñíîâíîé ðàñ÷åò: âû÷èñëåíèå äëèí ïðåäñòàâëåíèé ñèìâîëîâ.
7. Ëèñòèíãè
Ñëåäóþùèå ôðàãìåíòû íà àññåìáëåðå â îñíîâíîì ñîîòâåòñòâóþò
ìîäóëþ H.COM è íå ñëèøêîì ðàñõîäÿòñÿ ñ îïèñàíèÿìè àëãîðèòìîâ. Äåëî
â òîì, ÷òî ìèíèìàëüíûé îáúåì ÷àñòåé åùå íå ãàðàíòèðóåò ìèíèìóìà
ïðîãðàììû â öåëîì, ïîòîìó ÷òî ÷àñòè åùå íàäî ñîñòûêîâàòü. ×òîáû íå
îçàäà÷èâàòü ÷èòàòåëÿ ïðîáëåìàìè ñòûêîâêè, äàëåå ïðèâîäÿòñÿ, ìîæåò
áûòü, íå ñàìûå êîðîòêèå, íî ñîãëàñîâàííûå âàðèàíòû áëîêîâ.
Êðîìå òîãî, ïàìÿòü çäåñü ðàñõîäóåòñÿ íåñêîëüêî ðàñòî÷èòåëüíåå,
ïîñêîëüêó è òàê èñïîëüçóåòñÿ ëèøü íåçíà÷èòåëüíàÿ ÷àñòü ðåñóðñîâ ÝÂÌ.
Íàïðèìåð, âìåñòî ïîëóêèëîáàéòíîãî ìàññèâà äëÿ êîëè÷åñòâ âõîæäåíèé ñèìâîëîâ
èñïîëüçóåòñÿ êèëîáàéòíûé. Íà êàæäûé èç 256 ñèìâîëîâ îòâîäèòñÿ 4 áàéòà.
Ïåðâûé - íà ñàì ñèìâîë, âòîðîé - ïîä äëèíó ïðåäñòàâëåíèÿ, ïîñëåäíèå
äâà - ïîä êîëè÷åñòâî âõîæäåíèé, à ïîçæå ïîä âû÷èñëåííîå ïðåñòàâëåíèå.
Ðàáî÷èé ìàññèâ òîæå âäâîå áîëüøå, ïîëîâèíà åãî íå èñïîëüçóåòñÿ, íî
ýòî ïîçâîëÿåò íåìíîãî ñîêðàòèòü ìàøèííûå êîäû.
È åùå: îñîáåííîñòè ÝÂÌ âñåãäà îòêðûâàþò ïîëå äëÿ ïðèìåíåíèÿ
âû÷èñëèòåëüíûõ ïðèìåìîâ, îòíþäü íå âûòåêàþùèõ èç àëãîðèòìà.
Ê íà÷àëó ñëåäóþùèõ îïåðàöèé ïðåäïîëàãàþòñÿ, ÷òî â óêàçàííûõ
÷åòâåðêàõ ïåðâûé áàéò ñîäåðæèò îáùåïðèíÿòîå 8-áèòîâîå ïðåäñòàâëåíèå ñèìâîëà,
âòîðîé ðàâåí íóëþ, à äâà ïîñëåäíèõ ñîäåðæàò êîëè÷åñòâî âõîæäåíèé ñèìâîëà
â çàäàííûé òåêñò. Êàêàÿ-ëèáî óïîðÿäî÷åííîñòü ÷åòâåðîê íå íóæíà. (Íî â
H.COM îíà íà ñàìîì äåëå èìååòñÿ, õîòÿ äàëåå íå èñïîëüçóåòñÿ: ïî âîçðàñòàíèþ
íîìåðîâ ñèìâîëîâ, ò.å. ïî çíà÷åíèÿì â ïåðâûõ áàéòàõ ÷åòâåðîê. Òàê óäîáíåå
áûëî ïîäñ÷èòûâàòü êîëè÷åñòâà âõîæäåíèé.)
ÂÛ×ÈÑËÅÍÈÅ ÄËÈÍ ÏÐÅÄÑÒÀÂËÅÍÈÉ
Ýïàï 1 (52 áàéòà):
mov di,1024 ; Àäðåñ ðàáî÷åãî ìàññèâà
C1: mov cx,2 ; Êîëè÷åñòâî ìèíèìèçèðóåìûõ âõîæäåíèé
C2: mov dx,-1 ; Ðàáî÷åå çíà÷åíèå âõîæäåíèé
xor si,si ; Àäðåñ èñõîäíîãî ìàññèâà ñ ñèìâîëàìè è âõîæäåíèÿìè
M3: lodsw ; Óâåëè÷åíèå òåêóùåãî àäðåñà íà 2
lodsw ; ax = êîëè÷åñòâî âõîæäåíèé î÷åðåäíîãî ñèìâîëà
or ax,ax ; Ïðîâåðêà êîëè÷åñòâà âõîæäåíèé íà 0
je M4 ; Ñèìâîë óæå îáñëóæåí, ëèáî åãî íåò â òåêñòå
cmp ax,dx ; Ñðàâíåíèå òåêóùåãî çíà÷åíèÿ ñ ðàáî÷èì
jae M4 ; Òåêóùåå çíà÷åíèå íå ïðåäñòàâëÿåò èíòåðåñà
xchg ax,dx ; Êîððåêòèðîâêà ðàáî÷åãî çíà÷åíèÿ âõîæäåíèé
lea bx,[si-4] ; Çàïîìèíàíèå àäðåñà êàíäèäàòà íà ìèíèìóì
M4: cmp si,1024 ; Ïðîâåðêà íà èñ÷åðïàíèå èñõîäíîãî ìàññèâà
jne M3 ; Íà ïðîäîëæåíèå ïîèñêà ïðè î÷åðåäíîì àäðåñå
and word ptr [bx+2],0 ; Îáíóëåíèå êîë-âà âõîæä.íàéäåííîãî ñèìâîëà
push dx ; Çàïîìèíàíèå ìèí.çíà÷åíèÿ âõîæäåíèé
push bx ; Çàïîìèíàíèå àäðåñà ñèìâîëà
loop C2 ; Êîíåö ïîèñêà äâóõ ñèìâîëîâ ñ ìèí.âõîæäåíèÿìè
pop si ; Èçâëå÷åíèå àäðåñà 2-ãî ñèìâîëà
movsw ; Çàïîëíåíèå 1-ãî ýëåìåíòà ïàðû
pop bx ; Èçâëå÷åíèå êîëè÷åñòâà âõîæäåíèé 2-ãî ñèìâîëà
pop si ; Èçâëå÷åíèå àäðåñà 1-ãî ñèìâîëà
pop ax ; Èçâëå÷åíèå êîëè÷åñòâà âõîæäåíèé 1-ãî ñèìâîëà
add ax,bx ; Ñóììèðîâàíèå íàéäåííûõ ìèíèìàëüíûõ çíà÷åíèé
movsw ; Çàïîëíåíèå 2-ãî ýëåìåíòà ïàðû
mov [si],ax ; Ñóììà âõîæäåíèé ïðèïèñàíà êî 2-ìó ñèìâîëó
inc bx ; Àíàëèç êîëè÷åñòâà âõîæäåíèé 2-ãî ñèìâîëà
jne C1 ; Ñíîâà íà ïîèñê äâóõ ñèìâîëîâ
 îòëè÷èå îò îïèñàíèÿ àëãîðèòìà çäåñü â ðàáî÷èé ìàññèâ çàíîñèòñÿ
åùå îäíà ïàðà, êîòîðàÿ íå îòâå÷àåò íèêàêîìó ñëèÿíèþ è ôîðìèðóåòñÿ óæå
ïîñëå òîãî, êàê óæå â îáùåì èçâåñòíî, ÷òî ñ íåíóëåâîé ÷àñòîòîé îñòàëñÿ
òîëüêî îäèí ñèìâîë. Ýòî ïîçâîëÿåò èçáåæàòü èçëèøíåé ïåðåäà÷è óïðàâëåíèÿ
èç ñåðåäèíû íà âûõîä èç îïèñàííîãî âûøå áëîêà è, êàê ìû óâèäèì, ñîêðàòèòü
ïîñëåäóþùèå îïåðàöèè.
Çà ïîñëåäíèì, íå ïðèâåäøèì ê óñïåõó, ïîèñêîì ìèíèìàëüíîãî
íåíóëåâîãî çíà÷åíèÿ âñå ðàâíî èäåò îáíóëåíèå [bx+2]. Ýòî íå îøèáêà,
òàê êàê â bx íàõîäèòñÿ íå ñëó÷àéíîå ÷èñëî, à àäðåñ, ïî êîòîðîìó ïðîèçîøëî
ïðåäûäóùåå âïîëíå çàêîííîå îáíóëåíèå. Òàêèì îáðàçîì, â êîíöå ðàáî÷åãî
ìàññèâà îêàçûâàåòñÿ äîïîëíèòåëüíàÿ ïàðà, â êîòîðîé îáà ÷ëåíà ñîâïàäàþò
ñ ñèìâîëîì, ïîñëåäíèì ïîäâåðãøèìñÿ îáíóëåíèþ ñâîåãî êîëè÷åñòâà âõîæäåíèé,
ïðè÷åì äâàæäû. Ïðàâäà, òóò æå mov [si],ax âîçâðàùàåò åìó áåññìûñëåííîå
÷èñëî, íàõîäÿùååñÿ â ax, íî äëÿ 2-ãî ýòàïà îíî íå èãðàåò ðîëè.
Îò 1-ãî ýòàïà îñòàþòñÿ èñïîëüçóþùèåñÿ äàëåå çíà÷åíèÿ ðåãèñòðîâ:
cx=0, bx=0.
Ýòàï 2 (33 áàéòà):
mov ch,1 ; cx=256 = êîëè÷åñòâî îáîðîòîâ âíåøíåãî öèêëà
N1: mov bp,[bx] ; bp = ðàáî÷åå çíà÷åíèå = òåêóùèé ñèìâîë
mov dl,-1 ; dl = íà÷àëüíîå çíà÷åíèå ñ÷åò÷èêà
mov si,1024 ; si = íà÷àëî ðàáî÷åãî ìàññèâà
N2: lodsw ; ×òåíèå ïåðâîãî ÷ëåíà ïàðû
cmp ax,bp ; Ñðàâíåíèå ñèìâîëà ñ 1-ì ÷ëåíîì ïàðû
lodsw ; ×òåíèå âòîðîãî ÷ëåíà ïàðû
je N3
cmp ax,bp ; Ñðàâíåíèå ñèìâîëà ñî 2-ì ÷ëåíîì ïàðû
jne N4
N3: inc dx ; Óâåëè÷åíèå ñ÷åò÷èêà
xchg ax,bp ; Çàìåíà ðàá.çíà÷åíèÿ íà 2-é ÷ëåí ïàðû
N4: cmp si,di ; Ïðîâåðêà íà èñ÷åðïàíèå ðàáî÷åãî ìàññèâà
jne N2 ; Âîçâðàò íà íà÷àëî âíóòðåííåãî öèêëà
mov [bx+1],dl ; Çàíåñåíèå ðåçóëüòàòà âî 2-é áàéò ÷åòâåðêè
add bx,4 ; óâåëè÷åíèå òåêóùåãî àäðåñà
loop N1 ; Âîçâðàò íà íà÷àëî âíåøíåãî öèêëà
Ïîñêîëüêó ðàáî÷èé ìàññèâ ó íàñ íà îäíó ïàðó áîëüøå, òî
íà÷àëüíîå çíà÷åíèå ñ÷åò÷èêà âçÿòî íà åäèíèöó ìåíüøå. Ýòî íåáîëüøîå
óñëîæíåíèå ïîçâîëÿåò ïîïóòíî ïðèñâîèòü äëèíó -1 âñåì ñèìâîëàì,
íå ó÷àñòâóþùèì â òåêñòå, è ïî ýòîìó ïðèçíàêó èñêëþ÷èòü èç
ïîñëåäóþùèõ ðàñ÷åòîâ.
Çàòåì H.COM óïîðÿäî÷èâàåò ÷åòâåðêè ïî âîçðàñòàíèþ áåççíàêîâûõ
äâóáàéòîâûõ ÷èñåë èç ïåðâûõ ïîëîâèí ÷åòâåðîê. Äåëàåòñÿ ýòî ïðîñòîé
ïåðåñòàíîâêîé ñîñåäíèõ ÷åòâåðîê (à òî÷íåå, òîëüêî èõ ïåðâûõ ñëîâ, ÷òî
ïîçâîëÿåò çàìåòíî ñîêðàòèòü ìàøèííûå êîäû). Â ðåçóëüòàòå íåèñïîëüçóåìûå
ñèìâîëû (åñëè îíè åñòü) îêàçûâàþòñÿ â êîíöå ìàññèâà. Èìåííî çíà÷åíèÿ -1
äëÿ äëèí íåèñïîëüçóåìûõ ñèìâîëîâ ïîìîãàþò îðãàíèçîâàòü óïîðÿäî÷åíèå
çà 30 áàéòîâ ìàøèííîãî êîäà.
ÂÛ×ÈÑËÅÍÈÅ ÏÐÅÄÑÒÀÂËÅÍÈÉ
Ðåàëèçàöèÿ àëãîðèòìà çàìåòíî îòëè÷àåòñÿ îò åãî îïèñàíèÿ âûøå.
Çäåñü âîîáùå íåò îòäåëüíîãî ïåðâîãî øàãà, íåò íà÷àëüíîãî íàçíà÷åíèÿ
íóëÿ è åäèíèöû ïåðâûì äâóì ñèìâîëàì. Ýòîò øàã ïðîõîäèòñÿ íàðÿäó ñ
îñòàëüíûìè â åäèíîì öèêëå. Îáúÿñíÿòü ýòî â îïèñàíèè àëãîðèòìà
- ñòîëü æå ñîìíèòåëüíî, êàê ðàññêàçûâàòü î ìàòåìàòè÷åñêîé èíäóêöèè
è çàáûòü î åå ïåðâîì øàãå (áàçå èíäóêöèè). Çäåñü èñïîëüçîâàíû ðàçíûå
ïðèåìû ïðè ôîðìèðîâàíèè àäðåñîâ è ïðî÷èå ìàíèïóëÿöèè, êîòîðûìè
ñîâåðøåííî íåîáÿçàòåëüíî çàñîðÿòü ïðèíöèïèàëüíîå îïèñàíèå àëãîðèòìà.
Ê íà÷àëó âû÷èñëåíèÿ âòîðûå ñëîâà óïîìèíàâøèõñÿ âûøå ÷åòâåðîê
(è ñîñòàâëÿþùèõ ìàññèâ â 1 ÊÁ ñ àäðåñà 0), äîëæíû áûòü îáíóëåíû, à
ñàìè ÷åòâåðêè óïîðÿäî÷åíû ïî íåóáûâàíèþ äëèí ïðåäñòàâëåíèé (îá ýòîì
òîæå ãîâîðèëîñü). Ïîñëå 1-ãî ýòàïà âû÷èñëåíèÿ äëèí íóæíûå ñëîâà óæå
áûëè îáíóëåíû, âñå, êðîìå îäíîãî. ×òîáû îáíóëèòü è ïîñëåäíåå,
äîñòàòî÷íî äîáàâèòü ïîñëå ýòàïà 1 äâóáàéòîâóþ êîìàíäó mov [si],bx
Ñëåäóþùèé áëîê (47 áàéòîâ) äîïîëíèòåëüíî ê ïðåäñòàâëåíèÿì
âû÷èñëÿåò è òàáëèöó âåñîâ. Îíà ôîðìèðóåòñÿ ñ àäðåñà -100 (äîñòàòî÷íî
ïðîèçâîëüíîãî).
xor dx,dx ; dx = êîëè÷åñòâî îáñëóæåííûõ ñèìâîëîâ
xor bx,bx ; bx = íîìåð òåêóùåãî ðàçðÿäà
BEGIN: xor cx,cx ; cx = ñ÷åò÷èê ñèìâîëîâ ñ äëèíîé áîëåå bx
xor si,si ; si = àäðåñ èñòî÷íèêà äëÿ ïåðåíîñà
xor di,di ; di = àäðåñ ïðèåìíèêà
mov bp,dx ; bp = êîëè÷åñòâî îáîðîòîâ öèêëà
CALC: cmp bl,[di+1] ; Ñðàâíåíèå íîìåðà ðàçðÿäà ñ äëèíîé ñèìâîëà
jae M1
inc cx ; Óâåëè÷åíèå ñ÷åò÷èêà cx
inc dx ; Êîððåêòèðîâêà dx íà áóäóùåå
jmp M2
M1: lodsw ; Ôîðìèðîâàíèå àäðåñà èñòî÷íèêà
lodsw
M2: add di,4 ; Ôîðìèðîâàíèå àäðåñà ïðèåìíèêà
dec bp ; Ïðîâåðêà íà êîíåö öèêëà
jge CALC
mov [bx-100],cl ; Çàïîëíåíèå ìàññèâà âåñîâ
jcxz FIN ; Åñëè ñ÷åò÷èê = 0, òî êîíåö
BIT1: lodsw ; Íà÷àëî ïåðåìåùåíèé
lodsw ; ×òåíèå ïðåäñòàâëåíèÿ îáñëóæåííîãî ñèìâîëà
bts ax,bx ; Íàçíà÷åíèå 1 â ðàçðÿä bx
inc di ; Êîððåêòèðîâêà àäðåñà ïðèåìíèêà
inc di
stosw ; Ðàçìåùåíèå íîâîãî ïðåäñòàâëåíèÿ
loop BIT1 ; Êîíåö öèêëà ïåðåìåùåíèé
inc bx ; Î÷åðåäíîé ðàçðÿä
jmp BEGIN
FIN:
Èç íåâîøåäøèõ â ëèñòèíãè áëîêîâ óïîìÿíåì åùå îäèí ðàñ÷åò â H.COM,
íå îáÿçàòåëüíûé ïî ñóòè è äàæå óäëèííÿþùèé ïðîãðàììó, íî óñêîðÿþùèé
â äàëüíåéøåì êîäèðîâêó èñõîäíîãî òåêñòà. Îí ôîðìèðóåò ìàññèâ èç 512
áàéòîâ, â êîòîðîì ïîçèöèÿ êàæäîãî äâóáàéòîãî ñëîâà îòâå÷àåò èñõîäíîìó
îáùåóïîòðåáèòåëüíîìó íîìåðó ñèìâîëà, à íà ýòîé ïîçèöèè ëåæèò àäðåñ
ñîîòâåòñòâóþùåé ÷åòâåðêè â îñíîâíîì ìàññèâå.  òàêîì ñëó÷àå ïîñëå ÷òåíèÿ
î÷åðåäíîãî ñèìâîëà èç èñõîäíîãî òåêñòà íå íàäî ëàçèòü ïî âñåì ÷åòâåðêàì,
ïðîâåðÿÿ â êàêîé èç íèõ â ïåðâîì áàéòå ëåæèò èñêîìûé ñèìâîë. À ñðàçó
èçâëåêàåòñÿ íóæíûé àäðåñ íîâîãî áèòîâîãî ïðåäñòàâëåíèÿ ñèìâîëà.
Çàìàí÷èâî áûëî áû îïåðàöèåé ñäâèãà ïî áèòàì ÷åðåç ôëàã ïåðåíîñà
CF ïåðåêèäûâàòü ïðåäñòàâëåíèÿ ñèìâîëîâ â âûõîäíîé ìàññèâ. Íà ýòî èäåò
áîëåå êîðîòêèé ìàøèííûé êîä, íî ðàáîòàåò îí çàìåòíî äîëüøå. Â H.COM
ïðåäñòàâëåíèå î÷åðåäíîãî ñèìâîëà (òî÷íåå, 2 áàéòà èç ñîîòâåòñòâóþùåé
÷åòâåðêè) ïîìåùàåòñÿ â ax, ñòàðøåå ñëîâî â eax îáíóëÿåòñÿ. Çàòåì eax
ñäâèãàåòñÿ ñîîòâåòñòâåííî çàïîëíåíèþ ïîñëåäíåãî áàéòà â âûõîäíîì ìàññèâå
è îïåðàöèåé or âïèñûâàåòñÿ â ìàññèâ.
ÄÅÊÎÄÈÐÎÂÙÈÊ
Ñòðîãî ãîâîðÿ, â çàâèñèìîñòè îò èñõîäíîãî òåêñòà âñÿêèé ðàç
ñîçäàþòñÿ ðàçíûå äåêîäèðîâùèêè, òàê êàê â íèõ çàëîæåíû ðàçíûå çíà÷åíèÿ
ïàðàìåòðîâ. Íåèçìåííîé, çà èñêëþ÷åíèåì îäíîãî àäðåñà, ÿâëÿåòñÿ òîëüêî
îïèñàííàÿ íèæå öåíòðàëüíàÿ ÷àñòü (34 áàéòà). Ìû íå ïðèâîäèì îñòàëüíîå
îáðàìëåíèå, â ÷àñòíîñòè, ôàéëîâûå îïåðàöèè, ïîñêîëüêó âñå ýòî ìîæåò áûòü
ëèáî ÷óòü áîëüøå, ëèáî ÷óòü ìåíüøå â çàâèñèìîñòè îò âàæíîñòè ñèòóàöèè è
íåîáõîäèìîñòè äîïîëíèòåëüíûõ ïðîâåðîê, à ãëàâíîå, íå èìååò ïðÿìîãî
îòíîøåíèÿ ê àðõèâàöèè.
Öåíòðàëüíàÿ ÷àñòü ïðåäïîëàãàåò çàïîëíåííûìè ñëåäóþùèå ðåãèñòðû.
cl = 1.
bx = àäðåñ òàáëèöû ñîîòâåòñòâèÿ, íàõîäÿùåéñÿ íåïîñðåäñòâåííî
çà ñæàòûì òåêñòîì.
bp = àäðåñ ñæàòîãî òåêñòà.
di = 0 - ýòî íà÷àëüíûé àäðåñ âûõîäíîãî ìàññèâà îòíîñèòåëüíî
ñåãìåíòà ES.
CS=DS=SS - ýòî ïîëó÷àåòñÿ àâòîìàòè÷åñêè ïðè çàïóñêå COM-ôàéëà.
ES = àäðåñ ñâîáîäíîãî ñåãìåíòà.
C1: mov si, ... ; Ðàáî÷èé àäðåñ = âïàÿííûé àäðåñ òàáëèöû âåñîâ
xor dx,dx ; Îáíóëåíèå ñ÷åò÷èêîâ P=dl è R=dh
C2: lodsw ; ×òåíèå âåñîâ V=al è W=ah
dec si ; Êîððåêòèðîâêà àäðåñà ÷òåíèÿ âåñîâ
test [bp],cl ; Ïðîâåðêà î÷åðåäíîãî áèò ñæàòîãî òåêñòà
je M
add dl,al ; Äîáàâëåíèå âåñà V ê ñ÷åò÷èêó P
M: add dh,al ; Äîáàâëåíèå âåñà V ê ñ÷åò÷èêó R
rol cl,1 ; Êîððåêòèðîâêà ïîçèöèè ÷èòàåìîãî áèòà
adc bp,0 ; Êîððåêòèðîâêà àäðåñà ÷òåíèÿ ñæàòîãî òåêñòà
add ah,dl ; Äîáàâëåíèå P ê W
cmp ah,dh ; Ñðàâíåíèå W è R
ja C2 ; Íîìåð ñèìâîëà íå ñîáðàí
xchg ax,dx ; Íîìåð ñèìâîëà ñîáðàí è ïèøåòñÿ â al
xlat ; Çàìåíà ñîãëàñíî òàáëèöå ñîîòâåòñòâèÿ
stosb ; Çàïèñü ñèìâîëà â âûõîäíîé ìàññèâ
cmp bp,bx ; Ïðîâåðêà íà êîíåö ñæàòîãî òåêñòà
jb C1 ; Âîçâðàò íà ðàñøèôðîâêó î÷åðåäíîãî ñèìâîëà
Ïîñëåäíèé áàéò ñæàòîãî òåêñòà ìîæåò îêàçàòüñÿ íåïîëíûì, è
ñëó÷àéíîå ñîäåðæèìîå äîâåñêà ìîæåò ÷óòü óâåëè÷èòü çíà÷åíèå ðåãèñòðà di.
Ïîýòîìó ýòî ÷èñëî íå ãîäèòñÿ â êà÷åñòâå îáúåìà ñîçäàâàåìîãî ôàéëà.
Èñòèííîå çíà÷åíèå îáúåìà ìîæíî âïàÿòü â äåêîäèðîâùèê ïðè ôîðìèðîâàíèè
ñæàòîãî òåêñòà.
8. Çàêëþ÷åíèå
Íà ýòîì ìåñòå äîëæåí áûë áû ñòîÿòü ñïèñîê ëèòåðàòóðû. Îäíàêî,
åñëè íå ñ÷èòàòü îñíîâîïîëàãàþùåé èäåè Õàôôìàíà, òî íå óäàëîñü íàéòè
íè÷åãî, ÷òî õîòÿ áû îòäàëåííî íàïîìèíàëî èçëîæåííûå çäåñü ñîîáðàæåíèÿ
è ìîãëî áû áûòü ðåêîìåíäîâàíî â ïëàíå èõ ðàçâèòèÿ. Çàòî óäàëîñü íàéòè
ó÷åíûõ ìóæåé, íåñïåøíî ïîëçàþùèõ ïî ðàñêèäèñòîìó äåðåâó â ïîèñêàõ
íóæíîãî ëèñòî÷êà (òî áèøü ñèìâîëà) ïðè ðàñøèôðîâêå ñæàòîãî òåêñòà.
Óäàëîñü íàéòè ìàññó ÿâíî èçáûòî÷íûõ ðàñ÷åòîâ, çàòåì - ïîòîê
èññëåäîâàíèé ýòèõ ðàñ÷åòîâ è ò.ä.
Êîíå÷íî, áûëî áû ãëóïî èçîáðåòàòü âåëîñèïåä â ñòîëü äàâíåé è
áîðîäàòîé òåìàòèêå. Âî âñÿêîì ñëó÷àå êîïàíèå â ëèòåðàòóðå óòåøèëî àâòîðà
òåì, ÷òî îí äàëåêî íå îäèíîê â ñâîåì äèëåòàíòèçìå. Åñëè ýðóäèòû ñîîáùàò
èìåíà ïîäëèííûõ ïåðâîïðîõîäöåâ, òî â ïîñëåäóþùèõ âåðñèÿõ äàííîãî
ñî÷èíåíèÿ áóäóò íàçâàíû ýòè ñëàâíûå èìåíà âìåñòå ñ èìåíàìè ýðóäèòîâ.
Åñëè ñî÷èíåíèå äàæå íå áëåùåò íîâèçíîé, òî åãî çíà÷åíèå ïðåæäå
âñåãî â òîì, ÷òî ñäåëàíà ïîïûòêà âûäåëèòü íåïðåõîäÿùèå îñíîâû, âîêðóã
êîòîðûõ ìîãóò è äîëæíû ñòðîèòüñÿ áåñêîíå÷íûå îáîáùåíèÿ ìåòîäà Õàôôìàíà.
Äîïóñêàÿ âñåâîçìîæíûå íàäñòðîéêè, ïðåäëîæåííûå àëãîðèòìû
ïðåòåíäóþò íà íåâîçìîæíîñòü äâèæåíèÿ â îáðàòíóþ ñòîðîíó, ò.å. ÷òî
èç íèõ íåëüçÿ íè÷åãî âûêèíóòü è ÷òî íåëüçÿ ïðèäóìàòü áîëåå êîìïàêòíûå
ïðåîáðàçîâàíèÿ (ðàçóìååòñÿ, áåç ñóùåñòâåííîãî óùåðáà äëÿ ðåçóëüòàòîâ
è ñêîðîñòè êîäèðîâàíèÿ).
Òàê ëè ýòî íà ñàìîì äåëå? - ýòî âîïðîñ ê ÷èòàòåëÿì. Àâòîð
(è, âîçìîæíî, íàóêà) áóäåò áëàãîäàðåí äàæå çà âñÿêîå óëó÷øåíèå íà 1
áàéò ìàøèííûõ êîäîâ (îñîáåííî ïî ÷àñòè äåêîäèðîâùèêà), à óæ òåì
áîëåå çà íîâûå, áîëåå êîðîòêèå ïóòè, âåäóùèå ê ñæàòîìó òåêñòó ïîä
ôëàãîì Õàôôìàíà.
Íåâåñåíêî Í.Â.
22 îêòÿáðÿ 2002 ã.
© 2002 Suncloud.Ru
íàâåðõ