Êîäèðîâàíèå Øåííîíà-Ôàíî


Òåêñò âçÿò ñî ñòðàíèöû http://aforge.ibd.lv/?8
 
   Êîäèðîâàíèå Øåííîíà-Ôàíî ÿâëÿåòñÿ îäíèì èç ñàìûõ ïåðâûõ àëãîðèòìîâ ñæàòèÿ, êîòîðûé âïåðâûå ñôîðìóëèðîâàëè àìåðèêàíñêèå ó÷¸íûå Øåííîí (Shannon) è Ôàíî (Fano). Äàííûé ìåòîä ñæàòèÿ èìååò áîëüøîå ñõîäñòâî ñ êîäèðîâàíèåì Õàôôìàíà, êîòîðîå ïîÿâèëîñü íà íåñêîëüêî ëåò ïîçæå. Ãëàâíàÿ èäåÿ ýòîãî ìåòîäà - çàìåíèòü ÷àñòî âñòðå÷àþùèåñÿ ñèìâîëû áîëåå êîðîòêèìè êîäàìè, à ðåäêî âñòðå÷àþùèåñÿ ïîñëåäîâàòåëüíîñòè áîëåå äëèííûìè êîäàìè. Òàêèì îáðàçîì, àëãîðèòì îñíîâûâàåòñÿ íà êîäàõ ïåðåìåííîé äëèíû. Äëÿ òîãî, ÷îáû äåêîìïðåññîð âïîñëåäñòâèè ñìîã ðàñêîäèðîâàòü ñæàòóþ ïîñëåäîâàòåëüíîñòü, êîäû Øåííîíà-Ôàíî äîëæíû îáëàäàòü óíèêàëüíîñòüþ, òî åñòü, íå ñìîòðÿ íà èõ ïåðåìåííóþ äëèíó, êàæäûé êîä óíèêàëüíî îïðåäåëÿåò îäèí çàêîäèðîâàíûé ñèìâîë è íå ÿâëÿåòñÿ ïðåôèêñîì ëþáîãî äðóãîãî êîäà.
   Ðàññìîòðèì àëãîðèòì âû÷èñëåíèÿ êîäîâ Øåííîíà-Ôàíî (äëÿ íàãëÿäíîñòè âîçüì¸ì â êà÷åñòâå ïðèìåðà ïîñëåäîâàòåëüíîñòü 'aa bbb cccc ddddd'). Äëÿ âû÷èñëåíèÿ êîäîâ, íåîáõîäèìî ñîçäàòü òàáëèöó óíèêàëüíûõ ñèìâîëîâ ñîîáùåíèÿ c(i) è èõ âåðîÿòíîñòåé p(c(i)), è îòñîðòèðîâàòü å¸ â ïîðÿäêå íåâîçðàñòàíèÿ âåðîÿòíîñòè ñèìâîëîâ.

c(i) p(c(i))
d 5 / 17
c 4 / 17
space 3 / 17
b 3 / 17
a 2 / 17

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

ñèìâîë êîä
d 00
c 01
space 10
b 110
a 111

   Äëèíà êîäà s(i) â ïîëó÷åííîé òàáëèöå ðàâíà int(-lg p(c(i))), åñëè ñèâîëû óäàëîñòü ðàçäåëèòü íà ãðóïïû ñ îäèíàêîâîé ÷àñòîòîé, â ïðîòèâíîì ñëó÷àå, äëèíà êîäà ðàâíà int(-lg p(c(i))) + 1.

int(-lg p(c(i))) <= s(i) <= int(-lg p(c(i))) + 1

   Óñïîëüçóÿ ïîëó÷åííóþ òàáëèöó êîäîâ, êîäèðóåì âõîäíîé ïîòîê - çàìåíÿåì êàæäûé ñèìâîë ñîîòâåòñòâóþùèì êîäîì. Åñòåñòâåííî äëÿ ðàñæàòèÿ ïîëó÷åííîé ïîñëåäîâàòåëüíîñòè, äàííóþ òàáëèöó íåîáõîäèìî ñîõðàíÿòü âìåñòå ñî ñæàòûì ïîòîêîì, ÷òî ÿâëÿåòñÿ îäíèì èç íåäîñòàòêîâ äàííîãî ìåòîäà.  ñæàòîì âèäå, íàøà ïîñëåäîâàòåëüíîñòü ïðèíèìàåò âèä:

111111101101101101001010101100000000000

