
     ͻ
                             DOUGLAS W. JONES                        
     ͹
              APPLICATION OF SPLAY TREES TO DATA COMPRESSION         
     Ķ
        Communication of the ACM. 31, 8 ( August 1988 ), 996-1007.   
                                                                     
                             GENERAL TERMS:                          
                        Algorithms, Performance.                     
                                                                     
                   ADDITIONAL KEY WORDS AND PHRASES:                 
                                                                     
         Adaptive algorithms, arithmetic codes, data compression,    
                       splay trees, prefix codes.                    
     ͼ

                    饣  䨪      ᠬ
                     ⨢ p⬮ ᦠ , ᭮-
                    ᯮ짮 䨪᭮ . ᯮ㥬  
                  pp    ⠪   ⠪ p
                   p䬥᪮ ᦠ.  । ᯮ짮
                   ⬮  ஢  宦 pᮢ.
                                 
              .
            
     ᦠ   䥪⨢ ࠭   ।  
।⢮ ᮪饭 ⢠  筮.  ᦠ   -
⢥  室  ⥪ 筨   ந ᮮ⢥騩  ᦠ ⥪,
  ࠧ稢騩     室 ᦠ ⥪   砥 
  室 ࢮ砫 ⥪ 筨 (1). 設⢮ ⬮ ᦠ-
 ᬠਢ 室 ⥪   ப,     㪢 䠢
室 ⥪.
    筮  ।⠢ ப S  L(S) - H(S),  L(S)  -
 ।⠢  ,  H(S) - ய -  ᮤঠ ଠ樨, ⠪-
  ࠦ    . ⬮,        ଠ樨
ᦠ ப  襬  , 祬 ⠢  ய,   .
᫨   室 ⥪    㪢 ண 砩 -
p, ᯮ饣 䠢 ,  ய 室  㫥:

                     Ŀ           1
          H(S) = C(S)    p(c) log  ,
                     c A          p(c)

 C(S)  ⢮ 㪢   ப, p(c)  ᪠ ⭮ -
 ன 㪢 C. ᫨  業 p(c) ᯮ짮  
 㪢 c   ப S,  H(C) 뢠 ᠬய ப  S.  ⮩
 H (S) 㤥 ᯮ짮   祭 ᠬய ப, ⮩
 筮 筨.
    , ᭮  ਬ 筮 ⭮,   -
 ࠪਧ   筨. ਬ,   ᪮ ⥪, 㪢  U
 ࠭ 祬 E, ⮬  筮  ⭮ 㤥 -
쭮 ।᪠뢠,   QE      ࠭ ⠭,
祬 QU.  뢠 ⠪ 筨  ⭮  મ-
. 筨 મ  ⢮ ﭨ, ᬥ  ந室  
 । 㪢.  ﭨ 뢠  । -
⭮, ।騬 ᫥饥 ﭨ   ᫥ ந -
.  મ᪨ 筨, ।⠢騩 ᮡ ⥪,  ᪮-
, 뤠 㪢 Q,  ⠭ ﭨ,  ஬ U   -
 뢮. 쭥襥 祭 ᮢ, 易  ய, 묨 -
筨   筨  મ    த  設⢥   
⥮ਨ ଠ樨 [2].
    ᬮ  ,   讥 ⢮ ad hoc 室   ᦠ, -
ਬ,  ஢  p,  ⠪  ⥬᪨ 室.
 䬠  ।     ३. ஢ 
ᦠ 䬠 ॡ ᯮ짮  奬 ஢ ॢ,  
⠪ ਬ  ࠬ , 室 ⨢  䬥-
᪮ ᦠ. ਬ       ॢ쥢 -
p ⥫ 室⢮   楫 ஢.
    騥  ॢ  筮 뢠  ᨪ᪮ 㯮冷-
祭 p쥢 筮 ᪠,  ॢ, ᯮ㥬  ᦠ⨨ 
   ﭭ 㯮冷祭. ࠭ 㯮冷祭 ਢ
 ⥫쭮 饭 ᭮ 権 ७. 祭  ⮣ -
 ।쭮   .  砥 ਬ  䬠, p-
७ ਢ   쭮 ஢  ᦠ, p -
⥫쭮   ,     ⨣ ⨬쭮 ᦠ. -
   ਬ   䬥᪨ ,  १ ᦠ   -
쭮  ਡ⥫쭮 ⨬  ६.

          .
                    
    設⢮ ப  砥 ⬮  ᦠ  ᭮   
䬠.   䬠  㪢 室 ⥪ ।⠢  -
  ६ .   㪢 ।⠢ ⪨ ,
  - 묨. , ᯮ㥬  ᦠ⮬ ⥪  稭
᢮⢠ 䨪,  : ,  ᯮ짮   ᦠ⮬  ⥪   
 䨪ᮬ  㣮 .
     䨪    ।⢮ ॢ,  ஬  
ᮮ⢥  㪢 䠢 筨. H p㭪 1  ॢ -
 䨪  䠢  4 㪢.  䨪  㪢   ⠭
 室 p     ⮩ 㪢,  0 ᮮ⢥ 롮  
⢨,  1 - ࠢ. ॢ  䬠  ॢ  ࠢ ᮬ, 
   , ࠢ  砥 㪢  室 ⥪, 
७ 㧫 ᢮   . ॢ  ਬ 㤥 ⨬, ᫨
 㪢 A, B, C  D  0.125, 0.125, 0.25  0.5 ᮮ⢥⢥.

       0           0            0
A  o  o  o
                                               A = 000
             1           1           1         B = 001
                                               C = 01
             B            C            D          D = 1

         㭮 1. ॢ ।⠢  䨪.

       䬠 ॡ ।⥫쭮 ଠ樨   -
砥 㪢   室 ⥪,     室   -
ᬮ -   祭 祭  㪢, 㣮  ஢ ᠬ
ᦠ.  ᫥饬, 祭     㦭 ꥤ   ᠬ ᦠ
⥪⮬, ⮡   쭥襬  ᤥ    ࠧ뢠. ⨢
ᦠ⨥ 믮   蠣, .. , ᯮ㥬   㪢 室-
 ⥪, ᭮    ⠫ p  㪢 䠢. ᭮-
  䥪⨢ ॠ樨 ⨢  䬠 뫨  -
஬[3],  㡫 ࠪ  ⠪ ⬠[5],   
p[10].
    ⨬ ஢    ᥣ   ।  -
   㪢 筨   ⭮襭   ⨬쭮 筮  䬠,
 筮  ⠢  ᪮쪮 業⮢   H .  ⮬ ,    
䬠  ᥣ    ।    㪢 室 ⥪  H
(  ⨣  । ⮫쪮    㪢  p(C) = 2  ).   
࠭祭   ⭥ᥭ  筨 મ, ᫨ 筮  -
஢ ॢ 䬠 ᯮ   ﭨ 筨, 뢥-
   室 ⥪.   ᦠ   -
  ࠭祭.  -, ਬ, ᢠ ᫮
 p娢 䨪஢  ப 室 ⥪ p [11], 
