Ñàéò î ñæàòèè >> ARCTEST
Ñðàâíèòåëüíûå òåñòû Àëüòåðíàòèâíûå òåñòû
Ðóññêèé òåêñò
Àíãëèéñêèé òåêñò
Èñõîäíèêè
WinWord-ôàéë
Excel-ôàéë
EXE-ôàéë
Íîâûå òåñòû
|
|
Ñæàòèå èçîáðàæåíèé áåç ïîòåðü
|
|
Àðõèâ íîâîñòåé
|
|
Àðõèâ ðàññûëêè
|
|
Ôàéë-ìåíåäæåðû
Àðõ.-ìîäóëè äëÿ FAR
Àðõ.-ìîäóëè äëÿ Win. Commander
|
|
Ñòàòüè, èíòåðâüþ
Òåîðèÿ, àëãîðèòìû
Self-îïèñàíèÿ àðõèâàòîðîâ
FAQ
Ðàçíîå
|
|
Àðõèâàòîðíûå
COM/EXE/DLL-ïàêåðîâ
|
|
Î ïðîãðàììå
Íîâîñòè ñâåæèõ âåðñèé
Àðõèâ íîâîñòåé
|
Ïîäïèñêà íà ðàññûëêó íîâîñòåé
Àðõèâàòîðíûå îïðîñû
Îá àâòîðå
|
 |
 |
 |
|
Ñàéò î ñæàòèè >>
Íîâèíêè |
Î ñåðâåðå
(Compression Catalog! |
ENGLISH)
Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ" >> Áåç ïîòåðü | Èçîáðàæåíèé | Âèäåî Ðàçäåëû >> Còàòüè | Âèäåî | Arctest | Ññûëêè | Ru.compress | Ôîðóì Ïðîåêòû >> Ä.Âàòîëèíà | À.Ðàòóøíÿêà | Ì.Ñìèðíîâà | Â.Þêèíà | Å.Øåëâèíà | Ä.Øêàðèíà |
||
 |
||
Èäåÿ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ
Ïðè àðèôìåòè÷åñêîì êîäèðîâàíèè òåêñò ïðåäñòàâëÿåòñÿ âåùåñòâåííûìè ÷èñëàìè â èíòåðâàëå îò 0 äî 1. Ïî ìåðå êîäèðîâàíèÿ òåêñòà, îòîáðàæàþùèé åãî èíòåðâàë óìåíüøàåòñÿ, à êîëè÷åñòâî áèòîâ äëÿ åãî ïðåäñòàâëåíèÿ âîçðàñòàåò. Î÷åðåäíûå ñèìâîëû òåêñòà ñîêðàùàþò âåëè÷èíó èíòåðâàëà èñõîäÿ èç çíà÷åíèé èõ âåðîÿòíîñòåé, îïðåäåëÿåìûõ ìîäåëüþ. Áîëåå âåðîÿòíûå ñèìâîëû äåëàþò ýòî â ìåíüøåé ñòåïåíè, ÷åì ìåíåå âåðîÿòíûå, è, ñëåäîâàòåëüíî, äîáàâëÿþò ìåíüøå áèòîâ ê ðåçóëüòàòó.
Ïåðåä íà÷àëîì ðàáîòû ñîîòâåòñòâóþùèé òåêñòó èíòåðâàë åñòü [0; 1). Ïðè îáðàáîòêå î÷åðåäíîãî ñèìâîëà åãî øèðèíà ñóæàåòñÿ çà ñ÷åò âûäåëåíèÿ ýòîìó ñèìâîëó ÷àñòè èíòåðâàëà. Íàïðèìåð, ïðèìåíèì ê òåêñòó "eaii!" àëôàâèòà { a,e,i,o,u,! } ìîäåëü ñ ïîñòîÿííûìè âåðîÿòíîñòÿìè, çàäàííûìè â Òàáëèöå I.
Òàáëèöà I. Ïðèìåð ïîñòîÿííîé ìîäåëè äëÿ àëôàâèòà { a,e,i,o,u,! }
| Ñèìâîë | Âåðîÿòíîñòü | Èíòåðâàë |
|---|---|---|
| a | .2 | [0.0; 0.2) |
| e | .3 | [0.2; 0.5) |
| i | .1 | [0.5; 0.6) |
| o | .2 | [0.6; 0.8) |
| u | .1 | [0.8; 0.9) |
| ! | .1 | [0.9; 1.0) |
È êîäèðîâùèêó, è äåêîäèðîâùèêó èçâåñòíî, ÷òî â ñàìîì íà÷àëå èíòåðâàë åñòü [0; 1). Ïîñëå ïðîñìîòðà ïåðâîãî ñèìâîëà "e", êîäèðîâùèê ñóæàåò èíòåðâàë äî [0.2; 0.5), êîòîðûé ìîäåëü âûäåëÿåò ýòîìó ñèìâîëó. Âòîðîé ñèìâîë "a" ñóçèò ýòîò íîâûé èíòåðâàë äî ïåðâîé åãî ïÿòîé ÷àñòè, ïîñêîëüêó äëÿ "a" âûäåëåí ôèêñèðîâàííûé èíòåðâàë [0.0; 0.2).  ðåçóëüòàòå ïîëó÷èì ðàáî÷èé èíòåðâàë [0.2; 0.26), ò.ê. ïðåäûäóùèé èíòåðâàë èìåë øèðèíó â 0.3 åäèíèöû è îäíà ïÿòàÿ îò íåãî åñòü 0.06. Ñëåäóþùåìó ñèìâîëó "i" ñîîòâåòñòâóåò ôèêñèðîâàííûé èíòåðâàë [0.5; 0.6), ÷òî ïðèìåíèòåëüíî ê ðàáî÷åìó èíòåðâàëó [0.2; 0.26) ñóæèâàåò åãî äî èíòåðâàëà [0.23, 0.236).
Ïðîäîëæàÿ â òîì æå äóõå, èìååì:
|  íà÷àëå | [0.0; 1.0 ) | |
| Ïîñëå ïðîñìîòðà | "e"; | [0.2; 0.5 ) |
| Ïîñëå ïðîñìîòðà | "a" | [0.2; 0.26 ) |
| Ïîñëå ïðîñìîòðà | "i" | [0.23; 0.236 ) |
| Ïîñëå ïðîñìîòðà | "i" | [0.233; 0.2336) |
| Ïîñëå ïðîñìîòðà | "!" | [0.23354; 0.2336) |
Ïðåäïîëîæèì, ÷òî âñå ÷òî äåêîäèðîâùèê çíàåò î òåêñòå, ýòî êîíå÷íûé èíòåðâàë [0.23354; 0.2336). Îí ñðàçó æå ïîíèìàåò, ÷òî ïåðâûé çàêîäèðîâàííûé ñèìâîë åñòü "e", ò.ê. èòîãîâûé èíòåðâàë öåëèêîì ëåæèò â èíòåðâàëå, âûäåëåííîì ìîäåëüþ ýòîìó ñèìâîëó ñîãëàñíî Òàáëèöå I. Òåïåðü ïîâòîðèì äåéñòâèÿ êîäèðîâùèêà:
Ñíà÷àëà
[0.0; 1.0)
Ïîñëå ïðîñìîòðà "e" [0.2; 0.5)
Îòñþäà ÿñíî, ÷òî âòîðîé ñèìâîë - ýòî "a", ïîñêîëüêó ýòî ïðèâåäåò ê èíòåðâàëó [0.2; 0.26), êîòîðûé ïîëíîñòüþ âìåùàåò èòîãîâûé èíòåðâàë [0.23354; 0.2336). Ïðîäîëæàÿ ðàáîòàòü òàêèì æå îáðàçîì, äåêîäèðîâùèê èçâëå÷åò âåñü òåêñò.
Äåêîäèðîâùèêó íåò íåîáõîäèìîñòè çíàòü çíà÷åíèÿ îáåèõ ãðàíèö èòîãîâîãî èíòåðâàëà, ïîëó÷åííîãî îò êîäèðîâùèêà. Äàæå åäèíñòâåííîãî çíà÷åíèÿ, ëåæàùåãî âíóòðè íåãî, íàïðèìåð 0.23355, óæå äîñòàòî÷íî. (Äðóãèå ÷èñëà - 0.23354,0.23357 èëè äàæå 0.23354321 - âïîëíå ãîäÿòñÿ). Îäíàêî, ÷òîáû çàâåðøèòü ïðîöåññ, äåêîäèðîâùèêó íóæíî âîâðåìÿ ðàñïîçíàòü êîíåö òåêñòà. Êðîìå òîãî, îäíî è òî æå ÷èñëî 0.0 ìîæíî ïðåäñòàâèòü è êàê "a", è êàê "aa", "aaa" è ò.ä. Äëÿ óñòðàíåíèÿ íåÿñíîñòè ìû äîëæíû îáîçíà÷èòü çàâåðøåíèå êàæäîãî òåêñòà ñïåöèàëüíûì ñèìâîëîì EOF, èçâåñòíûì è êîäèðîâùèêó, è äåêîäèðîâùèêó. Äëÿ àëôàâèòà èç Òàáëèöû I äëÿ ýòîé öåëè, è òîëüêî äëÿ íåå, áóäåò èñïîëüçîâàòüñÿ ñèìâîë "!". Êîãäà äåêîäèðîâùèê âñòðå÷àåò ýòîò ñèìâîë, îí ïðåêðàùàåò ñâîé ïðîöåññ.
Äëÿ ôèêñèðîâàííîé ìîäåëè, çàäàâàåìîé ìîäåëüþ Òàáëèöû I, ýíòðîïèÿ 5-ñèìâîëüíîãî òåêñòà "eaii!" áóäåò:
- log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = - log 0.00006 ~ 4.22.
(Çäåñü ïðèìåíÿåì ëîãàðèôì ïî îñíîâàíèþ 10, ò.ê. âûøåðàññìîòðåííîå êîäèðîâàíèå âûïîëíÿëîñü äëÿ äåñÿòè÷íûõ ÷èñåë). Ýòî îáúÿñíÿåò, ïî÷åìó òðåáóåòñÿ 5 äåñÿòè÷íûõ öèôð äëÿ êîäèðîâàíèÿ ýòîãî òåêñòà. Ïî ñóòè, øèðèíà èòîãîâîãî èíòåðâàëà åñòü 0.2336 - 0.23354 = 0.00006, à ýíòðîïèÿ îòðèöàòåëüíûé äåñÿòè÷íûé ëîãàðèôì ýòîãî ÷èñëà. Êîíå÷íî, îáû÷íî ìû ðàáîòàåì ñ äâîè÷íîé àðèôìåòèêîé, ïåðåäàåì äâîè÷íûå ÷èñëà è èçìåðÿåì ýíòðîïèþ â áèòàõ.
Ïÿòè äåñÿòè÷íûõ öèôð êàæåòñÿ ñëèøêîì ìíîãî äëÿ êîäèðîâàíèÿ òåêñòà èç 4-õ ãëàñíûõ! Ìîæåò áûòü íå ñîâñåì óäà÷íî áûëî çàêàí÷èâàòü ïðèìåð ðàçâåðòûâàíèåì, à íå ñæàòèåì. Îäíàêî, ÿñíî, ÷òî ðàçíûå ìîäåëè äàþò ðàçíóþ ýíòðîïèþ. Ëó÷øàÿ ìîäåëü, ïîñòðîåííàÿ íà àíàëèçå îòäåëüíûõ ñèìâîëîâ òåêñòà "eaii!", åñòü ñëåäóþùåå ìíîæåñòâî ÷àñòîò ñèìâîëîâ:
{ "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }.
Îíà äàåò ýíòðîïèþ, ðàâíóþ 2.89 â äåñÿòè÷íîé ñèñòåìå ñ÷èñëåíèÿ, ò.å. êîäèðóåò èñõîäíûé òåêñò ÷èñëîì èç 3-õ öèôð. Îäíàêî, áîëåå ñëîæíûå ìîäåëè, êàê îòìå÷àëîñü ðàíåå, äàþò â îáùåì ñëó÷àå ãîðàçäî ëó÷øèé ðåçóëüòàò.
Ïðîãðàììà äëÿ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ
Íà Ðèñóíêå 1 ïîêàçàí ôðàãìåíò ïñåâäîêîäà, îáúåäèíÿþùåãî ïðîöåäóðû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ, èçëàãàåìûå â ïðåäûäóùåì ðàçäåëå. Ñèìâîëû â íåì íóìåðóþòñÿ êàê 1,2,3... ×àñòîòíûé èíòåðâàë äëÿ i-ãî ñèìâîëà çàäàåòñÿ îò cum_freq[i] äî cum_freq[i-1]. Ïðè óáûâàíèè i cum_freq[i] âîçðàñòàåò òàê, ÷òî cum_freq[0] = 1. (Ïðè÷èíà òàêîãî "îáðàòíîãî" ñîãëàøåíèÿ ñîñòîèò â òîì, ÷òî cum_freq[0] áóäåò ïîòîì ñîäåðæàòü íîðìàëèçóþùèé ìíîæèòåëü, êîòîðûé óäîáíî õðàíèòü â íà÷àëå ìàññèâà). Òåêóùèé ðàáî÷èé èíòåðâàë çàäàåòñÿ â [low; High] è áóäåò â ñàìîì íà÷àëå ðàâåí [0; 1) è äëÿ êîäèðîâùèêà, è äëÿ ðàñêîäèðîâùèêà.
Ê ñîæàëåíèþ ýòîò ïñåâäîêîä î÷åíü óïðîùåí, êîãäà êàê íà ïðàêòèêå ñóùåñòâóåò íåñêîëüêî ôàêòîðîâ, îñëîæíÿþùèõ è êîäèðîâàíèå, è äåêîäèðîâàíèå.
/* ÀËÃÎÐÈÒÌ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ ÊÎÄÈÐÎÂÀHÈß */
/* Ñ êàæäûì ñèìâîëîì òåêñòà îápàùàòüñÿ ê ïpîöåäópå encode_symbol() */
/* Ïpîâåpèòü, ÷òî "çàâåpøàþùèé" ñèìâîë çàêîäèpîâàí ïîñëåäíèì */
/* Âûâåñòè ïîëó÷åííîå çíà÷åíèå èíòåpâàëà [low; high) */
encode_symbol(symbol,cum_freq)
range = high - low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
/* ÀËÃÎÐÈÒÌ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ ÄÅÊÎÄÈÐÎÂÀHÈß */
/* Value - ýòî ïîñòóïèâøåå íà âõîä ÷èñëî */
/* Îápàùåíèå ê ïpîöåäópå decode_symbol() ïîêà îíà íå âîçâpàòèò */
/* "çàâåpøàþùèé" ñèìâîë */
decode_symbol(cum_freq)
ïîèñê òàêîãî ñèìâîëà, ÷òî
cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1]
/* Ýòî îáåñïå÷èâàåò pàçìåùåíèå value âíóòpè íîâîãî èíòåpâàëà */
/* [low; high), ÷òî îòpàæåíî â îñòàâøåéñÿ ÷àñòè ïpîãpàììû */
range = high - low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
return symbol
Ðèñóíîê 1. Ïñåâäîêîä àðèôìåòè÷åñêîãî êîäèðîâàíèÿ è äåêîäèðîâàíèÿ.
Ïðèðàùàåìûå ïåðåäà÷à è ïîëó÷åíèå èíôîðìàöèè.
Îïèñàííûé àëãîðèòì êîäèðîâàíèÿ íè÷åãî íå ïåðåäàåò äî ïîëíîãî çàâåðøåíèÿ êîäèðîâàíèÿ âñåãî òåêñòà, òàêæå è äåêîäèðîâùèê íå íà÷èíàåò ïðîöåññ, ïîêà íå ïîëó÷èò ñæàòûé òåêñò ïîëíîñòüþ. Äëÿ áîëüøèíñòâà ñëó÷àåâ íåîáõîäèì ïîñòåïåííûé ðåæèì âûïîëíåíèÿ.
Æåëàòåëüíîå èñïîëüçîâàíèå öåëî÷èñëåííîé àðèôìåòèêè.
Òðåáóåìàÿ äëÿ ïðåäñòàâëåíèÿ èíòåðâàëà [low; Íigh ) òî÷íîñòü âîçðàñòàåò âìåñòå ñ äëèíîé òåêñòà. Ïîñòåïåííîå âûïîëíåíèå ïîìîãàåò ïðåîäîëåòü ýòó ïðîáëåìó, òðåáóÿ ïðè ýòîì âíèìàòåëüíîãî ó÷åòà âîçìîæíîñòåé ïåðåïîëíåíèÿ è îòðèöàòåëüíîãî ïåðåïîëíåíèÿ.
Ýôôåêòèâíàÿ ðåàëèçàöèÿ ìîäåëè.
Ðåàëèçàöèÿ ìîäåëè äîëæíà ìèíèìèçèðîâàòü âðåìÿ îïðåäåëåíèÿ ñëåäóþùåãî ñèìâîëà àëãîðèòìîì äåêîäèðîâàíèÿ. Êðîìå òîãî, àäàïòèâíûå ìîäåëè äîëæíû òàêæå ìèíèìèçèðîâàòü âðåìÿ, òðåáóåìîå äëÿ ïîääåðæàíèÿ íàêàïëèâàåìûõ ÷àñòîò.
Ïðîãðàììà 1 ñîäåðæèò ðàáî÷èé êîä ïðîöåäóð àðèôìåòè÷åñêîãî êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. Îí çíà÷èòåëüíî áîëåå äåòàëüíûé ÷åì ïñåâäîêîä íà Ðèñóíêå 1. Ðåàëèçàöèÿ äâóõ ðàçëè÷íûõ ìîäåëåé äàíà â Ïðîãðàììå 2, ïðè ýòîì Ïðîãðàììà 1 ìîæåò èñïîëüçîâàòü ëþáóþ èç íèõ.
 îñòàâøåéñÿ ÷àñòè ðàçäåëà áîëåå ïîäðîáíî ðàññìàòðèâàåòñÿ Ïðîãðàììà 1 è ïðèâîäèòñÿ äîêàçàòåëüñòâî ïðàâèëüíîñòè ðàñêîäèðîâàíèÿ â öåëî÷èñëåííîì èñïîëíåíèè, à òàêæå äåëàåòñÿ îáçîð îãðàíè÷åíèé íà äëèíó ñëîâ â ïðîãðàììå.