äëèíîé â 39 áèò. Ó÷èòûâàÿ, ÷òî îðãèíàë èìåë äëèíó ðàâíóþ 136 áèò, ïîëó÷àåì êîýôôèöèåíò ñæàòèÿ ~28% - íå òàê óæ è ïëîõî.
   Ãëÿäÿ íà ïîëó÷åííóþ ïîñëåäîâàòåëüíîñòü, âîçíèêàåò âîïðîñ: "À êàê æå òåïåðü ýòî ðàñæàòü ?". Ìû íå ìîæåì, êàê â ñëó÷àå êîäèðîâàíèÿ, çàìåíÿòü êàæäûå 8 áèò âõîäíîãî ïîòîêà, êîäîì ïåðåìåííîé äëèíû. Ïðè ðàñæàòèè íàì íåîáõîäèìî âñ¸ ñäåëàòü íàîáîðîò - çàìåíèòü êîä ïåðåìåííîé äëèíû ñèìâîëîì äëèíîé 8 áèò.  äàííîì ñëó÷àå, ëó÷øå âñåãî áóäåò èñïîëüçîâàòü áèíàðíîå äåðåâî, ëèñòüÿìè êîòîðîãî áóäóò ÿâëÿòñÿ ñèìâîëû (àíàëîã äåðåâà Õàôôìàíà).
   Êîäèðîâàíèå Øåííîíà-Ôàíî ÿâëÿåòñÿ äîñòàòî÷íî ñòàðûì ìåòîäîì ñæàòèÿ , è íà ñåãîäíÿøíèé äåíü îíî íå ïðåäñòàâëÿåò îñîáîãî ïðàêòè÷åñêîãî èíòåðåñà (ðàçâå ÷òî êàê óïðàæíåíèå ïî êóðñó ñòðóêòóð äàííûõ).  áîëüøèíñòâå ñëó÷àåâ, äëèíà ñæàòîé ïîñëåäîâàòåëüíîñòè, ïî äàííîìó ìåòîäó, ðàâíà äëèíå ñæàòîé ïîñëåäîâàòåëüíîñòè ñ èñïîëüçîâàíèåì êîäèðîâàíèÿ Õàôôìàíà. Íî íà íåêîòîðûõ ïîñëåäîâàòåëüíîñòÿõ âñ¸ æå ôîðìèðóþòñÿ íå îïòèìàëüíûå êîäû Øåííîíà-Ôàíî, ïîýòîìó ñæàòèå ìåòîäîì Õàôôìàíà ïðèíÿòî ñ÷èòàòü áîëåå ýôôåêòèâíûì. Äëÿ ïðèìåðà, ðàññìîòðèì ïîñëåäîâàòåëüíîñòü ñ òàêèì ñîäåðæàíèåì ñèìâîëîâ: 'a' - 14, 'b' - 7, 'c' - 5, 'd' - 5, 'e' - 4. Ìåòîä Õàôôìàíà ñæèìàåò å¸ äî 77 áèò, à âîò Øåííîíà-Ôàíî äî 79 áèò.

ñèìâîë êîä Õàôôìàíà êîä Øåííîíà-Ôàíî
a 0 00
b 111 01
c 101 10
d 110 110
e 100 111
   Êñòàòè, â îäíîì èñòî÷íèêå (íå áóäó óêàçûâàòü êàêîì), ýòó ïîñëåäîâàòåëüíîñòü ñæàëè ìåòîäîì Øåííîíà-Ôàíî äî 84 áèò, à ìåòîäîì Õàôôìàíà äî òåõ æå 77. Òàêèå îòëè÷àè â ñòåïåíè ñæàòèÿ âîçíèêàþò èç-çà íåñòðîãîãî îïðåäåëåíèÿ ñïîñîáà äåëåíèÿ ñèìâîëîâ íà ãðóïïû.
   Êàê æå ìû äåëèëè íà ãðóïïû ? Äîñòàòî÷íî ïðîñòî:

  1. âåðîÿòíîòü ïåðâîé ãðóïïû (p1) è âòîðîé (p2) ðàâíà íóëþ;
  2. p1 <= p2 ?
    • äà: äîáàâèòü â ïåðâóþ ãðóïïó ñèìâîë ñ íà÷àëà òàáëèöû;
    • íåò: äîáàâèòü âî âòîðóþ ãðóïïó ñèìâîë ñ êîíöà òàáëèöû;
  3. åñëè âñå ñèìâîëû ðàçäåëåíû íà ãðóïïû, òî çàâåðøèòü àëãîðèòì, èíà÷å ïåðåéòè ê øàãó 2.

   Èç-çà òàêîé íåîïðåäåë¸ííîñòè ó íåêîòîðûõ ëþäåé âîçíèêàþò äàæå òàêèå ìûñëè: "... ïðîãðàììà èíîãäà íàçíà÷àåò íåêîòîðûì ñèìâîëàì ..." è òàê äàëåå - ðàññóæäåíèÿ î äëèíå êîäîâ. Åñëè âû íå ïèøåòå AI, òî òàêîå ïîíÿòèå, êàê "ïðîãðàììà èíîãäà" ÷òî-òî äåëàåò, çâó÷èò ñìåøíî. Ïðàâèëüíî ðåàëèçîâàííûé àëãîðèòì - ðàáîòàåò ñòðîãî îïåðåäåë¸ííî.


    Ïðèìåð ðåàëèçàöèè
 
[06.07.02]