䬥᪮ ᦠ⨥  ᯮ짮   ஢  㪢 筨 
 [12].

         ਬ ७   䨪.
                
    騥 ॢ 뫨  ᠭ  1983 [8]   p
ᬮ७  1985[9]. ࢮ砫쭮     ᠬᡠp-
 p쥢 筮 ᪠,  뫮 ⠪ ,    -
⢨ ᠬ  ॠ ਮ ।[4]. ᫨  㧥 -
饣 ॢ 㯥,    ७.  ,  㯭
㧥 ⠭ ୥,  㧫 ᫥   ࠧ   ॢ,
㧫 ࠢ -  ࠢ ॢ. ७ ⨣   室 -
  ண   楫 㧫  ᮢ襭 p ⮬  ,
⮬ 業 ७ ய樮쭠  ன .
      ⮭[9] ,  騥 ॢ 筮 ⨬-
. 㣨 ᫮, ᫨   㯭 㧫  ᮣ᭮ 筮 -
।  ⭮,  ᪮ 㯠  饬 ॢ  -
 ᡠ஢, ⨬஢ ⨬ ।,   ⫨
  㣠  ﭭ 樥,   筮  -
 㯮. ᪮ ॢ 䬠 ।⠢ ᮡ ਬ 筮 ᡠ-
஢ ॢ,  p ᯮ짮 ७  ᦠ , p-
 ᦠ⮣ ⥪ 㤥   । ண 樥   ࠧ
娢, 祭  ᯮ짮  䬠.
     뫮  ࢮ砫쭮 ᠭ, ७ ਬ  ॢ, ࠭-
騬    ७ 㧫,    . ॢ   䨪 -
  ᢮  ⮫쪮  . , , ਠ  ७,
뢠  ७,  ਬ    ॢ  䨪. 
 楫 㧥   ६頥   ७   䨪   ᫥ 
ந,      楫   㬥蠥 . -
७ ⨣   ⥮᪨ ࠭  । ﭭ -
,   ७.
      砥  ࠧ  室 ᨪ᪮ ॢ, ஢
 ७, ⠪  ७ ᫮,  ⫨稥  אַ -
    ࠢ  ॢ  楫 㧫 ( 砨  ᬮ-
७  [8], [9] ).  ⮩ 砩   㭪 2. ⢨ -
७     ( 㧥 w )   㧫 A 砥  -
 ⠬    ७ ᫥   㣮 㧫,  १-
 祣      㧫- ᮪頥    2 ࠧ.  
७  㧫   ,    ,    
 ( 㧫 x  z ),      ᪫ ( 㧫 w  y ).

      0          0         0         0       .        0             0
A  oo  oo  . A oo
          z        y         x        w  .            z            x
           1        1         1        1 .             1            1
                                         .       0             0    
           B         C          D         E  . B o  D o
                                             .            y            w
                                            .             1            1
                                  >  .                          
                                             .             C             E

         㭮 2. ७  ᠬ   ॢ .

    ࠭ 樥 ७  ᨪ᪮ 浪   ॢ
 䨪   易⥫. ⢥     
䨪  筮 ᮮ⢥⢨ ॢ, ᯮ㥬  楤ன ᦠ
ॢ, ᯮ㥬  楤ன ࠧ뢠.   , 饭-
  ᫥⥫쭮  騬 㪢, ந ⮫쪮   ⮬ 砥,
᫨  楤 ⢫     浪.
    H㦭 প ᨪ᪮ 浪 ⥫쭮 頥 -
 樨 ७    ᪫祭  .   
 ᤥ ஢મ 㧫      楫   ६ -
⠬ ࠢ ᫥    ﬨ.     ॢ. p
  䨪  楫  㤥    㫥, ᪮
 ⠫ ᠬ  ⮬.  㭪 3 ॢ 뫮    C.
   蠥  ࠭祭 ।⠢ ७. -
⥫⢮  ⮣  뢮   ⥭樠쭮  㭪樨, ਢ 
[9]  ⥫⢠ ᨬ ࠭祭 ।⠢  浪 ᫥-
 ॢ쥢 㧫.

       0          0         .         0          0          0          0
A oo    .  C oooo
           x         w    .             z         y         x         w
            1         1   .              1         1         1         1
       0                  .                                            
B o          E    .              D          B          A          E
           y             =====>
            1              .
       0                   .
C o               .
           z               .
            1              .
                           .
            D               .

         㭮 3.   C ᪫砥 室 
                    ࠧ ७.
                                 
    ஥  饭 ,    㦨,     
  ᮡ  ⮫쪮 ᫥  㧫,    ७ 㧫
ॢ  䨪ᮢ, ᪮       ଠ樨.  -
   ᯮ㥬   ७  p  ,
ॡ   ⮫쪮    ﬨ   楯,  㤥 뢠
.    㭪 4.   뢠 ⠪  -
        ,    p,  㭨⮦-
 ᨪ᪨ 冷, 믮  襬 ਬ 祭   ᠤ
ᥣ  ⢥  ॢ,   ६   p ⢫ -
  ᠤ 4 ⢥.

        0            0                          0            0
A  oo            C oo
             x           w                         x           w
              1           1                         1           1
                               =====>                            
                                                                
                                                                
              B            C                          B            A

         㭮 4. 㮡p  A.
            
    饩 室 稢 ॢ । 樥 ७
.  ⮣  ७    ਬ      
楫 設   ᠬ  . ਬ, ॢ  㭪  3 
 ७     㭪 5.  ⮬ ਬ ॢ -
    C, ᯮ 㮡p      ७
㧫    C   .  ,   १ ⮩ ६
  ᯮ   ﭨ  ,  ᫨  p-
 뫮 ᭠砫  ⠪,   C  ᠬ  ⮬,  ⥬ -
७  ⥬. ⮣ ॢ ⫨砥 ⮫쪮 ⪠ ७ -
  ६ ⠬ ᫥   .
    室 ⬥,      ७ ॢ 
㧫, ࠧ騥    ᮡ  ⭮   ⭮     
.  砥 ⭮   㧥   ⮬       
p   㮡p. ⮬, ᫨      ᭨ ,  㤥
ய饭 ७, ᫨ ,   ᫥ ७  㧥. ।⠢
 ॠ ਥ஢  室 ᢥ-.

       0            0           .         0                 0
A  oo      . A oo 
            x          w      .             x                w
             1          1     .              1                1
                               .                               
       0                      .                          0    
B o           E      .              E    C o
            y             =====>                               y
             1                 .                                1
                               .                                
       0                       .                           0    
C o                  .                   B o
            z                  .                               z
                                .                                1
             1                 .                                
                               .                                 
             D                  .                                D

         㭮 5. ७  C  ᯮ짮 㮡p.


          塞 䨪.

    ।⠢  ணࠬ ᠭ   ࠢ 몠 ᪠  -