arithmetic_coding.h
----------------------------------------------------------------------
1 /* ÎÁÚßÂËÅHÈß, HÅÎÁÕÎÄÈÌÛÅ ÄËß ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ */
2 /* ÊÎÄÈÐÎÂÀHÈß È ÄÅÊÎÄÈÐÎÂÀHÈß */
3
4 /* ÈHÒÅÐÂÀË ÇHÀ×ÅHÈÉ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ ÊÎÄÀ */
5
6 #define Code_value_bits 16 /* Êîëè÷åñòâî áèòîâ äëÿ êîäà */
7 typedef long code_value; /* Òèï àpèôìåòè÷åñêîãî êîäà */
8
9 #define Top_value (((long) 1 << Code_value_bits) - 1)
10 /* Ìàêñèìàëüíîå çíà÷åíèå êîäà */
11
12 /* ÓÊÀÇÀÒÅËÈ HÀ ÑÅÐÅÄÈHÓ È ×ÅÒÂÅÐÒÈ ÈHÒÅÐÂÀËÀ ÇHÀ×ÅHÈÉ ÊÎÄÀ */
13
14 #define First_qtr (Top_value/4+1) /* Êîíåö ïåpâîé ÷åpâåpòè */
15 #define Half (2*First_qtr) /* Êîíåö ïåpâîé ïîëîâèíû */
16 #define Third_qtr (3*First_qtr) /* Êîíåö òpåòüåé ÷åòâåpòè */
model.h
----------------------------------------------------------------------
17 /* ÈHÒÅÐÔÅÉÑ Ñ ÌÎÄÅËÜÞ */
18
19
20 /* ÌHÎÆÅÑÒÂÎ ÊÎÄÈÐÓÅÌÛÕ ÑÈÌÂÎËÎÂ */
21
22 #define No_of_chars 256 /* Êîëè÷åñòâî èñõîäíûõ ñèìâîëîâ */
23 #define EOF_symbol (No_of_chars+1) /* Èíäåêñ êîíöà ôàéëà */
24
25 #define No_of_symbols (No_of_chars+1) /* Âñåãî ñèìâîëîâ */
26
27
28 /* Òàáëèöû ïåpåêîäèpîâêè èñõîäíûõ è pàáî÷èõ ñèìâîëîâ */
29
30 int char_to_index[No_of_chars]; /* Èç èñõîäíîãî â pàáî÷èé */
31 unsigned char index_to_char[No_of_symbols+1]; /* Hàîáîpîò */
32
33
34 /* ÒÀÁËÈÖÀ HÀÊÎÏËÅHHÛÕ ×ÀÑÒÎÒ */
35
36 #define Max_frequency 16383 /* Ìàêñèìàëüíîå çíà÷åíèå */
37 /* ÷àñòîòû = 2^14 - 1 */
38 int cum_freq[No_of_symbols+1]; /* Ìàññèâ íàêîïëåííûõ ÷àñòîò */
encode.c
----------------------------------------------------------------------
39 /* ÃÎËÎÂHÀß ÏÐÎÖÅÄÓÐÀ ÊÎÄÈÐÎÂÀHÈß */
40
41 #include <stdio.h>
42 #include "model.h"
43
44 main()
45 { start_model();
46 start_outputing_bits();
47 start_encoding();
48 for (;;) { /* Öèêë îápàáîòêè ñèìâîëîâ */
49 int ch; int symbol;
50 ch = getc(stdin); /* ×òåíèå èñõîäíîãî ñèìâîëà */
51 if (ch==EOF) break; /* Âûõîä ïî êîíöó ôàéëà */
52 symbol = char_to_index[ch]; /* Hàéòè pàáî÷èé ñèìâîë */
53 encode_symbol(symbol,cum_freq); /* Çàêîäèpîâàòü åãî */
54 update_model(symbol); /* Îáíîâèòü ìîäåëü */
55 }
56 encode_symbol(EOF_symbol,cum_freq); /* Êîäèpîâàíèå EOF */
57 done_encoding(); /* Äîáàâëåíèå åùå íåñêîëüêèõ áèò */
58 done_outputing_bits();
59 exit(0);
60 }
arithmetic_encode.c
----------------------------------------------------------------------
61 /* ÀËÃÎÐÈÒÌ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ ÊÎÄÈÐÎÂÀHÈß */
62
63 #include "arithmetic_coding.h"
64
65 static void bit_plus_follow();
66
67
68 /* ÒÅÊÓÙÅÅ ÑÎÑÒÎßHÈÅ ÊÎÄÈÐÎÂÀHÈß */
69
70 static code_value low, high; /* Êpàÿ òåêóùåé îáëàñòè êîäîâ */
71 static long bits_to_follow; /* Êîëè÷åñòâî áèòîâ, âûâîäè- */
72 /* ìûõ ïîñëå ñëåäóþùåãî áèòà ñ îápàòíûì åìó çíà÷åíèåì */
73
74
75 /* HÀ×ÀËÎ ÊÎÄÈÐÎÂÀHÈß ÏÎÒÎÊÀ ÑÈÌÂÎËΠ*/
76
77 start_encoding()
78 { low = 0; /* Ïîëíûé êîäîâûé èíòåpâàë */
79 high = Top_value;
80 bits_to_follow = 0; /* Äîáàâëÿòü áèòû ïîêà íå íàäî */
81 }
82
83
84 /* ÊÎÄÈÐÎÂÀHÈÅ ÑÈÌÂÎËÀ */
85
86 encode_symbol(symbol,cum_freq)
87 int symbol; /* Êîäèpóåìûé ñèìâîë */
88 int cum_freq[]; /* Hàêàïëèâàåìûå ÷àñòîòû */
89 { long range; /* Øèpèíà òåêóùåãî */
90 range = (long)(high-low)+1; /* êîäîâîãî èíòåpâàëà */
91 high = low + /* Ñóæåíèå èíòåpâàëà êî- */
92 (range*cum_freq[symbol-1])/cum_freq[0]-1; /* äîâ äî */
93 low = low + /* âûäåëåííîãî äëÿ symbol*/
94 (range*cum_freq[symbol])/cum_freq[0];
95 for (;;) { /* Öèêë ïî âûâîäó áèòîâ */
96 if (high<Half) { /* Åñëè â íèæíåé ïîëîâèíå*/
97 bits_plus_follow(0); /* èñõîäíîãî èíòåpâàëà, */
98 } /* òî âûâîä 0 */
99 else if (low>=Half) { /* Åñëè â âåpõíåé, òî */
100 bit_plus_follow(1); /* âûâîä 1, à çàòåì */
101 low -= Half; /* óápàòü èçâåñòíóþ ó */
102 high -= Half; /* ãpàíèö îáùóþ ÷àñòü */
103 }
104 else if (low>=First_qtr /* Åñëè òåêóùèé èíòåpâàë */
105 && high<Third_qtr) { /* ñîäåpæèò ñåpåäèíó èñ- */
106 bits_to_follow +=1; /* õîäíîãî, òî âûâîä åùå */
107 low -= First_qtr; /* îäíîãî îápàòíîãî áèòà */
108 high -= First_qtr; /* ïîçæå, à ñåé÷àñ */
109 } /* óápàòü îáùóþ ÷àñòü */
110 else break; /* Èíà÷å âûéòè èç öèêëà */
111 low = 2*low; /* Ðàñøèpèòü òåêóùèé pà- */
112 high = 2*high+1; /* áî÷èé êîäîâûé èíòåpâàë*/
113 }
114 }
115
116
117 /* ÇÀÂÅÐØÅHÈÅ ÊÎÄÈÐÎÂÀHÈß ÏÎÒÎÊÀ */
118
119 done_encoding() /* Âûâîä äâóõ áèòîâ, */
120 { bits_to_follow += 1; /* îïpåäåëÿþùèõ ÷åpâåpòü,*/
121 if (low<First_qtr) bit_plus_follow(0); /* ëåæàùóþ â */
122 else bit_plus_follow(1); /* òåêóùåì èíòåpâàëå */
123 }
124
125
126 /* ÂÛÂÎÄ ÁÈÒÀ ÂÌÅÑÒÅ ÑÎ ÑËÅÄÓÞÙÈÌÈ ÇÀ HÈÌ ÎÁÐÀÒHÛÌÈ ÅÌÓ */
127
128 static void bit_plus_follow(bit)
129 int bit;
130 { output_bit(bit);
131 while (bits_to_follow>0) {
132 output_bit(!bit);
133 bits_to_follow -= 1;
134 }
135 }
decode.c
----------------------------------------------------------------------
136 /* ÃÎËÎÂHÀß ÏÐÎÖÅÄÓÐÀ ÄËß ÄÅÊÎÄÈÐÎÂÀHÈß */
137
138 #include <stdio.h>
139 #include "model.h"
140
141 main()
142 { start_model();
143 start_inputing_bits();
144 start_decoding();
145 for (;;) {
145 int ch; int symbol;
147 symbol = decode_symbol(cum_freq);
148 if (symbol == EOF_symbol) break;
149 ch = index_to_char(symbol);
150 putc(ch,stdout);
151 update_model(symbol);
152 }
153 exit(0);
154 }
arithmetic_decode.c
----------------------------------------------------------------------
155 /* ÀËÃÎÐÈÒÌ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÃÎ ÄÅÊÎÄÈÐÎÂÀHÈß */
156
157 #include "arithmetic_coding.h"
158
159
160 /* ÒÅÊÓÙÅÅ ÑÎÑÒÎßHÈÅ ÄÅÊÎÄÈÐÎÂÀHÈß */
161
162 static code_value value; /* Òåêóùåå çíà÷åíèå êîäà */
163 static code_value low, high; /* Ãpàíèöû òåêóùåãî */
164 /* êîäîâîãî èíòåpâàëà */
165
166 /* HÀ×ÀËÎ ÄÅÊÎÄÈÐÎÂÀHÈß ÏÎÒÎÊÀ ÑÈÌÂÎËΠ*/
167
168 start_decoding();
169 { int i;
170 value = 0; /* Ââîä áèòîâ äëÿ çàïîë- */
171 for (i = 1; i<=Code_value_bits; i++) { /* íåíèÿ çíà÷å- */
172 value = 2*value+input_bit(); /* íèÿ êîäà */
173 }
174 low = 0; /*  ñàìîì íà÷àëå òåêó- */
175 high = Top_value; /* ùèé pàáî÷èé èíòåpâàë */
176 } /* pàâåí èñõîäíîìó */
177
178
179 /* ÄÅÊÎÄÈÐÎÂÀHÈÅ ÑËÅÄÓÞÙÅÃÎ ÑÈÌÂÎËÀ */
180
181 int decode_symbol(cum_freq)
182 int cum_freq[]; /* Hàêîïëåííûå ÷àñòîòû */
183 { long range; /* Øèpèíà èíòåpâàëà */
184 int cum; /* Hàêîïëåííàÿ ÷àñòîòà */
185 int symbol; /* Äåêîäèpóåìûé ñèìâîë */
186 range = (long)(high-low)+1;
187 cum = /* Hàõîæäåíèå çíà÷åíèÿ íàêîïëåííîé ÷àñòîòû äëÿ */
188 (((long)(value-low)+1)*cum_freq[0]-1)/range; /* value */
189 for (symbol = 1; cum_freq[symbol]>cum; symbol++);
190 high = low + /* Ïîñëå íàõîæäåíèÿ ñèì- */
191 (range*cum_freq[symbol-1])/cum_freq[0]-1; /* âîëà */
192 low = low +
193 (range*cum_freq[symbol])/cum_freq[0];
194 for (;;) { /*Öèêë îòápàñûâàíèÿ áèòîâ*/
195 if (high<Half) { /* Ðàñøèpåíèå íèæíåé */
196 /* íè÷åãî */ /* ïîëîâèíû */
197 }
198 else if (low>=Half) { /* Ðàñøèpåíèå âåpõíåé */
199 value -= Half; /* ïîëîâèíû ïîñëå âû÷è- */
200 low -= Half; /* òàíèå ñìåùåíèÿ Half */
201 high -= Half;
202 }
203 else if (low>=First_qtr /* Ðàñøèpåíèå ñpåäíåé */
204 && high<Third_qtr) { /* ïîëîâèíû */
205 value -= First_qtr;
206 low -= First_qtr;
207 high -= First_qtr;
208 }
209 else break;
210 low = 2*low; /* Óâåëè÷èòü ìàñøòàá */
211 high = 2*high+1; /* èíòåpâàëà */
212 value = 2*value+input_bit(); /* Äîáàâèòü íîâûé áèò */
213 }
214 return symbol;
215 }
bit_input.c
----------------------------------------------------------------------
216 /* ÏÐÎÖÅÄÓÐÛ ÂÂÎÄÀ ÁÈÒÎÂ */
217
218 #include <stdio.h>
219 #include "arithmetic_coding.h"
220
221
222 /* ÁÈÒÎÂÛÉ ÁÓÔÅÐ */
223
224 static int buffer; /* Ñàì áóôåp */
225 static int bits_to_go; /* Ñêîëüêî áèòîâ â áóôåpå*/
226 static int garbage_bits; /* Êîëè÷åñòâî áèòîâ */
227 /* ïîñëå êîíöà ôàéëà */
228
229 /* ÈHÈÖÈÀËÈÇÀÖÈß ÏÎÁÈÒHÎÃÎ ÂÂÎÄÀ */
230
231 start_inputing_bits()
232 { bits_to_go = 0; /* Âíà÷àëå áóôåp ïóñò */
233 garbage_bits = 0;
234 }
235
236
237 /* ÂÂÎÄ ÁÈÒÀ */
238
239 int input_bit()
240 { int t;
241 if (bits_to_go==0) { /* ×òåíèå áàéòà, åñëè */
242 buffer = getc(stdin); /* áóôåp ïóñò */
243 if (buffer==EOF) {
244 garbage_bits += 1; /* Ïîìåùåíèå ëþáûõ áèòîâ */
245 if (garbage_bits>Code_value_bits-2) { /* ïîñëå */
246 fprintf(stderr,"Bad input file\n"); /* êîí- */
247 exit(-1); /* öà ôàéëà ñ ïpîâåpêîé */
248 } /* íà ñëèøêîì áîëüøîå èõ */
249 } /* êîëè÷åñòâî */
250 bits_to_go = 8;
251 }
252 t = buffer&1; /* Âûäà÷à î÷åpåäíîãî */
253 buffer >>= 1; /* áèòà ñ ïpàâîãî êîíöà */
254 bits_to_go -= 1; /* (äíà) áóôåpà */
255 return t;
256 }
bit_output.c
----------------------------------------------------------------------
257 /* ÏÐÎÖÅÄÓÐÛ ÂÛÂÎÄÀ ÁÈÒÎÂ */
258
259 #include <stdio.h>
260
261
262 /* ÁÈÒÎÂÛÉ ÁÓÔÅÐ */
263
264 static int buffer; /* Áèòû äëÿ âûâîäà */
265 static int bits_to_go; /* Êîëè÷åñòâî ñâîáîäíûõ */
266 /* áèòîâ â áóôåpå */
267
268 /* ÈHÈÖÈÀËÈÇÀÖÈß ÁÈÒÎÂÎÃÎ ÂÛÂÎÄÀ */
269
270 start_outputing_bits()
271 { buffer = 0; /* Âíà÷àëå áóôåp ïóñò */
272 bits_to_go = 8;
273 }
274
275
276 /* ÂÛÂÎÄ ÁÈÒÀ */
277
278 output_bit(bit)
279 int bit;
280 { buffer >>= 1; /* Áèò - â íà÷àëî áóôåpà */
281 if (bit) buffer |= 0x80;
282 bits_to_go -= 1;
283 if (bits_to_go==0) {
284 putc(buffer,stdout); /* Âûâîä ïîëíîãî áóôåpà */
285 bits_to_go = 8;
286 }
287 }
288
289
290 /* ÂÛÌÛÂÀHÈÅ ÏÎÑËÅÄHÈÕ ÁÈÒÎÂ */
291
292 done_outputing_bits()
293 { putc(buffer>>bits_to_go,stdout);
294 }
fixed_model.c
----------------------------------------------------------------------
1 /* ÌÎÄÅËÜ Ñ ÔÈÊÑÈÐÎÂÀHHÛÌ ÈÑÒÎ×HÈÊÎÌ */
2
3 include "model.h"
4
5 int freq[No_of_symbols+1] = {
6 0,
7 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,124, 1, 1, 1, 1, 1,
8 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
9
10 /* ! " # $ % & ' ( ) * + , - . / */
11 1236, 1, 21, 9, 3, 1, 25, 15, 2, 2, 2, 1, 79, 19, 60, 1,
12
13 /* 0 1 2 3 4 5 6 7 8 9 : ; < = > ? */
14 15, 15, 8, 5, 4, 7, 5, 4, 6, 3, 2, 1, 1, 1, 1, 1,
15
16 /* @ A B C D E F G H I J K L M N O */
17 1, 24, 15, 22, 12, 15, 10, 9, 16, 16, 8, 6, 12, 23, 13, 1,
18
19 /* P Q R S T U V W X Y Z [ \ ] ^ _ */
20 14, 1, 14, 28, 29, 6, 3, 11, 1, 3, 1, 1, 1, 1, 1, 3,
21
22 /* ' a b c d e f g h i j k l m n o */
23 1,491, 85,173,232,744,127,110,293,418, 6, 39,250,139,429,446,
24
25 /* p q r s t u v w x y z { | } */
26 111, 5,388,375,531,152, 57, 97, 12,101, 5, 2, 1, 2, 3, 1,
27
28 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
29 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
30 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
31 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
32 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
33 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
34 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
35 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
36 1
37 };
38
39
40 /* ÈHÈÖÈÀËÈÇÀÖÈß ÌÎÄÅËÈ */
41
42 start_model()
43 { int i;
44 for (i = 0; i<No_of_chars; i++) { /* Óñòàíîâêà òàáëèö */
45 char_to_index[i] = i+1; /* ïåpåêîäèpîâêè òèïîâ */
46 index_to_char[i+1] = i;
47 }
48 cum_freq[No_of_symbols] = 0;
49 for (i = No_of_symbols; i>0; i--) { /* Óñòàíîâêà */
50 cum_freq[i-1] = cum_freq[i] + freq[i]; /* ñ÷åò÷èêîâ */
51 } /* íàêîïëåííûõ ÷àñòîò */
52 if (cum_freq[0] > Max_frequency) abort(); /* Ïpîâåpêà */
53 } /* ñ÷åò÷èêîâ ïî ãpàíèöàì */
54
55
56 /* ÎÁHÎÂÈÒÜ ÌÎÄÅËÜ Â ÑÂßÇÈ Ñ HÎÂÛÌ ÑÈÌÂÎËÎÌ */
57
58 update_model(symbol)
59 int symbol;
60 { /* Hè÷åãî íå äåëàåòñÿ */
61 }
adaptive_model.c
----------------------------------------------------------------------
1 /* ÌÎÄÅËÜ Ñ HÀÑÒÐÀÈÂÀÅÌÛÌ ÈÑÒÎ×HÈÊÎÌ */
2
3 include "model.h"
4
5 int freq[No_of_symbols+1] /* ×àñòîòû ñèìâîëîâ */
6
7
8 /* ÈHÈÖÈÀËÈÇÀÖÈß ÌÎÄÅËÈ */
9
10 start_model()
11 { int i;
12 for (i = 0; i<No_of_chars; i++) { /* Óñòàíîâêà òàáëèö */
13 char_to_index[i] = i+1; /* ïåpåêîäèpîâêè ìåæäó */
14 index_to_char[i+1] = i; /* èñõîäíûìè è pàáî÷èìè */
15 } /* ñèìâîëàìè */
16 for (i = 0; i<No_of_symbols; i++) { /* Óñòàíîâêà çíà÷åíèé*/
17 freq[i] = 1; /* ñ÷åò÷èêîâ ÷àñòîò â 1 */
18 cum_freq[i] = No_of_symbol-i; /* äëÿ âñåõ ñèìâîëîâ */
19 }
20 freq[0] = 0; /* freq[0] äîëæåí îòëè- */
21 } /* ÷àòüñÿ îò freq[1] */
22
23
24 /* ÎÁHÎÂËÅHÈÅ ÌÎÄÅËÈ Â ÑÎÎÒÂÅÑÒÂÈÈ Ñ HÎÂÛÌ ÑÈÌÂÎËÎÌ */
25
26 update_model(symbol)
27 int symbol; /* Èíäåêñ íîâîãî ñèìâîëà */
28 { int i; /* Hîâûé èíäåêñ */
29 if (cum_freq[0]==Max_frequency) { /* Åñëè ñ÷åò÷èêè ÷àñ- */
30 int cum; /* òîò äîñòèãëè ñâîåãî */
31 cum = 0; /* ìàêñèìóìà */
32 for (i = No_of_symbols; i>=0; i--) { /* Òîãäà äåëèì */
33 freq[i] = (freq[i]+1)/2; /* èõ âñåõ ïîïîëàì, */
34 cum_freq[i] = cum; /* íå ïpèâîäÿ ê íóëþ */
35 cum += freq[i];
36 }
37 }
38 for (i = symbol; freq[i]==freq[i-1]; i--);
39 if (i<symbol) {
40 int ch_i, ch_symbol;
41 ch_i = index_to_char[i]; /* Îáíîâëåíèå ïåpå- */
42 ch_symbol = index_to_char[symbol]; /* êîäèpîâî÷íûõ */
43 index_to_char[i] = ch_symbol; /* òàáëèö â ñëó÷àå */
44 index_to_char[symbol] = ch_i; /* ïåpåìåùåíèÿ ñèì- */
45 char_to_index[ch_i] = symbol; /* âîëà */
46 char_to_index[ch_symbol] = i;
47 {
48 freq[i] += 1; /* Óâåëè÷èòü çíà÷åíèå */
49 while (i>0) { /* ñ÷åò÷èêà ÷àñòîòû äëÿ */
50 i -= 1; /* ñèìâîëà è îáíîâèòü */
51 cum_freq[i] += 1; /* íàêîïëåííûå ÷àñòîòû */
52 }
53 }
Ðåàëèçàöèÿ ìîäåëè
Ñàìà ðåàëèçàöèÿ îáñóæäàåòñÿ â ñëåäóþùåì ðàçäåëå, à çäåñü ìû êîñíåìñÿ òîëüêî èíòåðôåéñà ñ ìîäåëüþ (ñòðîêè 20-38).  ÿçûêå Ñè áàéò ïðåäñòàâëÿåò ñîáîé öåëîå ÷èñëî îò 0 äî 255 (òèï char). Çäåñü æå ìû ïðåäñòàâëÿåì áàéò êàê öåëîå ÷èñëî îò 1 äî 257 âêëþ÷èòåëüíî (òèï index), ãäå EOF òðàêòóåòñÿ êàê 257-îé ñèìâîë. Ïðåäïî÷òèòåëüíî îòñîðòèðîâàòü ìîäåëü â ïîðÿäêå óáûâàíèÿ ÷àñòîò äëÿ ìèíèìèçàöèè êîëè÷åñòâà âûïîëíåíèÿ öèêëà äåêîäèðîâàíèÿ (ñòðîêà 189). Ïåðåâîä èç òèïà char â index, è íàîáîðîò, ðåàëèçóåòñÿ ñ ïîìîùüþ äâóõ òàáëèö - index_to_char[ ] è char_to_index[ ].
 îäíîé èç íàøèõ ìîäåëåé ýòè òàáëèöû ôîðìèðóþò index ïðîñòûì äîáàâëåíèåì 1 ê char, íî â äðóãîé âûïîëíÿåòñÿ áîëåå ñëîæíîå ïåðåêîäèðîâàíèå, ïðèñâàèâàþùåå ÷àñòî èñïîëüçóåìûì ñèìâîëàì ìàëåíüêèå èíäåêñû.
Âåðîÿòíîñòè ïðåäñòàâëÿþòñÿ â ìîäåëè êàê öåëî÷èñëåííûå ñ÷åò÷èêè ÷àñòîò, à íàêàïëèâàåìûå ÷àñòîòû õðàíÿòñÿ â ìàññèâå cum_freq[ ]. Êàê è â ïðåäûäóùåì ñëó÷àå, ýòîò ìàññèâ - "îáðàòíûé", è ñ÷åò÷èê îáùåé ÷àñòîòû, ïðèìåíÿåìûé äëÿ íîðìàëèçàöèè âñåõ ÷àñòîò, ðàçìåùàåòñÿ â cum_freq[0].
Íàêàïëèâàåìûå ÷àñòîòû íå äîëæíû ïðåâûøàòü óñòàíîâëåííûé â Max_frequency ìàêñèìóì, à ðåàëèçàöèÿ ìîäåëè äîëæíà ïðåäîòâðàùàòü ïåðåïîëíåíèå ñîîòâåòñòâóþùèì ìàñøòàáèðîâàíèåì. Íåîáõîäèìî òàêæå õîòÿ áû íà 1 îáåñïå÷èòü ðàçëè÷èå ìåæäó äâóìÿ ñîñåäíèìè çíà÷åíèÿìè cum_freq[ ], èíà÷å ðàññìàòðèâàåìûé ñèìâîë íå ñìîæåò áûòü ïåðåäàí.
Ïðèðàùàåìàÿ ïåðåäà÷à è ïîëó÷åíèå
 îòëè÷èå îò ïñåâîäîêîäà íà Ðèñóíêå 1, Ïðîãðàììà 1 ïðåäñòàâëÿåò low è High öåëûìè ÷èñëàìè. Äëÿ íèõ, è äëÿ äðóãèõ ïîëåçíûõ êîíñòàíò, îïðåäåëåí ñïåöèàëüíûé òèï äàííûõ code_value. Ýòî - Toð_value, îïðåäåëÿþùèé ìàêñèìàëüíî âîçìîæíûé code_value, First_qtr è Third_qtr, ïðåäñòàâëÿþùèå ÷àñòè èíòåðâàëà (ñòðîêè 6-16).  ïñåâäîêîäå òåêóùèé èíòåðâàë ïðåäñòàâëåí ÷åðåç [low; High), à â ïðîãðàììå 1 ýòî [low; High] - èíòåðâàë, âêëþ÷àþùèé â ñåáÿ çíà÷åíèå High. Íà ñàìîì äåëå áîëåå ïðàâèëüíî, õîòÿ è áîëåå íåïîíÿòíî, óòâåðæäàòü, ÷òî â ïðîãðàììå 1 ïðåäñòàâëÿåìûé èíòåðâàë åñòü [low; High + 0.1111...) ïî òîé ïðè÷èíå, ÷òî ïðè ìàñøòàáèòîâàíèè ãðàíèö äëÿ óâåëè÷åíèÿ òî÷íîñòè, íóëè ñìåùàþòñÿ ê ìëàäøèì áèòàì low, à åäèíèöû ñìåùàþòñÿ â High. Õîòÿ ìîæíî ïèñàòü ïðîãðàììó íà îñíîâå ðàçíûõ äîãîâîðåííîñòåé, äàííàÿ èìååò íåêîòîðûå ïðåèìóùåñòâà â óïðîùåíèè êîäà ïðîãðàììû.
Ïî ìåðå ñóæåíèÿ êîäîâîãî èíòåðâàëà, ñòàðøèå áèòû low è High ñòàíîâÿòñÿ îäèíàêîâûìè, è ïîýòîìó ìîãóò áûòü ïåðåäàíû íåìåäëåííî, ò.ê. íà íèõ áóäóùèå ñóæåíèÿ èíòåðâàëà âñå ðàâíî óæå íå áóäóò âëèÿòü. Ïîñêîëüêó ìû çíàåì, ÷òî low<=High, ýòî âîïëîòèòñÿ â ñëåäóþùóþ ïðîãðàììó:
for (;;) {
if (high < Half) {
output_bit(0);
low = 2 * low;
high = 2 * high + 1;
}
else if (low >= Half) {
output_bit(1);
low = 2 * (low - Half);
high = 2 * (high - Half) + 1;
}
else break;
}
ãàðàíòèðóþùóþ, ÷òî ïîñëå åå çàâåðøåíèÿ áóäåò ñïðàâåäëèâî íåðàâåíñòâî: low<Íalf<=High. Ýòî ìîæíî íàéòè â ñòðîêàõ 95-113 ïðîöåäóðû encode_symbol(). Êðîìå òîãî, åñòü íåñêîëüêî äîïîëíèòåëüíûõ ñëîæíîñòåé, ñâÿçàííûõ ñ âîçìîæíîñòÿìè ïîòåðè çíà÷èìîñòè (ñì. ñëåäóþùèé ïîäðàçäåë). Êàê îòìå÷åíî âûøå, íóæíî âíèìàíèå ïðè ñäâèãå åäèíèö ê íà÷àëó High.
Ïðèðàùàåìûé ââîä èñõîäíûõ äàííûõ âûïîëíÿåòñÿ ñ ïîìîùüþ ÷èñëà, íàçâàííîãî value.  ïðîãðàììå 1, îáðàáîòàííûå áèòû ïåðåìåùàþòñÿ â âåðõíþþ ÷àñòü, à çàíîâî ïîëó÷àåìûå ïîñòóïàþò â íèæíþþ. Âíà÷àëå, start_decoding() (ñòðîêè 168-176) çàïîëíÿåò value ïîëó÷åííûìè áèòàìè. Ïîñëå îïðåäåëåíèÿ ñëåäóþùåãî âõîäíîãî ñèìâîëà ïðîöåäóðîé decode_symbol(), ïðîèñõîäèò âûíîñ íåíóæíûõ, îäèíàêîâûõ â low è â High, áèòîâ ñòàðøåãî ïîðÿäêà ñäâèãîì value íà ýòî êîëè÷åñòâî ðàçðÿäîâ (âûâåäåííûå áèòû âîñïîëíÿþòñÿ ââåäåíèåì íîâûé ñ íèæíåãî êîíöà).
for (;;) {
if (high < Half) {
value = 2 * value + input_bit();
low = 2 * low;
high = 2 * high + 1;
}
else if (low > Half) {
value = 2 * (value - Half) + input_bit();
low = 2 * (low - Half);
high = 2 * (high - Half) + 1;
}
else break;
}
Äîêàçàòåëüñòâî ïðàâèëüíîñòè äåêîäèðîâàíèÿ
Ïðîâåðèì âåðíîñòü îïðåäåëåíèÿ ïðîöåäóðîé decode_symbol() ñëåäóþùåãî ñèìâîëà. Èç ïñåâäîêîäà íà Ðèñóíêå 1 âèäíî, ÷òî decode_symbol() äîëæíà èñïîëüçîâàòü value äëÿ ïîèñêà ñèìâîëà, ñîêðàòèâøåãî ïðè êîäèðîâàíèè ðàáî÷èé èíòåðâàë òàê, ÷òî îí ïðîäîëæàåò âêëþ÷àòü â ñåáÿ value. Ñòðîêè 186-188 â decode_symbol() îïðåäåëÿþò òàêîé ñèìâîë, äëÿ êîòîðîãî
| (value-low+1)*cum_freq[0]-1 |
cum_freq[symbol] <= | --------------------------- | < cum_freq[symbol-1],
|_ high-low+1 _|
ãäå "|_ _|" îáîçíà÷àåò îïåðàöèþ âçÿòèÿ öåëîé ÷àñòè - äåëåíèå ñ îòáðàñûâàíèåì äðîáíîé ÷àñòè.  ïðèëîæåíèè ïîêàçàíî, ÷òî ýòî ïðåäïîëàãàåò:
| (high-low+1)*cum_freq[symbol] | | (high-low+1)*cum_freq[symbol-1] |
low + | ----------------------------- | <= value <= low + | ------------------------------- |,
|_ cum_freq[0] _| |_ cum_freq[0] _|
òàêèì îáðàçîì, ÷òî value ëåæèò âíóòðè íîâîãî èíòåðâàëà, âû÷èñëÿåìîãî ïðîöåäóðîé decode_symbol() â ñòðîêàõ 190-193. Ýòî îïðåäåëåííî ãàðàíòèðóåò êîððåêòíîñòü îïðåäåëåíèÿ êàæäîãî ñèìâîëà îïåðàöèåé äåêîäèðîâàíèÿ.
Îòðèöàòåëüíîå ïåðåïîëíåíèå
Êàê ïîêàçàíî â ïñåâäîêîäå, àðèôìåòè÷åñêîå êîäèðîâàíèå ðàáîòàåò ïðè ïîìîùè ìàñøòàáèðîâàíèÿ íàêîïëåííûõ âåðîÿòíîñòåé, ïîñòàâëÿåìûõ ìîäåëüþ â èíòåðâàëå [low; High] äëÿ êàæäîãî ïåðåäàâàåìîãî ñèìâîëà. Ïðåäïîëîæèì, ÷òî low è High íàñòîëüêî áëèçêè äðóã ê äðóãó, ÷òî îïåðàöèÿ ìàñøòàáèðîâàíèÿ ïðèâîäèò ïîëó÷åííûå îò ìîäåëè ðàçíûå ñèìâîëû ê îäíîìó öåëîìó ÷èñëó, âõîäÿùåìó â [low; High].  ýòîì ñëó÷àå äàëüíåéøåå êîäèðîâàíèå ïðîäîëæàòü íåâîçìîæíî. Ñëåäîâàòåëüíî, êîäèðîâùèê äîëæåí ñëåäèòü çà òåì, ÷òîáû èíòåðâàë [low; High] âñåãäà áûë äîñòàòî÷íî øèðîê. Ïðîñòåéøèì ñïîñîáîì äëÿ ýòîãî ÿâëÿåòñÿ îáåñïå÷åíèå øèðèíû èíòåðâàëà íå ìåíüøåé Max_frequency - ìàêñèìàëüíîãî çíà÷åíèÿ ñóììû âñåõ íàêàïëèâàåìûõ ÷àñòîò (ñòðîêà 36).
Êàê ìîæíî ñäåëàòü ýòî óñëîâèå ìåíåå ñòðîãèì? Îáúÿñíåííàÿ âûøå îïåðàöèÿ áèòîâîãî ñäâèãà ãàðàíòèðóåò, ÷òî low è High ìîãóò òîëüêî òîãäà ñòàíîâèòüñÿ îïàñíî áëèçêèìè, êîãäà çàêëþ÷àþò ìåæäó ñîáîé Íalf. Ïðåäïîëîæèì, îíè ñòàíîâÿòñÿ íàñòîëüêî áëèçêè, ÷òî
First_qtr <= low < Íalf <= High < Third_qtr.
(*)
Òîãäà ñëåäóþùèå äâà áèòà âûâîäà áóäóò èìåòü âçàèìîîáðàòíûå çíà÷åíèÿ: 01 èëè 10. Íàïðèìåð, åñëè ñëåäóþùèé áèò áóäåò íóëåì (ò.å. High îïóñêàåòñÿ íèæå Íalf è [0; Íalf] ñòàíîâèòñÿ ðàáî÷èì èíòåðâàëîì), à ñëåäóþùèé çà íèì - åäèíèöåé, ò.ê. èíòåðâàë äîëæåí ðàñïîëàãàòüñÿ âûøå ñðåäíåé òî÷êè ðàáî÷åãî èíòåðâàëà. Íàîáîðîò, åñëè ñëåäóþùèé áèò îêàçàëñÿ 1, òî çà íèì áóäåò ñëåäîâàòü 0. Ïîýòîìó òåïåðü èíòåðâàë ìîæíî áåçîïàñíî ðàñøèðèòü âïðàâî, åñëè òîëüêî ìû çàïîìíèì, ÷òî êàêîé áû áèò íå áûë ñëåäóþùèì, âñëåä çà íèì íåîáõîäèìî òàêæå ïåðåäàòü â âûõîäíîé ïîòîê åãî îáðàòíîå çíà÷åíèå. Ò.î. ñòðîêè 104-109 ïðåîáðàçóþò [First_qtr;Third_qtr] â öåëûé èíòåðâàë, çàïîìèíàÿ â bits_to_follow çíà÷åíèå áèòà, çà êîòîðûì íàäî ïîñûëàòü îáðàòíûé åìó. Ýòî îáúÿñíÿåò, ïî÷åìó âåñü âûâîä ñîâåðøàåòñÿ ÷åðåç ïðîöåäóðó bit_ðlus_follow() (ñòðîêè 128-135), à íå íåïîñðåäñòâåííî ÷åðåç outðut_bit().
Íî ÷òî äåëàòü, åñëè ïîñëå ýòîé îïåðàöèè ñîîòíîøåíèå (*) îñòàåòñÿ ñïðàâåäëèâûì? Ðèñóíîê 2 ïîêàçûâàåò òàêîé ñëó÷àé, êîãäà îòìå÷åííûé æèðíîé ëèíèåé ðàáî÷èé èíòåðâàë [low; High] ðàñøèðÿåòñÿ 3 ðàçà ïîäðÿä.
Ïóñòü î÷åðåäíîé áèò, êàê îáîçíà÷åíî ñòðåëêîé, ðàñïîëîæåííîé íà Ðèñóíêå 2à íèæå ñðåäíåé òî÷êè ïåðâîíà÷àëüíîãî èíòåðâàëà, îêàçàëñÿ íóëåì. Òîãäà ñëåäóþùèå 3 áèòà áóäóò åäèíèöàìè, ïîñêîëüêó ñòðåëêà íàõîäèòñÿ íå ïðîñòî âî âòîðîé åãî ÷åòâåðòè, à â âåðõíåé ÷åòâåðòè, äàæå â âåðõíåé âîñüìîé ÷àñòè íèæíåé ïîëîâèíû ïåðâîíà÷àëüíîãî èíòåðâàëà - âîò ïî÷åìó ðàñøèðåíèå ìîæíî ïðîèçâåñòè 3 ðàçà. Òî æå ñàìîå ïîêàçàíî íà Ðèñóíêå 2b äëÿ ñëó÷àÿ, êîãäà î÷åðåäíîé áèò îêàçàëñÿ åäèíèöåé, è çà íèì áóäóò ñëåäîâàòü íóëè. Çíà÷èò â îáùåì ñëó÷àå íåîáõîäèìî ñíà÷àëà ñîñ÷èòàòü êîëè÷åñòâî ðàñøèðåíèé, à çàòåì âñëåä çà î÷åðåäíûì áèòîì ïîñëàòü â âûõîäíîé ïîòîê íàéäåííîå êîëè÷åñòâî îáðàòíûõ åìó áèòîâ (ñòðîêè 106 è 131-134).
Ñëåäóÿ ýòèì ðåêîìåíäàöèÿì, êîäèðîâùèê ãàðàíòèðóåò, ÷òî ïîñëå îïåðàöèé ñäâèãà áóäåò èëè:
low < First_qtr < Íalf <= High (1a)
èëè
low < Íalf < Third_qtr <= High (1b).
Çíà÷èò, ïîêà öåëî÷èñëåííûé èíòåðâàë, îõâàòûâàåìûé íàêîïëåííûìè ÷àñòîòàìè, ïîìåùàåòñÿ â åå ÷åòâåðòü, ïðåäñòàâëåííóþ â code_value, ïðîáëåìà îòðèöàòåëüíîãî ïåðåïîëíåíèÿ íå âîçíèêíåò. Ýòî ñîîòâåòñòâóåò óñëîâèþ:
Top_value + 1
Max_frequency <= ------------- + 1,
4
êîòîðîå óäîâëåòâîðÿåò â ïðîãðàììå 1, ò.ê. Max_frequency = 2^14 - 1 è Toð_value = 2^16 - 1 (ñòðîêè 36, 9). Íåëüçÿ áåç óâåëè÷åíèÿ êîëè÷åñòâà áèòîâ, âûäåëÿåìûõ äëÿ code_values, èñïîëüçîâàòü äëÿ ïðåäñòàâëåíèÿ ñ÷åò÷èêîâ íàêîïëåííûõ ÷àñòîò áîëüøå 14 áèòîâ.
Ìû ðàññìîòðåëè ïðîáëåìó îòðèöàòåëüíîãî ïåðåïîëíåíèÿ òîëüêî îòíîñèòåëüíî êîäèðîâùèêà, ïîñêîëüêó ïðè äåêîäèðîâàíèè êàæäîãî ñèìâîëà ïðîöåññ ñëåäóåò çà îïåðàöèåé êîäèðîâàíèÿ, è îòðèöàòåëüíîå ïåðåïîëíåíèå íå ïðîèçîéäåò, åñëè âûïîëíÿåòñÿ òàêîå æå ìàñøòàáèðîâàíèå ñ òåìè æå óñëîâèÿìè.
Ïåðåïîëíåíèå
Òåïåðü ðàññìîòðèì âîçìîæíîñòü ïåðåïîëíåíèÿ ïðè öåëî÷èñëåííîì óìíîæåíèè, èìåþùåå ìåñòî â ñòðîêàõ 91-94 è 190-193. Ïåðåïîëíåíèÿ íå ïðîèçîéäåò, åñëè ïðîèçâåäåíèå range*Max_frequency âìåùàåòñÿ â öåëîå ñëîâî, ò.ê. íàêîïëåííûå ÷àñòîòû íå ìîãóò ïðåâûøàòü Max_frequency. Range èìååò íàèáîëüøåå çíà÷åíèå â Toð_value + 1, ïîýòîìó ìàêñèìàëüíî âîçìîæíîå ïðîèçâåäåíèå â ïðîãðàììå 1 åñòü 2^16*(2^14 - 1), êîòîðîå ìåíüøå 2^30.
Äëÿ îïðåäåëåíèÿ code_value (ñòðîêà 7) è range (ñòðîêè 89,183) èñïîëüçîâàí òèï long, ÷òîáû îáåñïå÷èòü 32-õ áèòîâóþ òî÷íîñòü àðèôìåòè÷åñêèõ âû÷èñëåíèé.
Îãðàíè÷åííîñòü ðåàëèçàöèè
Îãðàíè÷åíèÿ, ñâÿçàííûå ñ äëèíîé ñëîâà è âûçâàííûå âîçìîæíîñòüþ ïåðåïîëíåíèÿ, ìîæíî îáîáùèòü ïîëàãàÿ, ÷òî ñ÷åò÷èêè ÷àñòîò ïðåäñòàâëÿþòñÿ f áèòàìè, à code_values - c áèòàìè. Ïðîãðàììà áóäåò ðàáîòàòü êîððåêòíî ïðè f <= c - 2 è f + c <= ð, ãäå ð åñòü òî÷íîñòü àðèôìåòèêè.
 áîëüøèíñòâå ðåàëèçàöèé íà Ñè, ð=31, åñëè èñïîëüçóþòñÿ öåëûå ÷èñëà òèïà long, è ð=32 - ïðè unsigned long.  ïðîãðàììå 1 f=14 è c=16. Ïðè ñîîòâåòñòâóþùèõ èçìåíåíèÿõ â îáúÿâëåíèÿõ íà unsigned long ìîæíî ïðèìåíÿòü f=15 è c=17. Íà ÿçûêå àññåìáëåðà c=16 ÿâëÿåòñÿ åñòåñòâåííûì âûáîðîì, ïîñêîëüêó îí óñêîðÿåò íåêîòîðûå îïåðàöèè ñðàâíåíèÿ è ìàíèïóëèðîâàíèÿ áèòàìè (íàïðèìåð äëÿ ñòðîê 95-113 è 194-213).
Åñëè îãðàíè÷èòü ð 16 áèòàìè, òî ëó÷øèå èç âîçìîæíûõ çíà÷åíèé c è f åñòü ñîîòâåòñòâåííî 9 è 7, ÷òî íå ïîçâîëÿåò êîäèðîâàòü ïîëíûé àëôàâèò èç 256 ñèìâîëîâ, ïîñêîëüêó êàæäûé èç íèõ áóäåò èìåòü çíà÷åíèå ñ÷åò÷èêà íå ìåíüøå åäèíèöû. Ñ ìåíüøèé àëôàâèòîì (íàïðèìåð èç 26 áóêâ èëè 4-õ áèòîâûõ âåëè÷èí) ñïðàâèòñÿ åùå ìîæíî.
Çàâåðøåíèå
Ïðè çàâåðøåíèè ïðîöåññà êîäèðîâàíèÿ íåîáõîäèìî ïîñëàòü óíèêàëüíûé çàâåðøàþùèé ñèìâîë (EOF-ñèìâîë, ñòðîêà 56), à çàòåì ïîñëàòü âñëåä äîñòàòî÷íîå êîëè÷åñòâî áèòîâ äëÿ ãàðàíòèè òîãî, ÷òî çàêîäèðîâàííàÿ ñòðîêà ïîïàäåò â èòîãîâûé ðàáî÷èé èíòåðâàë. Ò.ê. ïðîöåäóðà done_encoding() (ñòðîêè 119-123) ìîæåò áûòü óâåðåíà, ÷òî low è High îãðàíè÷åíû ëèáî âûðàæåíèåì (1a), ëèáî (1b), åìó íóæíî òîëüêî ïåðåäàòü 01 èëè 10 ñîîòâåòñòâåííî, äëÿ óäàëåíèÿ îñòàâøåéñÿ íåîïðåäåëåííîñòè. Óäîáíî ýòî äåëàòü ñ ïîìîùüþ ðàíåå ðàññìîòðåííîé ïðîöåäóðû bit_ðlus_follow(). Ïðîöåäóðà inðut_bit() íà ñàìîì äåëå áóäåò ÷èòàòü íåìíîãî áîëüøå áèòîâ, èç òåõ, ÷òî âûâåëà outðut_bit(), ïîòîìó ÷òî åé íóæíî ñîõðàíÿòü çàïîëíåíèå íèæíåãî êîíöà áóôåðà. Íåâàæíî, êàêîå çíà÷åíèå èìåþò ýòè áèòû, ïîñêîëüêó EOF óíèêàëüíî îïðåäåëÿåòñÿ ïîñëåäíèìè ïåðåäàííûìè áèòàìè.
Ìîäåëè äëÿ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ
Ïðîãðàììà 1 äîëæíà ðàáîòàòü ñ ìîäåëüþ, êîòîðàÿ ïðåäîñòàâëÿåò ïàðó ïåðåêîäèðîâî÷íûõ òàáëèö index_to_char[ ] è char_to_index[ ], è ìàññèâ íàêîïëåííûõ ÷àñòîò cum_freq[ ]. Ïðè÷åì ê ïîñëåäíåìó ïðåäúÿâëÿþòñÿ ñëåäóþùèå òðåáîâàíèÿ:
. cum_freq[i-1] >= cum_freq[i];
. íèêîãäà íå äåëàåòñÿ ïîïûòêà êîäèpîâàòü ñèìâîë i, äëÿ êîòîpîãî
cum_freq[i-1] = cum_freq[i];
. cum_freq[0] <= Max_frequency.
Åñëè äàííûå óñëîâèÿ ñîáëþäåíû, çíà÷åíèÿ â ìàññèâå íå äîëæíû èìåòü ñâÿçè ñ äåéñòâèòåëüíûìè çíà÷åíèÿìè íàêîïëåííûõ ÷àñòîò ñèìâîëîâ òåêñòà. È äåêîäèðîâàíèå, è êîäèðîâàíèå áóäóò ðàáîòàòü êîððåêòíî, ïðè÷åì ïîñëåäíåìó ïîíàäîáèòñÿ ìåíüøå ìåñòà, åñëè ÷àñòîòû òî÷íûå. (Âñïîìíèì óñïåøíîå êîäèðîâàíèå "eaii!" â ñîîòâåòñòâèè ñ ìîäåëüþ èç Òàáëèöû I, íå îòðàæàþùåé, îäíàêî, ïîäëèííîé ÷àñòîòû â òåêñòå).
Ôèêñèðîâàííûå ìîäåëè
Ïðîñòåéøåé ìîäåëüþ ÿâëÿåòñÿ òà, â êîòîðîé ÷àñòîòû ñèìâîëîâ ïîñòîÿííû. Ïåðâàÿ ìîäåëü èç ïðîãðàììû 2 çàäàåò ÷àñòîòû ñèìâîëîâ, ïðèáëèæåííûå ê îáùèì äëÿ àíãëèéñêîãî òåêñòà (âçÿòûì èç ÷àñòè Ñâîäà Áðàóíà). Íàêîïëåííûì ÷àñòîòàì áàéòîâ, íå ïîÿâëÿâøèìñÿ â ýòîì îáðàçöå, äàþòñÿ çíà÷åíèÿ, ðàâíûå 1 (ïîýòîìó ìîäåëü áóäåò ðàáîòàòü è äëÿ äâîè÷íûõ ôàéëîâ, ãäå åñòü âñå 256 áàéòîâ). Âñå ÷àñòîòû áûëè íîðìàëèçîâàíû â öåëîì äî 8000. Ïðîöåäóðà èíèöèàëèçàöèè start_model() ïðîñòî ïîäñ÷èòûâàåò íàêîïëåííóþ âåðñèþ ýòèõ ÷àñòîò (ñòðîêè 48-51), ñíà÷àëà èíèöèàëèçèðóÿ òàáëèöû ïåðåêîäèðîâêè (ñòðîêè 44-47). Ñêîðîñòü âûïîëíåíèÿ áóäåò óñêîðåíà, åñëè ýòè òàáëèöû ïåðåóïîðÿäî÷èòü òàê, ÷òîáû íàèáîëåå ÷àñòûå ñèìâîëû ðàñïîëàãàëèñü â íà÷àëå ìàññèâà cum_freq[ ]. Ò.ê. ìîäåëü ôèêñèðîâàííàÿ, òî ïðîöåäóðà uðdate_model(), âûçûâàåìàÿ èç encode.c è decode.c áóäåò ïðîñòî çàãëóøêîé.
Ñòðîãîé ìîäåëüþ ÿâëÿåòñÿ òà, ãäå ÷àñòîòû ñèìâîëîâ òåêñòà â òî÷íîñòè ñîîòâåòñòâóþò ïðåäïèñàíèÿì ìîäåëè. Íàïðèìåð, ôèêñèðîâàííàÿ ìîäåëü èç ïðîãðàììû 2 áëèçêà ê ñòðîãîé ìîäåëè äëÿ íåêîòîðîãî ôðàãìåíòà èç Ñâîäà Áðàóíà, îòêóäà îíà áûëà âçÿòà. Îäíàêî, äëÿ òîãî, ÷òîáû áûòü èñòèííî ñòðîãîé, åå, íå ïîÿâëÿâøèåñÿ â ýòîì ôðàãìåíòå, ñèìâîëû äîëæíû èìåòü ñ÷åò÷èêè ðàâíûå íóëþ, à íå 1 (ïðè ýòîì æåðòâóÿ âîçìîæíîñòÿìè èñõîäíûõ òåêñòîâ, êîòîðûå ñîäåðæàò ýòè ñèìâîëû). Êðîìå òîãî, ñ÷åò÷èêè ÷àñòîò íå äîëæíû ìàñøòàáèðîâàòüñÿ ê çàäàííîé íàêîïëåííîé ÷àñòîòå, êàê ýòî áûëî â ïðîãðàììå 2. Ñòðîãàÿ ìîäåëü ìîæåò áûòü âû÷èñëåíà è ïåðåäàíà ïåðåä ïåðåñûëêîé òåêñòà. Êëèðè è Óèòòåí ïîêàçàëè, ÷òî ïðè îáùèõ óñëîâèÿõ ýòî íå äàñò îáùåãî ëó÷øåãî ñæàòèÿ ïî ñðàâíåíèþ ñ îïèñûâàåìûì íèæå àäàïòèâíûì êîäèðîâàíèåì.
Àäàïòèâíàÿ ìîäåëü
Îíà èçìåíÿåò ÷àñòîòû óæå íàéäåííûõ â òåêñòå ñèìâîëîâ.  íà÷àëå âñå ñ÷åò÷èêè ìîãóò áûòü ðàâíû, ÷òî îòðàæàåò îòñóòñòâèå íà÷àëüíûõ äàííûõ, íî ïî ìåðå ïðîñìîòðà êàæäîãî âõîäíîãî ñèìâîëà îíè èçìåíÿþòñÿ, ïðèáëèæàÿñü ê íàáëþäàåìûì ÷àñòîòàì. È êîäèðîâùèê, è äåêîäèðîâùèê èñïîëüçóþò îäèíàêîâûå íà÷àëüíûå çíà÷åíèÿ (íàïðèìåð, ðàâíûå ñ÷åò÷èêè) è îäèí è òîò æå àëãîðèòì îáíîâëåíèÿ, ÷òî ïîçâîëèò èõ ìîäåëÿì âñåãäà îñòàâàòüñÿ íà îäíîì óðîâíå. Êîäèðîâùèê ïîëó÷àåò î÷åðåäíîé ñèìâîë, êîäèðóåò åãî è èçìåíÿåò ìîäåëü. Äåêîäèðîâùèê îïðåäåëÿåò î÷åðåäíîé ñèìâîë íà îñíîâàíèè ñâîåé òåêóùåé ìîäåëè, à çàòåì îáíîâëÿåò åå.
Âòîðàÿ ÷àñòü ïðîãðàììû 2 äåìîíñòðèðóåò òàêóþ àäàïòèâíóþ ìîäåëü, ðåêîìåíäóåìóþ äëÿ èñïîëüçîâàíèÿ â ïðîãðàììå 1, ïîñêîëüêó íà ïðàêòèêå îíà ïðåâîñõîäèò ôèêñèðîâàííóþ ìîäåëü ïî ýôôåêòèâíîñòè ñæàòèÿ. Èíèöèàëèçàöèÿ ïðîâîäèòñÿ òàêæå, êàê äëÿ ôèêñèðîâàííîé ìîäåëè, çà èñêëþ÷åíèåì òîãî, ÷òî âñå ÷àñòîòû óñòàíàâëèâàþòñÿ â 0. Ïðîöåäóðà uðdate_model(symbol), âûçûâàåòñÿ èç encode_symbol() è decode_symbol() (ïðîãðàììà 1, ñòðîêè 54 è 151) ïîñëå îáðàáîòêè êàæäîãî ñèìâîëà.
Îáíîâëåíèå ìîäåëè äîâîëüíî äîðîãî ïî ïðè÷èíå íåîáõîäèìîñòè ïîääåðæàíèÿ íàêîïëåííûõ ñóìì.  ïðîãðàììå 2 èñïîëüçóåìûå ñ÷åò÷èêè ÷àñòîò îïòèìàëüíî ðàçìåùåíû â ìàññèâå â ïîðÿäêå óáûâàíèÿ ñâîèõ çíà÷åíèé, ÷òî ÿâëÿåòñÿ ýôôåêòèâíûì âèäîì ñàìîîðãàíèçóåìîãî ëèíåéíîãî ïîèñêà. Ïðîöåäóðà uðdate_model() ñíà÷àëà ïðîâåðÿåò íîâóþ ìîäåëü íà ïðåäìåò ïðåâûøåíèÿ åþ îãðàíè÷åíèé ïî âåëè÷èíå íàêîïëåííîé ÷àñòîòû, è åñëè îíî èìååò ìåñòî, òî óìåíüøàåò âñå ÷àñòîòû äåëåíèåì íà 2, çàáîòÿñü ïðè ýòîì, ÷òîáû ñ÷åò÷èêè íå ïðåâðàòèëèñü â 0, è ïåðåâû÷èñëÿåò íàêîïëåííûå çíà÷åíèÿ (ïðîãðàììà 2, ñòðîêè 29-37). Çàòåì, åñëè íåîáõîäèìî, uðdate_model() ïåðåóïîðÿäî÷èâàåò ñèìâîëû äëÿ òîãî, ÷òîáû ðàçìåñòèòü òåêóùèé â åãî ïðàâèëüíîé êàòåãîðèè îòíîñèòåëüíî ÷àñòîòíîãî ïîðÿäêà, ÷åðåäóÿ äëÿ îòðàæåíèÿ èçìåíåíèé ïåðåêîäèðîâî÷íûå òàáëèöû.  èòîãå ïðîöåäóðà óâåëè÷èâàåò çíà÷åíèå ñîîòâåòñòâóþùåãî ñ÷åò÷èêà ÷àñòîòû è ïðèâîäèò â ïîðÿäîê ñîîòâåòñòâóþùèå íàêîïëåííûå ÷àñòîòû.
Õàðàêòåðèñòèêà
Òåïåðü ðàññìîòðèì ïîêàçàòåëè ýôôåêòèâíîñòè ñæàòèÿ è âðåìåíè âûïîëíåíèÿ ïðîãðàììû 1.
Ýôôåêòèâíîñòü ñæàòèÿ
Âîîáùå, ïðè êîäèðîâàíèè òåêñòà àðèôìåòè÷åñêèì ìåòîäîì, êîëè÷åñòâî áèòîâ â çàêîäèðîâàííîé ñòðîêå ðàâíî ýíòðîïèè ýòîãî òåêñòà îòíîñèòåëüíî èñïîëüçîâàííîé äëÿ êîäèðîâàíèÿ ìîäåëè. Òðè ôàêòîðà âûçûâàþò óõóäøåíèå ýòîé õàðàêòåðèñòèêè:
(1) ðàñõîäû íà çàâåðøåíèå òåêñòà;
(2) èñïîëüçîâàíèå àðèôìåòèêè
íåáåñêîíå÷íîé òî÷íîñòè;
(3) òàêîå ìàñøòàáèðîâàíèå ñ÷åò÷èêîâ, ÷òî
èõ ñóììà íå ïðåâûøàåò Max_frequency.
Êàê áûëî ïîêàçàíî, íè îäèí èç íèõ íå çíà÷èòåëåí.  ïîðÿäêå âûäåëåíèÿ ðåçóëüòàòîâ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ, ìîäåëü áóäåò ðàññìàòðèâàòüñÿ êàê ñòðîãàÿ (â îïðåäåëåííîì âûøå ñìûñëå).
Àðèôìåòè÷åñêîå êîäèðîâàíèå äîëæíî äîñûëàòü äîïîëíèòåëüíûå áèòû â êîíåö êàæäîãî òåêñòà, ñîâåðøàÿ ò.î. äîïîëíèòåëüíûå óñèëèÿ íà çàâåðøåíèå òåêñòà. Äëÿ ëèêâèäàöèè íåÿñíîñòè ñ ïîñëåäíèì ñèìâîëîì ïðîöåäóðà done_encoding() (ïðîãðàììà 1 ñòðîêè 119-123) ïîñûëàåò äâà áèòà.  ñëó÷àå, êîãäà ïåðåä êîäèðîâàíèåì ïîòîê áèòîâ äîëæåí áëîêèðîâàòüñÿ â 8-áèòîâûå ñèìâîëû, áóäåò íåîáõîäèìî çàêðóãëÿòüñÿ ê êîíöó áëîêà. Òàêîå êîìáèíèðîâàíèå ìîæåò äîïîëíèòåëüíî ïîòðåáîâàòü 9 áèòîâ.
Çàòðàòû ïðè èñïîëüçîâàíèè àðèôìåòèêè êîíå÷íîé òî÷íîñòè ïðîÿâëÿþòñÿ â ñîêðàùåíèè îñòàòêîâ ïðè äåëåíèè. Ýòî âèäíî ïðè ñðàâíåíèè ñ òåîðåòè÷åñêîé ýíòðîïèåé, êîòîðàÿ âûâîäèò ÷àñòîòû èç ñ÷åò÷èêîâ òî÷íî òàêæå ìàñøòàáèðóåìûõ ïðè êîäèðîâàíèè. Çäåñü çàòðàòû íåçíà÷èòåëüíû - ïîðÿäêà 10^-4 áèòîâ/ñèìâîë.
Äîïîëíèòåëüíûå çàòðàòû íà ìàñøòàáèðîâàíèå ñ÷åò÷èêîâ îò÷àñòè áîëüøå, íî âñå ðàâíî î÷åíü ìàëû. Äëÿ êîðîòêèõ òåêñòîâ (ìåíüøèõ 2^14 áàéò) èõ íåò. Íî äàæå ñ òåêñòàìè â 10^5 - 10^6 áàéòîâ íàêëàäíûå ðàñõîäû, ïîäñ÷èòàííûå ýêñïåðèìåíòàëüíî, ñîñòàâëÿþò ìåíåå 0.25% îò êîäèðóåìîé ñòðîêè.
Àäàïòèâíàÿ ìîäåëü â ïðîãðàììå 2, ïðè óãðîçå ïðåâûøåíèÿ îáùåé ñóììîé íàêîïëåííûõ ÷àñòîò çíà÷åíèå Max_frequency, óìåíüøàåò âñå ñ÷åò÷èêè. Ýòî ïðèâîäèò ê òîìó, ÷òî âçâåøèâàòü ïîñëåäíèå ñîáûòèÿ òÿæåëåå, ÷åì áîëåå ðàííèå. Ò.î. ïîêàçàòåëè èìåþò òåíäåíöèþ ïðîñëåæèâàòü èçìåíåíèÿ âî âõîäíîé ïîñëåäîâàòåëüíîñòè, êîòîðûå ìîãóò áûòü î÷åíü ïîëåçíûìè. (Ìû ñòàëêèâàëèñü ñî ñëó÷àÿìè, êîãäà îãðàíè÷åíèå ñ÷åò÷èêîâ äî 6-7 áèòîâ äàâàëî ëó÷øèå ðåçóëüòàòû, ÷åì ïîâûøåíèå òî÷íîñòè àðèôìåòèêè). Êîíå÷íî, ýòî çàâèñèò îò èñòî÷íèêà, ê êîòîðîìó ïðèìåíÿåòñÿ ìîäåëü.
Âðåìÿ âûïîëíåíèÿ
Ïðîãðàììà 1 áûëà íàïèñàíà ñêîðåå äëÿ ÿñíîñòè, ÷åì äëÿ ñêîðîñòè. Ïðè âûïîëíåíèè åå âìåñòå ñ àäàïòèâíîé ìîäåëüþ èç ïðîãðàììû 2, ïîòðåáîâàëîñü îêîëî 420 ìêñ íà áàéò èñõîäíîãî òåêñòà íà ÝÂÌ VAX-11/780 äëÿ êîäèðîâàíèÿ è ïî÷òè ñòîëüêî æå äëÿ äåêîäèðîâàíèÿ. Îäíàêî, ëåãêî óñòðàíÿåìûå ðàñõîäû, òàêèå êàê âûçîâû íåêîòîðûõ ïðîöåäóð, ñîçäàþùèå ìíîãèå èç íèõ, è íåêîòîðàÿ ïðîñòàÿ îïòèìèçàöèÿ, óâåëè÷èâàþò ñêîðîñòü â 2 ðàçà.  ïðèâåäåííîé âåðñèè ïðîãðàììû íà ÿçûêå Ñè áûëè ñäåëàíû ñëåäóþùèå èçìåíåíèÿ:
(1) ïðîöåäóðû inðut_bit(), outðut_bit() è bit_ðlus_follow()
áûëè ïåðåâåäåíû â ìàêðîñû, óñòðàíèâøèå
ðàñõîäû ïî âûçîâó ïðîöåäóð;
(2) ÷àñòî èñïîëüçóåìûå âåëè÷èíû áûëè
ïîìåùåíû â ðåãèñòðîâûå ïåðåìåííûå;
(3) óìíîæåíèÿ íå äâà áûëè çàìåíåíû
äîáàâëåíèÿìè ("+=");
(4) èíäåêñíûé äîñòóï ê ìàññèâó â öèêëàõ ñòpîê 189 ïpîãpàììû 1 è 49-52 ïpîãpàììû 2 àäàïòèâíîé ìîäåëè áûë çàìåíåí
îïåðàöèÿìè ñ óêàçàòåëÿìè.
Ýòî ñðåäíå îïòèìèçèðîâàííàÿ ðåàëèçàöèÿ íà Ñè èìåëà âðåìÿ âûïîëíåíèÿ â 214/252 ìêñ íà âõîäíîé áàéò, äëÿ êîäèðîâàíèÿ/äåêîäèðîâàíèÿ 100.000 áàéòîâ àíãëèéñêîãî òåêñòà íà VAX-11/780, êàê ïîêàçàíî â Òàáëèöå II.
Òàì æå äàíû ðåçóëüòàòû äëÿ òîé æå ïðîãðàììû íà Aððle Macintosh è SUN3/75. Êàê ìîæíî âèäåòü, êîäèðîâàíèå ïðîãðàììû íà Ñè îäíîé è òîé æå äëèíû âåçäå îñóùåñòâëÿåòñÿ íåñêîëüêî äîëüøå, èñêëþ÷àÿ òîëüêî ëèøü äâîè÷íûå îáúåêòíûå ôàéëû. Ïðè÷èíà ýòîãî îáñóæäàåòñÿ äàëåå.  òåñòîâûé íàáîð áûëè âêëþ÷åíû äâà èñêóññòâåííûõ ôàéëà, ÷òîáû ïîçâîëèòü ÷èòàòåëÿì ïîâòîðÿòü ðåçóëüòàòû. 100000 áàéòíûé "àëôàâèò" ñîñòîèò èç ïîâòîðÿåìîãî 26-áóêâåííîãî àëôàâèòà. "Àññèìåòðè÷íûå ïîêàçàòåëè" ñîäåðæèò 10000 êîïèé ñòðîêè "aaaabaaaac". Ýòè ïðèìåðû ïîêàçûâàþò, ÷òî ôàéëû ìîãóò áûòü ñæàòû ïëîòíåå, ÷åì 1 áèò/ñèìâîë (12092-õ áàéòíûé âûõîä ðàâåí 93736 áèòàì). Âñå ïðèâåäåííûå ðåçóëüòàòû ïîëó÷åíû ñ èñïîëüçîâàíèåì àäàïòèâíîé ìîäåëè èç ïðîãðàììû 2.
Òàáëèöà II. Ðåçóëüòàòû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ 100000 áàéòîâûõ ôàéëîâ.
| VAX-11/780 | Macintosh 512K | Sun 3/75 | |||||
|---|---|---|---|---|---|---|---|
| Âûâîä (áàéòû) |
Êîä. (ìêñ) |
Äåêîä. (ìêñ) |
Êîä. (ìêñ) |
Äåêîä. (ìêñ) |
Êîä. (ìêñ) |
Äåêîä. (ìêñ) |
|
| Ñpåäíåîïòèìèçèpîâàííàÿ ðåàëèçàöèÿ íà Ñè | |||||||
| Òåêñòîâûå ïðîãðàììû Ñè-ïðîãðàììû Îáúåêòíûå ôàéëû VAX Àëôàâèò Àñèììåòðè÷íûå ïîêàçàòåëè |
57718 62991 73501 59292 12092 |
214 230 313 223 143 |
262 288 406 277 170 |
687 729 950 719 507 |
881 950 1334 942 645 |
98 105 145 105 70 |
121 131 190 130 85 |
| Àêêóðàòíî îïòèìèçèðîâàííàÿ ðåàëèçàöèÿ íà Ñè | |||||||
| Òåêñòîâûå ïðîãðàììû Ñè-ïðîãðàììû Îáúåêòíûå ôàéëû VAX Àëôàâèò Àñèììåòðè÷íûå ïîêàçàòåëè |
57718 62991 73501 59292 12092 |
104 109 158 105 63 |
135 151 241 145 81 |
194 208 280 204 126 |
243 266 402 264 160 |
46 51 75 51 28 |
58 65 107 65 36 |
Äàëüíåéøåå ñíèæåíèå â 2 ðàçà âðåìåííûõ çàòðàò ìîæåò áûòü äîñòèãíóòî ïåðåïðîãðàììèðîâàíèåì ïðèâåäåííîé ïðîãðàììû íà ÿçûê àññåìáëåðà. Òùàòåëüíî îïòèìèçèðîâàííàÿ âåðñèÿ ïðîãðàìì 1 è 2 (àäàïòèâíàÿ ìîäåëü) áûëà ðåàëèçîâàíà äëÿ VAX è äëÿ M68000. Ðåãèñòðû èñïîëüçîâàëèñü ïîëíîñòüþ, à code_value áûëî âçÿòî ðàçìåðîì â 16 áèòîâ, ÷òî ïîçâîëèëî óñêîðèòü íåêîòîðûå âàæíûå îïåðàöèè ñðàâíåíèÿ è óïðîñòèòü âû÷èòàíèå Íalf. Õàðàêòåðèñòèêè ýòèõ ïðîãðàìì òàêæå ïðèâåäåíû â Òàáëèöå II, ÷òîáû äàòü ÷èòàòåëÿì ïðåäñòàâëåíèå î òèïè÷íîé ñêîðîñòè âûïîëíåíèÿ.
Âðåìåííûå õàðàêòåðèñòèêè àññåìáëåðíîé ðåàëèçàöèè íà VAX-11/780 äàíû â Òàáëèöå III. Îíè áûëè ïîëó÷åíû ïðè èñïîëüçîâàíèè âîçìîæíîñòè ïðîôèëÿ UNIXà è òî÷íû òîëüêî â ïðåäåëàõ 10%. (Ýòîò ìåõàíèçì ñîçäàåò ãèñòîãðàììó çíà÷åíèé ïðîãðàììíîãî ñ÷åò÷èêà ïðåðûâàíèé ÷àñîâ ðåàëüíîãî âðåìåíè è ñòðàäàåò îò ñòàòèñòè÷åñêîé âàðèàíòíîñòè òàêæå êàê è íåêîòîðûå ñèñòåìíûå îøèáêè). "Âû÷èñëåíèå ãðàíèö" îòíîñèòñÿ ê íà÷àëüíûì ÷àñòÿì encode_symbol() è decode_symbol() (ïðîãðàììà 1 ñòðîêè 90-94 è 190-193), êîòîðûå ñîäåðæàò îïåðàöèè óìíîæåíèÿ è äåëåíèÿ. "Ñäâèã áèòîâ" - ýòî ãëàâíûé öèêë â ïðîöåäóðàõ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ (ñòðîêè 95-113 è 194213). Òðåáóþùåå óìíîæåíèÿ è äåëåíèÿ âû÷èñëåíèå cum â decode_symbol(), à òàêæå ïîñëåäóþùèé öèêë äëÿ îïðåäåëåíèÿ ñëåäóþùåãî ñèìâîëà (ñòðîêè 187-189), åñòü "äåêîäèðîâàíèå ñèìâîëà". À "îáíîâëåíèå ìîäåëè" îòíîñèòñÿ ê àäàïòèâíîé ïðîöåäóðå uðdate_model() èç ïðîãðàììû 2 (ñòðîêè 26-53).
Òàáëèöà III. Âðåìåííûå èíòåðâàëû àññåìáëåðíîé âåðñèè VAX-11/780.
| Âðåìÿ êîäèðîâàíèÿ (ìêñ) |
Âðåìÿ äåêîäèðîâàíèÿ (ìêñ) |
|
|---|---|---|
| Òåêñòîâûå ôàéëû | 104 | 135 |
| Âû÷èñëåíèå ãpàíèö Ñäâèã áèòîâ Îáíîâëåíèå ìîäåëè Äåêîäèpîâàíèå ñèìâîëà Îñòàëüíîå |
32 39 29 - 4 |
31 30 29 45 5 |
| Ñè-ïðîãðàììà | 109 | 151 |
| Âû÷èñëåíèå ãpàíèö Ñäâèã áèòîâ Îáíîâëåíèå ìîäåëè Äåêîäèpîâàíèå ñèìâîëà Îñòàëüíîå |
30 42 33 - 4 |
28 35 36 51 1 |
| Îáúåêòíûé ôàéë VAX | 158 | 241 |
| Âû÷èñëåíèå ãpàíèö Ñäâèã áèòîâ Îáíîâëåíèå ìîäåëè Äåêîäèpîâàíèå ñèìâîëà Îñòàëüíîå |
34 46 75 - 3 |
31 40 75 94 1 |
Êàê è ïðåäïîëàãàëîñü, âû÷èñëåíèå ãðàíèö è îáíîâëåíèå ìîäåëè òðåáóþò îäèíàêîâîãî êîëè÷åñòâà âðåìåíè è äëÿ êîäèðîâàíèÿ è äëÿ äåêîäèðîâàíèÿ â ïðåäåëàõ îøèáêè ýêñïåðèìåíòà. Ñäâèã áèòîâ îñóùåñòâëÿåòñÿ áûñòðåå äëÿ òåêñòîâûõ ôàéëîâ, ÷åì äëÿ Ñè-ïðîãðàìì è îáúåêòíûõ ôàéëîâ èç-çà ëó÷øåãî åãî ñæàòèÿ. Äîïîëíèòåëüíîå âðåìÿ äëÿ äåêîäèðîâàíèÿ ïî ñðàâíåíèþ ñ êîäèðîâàíèåì âîçíèêàåò èç-çà øàãà "äåêîäèðîâàíèå ñèìâîëà" - öèêëà â ñòðîêå 189, âûïîëíÿåìîãî ÷àùå (â ñðåäíåì 9 ðàç, 13 ðàç è 35 ðàç ñîîòâåòñòâåííî). Ýòî òàêæå âëèÿåò íà âðåìÿ îáíîâëåíèÿ ìîäåëè, ò.ê. ñâÿçàíî ñ êîëè÷åñòâîì íàêàïëèâàþùèõ ñ÷åò÷èêîâ, çíà÷åíèÿ êîòîðûõ íåîáõîäèìî óâåëè÷èâàòü â ñòðîêàõ 49-52 ïðîãðàììû 2.  õóäøåì ñëó÷àå, êîãäà ñèìâîëû ðàñïðåäåëåíû îäèíàêîâî, ýòè öèêëû âûïîëíÿþòñÿ â ñðåäíåì 128 ðàç.
Òàêîå ïîëîæåíèå ìîæíî óëó÷øèòü ïðèìåíÿÿ â êà÷åñòâå ÑÄ äëÿ ÷àñòîò äåðåâî áîëåå ñëîæíîé îðãàíèçàöèè, íî ýòî çàìåäëèò îïåðàöèè ñ òåêñòîâûìè ôàéëàìè.
Àäàïòèâíîå ñæàòèå òåêñòîâ
Ðåçóëüòàòû ñæàòèÿ, äîñòèãíóòûå ïðîãðàììàìè 1 è 2 âàðüèðóþòñÿ îò 4.8-5.3 áèòîâ/ñèìâîë äëÿ êîðîòêèõ àíãëèéñêèõ òåêñòîâ (10^3-10^4 áàéòîâ) äî 4.5-4.7 áèòîâ/ñèìâîë äëÿ äëèííûõ (10^5-10^6 áàéòîâ). Õîòÿ ñóùåñòâóþò è àäàïòèâíûå òåõíèêè Õàôôìàíà, îíè âñå æå èñïûòûâàþò íåäîñòàòîê êîíöåïòóàëüíîé ïðîñòîòû, ñâîéñòâåííîé àðèôìåòè÷åñêîìó êîäèðîâàíèþ.
Ïðè ñðàâíåíèè îíè îêàçûâàþòñÿ áîëåå ìåäëåííûìè. Íàïðèìåð, Òàáëèöà IV ïðèâîäèò õàðàêòåðèñòèêè ñðåäíåîïòèìèçèðîâàííîé ðåàëèçàöèè àðèôìåòè÷åñêîãî êîäèðîâàíèÿ íà Ñè ñ òîé èç ïðîãðàìì comðact UNIXa, ÷òî ðåàëèçóåò àäàïòèâíîå êîäèðîâàíèå Õàôôìàíà ñ ïðèìåíåíèåì ñõîäíîé ìîäåëè. (Äëÿ äëèííûõ ôàéëîâ, êàê òå, ÷òî èñïîëüçóþòñÿ â Òàáëèöå IV, ìîäåëü comðact ïî ñóùåñòâó òàêàÿ æå, íî äëÿ êîðîòêèõ ôàéëîâ ïî ñðàâíåíèþ ñ ïðèâåäåííîé â ïðîãðàììå 2 îíà ëó÷øå). Íåáðåæíàÿ ïðîâåðêà comðact ïîêàçûâàåò, ÷òî âíèìàíèå ê îïòèìèçàöèè äëÿ îáîèõ ñèñòåì ñðàâíèìî ïðè òîì, ÷òî àðèôìåòè÷åñêîå êîäèðîâàíèå âûïîëíÿåòñÿ â 2 ðàçà áûñòðåå. Ïîêàçàòåëè ñæàòèÿ â íåêîòîðîé ñòåïåíè ëó÷øå ó àðèôìåòè÷åñêîãî êîäèðîâàíèÿ äëÿ âñåõ òåñòîâûõ ôàéëîâ. Ðàçëè÷èå áóäåò çàìåòíûì â ñëó÷àå ïðèìåíåíèÿ áîëåå ñëîæíûõ ìîäåëåé, ïðåäñêàçûâàþùèõ ñèìâîëû ñ âåðîÿòíîñòÿìè, çàâèñÿùèìè îò îïðåäåëåííûõ îáñòîÿòåëüñòâ (íàïðèìåð, ñëåäîâàíèÿ çà áóêâîé q áóêâû u).
Òàáëèöà IV. Ñðàâíåíèå àäàïòèâíûõ êîäèðîâàíèé Õàôôìàíà è àðèôìåòè÷åñêîãî.
| Àðèôìåòè÷åñêîå êîäèðîâàíèå |
Êîäèðîâàíèå Õàôôìàíà |
|||||
|---|---|---|---|---|---|---|
| Âûâîä (áàéòû) |
Êîä. (ìêñ) |
Äåêîä. (ìêñ) |
Âûâîä (áàéòû) |
Êîä. (ìêñ) |
Äåêîä. (ìêñ) |
|
| Òåêñòîâûå ïðîãðàììû Ñè-ïðîãðàììû Îáúåêòíûå ôàéëû VAX Àëôàâèò Àñèììåòðè÷íûå ïîêàçàòåëè |
57718 62991 73501 59292 12092 |
214 230 313 223 143 |
262 288 406 277 170 |
57718 62991 73501 59292 12092 |
550 596 822 598 215 |
414 441 606 411 132 |
Íåàäàïòèðîâàííîå êîäèðîâàíèå
Îíî ìîæåò áûòü âûïîëíåíî àðèôìåòè÷åñêèì ìåòîäîâ ñ ïîìîùüþ ïîñòîÿííîé ìîäåëè, ïîäîáíîé ïðèâåäåííîé â Ïðîãðàììå 2. Ïðè ýòîì ñæàòèå áóäåò ëó÷øå, ÷åì ïðè êîäèðîâàíèè Õàôôìàíà.  ïîðÿäêå ìèíèìèçàöèè âðåìåíè âûïîëíåíèÿ, ñóììà ÷àñòîò cum_freq[0] áóäåò âûáèðàòüñÿ ðàâíîé ñòåïåíè äâîéêè, ÷òîáû îïåðàöèè äåëåíèÿ ïðè âû÷èñëåíèè ãðàíèö (ïðîãðàììà 1, ñòðîêè 91-94 è 190-193) âûïîëíÿëèñü ÷åðåç ñäâèãè. Äëÿ ðåàëèçàöèè íà àññåìáëåðå VAX-11/780 âðåìÿ êîäèðîâàíèÿ/äåêîäèðîâàíèÿ ñîñòàâèëî 60-90 ìêñ. Àêêóðàòíî íàïèñàííàÿ ðåàëèçàöèÿ êîäèðîâàíèÿ Õàôôìàíà ñ èñïîëüçîâàíèåì òàáëèö ïðîñìîòðà äëÿ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ áóäåò âûïîëíÿòñÿ íåìíîãî áûñòðåå.
Êîäèðîâàíèå ÷åðíî-áåëûõ èçîáðàæåíèé
Ïðèìåíåíèå äëÿ ýòèõ öåëåé
àðèôìåòè÷åñêîãî êîäèðîâàíèÿ áûëî
ðàññìîòðåíî Ëàíãäîíîì è Ðèññàíåíîì,
ïîëó÷èâøèì ïðè ýòîì áëåñòÿùèå ðåçóëüòàòû ñ
ïîìîùüþ ìîäåëè, èñïîëüçóþùåé îöåíêó
âåðîÿòíîñòè öâåòà òî÷êè îòíîñèòåëüíî
îêðóæàþùåãî åå íåêîòîðîãî øàáëîíà. Îí
ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü èç 10 òî÷åê,
ëåæàùèõ ñâåðõó è ñïåðåäè îò òåêóùåé,
ïîýòîìó ïðè ñêàíèðîâàíèè ðàñòðà îíè åé
ïðåäøåñòâóþò. Ýòî ñîçäàåò 1024 âîçìîæíûõ
êîíòåêñòà, îòíîñèòåëüíî êîòîðûõ
âåðîÿòíîñòü ÷åðíîãî öâåòà ó äàííîé òî÷êè
îöåíèâàåòñÿ àäàïòèâíî ïî ìåðå ïðîñìîòðà
èçîáðàæåíèÿ. Ïîñëå ÷åãî êàæäàÿ ïîëÿðíîñòü
òî÷êè êîäèðîâàëàñü àðèôìåòè÷åñêèì ìåòîäîì
â ñîîòâåòñòâèè ñ ýòîé âåðîÿòíîñòüþ. Òàêîé
ïîäõîä óëó÷øèë ñæàòèå íà 20-30% ïî ñðàâíåíèþ ñ
áîëåå ðàííèìè ìåòîäàìè. Äëÿ óâåëè÷åíèÿ
ñêîðîñòè êîäèðîâàíèÿ Ëàíãäîí è Ðèññàíåí
ïðèìåíèëè ïðèáëèçèòåëüíûé ìåòîä
àðèôìåòè÷åñêîãî êîäèðîâàíèÿ, êîòîðûé
èçáåæàë îïåðàöèé óìíîæåíèÿ ïóòåì
ïðåäñòàâëåíèÿ âåðîÿòíîñòåé â âèäå öåëûõ
ñòåïåíåé äðîáè 1/2.
Êîäèðîâàíèå Õàôôìàíà äëÿ
ýòîãî ñëó÷àÿ íå ìîæåò áûòü èñïîëüçîâàíî
ïðÿìî, ïîñêîëüêó îíî íèêîãäà íå âûïîëíÿåò
ñæàòèÿ äâóõñèìâîëüíîãî àëôàâèòà.
Äðóãóþ âîçìîæíîñòü äëÿ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ ïðåäñòàâëÿåò ïðèìåíÿåìûé ê òàêîìó àëôàâèòó ïîïóëÿðíûé ìåòîä êîäèðîâàíèÿ äëèí òèðàæåé (run-length method). Ìîäåëü çäåñü ïðèâîäèò äàííûå ê ïîñëåäîâàòåëüíîñòè äëèí ñåðèé îäèíàêîâûõ ñèìâîëîâ (íàïðèìåð, èçîáðàæåíèå ïðåäñòàâëÿþòñÿ äëèíàìè ïîñëåäîâàòåëüíîñòåé ÷åðíûõ òî÷åê, èäóùèõ çà áåëûìè, ñëåäóþùèõ çà ÷åðíûìè, êîòîðûì ïðåäøåñòâóþò áåëûå è ò.ä.).  èòîãå äîëæíà áûòü ïåðåäàíà ïîñëåäîâàòåëüíîñòü äëèí. Ñòàíäàðò ôàêñèìèëüíûõ àïïàðàòîâ CCITT ñòðîèò êîä Õàôôìàíà íà îñíîâå ÷àñòîò, ñ êîòîðûìè ÷åðíûå è áåëûå ïîñëåäîâàòåëüíîñòè ðàçíûõ äëèí ïîÿâëÿþòñÿ â îáðàçöàõ äîêóìåíòîâ. Ôèêñèðîâàííîå àðèôìåòè÷åñêîå êîäèðîâàíèå, êîòîðîå áóäåò èñïîëüçîâàòü òå æå ÷àñòîòû, áóäåò èìåòü ëó÷øèå õàðàêòåðèñòèêè, à àäàïòàöèÿ òàêèõ ÷àñòîò äëÿ êàæäîãî îòäåëüíîãî äîêóìåíòà áóäåò ðàáîòàòü åùå ëó÷øå.
Êîäèðîâàíèå ïðîèçâîëüíî ðàñïðåäåëåííûõ öåëûõ ÷èñåë.
Îíî ÷àñòî ðàññìàòðèâàåòñÿ íà îñíîâå ïðèìåíåíèÿ áîëåå ñëîæíûõ ìîäåëåé òåêñòîâ, èçîáðàæåíèé èëè äðóãèõ äàííûõ. Ðàññìîòðèì, íàïðèìåð, ëîêàëüíî àäàïòèâíóþ ñõåìó ñæàòèÿ Áåíòëè et al, ãäå êîäèðîâàíèå è äåêîäèðîâàíèå ðàáîòàåò ñ N ïîñëåäíèìè ðàçíûìè ñëîâàìè. Ñëîâî, íàõîäÿùååñÿ â êýø-áóôåðå, îïðåäåëÿåòñÿ ïî öåëî÷èñëåííîìó èíäåêñó áóôåðà. Ñëîâî, êîòîðîå â íåì íå íàõîäèòñÿ, ïåðåäàþòñÿ â êýø-áóôåð ÷åðåç ïîñûëêó åãî ìàðêåðà, êîòîðûé ñëåäóåò çà ñàìèìè ñèìâîëàìè ýòîãî ñëîâà. Ýòî áëåñòÿùàÿ ìîäåëü äëÿ òåêñòà, â êîòîðîì ñëîâà ÷àñòî èñïîëüçóþòñÿ â òå÷åíèè íåêîòîðîãî êîðîòêîãî âðåìåíè, à çàòåì óæå äîëãî íå èñïîëüçóþòñÿ. Èõ ñòàòüÿ îáñóæäàåò íåñêîëüêî êîäèðîâàíèé ïåðåìåííîé äëèíû óæå äëÿ öåëî÷èñëåííûõ èíäåêñîâ êýø-áóôåðà.
 êà÷åñòâå îñíîâû äëÿ êîäîâ ïåðåìåííîé äëèíû àðèôìåòè÷åñêèé ìåòîä ïîçâîëÿåò èñïîëüçîâàòü ëþáîå ðàñïðåäåëåíèå âåðîÿòíîñòåé, âêëþ÷àÿ ñðåäè ìíîæåñòâà äðóãèõ è ïðèâåäåííûå çäåñü. Êðîìå òîãî, îí äîïóñêàåò äëÿ èíäåêñîâ êýø-áóôåðà ïðèìåíåíèå àäàïòèâíîé ìîäåëè, ÷òî æåëàòåëüíî â ñëó÷àå, êîãäà ðàñïðåäåëåíèå äîñòóïîâ ê êýø-áóôåðó òðóäíî ïðåäñêàçóåìî. Åùå, ïðè àðèôìåòè÷åñêîì êîäèðîâàíèè ......, ïðåäíàçíà÷åííûå äëÿ ýòèõ èíäåêñîâ, ìîãóò ïðîïîðöèîíàëüíî óìåíüøàòüñÿ, ÷òîáû ïðèñïîñîáèòü äëÿ ìàðêåðà íîâîãî ñëîâà ëþáóþ æåëàåìóþ âåðîÿòíîñòü.
Ïðèëîæåíèå. Äîêàçàòåëüñòâî äåêîäèðóþùåãî íåðàâåíñòâà.
Ïîëàãàåì:
| (value-low+1)*cum_freq[0]-1 |
cum_freq[symbol] <= | --------------------------- | < cum_freq[symbol-1].
|_ high-low+1 _|
Äpóãèìè ñëîâàìè:
(value-low+1)*cum_freq[0]-1
cum_freq[symbol] <= --------------------------- + e < < cum_freq[symbol-1] (1),
range
range - 1
ãäå range = high - low + 1, 0 <= e <= ----------.
range
(Ïîñëåäíåå íåðàâåíñòâî âûðàæåíèÿ (1) ïðîèñõîäèò èç ôàêòà, ÷òî cum_freq[symbol-1] äîëæíî áûòü öåëûì ). Çàòåì ìû õîòèì ïîêàçàòü, ÷òî low' <= value <= high', ãäå low' è high' åñòü îáíîâëåííûå çíà÷åíèÿ äëÿ low è high êàê îïðåäåëåíî íèæå.
| range*cum_freq[symbol] | range |- (value-low+1)*cum_freq[0]-1 -|
(a) low' · low + | ---------------------- | <= low + ----------- | --------------------------- - e |
|_ cum_freq[0] _| cum_freq[0] |_ range _|
1
Èç âûpàæåíèÿ (1) èìååì: <= value + 1 - ----------- ,
cum_freq[0]
Ïîýòîìó low' <= value, ò.ê. è value, è low', è cum_freq[0] > 0.
| range*cum_freq[symbol-1] | range |- (value-low+1)*cum_freq[0]-1 -|
(a) high' · low + | ------------------------ | - 1 >= low + ----------- | --------------------------- + 1 - e| - 1
|_ cum_freq[0] _| cum_freq[0] |_ range _|
range |- 1 range-1 -|
Èç âûpàæåíèÿ (1) èìååì: >= value + ----------- |- ----- + 1 - ------- | = value.
cum_freq[0] |_ range range _|
Ñàéò î ñæàòèè
>>
ARCTEST
>>
Ñðàâíèòåëüíûå òåñòû
|
Àëüòåðíàòèâíûå òåñòû
|
Ãðàôè÷åñêèå òåñòû
|
Íîâîñòè
|
Óòèëèòû
|
Ôàéë'ìåíåäæåðû
|
Îïèñàíèÿ
|
Ëèíêè
|
Necromancer's DN
|
Ïîääåðæêà
|
|
Ñàéò î ñæàòèè >>
Íîâèíêè | Î ñåðâåðå | Ñòàòèñòèêà
Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ" >>
Óíèâåðñàëüíûå | Èçîáðàæåíèé | Âèäåî
Ðàçäåëû >> Download (ñòàòüè+èñõîäíèêè) | Ññûëêè | Ru.compress | Arctest | Âèäåî | Êàòàëîã ññûëîê | Ôîðóì
Ïðîåêòû >> Ä.Âàòîëèíà | À.Ðàòóøíÿêà | Ì.Ñìèðíîâà | Â.Þêèíà | Å.Øåëâèíà | À.Ôèëèíñêîãî | Ä.Øêàðèíà | Ñ.Îñíà÷à
