Реферат - Реалізація ідеї арифметичного кодування
19

7 >A=>2>N 10, 1> 28I5=02545=5 :>4C20==O 28:>=C20;>AO 4;O 45AOB:>28E G8A5;). &5 ?>OA=NT, G><C ?>B@V1=> 5 45AOB:>28E F8D@ 4;O :>4C20==O FL>3> B5:ABC. "0:8< G8=><, H8@8=0 ?V4AC<:>2>3> V=B5@20;C T 0,2336 0, 23354 = 0,00006, 0 5=B@>?VO 2V4 T<=89 45AOB:>289 ;>30@8D< FL>3> G8A;0. 28G09=> <8 ?@0FNT<> 7 42V9:>2>N 0@8D<5B8:>N, ?5@540T<> 42V9:>2V G8A;0 B0 28<V@NT<> 5=B@>?VN 2 1VB0E. OB8 45AOB:>28E F8D@ 740TBLAO 701030B> 4;O :>4C20==O B5:ABC 7 G>B8@L>E 3>;>A=8E! 01CBL =5 7>2AV< 240;> 1C 70:V=GC20B8 ?@8:;04 @>73>@B0==O<, 0 =5 7B8A:0==O<. 4=0: 7@>7C<V;>, I> @V7=V <>45;V 40NBL @V7=C 5=B@>?VN. @0I0 <>45;L, ?>1C4>20=0 =0 0=0;V7V >:@5<8E A8<2>;V2 B5:ABC 50VV! , T B0:0 <=>68=0 G0AB>B A8<2>;V2: 5 (0,2), 0 (0,2), V (0,4), ! (0,2) . >=0 40T 5=B@>?VN, I> 4>@V2=NT 2,89 2 45AOB:>2V9 A8AB5<V 2V4;V:C, B>1B> :>4CT 28EV4=89 B5:AB G8A;>< 7 B@L>E F8D@. 4=0:, 1V;LH A:;04=V <>45;V, O: 2V4<VG0;>AO @0=VH5, 40NBL 2 7030;L=><C 28?04:C =01030B> :@0IV9 @57C;LB0B.3. @>3@0<0 4;O 0@8D<5B8G=>3> :>4C20==O.0 @8AC=:C 1 ?>:070=> D@03<5=B ?A524>:>4C, O:89 ?>T4=CT ?@>F54C@8 :>4C20==O B0 45:>4C20==O, O:V 1C;> 28:;045=> 2 ?>?5@54=L><C @>74V;V. !8<2>;8 2 =L><C =C<5@CNBLAO O: 1, 2, 3& '0AB>B=89 V=B5@20; 4;O V-B>3> A8<2>;C 7040TBLAO 2V4 cum_freeq[i] 4> cum_freeq[i-1]. @8 7<5=H5==V V cum_freeq[i] 7@>AB0T B0:, I> cum_freeq[0] = 1. (@8G8=0 B0:>3> 72>@>B=L>3> 4>3>2>@C ?>;O30T 2 B><C, I> cum_freeq[0] 1C45 ?>BV< <VAB8B8 =>@<0;V7CNG89 <=>6=8:, O:89 7@CG=> 715@V30B8 =0 ?>G0B:C <0A82C). >B>G=89 @>1>G89 V=B5@20; 7040TBLAO 2 [low; high] V 1C45 2 A0<><C ?>G0B:C 4>@V2=N20B8 [0; 1) V 4;O :>4C20;L=8:0, V 4;O 45:>4C20;L=8:0.0 60;L, F59 ?A524>:>4 7=0G=> A?@>I5=89, B>4V O: 2 ?@0:B8G=><C 70AB>AC20==V VA=CT 45:V;L:0 G8==8:V2, O:V CA:;04=NNBL V :>4C20==O, V 45:>4C20==O.3.1 ;3>@8B< 0@8D<5B8G=>3> :>4C20==O./* :>6=8< =0ABC?=8< A8<2>;>< B5:ABC 725@B0B8AO *//*4> ?@>F54C@8 encode_symbol() *//*5@52V@8B8, I> B5@<V=0;L=89 A8<2>; 70:>4>20=89 >AB0==V<*//*825AB8 >45@60=5 7=0G5==O V=B5@20;C [low; high) */encode_symbol(symbol, cum_freq)range = high lowhigh = low + range*cum_freq[symbol - 1]low = low + range*cum_freq[symbol]3.2 ;3>@8B< 0@8D<5B8G=>3> 45:>4C20==O./* Value F5 G8A;>, O:5 >45@60=> =0 2EV4*//*25@B0==O 4> ?@>F54C@8 decode_symbol() 4> B>3> <><5=BC*//*?>:8 2>=0 =5 ?>25@=5 B5@<V=0;L=89 A8<2>;*/decode_symbol(cum_freq)?>HC: B0:>3> A8<2>;C, I>cum_freq[symbol] <= (value - low) / (high - low) < cum_freq[symbol - 1]/*F5 70157?5GCT @>7<VI5==O Value 2 <560E =>2>3> V=B5@20;C*//*[low; high], I> 2V4>1@065=> 2 7025@H5==V ?@>3@0<8*/range = high lowhigh = low + range*cum_freq[symbol - 1]low = low + range*cum_freq[symbol]return symbol 8AC=>: 1. A524>:>4 0@8D<5B8G=>3> :>4C20==O B0 45:>4C20==O.4. 0C2065==O 4> @50;V70FVW.4.1 @8@>IC20=V ?5@540G0 V >B@8<0==O V=D>@<0FVW.02545=89 0;3>@8B< :>4C20==O =VG>3> =5 ?5@540T 4> ?>2=>3> 7025@H5==O :>4C20==O 2AL>3> B5:ABC, 0 B0:>6 V 45:>4C20;L=8: =5 ?>G8=0T F59 ?@>F5A, ?>:8 =5 >B@8<0T AB8A=5=89 B5:AB FV;:><. ;O 1V;LH>ABV 28?04:V2 =5>1EV45= ?>5B0?=89 @568< 28:>=0==O .4.2 060=5 28:>@8AB0==O FV;>G8A;5=>W 0@8D<5B8:8.>B@V1=0 4;O ?@54AB02;5==O V=B5@20;C [low; high] B>G=VABL 7@>AB0T @07>< 7 4>268=>N B5:ABC. >5B0?=5 28:>=0==O 4>?><030T 28@VH8B8 FN ?@>1;5<C, 0;5 28<030T ?@8 FL><C C206=>3> >1;V:C <>6;82>3> ?5@5?>2=5==O B0 2V4 T<=>3> ?5@5?>2=5==O.4.3 D5:B82=0 @50;V70FVO <>45;V. 50;V70FVO <>45;V ?>28==0 <V=V<V7C20B8 G0A 287=0G5==O =0ABC?=>3> A8<2>;C 0;3>@8B<>< 45:>4C20==O. @V< B>3>, 040?B82=V <>45;V ?>28==V B0:>6 <V=V<V7C20B8 G0A, O:89 28<030TBLAO 4;O ?V4B@8<0==O =0:>?8G5=8E G0AB>B.5. 50;V70FVO <>45;V.!0<0 @50;V70FVO 1C45 >13>2>@N20B8AO 2 =0ABC?=><C @>74V;V, 0 BCB B@510 ;8H5 B>@:=CB8AO BV;L:8 V=B5@D59AC 7 <>45;;N. /: 2V4><>, 109B ?@54AB02;OT A>1>N FV;5 G8A;> 2V4 0 4> 255 (B8? char). "CB <8 ?@54AB02;OT<> 109B O: FV;5 G8A;> 2V4 1 4> 257 2:;NG=> (B8? index), 45 EOF B@0:BCTBLAO O: 257-9 A8<2>;. C;> 1 4>1@5 2V4A>@BC20B8 <>45;L 2 ?>@O4:C 7<5=H5==O G0AB>B 4;O <V=V<V70FVW :V;L:>ABV 28:>=0==O F8:;C 45:>4C20==O. 5@5B2>@5==O 7 B8?C char 2 index, B0 =02?0:8, @50;V7>20=> 70 4>?><>3>N 42>E B01;8FL index_to_char[] i char_to_index[]. 040?B82=V9 <>45;V 28:>=CTBLAO ?5@5:>4C20==O, O:5 ?@8A2>NT =09G0ABVH8< A8<2>;0< <0;5=L:V V=45:A8.<>2V@=>ABV ?@54AB02;ONBLAO 2 <>45;V O: FV;>G8A5;5=V ;VG8;L=8:8 G0AB>B, 0 =0:>?8GC20=V G0AB>B8 715@V30NBLAO 2 <0A82V cum_freq[]. /: V 2 ?>?5@54=L><C 28?04:C, F59 <0A82 72>@>B=V9 , V ;VG8;L=8: 7030;L=>W G0AB>B8, O:89 28:>@8AB>2CTBLAO 4;O =>@<0;V70FVW 2AVE G0AB>B, @>7<VICTBLAO 2 cum_freq[0]. 0:>?8GC20=V G0AB>B8 =5 ?>28==V ?5@528IC20B8 2AB0=>2;5==89 2 Max_frequency <0:A8<C<, 0 @50;V70FVO <>45;V ?>28==0 70?>1V30B8 ?5@5?>2=5==N 2V4?>2V4=8< <0HB01C20==O<. 5>1EV4=> B0:>6 ?@8=09<=V =0 1 70157?5G8B8 @V7=8FN <V6 42><0 ACAV4=8<8 7=0G5==O<8 cum_freq[], 2 ?@>B82=><C 28?04:C A8<2>;, I> ?5@53;O40TBLAO, =5 1C45 ?5@540=89.6. >2545==O ?@028;L=>ABV 45:>4C20==O.5@52V@8<> ?@028;L=VABL 287=0G5==O ?@>F54C@>N decode_symbol() =0ABC?=>3> A8<2>;C. ?A524>:>4C =0 @8AC=:C 1 7@>7C<V;>, I> decode_symbol() ?>28==0 28:>@8AB>2C20B8 Value 4;O ?>HC:C A8<2>;0, O:89 ?@8 :>4C20==V A:>@>B82 @>1>G89 V=B5@20; B0:, I> 2V= ?@>4>26CT 2:;NG0B8 2 A515 Value. @>1>GV9 ?@>3@0<V 2 decode_symbol() 287=0G0TBLAO B0:89 A8<2>;, 4;O O:>3>:cum_freq [symbol] ( (((value low +1)*cum_freq [0] 1)/(high low + 1) ( < cum_freq [symbol - 1], 45 ( ( >7=0G0T >?5@0FVN 27OBBO FV;>W G0AB8=8 4V;5==O 7 2V4:840==O< 4@>1>2>W G0AB8=8. >:070=>, I> F5 ?5@5410G0T: low + ( ((high - low + 1)*cum_freq [symbol]) / cum_freq [0] ( ( value ( low + ( ((high low +1)*cum_freq [symbol - 1]) / cum_freq [0](, B0:8< G8=><, I> value =0;568BL =>2><C V=B5@20;C, O:89 28@0E>2CTBLAO ?@>F54C@>N decode_symbol(). &5 30@0=BCT :>@5:B=VABL 287=0G5==O :>6=>3> A8<2>;C >?5@0FVT9 45:>4C20==O.7. @>1;5<0 ?5@5?>2=5==O V 7025@H5==O :>4C20==O.7.1 V4 T<=5 ?5@5?>2=5==O./: ?>:070=> 2 ?A524>:>4V, 0@VD<5B8G=5 :>4C20==O ?@0FNT 70 4>?><>3>N <0AHB01C20==O =0:>?8G5=8E 9<>2V@=>AB59, O:V =040NBLAO <>45;N 2 V=B5@20;V [low; high] 4;O :>6=>3> A8<2>;C, I> ?5@540TBLAO. @8?CAB8<>, I> low i high B0: 1;87L:V >48= 4> >4=>3>, I> >?5@0FVO <0AHB01C20==O ?@872>48BL >45@60=V 2V4 <>45;V @V7=V A8<2>;8 4> >4=>3>

---

Сторінки: 1 2 3 4 5 6