ﬨ, 騬 ﭭ 祭  ⠢塞묨  ⢥ ⠭ 
襭 ⠥ ணࠬ.  , ᯮ㥬  ਬ, ॠ-
   ᭮ ᨢ,   ᫨ ᪠    
᭮  ᯮ짮 ᥩ   뫮.  ᮮ⢥ ଥ ।⠢-
  ࠭ ࠡ  ⮩  ⥬⨪ [5,10],  ⠪  ⢫
 ⮥ 襭   ,  ப ᯮ㥬 몠, ⠪  -
࠭,  ⭮  ।⠢ 㪠⥫.  ७ 㧥  ॢ
      ᢮ ᫥    ᢮ த⥫. 
⮩ ᯮᮡ   ⮣ - ᯮ짮   㧫  3 㪠⥫: ,
ࠢ  .  ।⠢, 㦤  [9] 뫮 ॠ ⮫쪮
   㪠⥫   㧥(2),    ⮬  ⭮ ࠭  
 㤥 ஢ ⠭ ⥫쭮 믮  ணࠬ  
⠭  .  ॡ ᫥騥 ᭮  :

const
  maxchar = ... { ᨬ  ᨬ 室 ⥪ };
  succmax = maxchar + 1;
  twicemax = 2 * maxchar + 1;
  root = 1;
type
  codetype = 0..maxchar {  ࢠ  ᨬ 室 ⥪ };
  bit = 0..1;
  upindex = 1..maxchar;
  downindex = 1..twicemax;
var
  left,right: array[upindex] of downindex;
  up: array[downindex] of upindex;

     upindex  downindex ᯮ  㪠⥫     -
 . ⥫     㪠뢠    ,  
७ 㧫,    ६   뫪  㪠뢠 ⮫쪮   ७
㧫. ७ 㧫  ࠭  쥢, ⮬  祭 ᮢ
 1  maxchar ⥫쭮  ਬ  祭 뫮  -
७ 㧫,   祭 ᮢ   maxchar + 1   2 * maxchar + 1
⥫쭮 - 뫮  . ⨬  ७ ॢ ᥣ  室 
1- 祩   । த⥫. C⢥  㪢 
  ⠭ maxchar + 1   .
    ᫨ 砭 ⥪ 筨   㦥   ⥪, 
 室 䠢  室  ࢠ codetype,  ᨬ쭮 -
  ⮬ ⥪ 祭  㤥 maxchar.  ⨢ 砥, ࢠ
codetype     ७      ᠭ ᯥ樠쭮 ᨬ
" 䠩".  砥,  maxchar 㤥  1  祭 ᨬ-
  ᨬ 室 ⥪.
     楤 樠  ॢ .  ந ᡠ-
஢ ॢ ,   ᠬ ,  砫쭮 ॢ 㤥 㤮-
⢮⥫   ,    ᯮ   ᦠ   ࠧ-
.

procedure initialize;
var
  i: downindex;
  j: upindex;

begin
  for i := 2 to twicemax do
    up[i] := i div 2;
  for j := 1 to maxchar do begin
    left[j] := 2 * j;
    right[j] := 2 * j + 1;
  end
end { initialize };

    ᫥ ⮣,   㪢 ᦠ ( ࠧ )   ⥪饩 ᨨ
ॢ  ,      ७    ⮩ 㪢. 
⮩ 樨    ᫥饩 楤, ᯮ饩  ७ ᭨-
:

procedure splay( plain: codetype );
var
  c, d: upindex    {  㧫  㮡p };
  a, b: downindex  { p頥 ᫥ 㧫 };

begin
  a := plain + succmax;
  repeat           { 室 ᭨  ।㥬 ॢ }
    c := up[a];
    if c # root then begin { ⠢塞  }
      d := up[c];
      { ६ ⠬ ᫥  }
      b := left[d];
      if c = b then begin b := right[d];
                          right[d] := a;
      end else            left[d] := a;
      if a = left[c] then left[c] := b;
      else                right[c] := b;
      up[a] := d;
      up[b] := c;
      a := d;
    end else a := c         { ࠢ    㧫 };
  until a = root;
end { splay };

    ⮡ ᦠ 㪢 室 ⥪   㦭 ஢, ᯮ -
 ,  ⥬ ।. ᪮  ஢ ந  -
室 ॢ      ,    뢠   p⭮ 浪.
  浪 ᫥ ⮢ 楤 compress p ᢮ ⥪,
  ண     । 楤 transmit.

procedure compress( plain: codetype );
var
  a: downindex;
  sp: 1..succmax;
  stack: array[upindex] of bit;

begin
  { ஢ }
  a := plain + succmax;
  sp := 1;
  repeat { 室 ᭨  ॢ  饭  ⥪ ⮢ }
    stack[sp] := ord( right[up[a]] = a );
    sp := sp + 1;
    a := up[a];
  until a = root;
  repeat { transmit }
    sp := sp - 1;
    transmit( stack[sp] );
  until sp = 1;
  splay( plain );
end { compress };

     ࠧ뢠 㪢 室   娢 ᫥騥   -
    㭪樨 receive.  ⠭     蠣 
 室 ॢ    , ।饬 ࠧ稢 㪢.

function expand: codetype;
var
  a: downindex;

begin
  a := root;
  repeat {  ࠧ      }
    if receive = 0 then a := left[a]
    else                a := rignt[a];
  until a > maxchar;
  splay( a - succmax );
  expand := a - succmax;
end { expand };

    楤, ࠢ騥 ᦠ⨥  ࠧ뢠,   ।⠢ -
 맮 楤  initialize,   ᫥ 맮   compress, 
expand   ࠡ뢠 㪢.

         ࠪ⨪ ⬠ 塞 䨪.
                
     ࠪ⨪, 塞  ॢ,    ᭮뢠  䨪,
     ⨬묨,    묨 묨 ⢠.
० ᥣ   ᪮ 믮, ⮩  ணࠬ     
 .  ⬠ 塞 䨪 ॡ ⮫쪮  3 -
ᨢ,   ६   -⬠ , 饣 ⨬ -
஢  䨪, -  11 ᨢ  [10]. ।,    祭
⢠ ᨬ 室 ⥪ ᯮ 8   ᨬ,   䠩-
 । ᨬ, 室騬  8-⮢ ।, maxchar = 256, 
  ᨢ  ᮤঠ  9  10 ⮢ ( 2   設⢥
設)(3).     ⬠ 塞 䨪 ⠢-
 ਡ⥫쭮 9.7 ⮢ (2 ⮢  設⢥ 設).  -
室  ࠭ ᨢ    -⬥ ॡ  57 ⮢ (10 ⮢ 
設⢥ 設 ).
    㣨 ப ਬ塞  ᦠ ॡ   襣 ࠭-
