2. Àëãîðèòì PPM
    Äëÿ êàæäîé êîíòåêñòíîé ìîäåëè (èëè, ÷òî êîðî÷å, êîíòåêñòà) çàâîäèì ñ÷åò÷èêè ñèìâîëîâ. Åñëè êàêîé-òî ñèìâîë ïîÿâëÿåòñÿ â äàííîì êîíòåêñòå, òî çíà÷åíèå ñîîòâåòñòâóþùåãî ñ÷åò÷èêà ýòîãî êîíòåêñòà óâåëè÷èâàåòñÿ.
    Ê àëôàâèòó ñæèìàåìîé ïîñëåäîâàòåëüíîñòè äîáàâëÿåòñÿ îäèí ñïåöèàëüíûé ñèìâîë - òàê íàçûâàåìûé êîä óõîäà 'esc'. Âåðîÿòíîñòü óõîäà - ýòî âåðîÿòíîñòü, êîòîðóþ èìåþò åùå íå ïîÿâëÿâøèåñÿ â êîíòåêñòå ñèìâîëû. Ëþáàÿ êîíòåêñòíàÿ ìîäåëü äîëæíà äàâàòü îòëè÷íóþ îò íóëÿ îöåíêó âåðîÿòíîñòè óõîäà. Èñêëþ÷åíèå èç ýòîãî ïðàâèëà ìîãóò ñîñòàâëÿòü òîëüêî òå ñëó÷àè, êîãäà çàðàíåå èçâåñòíî, ÷òî ëþáîé ñèìâîë àëôàâèòà ìîæåò áûòü îöåíåí â ðàññìàòðèâàåìîì êîíòåêñòå. Îöåíêà âåðîÿòíîñòè óõîäà - ýòî îñíîâíàÿ ïðîáëåìà PPM, êîòîðàÿ áóäåò ðàññìîòðåíà íèæå â ïóíêòå 4.
    Åñëè ñèìâîë S êîäèðóåòñÿ PPM-ìîäåëüþ ñ ìàêñèìàëüíûì ïîðÿäêîì M, òî â ïåðâóþ î÷åðåäü ðàññìàòðèâàåòñÿ êîíòåêñòíàÿ ìîäåëü ñòåïåíè M. Åñëè îíà îöåíèâàåò âåðîÿòíîñòü S ÷èñëîì, íå ðàâíûì íóëþ, òî ñàìà è èñïîëüçóåòñÿ äëÿ êîäèðîâàíèÿ S. Èíà÷å âûäàåòñÿ êîä óõîäà, è íà îñíîâå ñëåäóþùåãî ìåíüøåãî ïî äëèíå êîíòåêñòà ïðîèçâîäèòñÿ î÷åðåäíàÿ ïîïûòêà îöåíèòü âåðîÿòíîñòü S. Êîäèðîâàíèå ïðîèñõîäèò ÷åðåç óõîä ê ìåíüøèì êîíòåêñòàì äî òåõ ïîð, ïîêà S íå áóäåò îöåíåí. Êîíòåêñò -1 ñòåïåíè ãàðàíòèðóåò, ÷òî ýòî â êîíöå êîíöîâ ïðîèçîéäåò. Òàêèì îáðàçîì êàæäûé ñèìâîë êîäèðóåòñÿ ñåðèåé ñèìâîëîâ óõîäà, çà êîòîðûìè ñëåäóåò êîä ñàìîãî ñèìâîëà. Èç ýòîãî ñëåäóåò, ÷òî âåðîÿòíîñòü óõîäà òàêæå ìîæíî ðàññìàòðèâàòü êàê âåðîÿòíîñòü ïåðåõîäà ê ìîäåëè ìåíüøåãî ïîðÿäêà.
    Ïðè îöåíêå âåðîÿòíîñòè ñèìâîëà â ìîäåëè ïîðÿäêà m ìû ìîæåì èñêëþ÷èòü èç ðàññìîòðåíèÿ âñå ñèìâîëû, êîòîðûå óæå âñòðå÷àëèñü â êîíòåêñòàõ áîëåå âûñîêèõ ïîðÿäêîâ (M...m+1), ïîñêîëüêó îíè óæå íå ìîãóò êîäèðîâàòüñÿ ìîäåëüþ áîëåå íèçêîãî ïîðÿäêà, òàê êàê ñèìâîë S òî÷íî íå îäèí èç íèõ. Äëÿ ýòîãî âî âñåõ ìîäåëÿõ ìåíüøèõ ïîðÿäêîâ íóæíî çàìàñêèðîâàòü çíà÷åíèÿ ñ÷åò÷èêîâ ñèìâîëîâ, âåðîÿòíîñòü êîòîðûõ ìîãëà áûòü óæå îöåíåíà ìîäåëüþ áîëåå âûñîêîãî ïîðÿäêà. Òàêàÿ òåõíèêà íàçûâàåòñÿ ìåòîäîì èñêëþ÷åíèÿ (exclusions).

Ïðèìåð 2.
    Èìååì ïîñëåäîâàòåëüíîñòü ñèìâîëîâ "bcbcabcbcabccbc" àëôàâèòà { a, b, c, d }, êîòîðàÿ óæå áûëà çàêîäèðîâàíà. Áóäåì ñ÷èòàòü, ÷òî ñ÷åò÷èê âåðîÿòíîñòè óõîäà ðàâåí 1 äëÿ âñåõ ìîäåëåé, ñ÷åò÷èêè ñèìâîëîâ óâåëè÷èâàþòñÿ íà 1, ïðèìåíÿåòñÿ ìåòîä èñêëþ÷åíèé, è ìàêñèìàëüíûé êîíòåêñò èìååò äëèíó 4 (M=4). Ðàññìîòðèì êîäèðîâàíèå òåêóùåãî ñèìâîëà 'd'. Ñíà÷àëà ðàññìàòðèâàåòñÿ êîíòåêñò 4-ãî ïîðÿäêà , íî ïîñêîëüêó ðàíåå îí åùå íå âñòðå÷àëñÿ, òî ìû, íè÷åãî íå ïîñëàâ íà âûõîä, ïåðåõîäèì ê êîíòåêñòó O-3. Åäèíñòâåííûì ðàíåå âñòðå÷àâøèìñÿ â ýòîì êîíòåêñòå () ñèìâîëîì ÿâëÿåòñÿ 'a', ñ÷åò÷èê êîòîðîãî ðàâåí 2, ïîýòîìó óõîä êîäèðóåòñÿ ñ âåðîÿòíîñòüþ 1/(2+1) (2 - êîëè÷åñòâî èñïîëüçîâàíèé êîíòåêñòà, 1 - ó÷èòûâàåì ñèìâîë óõîäà).  ìîäåëè 2-ãî ïîðÿäêà çà ñëåäóþò 'a', êîòîðûé èñêëþ÷àåòñÿ, äâàæäû 'b', è îäèí ðàç 'c', ïîýòîìó âåðîÿòíîñòü óõîäà áóäåò 1/(3+1).  ìîäåëÿõ O-1 è O-0 ìîæíî îöåíèòü 'a', 'b' è 'c', íî êàæäûé èç íèõ èñêëþ÷àåòñÿ, ïîñêîëüêó óæå âñòðå÷àëñÿ â êîíòåêñòå áîëåå âûñîêîãî ïîðÿäêà, ïîýòîìó çäåñü âåðîÿòíîñòÿì óõîäà äàþòñÿ çíà÷åíèÿ ðàâíûå 1. Ñèñòåìà çàâåðøàåò ðàáîòó ñ âåðîÿòíîñòÿìè óõîäîâ â ìîäåëè ïîðÿäêà -1, ãäå 'd' îñòàåòñÿ åäèíñòâåííûì íåîöåíåííûì ñèìâîëîì, ïîýòîìó îí êîäèðóåòñÿ ñ âåðîÿòíîñòüþ 1 ïîñðåäñòâîì 0 áèòîâ.  ðåçóëüòàòå ïîëó÷èì, ÷òî äëÿ êîäèðîâàíèÿ 'd' èñïîëüçóåòñÿ 3.6 áèòîâ. Òàáë.2 äåìîíñòðèðóåò êîäû, êîòîðûå äîëæíû áûëè áûòü èñïîëüçîâàíû äëÿ ëþáîãî òåêóùåãî ñèìâîëà èç âñåõ âîçìîæíûõ.  /* êîíåö ïðèìåðà */

Òàáëèöà 2. Ìåõàíèçì êîäèðîâàíèÿ ñ èñêëþ÷åíèÿìè 4-õ ñèìâîëîâ àëôàâèòà { a, b, c, d }, êîòîðûå ìîãóò ñëåäîâàòü çà ñòðîêîé "bcbcabcbcabccbc".

Ñèìâîë	Êîäèðîâàíèå
a	a 2/3	( Âñåãî = 2/3 ; 0.58 áèòîâ )
b	"esc" b 1/3 2/4	( Âñåãî = 1/6 ; 2.6 áèòîâ )
c	"esc" c 1/3 1/4	( Âñåãî = 1/12; 3.6 áèòîâ )
d	"esc" "esc" "esc" "esc" 1/3 1/4 1 1	( Âñåãî = 1/12; 3.6 áèòîâ )

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

3. Äîñòîèíñòâà è íåäîñòàòêè PPM
    Âîò óæå â òå÷åíèå äåñÿòèëåòèÿ PPM îñòàåòñÿ íàèáîëåå ìîùíûì ïðàêòè÷åñêèì àëãîðèòìîì ñ òî÷êè çðåíèÿ ñòåïåíè ñæàòèÿ. Ïî-âèäèìîìó, ïîáèòü åãî â ýòîì ñìîãóò òîëüêî áîëåå èçîùðåííûå ìåòîäû êîíòåêñòíîãî ìîäåëèðîâàíèÿ, êîòîðûå íåñîìíåííî áóäóò ïîÿâëÿòüñÿ, òàê êàê ïðîöåññîðû ñòàíîâÿòñÿ âñå áûñòðåå, à äîñòóïíîé ïàìÿòè âñå áîëüøå.
    Àëãîðèòì PPM îáåñïå÷èâàåò íàèáîëåå áûñòðîå ñõîæäåíèå ê îïòèìàëüíîìó êîäó. Äëÿ ïåðâûõ N ñèìâîëîâ ñæèìàåìîé ñòðîêè ñðåäíÿÿ äëèíà êîäà áóäåò ëèøü íà O(lg2(N)/N) áîëüøå ýíòðîïèè èñòî÷íèêà, ïîðîäèâøåãî ñòðîêó. Ïðè ýòîì äîêàçàíî, ÷òî íèêàêîé óíèâåðñàëüíûé àëãîðèòì íå ìîæåò èìåòü áîëüøåé ñêîðîñòè ñõîæäåíèÿ, ÷åì O(lg2(N)/N). Äëÿ ñëîâàðíûõ ñõåì ýòè àñèìïòîòè÷åñêèå îöåíêè èìåþò âèä:
LZ77 -- O( lg2 (lg2(N)) / lg2(N) );
LZ78 -- O(1/lg2(N)).
    Íàèëó÷øèå ðåçóëüòàòû PPM ïîêàçûâàåò íà òåêñòàõ: îòëè÷íûé êîýôôèöèåíò ñæàòèÿ ïðè âûñîêîé ñêîðîñòè, ÷åìó íàãëÿäíûì ïðèìåðîì ÿâëÿåòñÿ [12].
    Íåäîñòàòêè PPM çàêëþ÷àþòñÿ â ñëåäóþùåì: ìåäëåííîå äåêîäèðîâàíèå (îáû÷íî íà 5-10% ìåäëåííåå êîäèðîâàíèÿ); íåñîâìåñòèìîñòü ïðîãðàìì â ñëó÷àå èçìåíåíèÿ àëãîðèòìà êîäèðîâàíèÿ; ÷ðåçâû÷àéíî ìåäëåííàÿ îáðàáîòêà ìàëîèçáûòî÷íûõ äàííûõ (ñêîðîñòü ìîæåò ïàäàòü íà ïîðÿäîê); äëÿ ðàçëè÷íûõ ôàéëîâ îïòèìàëüíûé ìàêñèìàëüíûé ïîðÿäîê ìîäåëè êîëåáëåòñÿ îáû÷íî â ðàéîíå 4..10, ïîýòîìó ïðè âûáîðå ìîäåëè êàêîãî-òî ôèêñèðîâàííîãî ïîðÿäêà ÷àñòü ôàéëîâ áóäåò ñæèìàòüñÿ õóæå, ÷åì ìîãëà áû; ïëîõîå ñæàòèå ôàéëîâ ñ íåñòàáèëüíûìè êîíòåêñòàìè, çäåñü êëàññè÷åñêèé PPM çàìåòíî ïðîèãðûâàåò LZ-ìåòîäàì; áîëüøèå çàïðîñû ïàìÿòè â ñëó÷àå èñïîëüçîâàíèÿ ñëîæíûõ ìîäåëåé âûñîêîãî ïîðÿäêà - äëÿ áåçáåäíîé æèçíè íóæíî íå ìåíåå 15Ìá, à âåäü àëãîðèòì ñèììåòðè÷íûé, äëÿ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ òðåáóþòñÿ ïðàêòè÷åñêè îäèíàêîâûå îáúåìû ïàìÿòè; ïðîâàëû â ñòåïåíè ñæàòèÿ ïî ñðàâíåíèþ ñ LZ íà ôàéëàõ, èìåþùèõ äëèííûå ïîâòîðû áëîêîâ ñèìâîëîâ.
    Íåñìîòðÿ íà òî, ÷òî ïðàêòè÷åñêè âñåãäà ìîæíî ïîäîáðàòü òàêóþ PPM-ìîäåëü, ÷òî îíà áóäåò äàâàòü ëó÷øåå ñæàòèå, ÷åì LZ èëè BWT, ïðèìåíåíèå PPM-êîìïðåññîðîâ ãëàâíûì îáðàçîì öåëåñîîáðàçíî äëÿ ñæàòèÿ òåêñòîâ è òîìó ïîäîáíîé èíôîðìàöèè: äëÿ ìàëîèçáûòî÷íûõ ôàéëîâ âåëèêè âðåìåííûå çàòðàòû, èçáûòî÷íûå ôàéëû ñ äëèííûìè ïîâòîðÿþùèìèñÿ ñòðîêàìè (òåêñòû ïðîãðàìì) ìîæíî ñæèìàòü ñ ïîìîùüþ BWT-êîìïðåññîðîâ è äàæå ñëîâàðíûõ ìåòîäîâ, òàê êàê ñîîòíîøåíèå ñæàòèå-ñêîðîñòü-ïàìÿòü îáû÷íî ëó÷øå. Äëÿ ñèëüíî èçáûòî÷íûõ äàííûõ ëó÷øå âñå-òàêè èñïîëüçîâàòü PPM, òàê êàê LZ77, BWT-ìåòîäû îáû÷íî ðàáîòàþò ïðè ýòîì ñðàâíèòåëüíî ìåäëåííî èç-çà äåãðàäàöèè ñòðóêòóð äàííûõ.

4. Îöåíêà âåðîÿòíîñòè êîäà óõîäà (ÎÂÓ)
    ÎÂÓ ñâÿçàíà ñ òàê íàçûâàåìîé "ïðîáëåìîé íóëåâîé ÷àñòîòû" ("zero frequency problem"), îïèñàííîé â [7].
    Ìîæíî âûäåëèòü äâà ïîäõîäà ê ðåøåíèþ ïðîáëåìû ÎÂÓ: àïðèîðíûå ìåòîäû, îñíîâàííûå íà ïðåäïîëîæåíèÿõ î ïðèðîäå ñæèìàåìûõ äàííûõ, è àäàïòèâíûå ìåòîäû, êîòîðûå ïûòàþòñÿ ïðèñïîñîáèòüñÿ ê ñæèìàåìûì äàííûì.

4.1. Àïðèîðíûå ìåòîäû
    Ââåäåì îáîçíà÷åíèÿ:

C	- îáùåå ÷èñëî ïðîñìîòðîâ êîíòåêñòà;
Q	- êîëè÷åñòâî ðàçíûõ ñèìâîëîâ â êîíòåêñòå;
Qi	- êîëè÷åñòâî òàêèõ ðàçíûõ ñèìâîëîâ, ÷òî îíè âñòðå÷àëèñü â êîíòåêñòå ðîâíî i ðàç;
Escx	- ÎÂÓ ïî ìåòîäó x.

    Èçîáðåòàòåëè àëãîðèòìà PPM Cleary è Witten â ñâîåé îðèãèíàëüíîé ñòàòüå [1] ïðåäëîæèëè äâà ìåòîäà ÎÂÓ: òàê íàçûâàåìûå ìåòîä A è ìåòîä B. ×àñòíûå ñëó÷àè àëãîðèòìà PPM ñ èñïîëüçîâàíèåì ýòèõ ìåòîäîâ íàçûâàþòñÿ, ñîîòâåòñòâåííî, PPMA è PPMB.
    ÎÂÓ ïî ìåòîäó A:

          1
EscA = -------
        C + 1

       Q - Q1
EscB = ------
         C

         Q
EscC = -----
       C + Q

         Q
EscD = -----
        2*C

         Q1    Q2    Q3
EscP  = --- - --- - --- - ...
         C    C^2   C^3
         Q1
EscX  = ---
         C
         Q1
EscXC = ---   ïðè 0 < Q1 < C, èíà÷å ïî ìåòîäó C
         C

  1              1                    1
 --- = e * lg2 (---) + (1-e) * lg2 (-----)
  w              e                  1 - e

        sum (e  w )
              i  i
EscZ =  ----------- ,  i = 0,1,2.
          sum w
               i

5. Îáíîâëåíèå ñ÷åò÷èêîâ ñèìâîëîâ
    Ìîäèôèêàöèÿ ñ÷åò÷èêîâ ïîñëå îáðàáîòêè î÷åðåäíîãî ñèìâîëà ìîæåò áûòü ðåàëèçîâàíà ðàçëè÷íûì îáðàçîì. Ïîñëå êîäèðîâàíèÿ êàæäîãî ñèìâîëà åñòåñòâåííî èçìåíÿòü ñîîòâåòñòâóþùèå ñ÷åò÷èêè âî âñåõ ìîäåëÿõ 0,1,..M. Íî â ñëó÷àå êëàññè÷åñêîãî PPM ëó÷øèå ðåçóëüòàòû äîñòèãàþòñÿ â òîì ñëó÷àå, êîãäà óâåëè÷èâàþòñÿ ñ÷åò÷èêè îöåíåííîãî ñèìâîëà òîëüêî â òåõ êîíòåêñòàõ, â êîòîðûõ îí ðàíåå íå âñòðå÷àëñÿ, è â òîì êîíòåêñòå, ãäå îí áûë îöåíåí. Èíà÷å ãîâîðÿ, ñ÷åò÷èê îöåíåííîãî ñèìâîëà íå óâåëè÷èâàåòñÿ, åñëè îí áûë îöåíåí â êîíòåêñòå áîëåå âûñîêîãî ïîðÿäêà. Ýòà òåõíèêà èìååò ñàìîñòîÿòåëüíîå íàçâàíèå - îáíîâëÿåìîå èñêëþ÷åíèå (update exclusions). Îáû÷íî ïîä èñêëþ÷åíèåì ïîíèìàþò ñàì ìåõàíèçì óõîäîâ ñ èñêëþ÷åíèåì èç îöåíêè ñ÷åò÷èêîâ òåõ ñèìâîëîâ, êîòîðûå âñòðå÷àëèñü â êîíòåêñòàõ áîëüøåãî ïîðÿäêà, â ñî÷åòàíèè ñ èìåííî îáíîâëÿåìûì èñêëþ÷åíèåì. Ïðèìåíåíèå îáíîâëÿåìîãî èñêëþ÷åíèÿ ïîçâîëÿåò óëó÷øèòü ñæàòèå ïðèìåðíî íà 2% ïî ñðàâíåíèþ ñ òåì ñëó÷àåì, êîãäà ïðîèçâîäèòñÿ îáíîâëåíèå ñ÷åò÷èêîâ ñèìâîëà âî âñåõ ìîäåëÿõ. Èñêëþ÷åíèå èç îöåíêè ñèìâîëîâ, âñòðå÷åííûõ óæå â ñòàðøèõ êîíòåêñòàõ, óëó÷øàåò ñæàòèå íà 2-5% äëÿ ìîäåëåé PPM íåáîëüøîãî ïîðÿäêà (3..5). Ïðè óâåëè÷åíèè ïîðÿäêà ýòîò ìåõàíèçì ñòàíîâèòñÿ àáñîëþòíî íåîáõîäèìûì, èíà÷å óñëîæíåíèå ìîäåëè ïðèâåäåò òîëüêî ê óõóäøåíèÿ ñæàòèÿ ïðàêòè÷åñêè âî âñåõ ñëó÷àÿõ.
    Òàêæå âûäåëÿþò òàêóþ òåõíèêó êàê ÷àñòè÷íîå îáíîâëÿåìîå èñêëþ÷åíèå (partial update exclusions), ïðè êîòîðîì ïðîèçâîäèòñÿ óâåëè÷åíèå ñ÷åò÷èêîâ âî âñåõ òàê íàçûâàåìûõ äåòåðìèíèðîâàííûõ êîíòåêñòàõ; åñëè èõ íåò, òî òîëüêî â ñàìîì äëèííîì íåäåòåðìèíèðîâàííîì. Ïîä äåòåðìèíèðîâàííûì ïîíèìàåòñÿ êîíòåêñò, â êîòîðîì äî äàííîãî ðàññìàòðèâàåìîãî ìîìåíòà âñòðå÷àëñÿ òîëüêî îäèí óíèêàëüíûé ñèìâîë (ëþáîå ÷èñëî ðàç). ×àñòè÷íîå îáíîâëÿåìîå èñêëþ÷åíèå ïðèìåíÿåòñÿ â PPM*.
    Ïðè óâåëè÷åíèè çíà÷åíèé ñ÷åò÷èêîâ ìîæåò âîçíèêíóòü ïåðåïîëíåíèå â àðèôìåòè÷åñêîì êîäåðå. Âî èçáåæàíèå ýòîãî îáû÷íî ïðîèçâîäÿò äåëåíèå çíà÷åíèé ïîïîëàì ïðè äîñòèæåíèè îïðåäåëåííîãî ïîðîãà. Ìàêñèìàëüíîå çíà÷åíèå ïîðîãà îïðåäåëÿåòñÿ îñîáåííîñòÿìè êîíêðåòíîãî àðèôìåòè÷åñêîãî êîäåðà. Ñ äðóãîé ñòîðîíû, ìàñøòàáèðîâàíèå ñ÷åò÷èêîâ äàåò ïîáî÷íûé ýôôåêò â âèäå óëó÷øåíèÿ ñæàòèÿ ïðè êîäèðîâàíèè äàííûõ ñ áûñòðî ìåíÿþùèìèñÿ êîíòåêñòàìè. ×åì íåñòàáèëüíåå êîíòåêñò, òåì ÷àùå ñëåäóåò ìàñøòàáèðîâàòü, îòáðàñûâàÿ òàêèì îáðàçîì ÷àñòü èíôîðìàöèè î ïîâåäåíèè êîíòåêñòà â ïðîøëîì.  ñâåòå ýòîãî åñòåñòâåííîé ÿâëÿåòñÿ èäåÿ îá óâåëè÷åíèè ñ÷åò÷èêîâ ñ íåðàâíûì øàãîì, òàê ÷òîáû íåäàâíî âñòðå÷åííûå ñèìâîëû ïîëó÷àëè áîëüøèå âåñà, ÷åì "ñòàðûå" ñèìâîëû.