⢠, ਬ,  ᮢ  ॠ樨 ⮤  - [11] ᯮ-
 -⠡  4096 ⮢  20 ⮢ ,   ⮣ ⠢-
 㦥  82 ⮢ ( 12 ⮢  設⢥ 設 ). ப ᯮ㥬 -
 ᦠ  ⥬  ફ ਬ   -, ᭮ 
⠡    64 ⮢  ࠩ    24  ,    ⮣ 
1572 ⮢ ( 196 ⮢  設⢥ 設 ).
     ⠡ I   -    饣 -
䨪 ࠪਧ  ⢥ ࠧࠧ ⮢ .   -
  ਬ 䠢   256 ⤥ ᨬ, ७ ⥫-
   䠩.   䠩, १ ࠡ -⬠ 室-
  । 5%  H   筮 ⠢ 2%  H .  ࠡ -
 饣 䨪   ॢ蠥 H  , 祬  20%,  -
 뢠   H .
    ⮢   ணࠬ   (䠩 1),  ணࠬ  ᪠-
 (䠩 2  3)  ࠭ ।   (䠩 4).  4 ⥪⮢ -
 ᯮ ⢮ ᨬ   ASCII   ⠡樥, 饩 㯯
 8 ஡  砫,   ஡   ப.     䠩  -
 ⨣ १⮢, ⠢ ਬ୮ 60%  ࠧ஢ 室-
 ⥪,   ७ - 70%.  ᠬ 訩 砩 ᦠ, -
  ࠢ ⬮.
     ꥪ 䠩 68000 뫨  ᦠ ( 䠩 5  6 ) ⠪  ,  
䠩  뢮  TEX  ଠ  .DVI ( 䠩 7 ).    筮,
祬 ⥪⮢ 䠩,  ⮬   ⮤ ᦠ   ᮪  ࠧ-
  筮  䥪⨢.   ,   ⬠  㤠  ᯥ譮
ᦠ , 祬  ७  १, 訥  १⮢
ࠡ -⬠ ਡ⥫쭮  10%.
    뫨 ᦠ  ᪨ 䠩, ᮤঠ騥  ࠦ 祫᪨ 
( 䠩 8, 9  10 ).  ᮤঠ ࠧ筮 ᫮ 祪  ॠ १ 16
⥭ ண 梥, 祬  ࠭  뢠 1  -
.   䠩 १ ࠡ -⬠ ⠢ ਡ⥫쭮  40%
 ࢮ砫쭮 ࠧ 䠩,   ⬠ ७ - ⮫쪮  25%
 60%  H  .      룫廊 , ᪮ H   
⥮᪨ ଠ樮 ,    ७ ८ 
  ᯮ짮 મ᪨ ࠪ⨪ 筨.
    ᫥  3 䠩 뫨 ⢥ ᮧ   祭  筨-
,   塞 䨪 ॢ室  ( 䠩 11, 12  13 ) 
⠫.   ᮤঠ  ⢮    256  ᨬ-
, ⮬  H       3- 䠩  ࠢ  ப  .
 11,   ⢮ ᨬ   64 ࠧ,  -
 䨪  ८ࠧ ⥫쭮    ࠢ  H  .  䠩  12
⢮ ᨬ   64 ࠧ,    ᨬ 饭, 
९ ७ ᮢ襭⢮ ⭮⥫쭮 H  . 祢  ⫨稥
  ⨬  ﬨ ⮨   ⮬,    䠩  11 ᫥騥  
㣮 ᨬ  ⭮ 室    ॢ ,    ६  
䠩  12  ⭮.  䠩  13 ⢮ ᨬ   7 ࠧ,
祬 ᫥⥫쭮, ࠧ㥬  ᨬ ᫥ ண ७ 
⢠, 㢥稢 . 砥,  䠩  稢 㯯 
32 ᨬ "a",  ன ᫥ 32 ᨬ "b"  ..  ⮬ 砥  -
  塞  䨪 ਭ     ᫥⥫쭮
 ᨬ, ⮬ १  ᥣ 25%  H ,   --
   뤥 ᨬ,   ࠭   ⥪ ⭮-
⥫쭮 㣨, ⮬   ᥬ 殮 ஢   ᯮ짮  
 .
     ᨬ   騬  塞 䨪 ᫥-
⥫쭮 砥     襩 : ᫥   ࠩ  log  n
७   㪢  n-㪢 䠢,   㤥 ᮮ⢥⢮  
 ᥣ    1 .   騩 १ ਬ -
⬠ ७  䠩 13.  ⮣, ᫨ 㪢   ॢ ॢ
  騥 뫪,  㬥   ࠧ   
㪢 ॢ.  , 祬   ࠡ⠫  䠩 11.

͸
 file   type    bytes    bits      H(s)      bits   splay bits 
͵
  1    C        12090    96720   58880.2     60176     66344   
  2    Pascal    3632    29056   16882.0     17544     19608   
  3    Pascal    9720    77760   45788.6     46704     53552   
  4    text     55131   441048  270814.9    274032    309496   
  5    object   32207   257656  193665.3    196760    206280   
  6    object   41456   331648  249270.7    252312    263744   
  7    .DVI     41881   335048  257542.3    260592    282304   
  8    image    46187   369496  147296.7    149056     94936   
  9    image    60141   481128  183023.7    186032    115576   
 10    image   144981  1159848  506817.1    515304    262376   
 11    test     16385   131080  131080.2    132552    122296   
 12    test     16385   131080  131080.2    132592    144544   
 13    test     16385   131080  131080.2    132552     32424   
;

          I.  ஢ -⬠  ⬠
                       塞 䨪.

    ।  ᪨   ।  뢠, ⮡  ᪮쪮 ᫥-
⥫ 祪  ᪮    梥⮢ ⥭ᨢ,
   ।     த ன ࠦ,   
ਬ  ᢮ । 筮 ⭮.  ᦠ⨨ ᫥⥫-
 祪 ᪮ , ந室 ᢮ ⪨  ⥬  窠,
梥   ࠭   ⥪饩 .   -
室     ன    㣮 ன,  ⪨
  । 梥⠬,   ࠭    , 
  㦥   ᯮ㥬  梥⮢ ⥯ ⠭ . 室 
ࠪ  ⠪ ,   塞 䨪   -
 .  쭮 ⨢   ᯮᮡ  ⨣
ਥ १⮢  p ᦠ⨨  筨  મ,   
ﭨ   , ⮡  ᯮᮡ  ⮬ -
ﭨ.
    㣨  쭮 ஢    ᦠ   뫨 ।
⮬[5]  ⫨ et al [1].  ।  쭮 ஢ 
䬠,  ஬ , ᯮ㥬   । 㪢 । n -
 㪢.  室  窨 ७ ᫥  ᫮, 祬
 ஢  䬠,  ᮮ⢥饥 祭 n -
    ﭨ 筨. ⫨  et al । ᯮ-
  孨 ६饭   砫 ( move-to-front )  ࣠-
樨 ᯨ᪠ ᫥ ᯮ짮 ᫮ ( ।,  ⥪ 筨-
   ( ᫮ )  )  ᮥ  쭮 -
஢  䬠  ஢ ⢠ ஡  ᯨ᪥.  
䬠 砥 ਮ᪮ 㬥襭 ᮢ  㪢 ॢ  ।⢮
㬭   ﭭ ᫮,  1. 宦 室 ᯮ짮   [12]
 䬥᪨ . ਮ᪮ 㬥襭 ᮢ  㪢   ⨢-
  䬠   䬥᪮   १   ⭮襭-
 祭 宦  १⮬ ࠡ ᠭ   ७.
      , ॡ㥬  ⬮  塞 䨪,
 ॠ㥬  મ    ⭮⥫쭮 訬 ᫮
ﭨ. ਬ,   祬   30 ﭨﬨ   ॠ
 196 ,   ᤥ    ᦠ  ⥬  ફ. ।-
   ணࠬ        મ ।⢮
  ६  state  ᨢ ﭨ    3- -
ᨢ, ॠ  ॢ . ॢ     ﭨ  
樨஢ ,    室     楤
splay    ﭨ   ᭮  ।饩  㪢 (  
 ᫮ ,  ᭮  ।饩 㪢  ।饣 -
ﭨ ).
     ⥬  n ﭨﬨ,  ।饩 㪢 뫠 ,  ᯮ짮-
 祭  mod n   । ᫥饣 ﭨ.   -
 ᫥ ॢ   n- 㪢 䠢    ﭨ.   ᦠ
⥪⮢, ꥪ⭮  ᪮ ( 䠩 8 ) 䠩 祭  n 﫨
 ।  1   64.   ⮢   㭪 6.  -
⭮ 䠩 뫮 筮    64 ﭨﬨ, ⮡  १-
, 襣  祬    ᦠ, ᭮  ⮤ -,  -
  4 ﭨﬨ 㦥 ४뢠 H .  ⥪⮢ 䠩    64 -
ﭨﬨ 㦥   १   ᦠ,     8 ﭨﬨ
筠  ८  H .  ᪨  ( 䠩 8 ) -
   16 ﭨﬨ 筮, ⮡   १  ᦠ, 
⮬    ᢮ १⠬  ४뢠 H .  મ-
  祬   8 ﭨﬨ 뫨  䥪⨢, 祬  筠 -
, ਬ塞   ᪨  ,  ᠬ  宩 १  
    3 ﭨﬨ.  稫   ⮩ 稭,  ᯮ짮
 મ 㦨 宩 쭮 ஢  ⬠ -
塞 䨪.
       .                   H
      
      
   200                                         ᦠ⨥  UNIX
      
       
      
      
      
   100
                     ooo
      
                                     o - ꥪ 䠩
                                      o - ⥪⮢ 䠩
                                     o - ᪨ 䠩
      Ŀ
        2 4   8      16              32                              64
                         ﭨ  મ.
 
     㭮 6. ࠪ⨪ ⬠ 饣 䨪
                     મ᪮ .

     ⬠, -    塞 䨪, 믮   ६ אַ
ய樮쭮 ࠧ 室 䠩,    , 室   襬
ਠ    O(H ), ..     믮   襬 砥 
६  O(H ). ﭭ 樥 ⫨, ᪮  -
 䨪 ந  ࠡ    뢮,   襬 砥 -
   室  ⮢.   13 䠩, ।⠢  ⠡ I, -
 뢮  । 2 ⮢  ᥪ㭤,    塞
䨪 -  4 ⮢  ᥪ㭤, .. ன  ᥣ  -
॥.  ⥫ 뫨 祭  ࠡ祩 ⠭樨 68000, ਨ  200 9836CU
 , 饩 OC HP-UX.  ⬠ 뫨  ॠ   ᪠,
室  ᠭ  ।⠢  몮.

          .
                                
    T, 祭   ᦠ⨨ 䬥᪨ , ᬠਢ  -
⢥ ஡,   㪢   䠢 뢠   ࢠ-
 ⮣ ࠢ ࢠ [0,1).  筨   ᬠਢ 
㪢쭮  ।⠢  ஡, ᯮ饩  ⥬ ᫥,  
㪢  䠢 ᯮ  ⢥ ᫠,  ࢠ 祭, 易
     砥 ⮩ 㪢. ࢠ 㪢 ᦠ⮣ ⥪
(ᠬ "" )   ஢ 宦 㪢, 㨭p-
  ன 砥  祭 p⠢饩  ⥪ ஡. ᫥ ।
। 㪢 室 ⥪, ஡ 뢠  宦 ᫥-
饩.  ⢫ ⠭   ஡ ᭮ 易   -
 ,   १  ਭ  㨭ࢠ. ᫥ -
襭 ⮩ 樨  ஢ ᫥ 㪢.
     ⢥  ਬ 䬥᪮ ஢ ᬮਬ 䠢   4-
㪢 (A, B, C, D)  ⭮ﬨ ( 0.125, 0.125, 0.25, 0.5 ). ࢠ [ 0,1)
  ࠧ ᫥騬 ࠧ:
    A = [ 0, 0.125 ), B = [ 0.125, 0.25 ), C = [ 0.25, 0.5 ), D = [ 0.5, 1 ).
 ࢠ  ⢫ ।⢮  ⭮⥩ -
 㪢 䠢   ।⢥.  ᦠ ⥪ 0.6 ( ।⠢-
    筮 ஡ ), ⮣  ࢮ  㪢   D, ⮬
  ᫮   ࢠ [ 0.5, 1 ).   १:
    ( 0.6 - 0.5 ) / 0.5 = 0.2
ன  㪢 㤥  B, ..   ஡    ࢠ [ 0.125, 0.25 ).
 :
    ( 0.2 - 0.125 ) / 0.125 = 0.6.
 ,  3- 㪢  D,  室 ⥪  ⢨ ଠ樨 
 , 㤥 饩 ப DBDBDB ...
    ࢮ।  ஡    ᮪ 筮  䬥⨪ 
   pp  ᯫ ⮢ ⮪,  룫廊 ᦠ
⥪, ᬠਢ  ⢥ ᫠.  ஡ 뫠 襭   1979 
[6]. 䥪⨢ ᦠ ⮤ 筮 䬥᪮ ஢ 㤥
ࠢ H , ⮫쪮    ᯮ짮 䬥⨪ ࠭祭 筮.   
࠭祭  筮 設⢠ 設 筮, ⮡  -
 祭 襥 ᦠ⨥.  ६  16 ⮢, 32-⮢ ந-
   筮, ⮡ १ ⨢ 䬥᪮ ᦠ-
    ᪮쪨 業  ।        ᥣ 