6. Ìàñøòàáèðîâàíèå ñ÷åò÷èêà ïîñëåäíåãî âñòðå÷åííîãî ñèìâîëà èëè recency scaling
    Åñëè ïîñëåäíèé ðàç â òåêóùåì êîíòåêñòå áûë âñòðå÷åí íåêèé ñèìâîë S, òî âåðîÿòíîñòü òîãî, ÷òî è òåêóùèé ñèìâîë òàêæå S, âûðàñòàåò, ïðè÷åì ÷àñòî çíà÷èòåëüíî. Ýòîò ôàêò ïîçâîëÿåò óëó÷øèòü ïðåäñêàçàíèå çà ñ÷åò óìíîæåíèÿ ñ÷åò÷èêà ïîñëåäíåãî âñòðå÷åííîãî ñèìâîëà íà íåêèé êîýôôèöèåíò.  áîëüøèíñòâå ñëó÷àåâ õîðîøî ðàáîòàåò ìíîæèòåëü 1.1-1.2, òî åñòü ïðè òàêîì çíà÷åíèè íàáëþäàåòñÿ óëó÷øåíèå ñæàòèÿ áîëüøèíñòâà ôàéëîâ è ìàëîâåðîÿòíî óõóäøåíèå ñæàòèÿ êàêîãî-òî ïðèâåðåäëèâîãî ôàéëà. Íî ÷àñòî îïòèìàëüíîå çíà÷åíèå ìàñøòàáèðóþùåãî êîýôôèöèåíòà êîëåáëåòñÿ â ðàéîíå 2-2.5, òàê ÷òî ìîæíî óëó÷øèòü îöåíêó çà ñ÷åò àäàïòèâíîãî èçìåíåíèÿ ìíîæèòåëÿ. Ïîäõîäÿùåå çíà÷åíèå âûáèðàåòñÿ íà îñíîâå àíàëèçà ñæèìàåìûõ äàííûõ ñ ïîìîùüþ ýìïèðè÷åñêèõ ôîðìóë.
    Ïðèìåíåíèå recency scaling ïîçâîëÿåò óëó÷øèòü ñæàòèå â ñðåäíåì íà 0.5%.

7. Ìàñøòàáèðîâàíèå â äåòåðìèíèðîâàííûõ êîíòåêñòàõ èëè deterministic scaling
    Èçâåñòíî, ÷òî ìåòîäû A..C ïåðåîöåíèâàþò âåðîÿòíîñòü óõîäà äëÿ äåòåðìèíèðîâàííûõ êîíòåêñòîâ. Ýòî ìîæíî èñïðàâèòü, óìíîæàÿ ñ÷åò÷èê ñèìâîëà íà îïðåäåëåííûé êîýôôèöèåíò. Íåòðóäíî çàìåòèòü, ÷òî ýòîò ìåõàíèçì åñòü ÷àñòíûé ñëó÷àé recency scaling.
    Â [4] óòâåðæäàåòñÿ, ÷òî ýôôåêò îò deterministic scaling óâåëè÷èâàåòñÿ, åñëè ïðè ýòîì èñïîëüçóåòñÿ ÷àñòè÷íîå îáíîâëÿåìîå èñêëþ÷åíèå, à íå îáû÷íîå îáíîâëÿåìîå.
    Deterministic scaling ìàëî ÷òî äàåò â ñëó÷àå èñïîëüçîâàíèÿ ìåòîäà D. Âîîáùå, ÷åì òî÷íåå âû÷èñëÿåòñÿ âåðîÿòíîñòü óõîäà, òåì ïîëüçû îò ýòîãî ìàñøòàáèðîâàíèÿ ìåíüøå. È îíî âîâñå íå íóæíî ïðè èñïîëüçîâàíèè SEE.