, 祬  ⨬쭮 ஢  䬠, । ஬.
        砥  䬠,  䬥᪨  ॡ 
室  ࢮ砫쭮   㪢. ஢ 䬥᪨
 ॡ 䥪⨢ ⬠   ঠ   ଠ樨  
饩        ࠡ⪨ 㪢. ⥩訩  
⮣ -  稪   㪢, 㢥稢騩  ᢮ 祭  -
 直 ࠧ,  祭 ᠬ   㪢     ᫥ ᫥
  䠢.  ᮮ⢥⢨  ⨬ 室,  㪢  ࠧ -
 ᫮     ᫮    ।⢥.  ⮩
室  ॡ O(n) 権   㪢 n-୮ 䠢.  ॠ-
   ⥭,    ⬥ ᦠ 䬥᪨ 
[12], । 祭 뫮 襭 ।⢮ ᯮ짮 樯 move
-to-front,  ᮪⨫  ⢮ 稪, 祭   
 ࠧ,  ࠡ뢠 㪢.
    쭥襥 襭 ࣠樨 ।   ॡ
७ 室   , ᯮ㥬  [12]. ॡ  
⢥     , ᫨ ࠧ   १ ࠪ ⨯ 
  ᫥騬   ﬨ:  initialize, update, findletter, findrange 
maxrange.  樠樨 ⠭   㪢   1,  
 ࠢ   祭 㤥 ⢮   ,   ஢-
  ᪮஢ ᯮ  砫 . 砫쭮 -
  , ࠢ , 㤥 ᢠ ᨬ   ⢥ ⮣ -
ࢠ, .. ।०   ।  祭.
     update(c) 㢥稢  㪢 . 㭪樨 findletter  find-
range   ,  update  믮   浪 -
䠢,  ࠭  ⭠ .    ६ findletter
( f, c, min, max ) 㤥  㪢 c  易   
  ࢠ [ min, max ),  f   [ min, max ). ⭠ 㭪 find-
range( c, min, max ) 㤥   祭 min  max    㪢 c.
㭪 maxrange 頥 㬬      㪢  䠢,  㦭
 ᫥    ࢠ [ 0, 1 ).

         ਬ ७  䬥᪨ .
                
    箬   ॠ樨 , 饩  祭     襬 砥
ॡ饩   㪢 , 祬 O(n) 権  n-㪢 䠢,
  ।⠢  㪢 䠢   ⢥ 쥢 ॢ.  
ॢ  , ࠢ  砥 㪢,   㧫 ।⠢-
  ᮡ 㬬 ᮢ   ᫥. 㭮 7  ⠪ ॢ
  4--㪢  䠢 ( A, B, C, D )   ⭮ﬨ  ( 0.125, 0.125,
0.25, 0.5 )  ⠬ ( 1, 1, 2, 4 ). 㭪 maxrange   ⠪ ॢ  -
  ୮ -     頥    . 㭪樨 update 
findrange   ᫥ ⮤ 室 ॢ    ,  㭪-
 findletter -    .

      A/1  o  o  o
                 2       4       8
                                  
                 B/1      C/2      D/4

         㭮 7. ॢ  .
                         
      ।⠢ ॢ     ⠪ , 
 ᬮ७ ࠭   ।⠢ ॢ  䨪ᮢ,  
ᨢ, ࠭饣   㧫.

const
  maxchar = ... { maximum source character code };
  succmax = maxchar + 1;
  twicemax = 2 * maxchar + 1;
  root = 1;
type
  codetype = 0..maxchar { source character code range };
  bit = 0..1;
  upindex = 1..maxchar;
  downindex = 1..twicemax;
var
  up: array[downindex] of upindex;
  freq: array[downindex] of integer;
  left,right: array[upindex] of downindex;
        
    樠 ⮩  砥   ᥡ   ⮫쪮 ஥ ॢ-
 ,   樠     㧫 ᫥騬 ࠧ:

procedure initialize;
var
  u: upindex;
  d: downindex;

begin
  for d := succmax to twicemax do freq[d] := 1;
  for u := maxchar downto 1 do begin
    left[u] := 2 * u;
    right[u] := ( 2 * u ) + 1;
    freq[u] := freq[left[u]] + freq[right[u]];
    up[left[u]] := u;
    up[right[u]] := u;
  end;
end { initialize };
    
     ⮣, ⮡ ᪠  㪢   ᮮ⢥騩  ࢠ 
,  ⭠ ⤥쭠  , 室  -
 稭     ࠢ  㪢, ந  ᫥ -
 , ᮮ⢥饣  ⥪饩 ⪥ ॢ. ࢠ, ᮮ⢥騩
,  [0, freq[root]],   ᮤঠ f. ᫨ ⤥ 㧥 p
i 易   ࢠ [a, b),  a - b = freq[i],  ࢠ, 易묨
  ॢﬨ  ࢠ [a, a+freq[left[i]] )  [a+freq[left[i]],
b).   ᥪ, ⮬    ॢ 㤥 ⠪,  f ᮤ-
   ࢠ, 易    㧫   ⮬ .   
᫥饩 楤:

procedure findsymbol( f: integer; var c: codetype; var a, b: integer );
var
  i: downindex;
  t: integer;

begin
  a := 0;
  i := root;
  b := freq[root];
  repeat
    t := a + freq[left[i]];
    if f < t then begin { p  }
      i := left[i];
      b := t;
    end else begin  { p p }
      i := right[i];
      a := t;
    end;
  until i > maxchar;
  c := i - succmax;
end { findsymbol };
    
    ⮡   易   㪢   ࢠ, , ᠭ 
findsymbol  ந室  ⭮ ࠢ. ࢮ砫쭮 ⢥-
  ଠ樥, ⭮   㪢 㧫 ॢ i,    ⮩ 㪢 -
freq[i].   砥,  ࢠ [0, freq[i]) 㤥 ᮮ⢥⢮ -
 㪢, ᫨  䠢 ⮨   . : ࢠ [a, b) -
    ⮬ ॢ  ୥  㧫 i, ⮣   ᫥
ࢠ, 易  ⨬ ⮬  ॢ up[i]. ᫨ i -  ᫥,
        ࢠ [ a, b ), ᫨  ࠢ,  - [ a + d, b + d ), 
d = freq[up[i]] - freq[i], ,         : d = freq[left[up[i]]].

procedure findrange( c: codetype; var a, b: integer );
var
  i: downindex;
  d: integer;

begin
  a := 0;
  i := c + succmax;
  b := freq[i];
  repeat
    if right[up[i]] = i then begin { i is right child }
      d := freq[left[up[i]]];
      a := a + d;
      b := b + d;
    end;
    i := up[i];
  until i = root;
end { findrange };

    ᫨ ஡ ࠭ ᡠ஢   ॢ  
 ⮨,  㭪 update 㤥 ਢ쭮, 饩   室  ॢ 
塞     , ᮯ஢饣  㢥祭  祭 
祭  㧫  .  ⨢ 砥 ६, 祭  -
樨 findletter, findrange   update  ࢮ砫쭮  ᡠ஢ ॢ
㤥   p O(log n)    㪢  n-㪢 䠢.  ,
祬 訩 ਠ O(n), ⨣ ।⢮ ਬ   ( -
樥 move-to-front    ),    襭 .
    ,   㪢, ᦠ  䬥᪨ ⮤ ॡ -
  楤 findrange,   ᫥ 맮 update. ..   
 㪢  ॢ   㤥 த    ६ ᦠ 
  ६ ࠧ뢠.  饣 ६ ᦠ  ࠧ-
 ᮮ饭 ॡ 樨 饩   ⥩, ன  -
. ᫨  㪢  ࠭,  筮 ॢ 䬠 㤥 -
஢  ⮣ !     ᮮ饭 S 㤥 ࠭-
 祭 2(Hs(S) + C(S)),  C(S) - ⢮ 㪢  ப,  ⥫
2 ࠦ  䠪,    室 .
     ᫠   ᯮ짮  ॢ  , ᫨  -
  ࠭,   ਬ  ᪮ ⠡  
宦 ⭮⥩. ᫨  ,  ⨬ - -
    ஢  ࠢ ॢ  ,
祬   室 ॢ,    ६ ᦠ  ࠧ뢠-
  㤥 ॢ 祭 2( H (S) + C(S) ). 筮   ᯮ짮-
   饣 䨪, 饣 ࠭祭 O(H (S))  
,   襬 ﭭ ⥫.  p  १-
 뢠,   ﭭ ⥫  祬  ⮩
⬠ 饣 䨪.

                 x            w                       x - A + C        w
    A  oo            C oo
                                                                    
                                   =====>                            
                                                                    
                  B            C                          B          A + 1

         㭮 8. 㮡p  ॢ  .

     ᮮ⢥⢨  ⨬ ⬮ 樨 ७   㦭 ࠣ
ଠ樨  ७  㧫 ॢ.  ७  믮   
樨 update,     p饭  ।࠭ ਠ
ॣ㫨஢  ᮢ 㧫 ॢ.  㭪 8 ॢ p頥  ,
 १⮬ ,     ᮪頥 ᮬ    騢 ᮬ . 
  ६, ᪮    ୮     ,   㢥-
稢. ⮣  㤥:

procedure update( c: codetype );
var
  c, d: upindex   {  p頥 㧫 };
  a, b: downindex { ᫥ p饬 㧫 };

begin
  a := c + succmax;
  repeat {   ॢ, ।  騢 }
    c := up[a];
    if c # root then begin { ⠢  }
      d := up[c];
      {   ᫥  }
      b := left[d];
      if c = b then begin b := right[d];
                          right[d] := a;
      end else left[d] := a;
      if a = left[c] then left[c] := b
      else                right[c] := b;
      up[a] := d;
      up[b] := c;
      freq[c] := ( freq[c] - freq[a] ) + freq[b];
      freq[a] := freq[a] + 1;
      a := d;
    end else begin { 饭 ୮ ( ⭮ ) 㧫    }
      freq[a] := freq[a] + 1;
      a := up[a];
    end;
  until a = root;
  freq[root] := freq[root] + 1;
end { update };

    ணࠬ  ஡ ९ 稪 . 䬥-
  ᦠ⨥   ﭭ  ந ᫥   㫥 a * b / c, 
।  筮 १ ᫥ । ࠧ஬ , 뤥-
 ஬ ந   ,   ᠬ 楫᫥ ६-
.  32- 設 뢠 32-⮢ ࠭祭  ந-
  ,   ..  ᠬ  ⠭ 16-⮢ ।  ।-
⠢ 楫 ᥫ a, b  c  㪠 ࠦ.   ࠭-
 ।  ᠬ ணࠬ 娢,   १  -
࠭祭  16383  ᨬ쭮 祭, 頥 㭪樥 maxrange
  祭 freq[root]. ⮬, ᫨  ᦠ 䠩     16383
⮢, 室  ਮ᪨  뢠    , ⮡ -
      ࢠ. ⮩     ⮣ - ࠧ 祭 
   ⠭, ਬ 2,   㣫   ।࠭
  㫥.
    祭 쥢   ॢ      -
⠭   2,  祭 ७ 㧫   ⠪  -
  㤭 ࠭  㣫塞 १⮢   ॢ. -
⥩訩 ᯮᮡ ன ॢ   ᫥饩 楤:

procedure rescale;
var
  u: upindex;
  d: downindex;

begin
  for d := succmax to twicemax do
    freq[d] := ( freq[d] + 1 ) div 2;
  for u := maxchar downto 1 do begin
    left[u] := 2 * u;
    right[u] := ( 2 * u ) + 1;
    freq[u] := freq[left[u]] + freq[right[u]];
    up[left[u]] := u;
    up[right[u]] := u;
  end;
end { rescale };

         ࠪ⨪ 䬥᪨ .
                    
    H ᭮ p⬠ ⥭,   [12] 襯।⠢ 楤-
 뫨 쥤  । 몠 ᪠.   , ⥫쭮 ࠧ-
   ᦠ묨 ⥪⠬, 祭묨   १  ࠡ ࢮ砫쭮 
஢ ⬮ 䬥᪮ ᦠ   . 筮  
⥪   .

     3                                            ꥪ
                                        ⮢     
                          ᪨
       
     2 
s 10   
 
 C(S)  
     1 
       
                              o - p砫 (move-to-front).
                              o - p (pp騥 p).
     0 Ŀ
       0       1       2       3       4       5       6       7       8
                            H (S) / C(S)

         㭮 9. ࠪ⨪ ⬮ 䬥᪮ ᦠ.
        
    㭮 9 뢠 ᪮   ⬮  㭪  H . -
 ।⠢  ᥪ㭤   室 ⥪,  ய -   
  筨.   2 ⠬/  8 ⠬/ ᮧ ⢥,
 ⠫ ।⠢ ᮡ:
    - ஢ ᪨ 䠩, ᯮ騩 16 ⥭ ண 梥 
      ( 3.49 / );
    - ⥪⮢ 䠩 ( 4.91 / 室 ⥪ );
    - M68000 ꥪ 䠩 ( 6.02 / ).
६ 﫮  ࠡ祩 ⠭樨 HP9836  । HP-UX.
        㭪 9, ਬ  ७   ॢ 
 蠥  move-to-front, ᯮ㥬  ⥭,   
[12], ⮫쪮  ᦨ    ய  , 祬 6.5 /.
 ⮣ 祭 ⮤ move-to-front ᥣ ࠡ⠥   -