8. Âûáîð ïîðÿäêà äëÿ êîäèðîâàíèÿ ñèìâîëà èëè Local Order Estimation (LOE)
    Ïîñëå çàäà÷è îöåíêè âåðîÿòíîñòè óõîäà âòîðîé ïî çíà÷èìîñòè ïðîáëåìîé PPM ÿâëÿåòñÿ âûáîð ïîðÿäêà ìîäåëè, îáåñïå÷èâàþùåé íàèëó÷øåå ñæàòèå îáðàáàòûâàåìûõ äàííûõ.  çàâèñèìîñòè îò âèäà äàííûõ îïòèìàëüíûé ïîðÿäîê ìîäåëè ìîæåò áûòü îò 0 äî 16 (äëÿ òåêñòîâ â ðàéîíå 4-6) è áîëüøå, êðîìå òîãî, îáû÷íî èìåþòñÿ ëîêàëüíûå èçìåíåíèÿ âíóòðè ôàéëà.
    Ìåõàíèçì âûáîðà ïîðÿäêà ìîäåëè äëÿ êîäèðîâàíèÿ òåêóùåãî ñèìâîëà ïîëó÷èë íàçâàíèå LOE. Âñå ñõåìû LOE íîñÿò ÷èñòî ýâðèñòè÷åñêèé õàðàêòåð (èñêëþ÷àÿ ìåòîä CTW [8], ðàáîòàþùèé ñ äâîè÷íûì àëôàâèòîì) è çàêëþ÷àþòñÿ â òîì, ÷òî çàäàåì íåêóþ ôóíêöèþ "äîâåðèÿ" è ïðîáóåì ïðåäñêàçàòü ñ åå ïîìîùüþ ýôôåêòèâíîñòü êîäèðîâàíèÿ òåêóùåãî ñèìâîëà â òîì èëè èíîì äîñòóïíîì êîíòåêñòå ïîðÿäêà îò 0 äî íàïåðåä çàäàííîãî M. Ìîæíî âûäåëèòü òðè òèïà ñõåì LOE:
    - èùåì îïòèìàëüíûé ïîðÿäîê ñâåðõó âíèç îò êîíòåêñòà ìàêñèìàëüíîãî ïîðÿäêà ê êîíòåêñòó ìèíèìàëüíîãî ïîðÿäêà, ïðåêðàùàåì ïîèñê êàê òîëüêî êîíòåêñò ìåíüøåãî ïîðÿäêà êàæåòñÿ íàì áîëåå "ïîäîçðèòåëüíûì", ÷åì òåêóùèé, êîòîðûé è èñïîëüçóåì â êà÷åñòâå ïåðâîãî êîíòåêñòà äëÿ îöåíêè âåðîÿòíîñòè ñèìâîëà;
    - ïîèñê ñíèçó ââåðõ;
    - îöåíêà âñåõ äîñòóïíûõ êîíòåêñòîâ.
    Åñëè â âûáðàííîì êîíòåêñòå çàêîäèðîâàòü ñèìâîë íå óäàëîñü, òî, âîîáùå ãîâîðÿ, ïðîöåäóðó ïîèñêà îïòèìàëüíîãî ìîæíî ïîâòîðèòü, íî îáû÷íî èùóò òîëüêî íà÷àëüíûé ïîðÿäîê, à â ñëó÷àå óõîäà ïðîñòî ïåðåõîäÿò íà óðîâåíü íèæå, òî åñòü äàëüøå èñïîëüçóåòñÿ îáû÷íûé àëãîðèòì PPM.
    Âûáîð òîé èëè èíîé ôóíêöèè äîâåðèÿ çàâèñèò îò îñîáåííîñòåé êîíêðåòíîé ðåàëèçàöèè PPM è ëè÷íûõ ïðèñòðàñòèé ðàçðàáîò÷èêà. Êàê ïîêàçàë îïûò, ðàçëè÷íûå "íàèâíûå" ýíòðîïèéíûå îöåíêè òåêóùåãî êîíòåêñòà ïî ñðàâíåíèþ ñî ñëåäóþùèì âîçìîæíûì ðàáîòàþò ïëîõî. Ýòè îöåíêè îñíîâûâàëèñü íà ñðàâíåíèè ñðåäíåé äëèíû êîäà â òåêóùåì êîíòåêñòå è â ñëåäóþùåì; ÿñíîå äåëî, èç ýòîãî íè÷åãî íå ïîëó÷àëîñü, òàê êàê ôóíêöèÿ ðàñïðåäåëåíèÿ â òåêóùåì êîíòåêñòå ìîæåò áûòü áîëåå ïëîñêîé, ÷åì â ñëåäóþùåì, ïîýòîìó ñðàâíèâàòü íàäî ñðåäíþþ äëèíó êîäà, óñðåäíåííóþ ïî âñåì äî÷åðíèì êîíòåêñòàì òåêóùåãî êîíòåêñòà, ñî ñðåäíåé äëèíîé êîäà, óñðåäíåííîé ïî âñåì äî÷åðíèì êîíòåêñòàì ñëåäóþùåãî ðàññìàòðèâàåìîãî êîíòåêñòà. Ïîä äî÷åðíèì êîíòåêñòîì ïîíèìàåòñÿ êîíòåêñò áîëüøåãî ïîðÿäêà, ñîäåðæàùèé â ñåáå ñòðîêó òåêóùåãî êîíòåêñòà ("abcd" ÿâëÿåòñÿ äî÷åðíèì äëÿ "bcd").
    Â [3] áûë ïðåäëîæåí ýôôåêòèâíûé è ïðîñòîé ìåòîä, äàþùèé îöåíêó èñõîäÿ èç âåðîÿòíîñòè P íàèáîëåå âåðîÿòíîãî ñèìâîëà â êîíòåêñòå (Most Probable Symbol's Probability, MPS-P) è êîëè÷åñòâà óõîäîâ èç êîíòåêñòà E. Îáîáùåííî ôîðìóëó ìîæíî çàïèñàòü òàê:

a*P*lg2 (P) + b*E*( lg2 (E) - c ) + d*( 1 - P )*( lg2 (E) - c ),

ãäå êîíñòàíòû a,b,c,d áåðóòñÿ "ñ ïîòîëêà". Âïðî÷åì, æåëàþùèå ìîãóò åùå äîáàâèòü êîíñòàíò ïî ñâîåìó âêóñó - íà êàêîì-íèáóäü ôàéëå ýòî îáÿçàòåëüíî äàñò âûèãðûø.
    Ê ñ÷àñòüþ, îöåíêà òîëüêî ïî P äàåò õîðîøèå ðåçóëüòàòû óæå â òîì ñëó÷àå, êîãäà ïðîñòî âûáèðàåì êîíòåêñò ñ ìàêñèìàëüíûì P (ñîîòâåòñòâóåò âàðèàíòó îáîáùåííîé ôîðìóëû ïðè b=d=0).

9. Unbounded PPM èëè PPM*
    Ïðè ôèêñèðîâàíèè ìàêñèìàëüíîãî ïîðÿäêà êîíòåêñòîâ â ðàéîíå 5-6 PPM äàåò îòëè÷íûå ðåçóëüòàòû íà òåêñòàõ, íî âåñüìà ïëîõî ðàáîòàåò íà âûñîêîèçáûòî÷íûõ äàííûõ ñ áîëüøèì êîëè÷åñòâîì äëèííûõ ïîâòîðÿþùèõñÿ ñòðîê.  [9] áûë îïèñàí ìåòîä áîðüáû ñ ýòèì íåäîñòàòêîì. Ïðåäëîæåííûé àëãîðèòì, PPM*, áûë îñíîâàí íà èñïîëüçîâàíèè êîíòåêñòîâ íåîãðàíè÷åííîé äëèíû. Àâòîðû ïðåäëîæèëè ñëåäóþùóþ ñòðàòåãèþ âûáîðà ìàêñèìàëüíîãî ïîðÿäêà íà êàæäîì øàãå: â êà÷åñòâå êîíòåêñòà ìàêñèìàëüíîãî ïîðÿäêà âûáèðàåì ñàìûé êîðîòêèé äåòåðìèíèðîâàííûé êîíòåêñò.  êà÷åñòâå ñòðóêòóðû äàííûõ èñïîëüçóåòñÿ context trie, ñîäåðæàùåå ññûëêè íà óæå îáðàáîòàííóþ ÷àñòü ôàéëà.
    Ðåàëèçàöèÿ PPM*, îïèñàííàÿ îäíèì èç àâòîðîì àëãîðèòìà â [4], èìåëà âåñüìà õèëûå õàðàêòåðèñòèêè: ñæàòèå íà óðîâíå PPMD order-5, ñêîðîñòü, êàê óòâåðæäàåòñÿ, òàêæå ñîïîñòàâèìà, íî ïàìÿòè ðàñõîäóåòñÿ çíà÷èòåëüíî áîëüøå.  ïðèíöèïå, ðàñõîäû ïàìÿòè ìîãóò áûòü ñîïîñòàâèìû, òàê êàê context trie, åñëè åãî îôîðìèòü â âèäå PATRICIA trie, ïîçâîëÿåò äîñòàòî÷íî ýêîíîìíî èñïîëüçîâàòü ïàìÿòü (ðàñõîä ïðè ýòîì çàâèñèò ëèíåéíî îò ðàçìåðà âõîäíûõ äàííûõ).  [6] ïðèâîäèòñÿ ñòðóêòóðà äàííûõ íà îñíîâå suffix tree, òðåáóþùàÿ ïðèìåðíî â äâà ðàçà ìåíüøå ïàìÿòè, ÷åì context trie, ïðåäëîæåííûé àâòîðàìè PPM*.

10. Êîìïðåññîðû, èñïîëüçóþùèå PPM
    Ïðàêòè÷åñêè âñå êîìïðåññîðû ìîæíî íàéòè íà
ftp://ftp.elf.stuba.sk/pub/pc/pack/

Êîìïðåññîð	Àâòîð
boa	Ian Sutton
ha	Harry Hirvola
lgha	Þðèé Ëÿïêî
arhangel	Þðèé Ëÿïêî
PPMd	Äìèòðèé Øêàðèí
ppmz	Charles Bloom
rk	Malcolm Taylor
rkuc	Malcolm Taylor
rkive	Malcolm Taylor
x1	Stig Valentini

boa	- âàðèàöèè íà òåìó PPMZ
ha	- order-4, îðèãèíàëüíûé ìåòîä ÎÂÓ: âñå åùå àïðèîðíûé, íî åñòü íàìåêè íà àäàïòàöèþ, â êà÷åñòâå ñòðóêòóðû äàííûõ äëÿ ïîèñêà êîíòåêñòîâ èñïîëüçóþòñÿ õåø-öåïî÷êè; äîñòóïíû èñõîäíèêè [11]
lgha	- ha, ïåðåïèñàííûé íà ÿçûêå Àññåìáëåðà
arhangel	- âàðèàöèè íà òåìó ha; ïðèìåíÿþòñÿ ðàçëè÷íûå ôèëüòðû äëÿ òåêñòîâ, òàáëèö, ýêçåøíèêîâ è ìóëüòèìåäèè
PPMd	- îãðàíè÷åííûé ïîðÿäîê ìîäåëè, order-1 SEE (ñ ìåòîäîì D èìååò ðàçâå ÷òî îáùèõ çíàêîìûõ) íà îñíîâàíèè ñòàòèñòèêè êîíòåêñòîâ-ïðåäêîâ, íàñëåäîâàíèå èíôîðìàöèè (â ýòîì òåêñòå íå ðàññìîòðåííîå); äîñòóïíû èñõîäíèêè [12]
ppmz	- ìåòîä Z, LOE, îòäåëüíî îáðàáàòûâàþòñÿ äëèííûå äåòåðìèíèðîâàííûå êîíòåêñòû, îïöèîíàëüíî èìååòñÿ LZP; äîñòóïíû èñõîäíèêè [13]
rk	- ýëåìåíòû PPMZ, áèíàðíûå êîíòåêñòû (ñ ïðîïóñêîì ñèìâîëîâ, òèïà: "ABCD", "ACCD" ñîîòâåòñòâóþò îäíîìó êîíòåêñòó "AxCD"), ðàçëè÷íûå ôèëüòðû
rkuc	- ïîðÿäêè: 16-12-8-5-3-2-1-0 (-1)?, LOE, áèíàðíûå êîíòåêñòû
rkive	- LZP+PPM, ðàçëè÷íûå ôèëüòðû

11. Ëèòåðàòóðà, èñõîäíèêè
Äëÿ îçíàêîìëåíèÿ ñ êîíòåêñòíûì ìîäåëèðîâàíèåì è ìåòîäàìè ñæàòèÿ âîîáùå íàñòîÿòåëüíî ðåêîìåíäóåòñÿ ê ïðî÷òåíèþ [2]. Èç ïðî÷åé ëèòåðàòóðû ïîëåçíûìè ñëåäóåò ïðèçíàòü ïóíêòû [5], [6].

Ëèòåðàòóðà:
[1] Cleary J.G. and Witten I.H. Data compression using adaptive coding and partial string matching.
   http://compression.graphicon.ru/download/articles/ppm/cleary_witten_1984_pdf.rar
[2] Bell T., Witten I.H., Cleary J.G. Modeling for text compression.
   http://compression.graphicon.ru/download/articles/rev_univ/bell_1989_modeling_pdf.rar
  Åñòü ðóññêèé ïåðåâîä:
   http://compression.graphicon.ru/download/articles/rev_univ/modeling.rar
[3] Bloom C. Solving the problems of context modeling.
   http://compression.graphicon.ru/download/articles/ppm/bloom_1996_ppmz_pdf.rar
[4] Teahan W.J. Probability estimation for PPM.
   http://compression.graphicon.ru/download/articles/ppm/teahan_1995_probest_pdf.rar
[5] Howard P.G. The design and analysis of efficient lossless data compression systems.
   http://compression.graphicon.ru/download/articles/ppm/howard_phd_1993_pdf.rar
[6] Bunton S. On-line stochastic processes in data compression.
   http://compression.graphicon.ru/download/articles/ppm/bunton_phd_1996_pdf.rar
[7] Witten I.H. and Bell T.C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression.
   http://compression.graphicon.ru/download/articles/ppm/witten_bell_1991_zerofreq_pdf.rar
[8] Willems F., Shtarkov Y., Tjalkens T. The context tree weighting method: basic properties.
   http://compression.graphicon.ru/download/articles/cm/willems_1995_ctw_basic_pdf.rar
[9] Cleary J.G., Teahan W.J., Witten I.H. Unbounded length contexts for PPM.
   http://compression.graphicon.ru/download/articles/ppm/cleary_teahan_1997cj_pdf.rar

Èñõîäíèêè:
[10] COMP-2 by Mark Nelson
   http://compression.graphicon.ru/download/articles/ppm/
nelson_1991_ddj_arithmetic_modeling_html.rar
[11] HA by Harry Hirvola
   http://compression.graphicon.ru/download/sources/cm/ha_src.rar
[12] PPMD Äìèòðèÿ Øêàðèíà
Âåðñèÿ I ðåâèçèÿ 1:
   http://compression.graphicon.ru/download/sources/cm/ppmdi1.rar
[13] PPMZ by Charles Bloom
   http://compression.graphicon.ru/download/sources/cm/ppmz91.rar

íàâåðõ