. .. ७  㣨 室   ஢ ॢ 
 ⭮   ࠢ뢠 p ᦠ⨨ , ᯮ  256-㪢-
 䠢. ,   뢠,    襣  䠢 p७
  訬 室.

         祭.
        
    ।⠢    塞 䨪  ⭮ -
     ⨢ ⬮ ᦠ, ᭮  ᯮ짮-
   䨪.  ࠪ  - 祭 讥 ⢮ ॡ-
    쭮 ⨢ .  㯭 訥 ꥬ ,
ᯮ짮 ⮣ ⬠     મ    ᦠ
 , 祬   騥   ⮬  ꥬ .
     २⢠ ⬠ 饣 䨪 來 ᥣ   
ᦠ⨨ ᪨ . 쭮 ஢ ࠪ ⬠ -
 ᦨ ࠦ  襬  , 祬 ᠬய, ७
 筮  筨.  ⮣,    મ, ਬ塞  -
⬥ 饣 䨪,    ⢨ 襥 ᦠ⨥, 祬
ப ᯮ㥬  -  ᮯ⠢ ꥬ .
      䬥᪮ ᦠ   믮  ६ O(H  )
  ᯮ짮  ॢ   , 㥬 ᪨
७   ॡ㥬  ⬮ ᪮  .  ᮧ -
 ࠭祭, ⮬ ⮩ ᪨ ⮤ 饭  砫 ( move
-to-front )   䥪⨢  쪨 ⨯ 䠢⮢(4).
       饣 䨪,  ᯮ짮 ७  ࠢ-
 ॢ     㦠 묨 ﬨ ਬ
७   ࠢ  ᨪp᪨ 㯮冷祭묨 ॢﬨ. 
, ।饣 ७ ॢ,   ਬ   -
᪨ ॢ, ࠢ   ⨥ 㮡p  ஢ ⠪
ॢ쥢. ਬ,   ਬ  ᫨ﭨ, p ᯮ짮 筮-
 ॢ  2- ﬨ ᫨ﭨ  ஥  n-⥢ ᫨ﭨ.  ᢠ
㦥 﫨    ࠧࠡ⪥ । ᫨ﭨ ॢ쥢  ஫-
[7].
    ᭮ ⬥,   ࠢ  㣨 ⨢묨 奬 ᦠ,
  1   ⮪ ᦠ   䮩! ⮬  p-
襭 ஡  ⠭  ⮩   ।⠢ ᮬ ,
 ஬ ⮣ ।  ᯮ짮 ⠪ 奬 ᦠ  -
⮣䨨.  ⭮,  ᦠ⨥  ᮮ饭 ।  ஢ 㢥-
 㤭 뢠   ⮬,    ᭮  -
筮 ଠ樨  ஢ ⥪,  ᦠ⨥ ᮪頥  ⢮.
 , ।⠢  ᠭ   ⬠ ᦠ, -
   ᯮ짮  砫쭮 ﭨ ॢ 䨪   砫쭮
ﭨ ॢ     ⢥   אַ ஢
  ᦠ.  䬥᪮  ᦠ  ஬ ⮣ ᫮
ࠡ 騪   ⥬,  ࠭ 㪢  易⥫쭮 室 ⠪ 
 ⠬.
    祢 ࠭⢮  ⠪ ⬠ ஢ ஬.   n 㪢
䠢  n! ⠭     C   ॢ쥢, ᮤ-
 n - 1 ७ 㧫,  C = ( 2i )! / i! ( i+1 )!   i- ᫮
⠫.  ந 頥  ( 2( n-1 ) )! / ( n-1 )!.   n = 257
( 256 㪢  ᨬ end-of-file  䠩 )  㤥 512!/256!  -
襥 2   . ⭮ 楫 ।⠢   ⮣ ࠭⢠ 㤥
  675 , ⮬ ᮬ  ⠪ 訥    ⠢ 
㯨.  ࠪ⨪    襭 㤥    砫  ࠡ   㦥
ᡠ஢ ॢ,    ᬮ७  ⬠ ᦠ,  -
⥬ ७ ⮣ ॢ   ᨬ  祢 ப, ।-
⠢ 짮⥫. p    㤥    675 , -
, ⮡   ७ ⠭ ॢ     ﭨ,
㦭      祬 ,   ⪨    -
⢨ ஢  ਥ ஢.

------------------------------------------------------------------------------
(1)     .  ⮩  p  堬 
    ਡ  ᬠਢ.
(2)  [9]  砥 ன⢥ ॠ樨 室 譨   㧥, ⮡
    ⫨ ⮫쪮  ᫥   ⮫쪮  ࠢ,  ᪮ ॢ 
     䨪 楫 筮,     㦥.
(3) ६   ⠭  ᨢ     0  255 
      1  256,        ⬠.
(4)    쭡᪮ 㭨 ᨬ ⨣   -
    ⮢ ᯮ   뢥  ⭮   ਠ-
    .


         .

1.  Bently,J.l., Sleator,D.D., Tarjan,R.E., and Wei,V.K.
    A locally adaptive data compression scheme.
    Communications of the ACM. 29, 4 ( Apr. 1986 ), 320-330.
2.  Gallagen,R.G. 
    Information Theory and Reliable Communication.
    John Wiley & Sons, New York, 1968.
3.  Gallager,R.G.
    Variations on a theme by Huffman.
    IEEE Trans.Inform.Theory IT-24, 6 ( Nov.1978 ), 666-674.
4.  Jones,D.W.
    An empirical comparison of priority queue and set inplementations.
    Communication of the ACM. 29, 4 ( Apr. 1986 ), 300-311.
5.  Knuth,D.E.
    Dynamic Huffman coding.
    J.Algorithms 6, 2 ( Feb. 1985 ), 163-180.
6.  Rubin,F.
    Arithmetic stream coding using fixed precision registers.
    IEEE Trans.Inform.Theory IT-25, 6 ( Nov. 1979 ), 672-675.
7.  Saraswat,V.
    Merge trees using splaying - or how to splay in parralel and bottom-up.
    PROLOG Digest 5, 22 ( Mar. 27, 1987 ).
8.  Sleator,D.D., and Tarjan,R.E.
    Self-adjusting binary trees.
    In Proceedings of the ACM SIGACT Symposium on Theory of Computing
    ( Boston, Mass., Apr.25-27 ).ACM, New York, 1983, pp.235-245.
9.  Tarjan,R.E., and Sleator,D.D.
    Self-adjusting binary search trees.
    J.ACM 32, 3 ( July 1985 ), 652-686.
10. Vitter,J.S.
    Two papers on dynamic Huffman codes.
    Tech.Rep.CS-85-13.Brown University Computer Science,
    R.I. Revised Dec.1986.
11. Welch,T.A.
    A technique for high-performance data compression.
    IEEE Comput. 17, 6 ( June 1984 ), 8-19.
12. Witten,I.H.,Neal,R.M., and Cleary,J.G.
    Arithmetic coding for data compression.
    Communication of the ACM. 30, 6 ( June 1987 ), 520-540.