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

4>@V2=NT 5=B@>?VW FL>3> B5:ABC 2V4=>A=> 28:>@8AB0=>W 4;O :>4C20==O <>45;V. "@8 G8==8:0 28:;8:0NBL ?>3V@H5==O FVTW E0@0:B5@8AB8:8: 2840B:8 =0 7025@H5==O B5:ABC; 28:>@8AB0==O 0@8D<5B8:8 7 :V=F52>N B>G=VABN; B0:5 <0AHB01C20==O ;VG8;L=8:V2, I> WE AC<0 =5 ?5@528ICT Max_frequency./: 1C;> ?>:070=>, 6>45= 7 =8E =5 T 7=0G=8<. ?>@O4:C 284V;5==O @57C;LB0BV2 0@8D<5B8G=>3> :>4C20==O, <>45;L 1C45 @>73;O40B8AO O: AC2>@0 (2 287=0G5=><C 28I5 A5=AV). @8D<5B8G=5 :>4C20==O ?>28==5 4>A8;0B8 4>40B:>2V 1VB8 2 :V=5FL :>6=>3> B5:ABC, 74V9A=NNG8 B0:8< G8=>< 4>40B:>2V 7CA8;;O =0 7025@H5==O B5:ABC. ;O ;V:2V40FVW =5?>@>7C<V==O 7 >AB0==V< A8<2>;>< ?@>F54C@0 done_encoding () ?>A8;0T 420 1VB8. 28?04:C, :>;8 ?5@54 :>4C20==O< ?>B>: 1VBV2 <0T 1;>:C20B8AO 2 8-1VB>2V A8<2>;8, 1C45 =5>1EV4=> 7025@HC20B8 4> :V=FO 1;>:C. "0:5 :><1V=C20==O <>65 4>40B:>2> ?>B@V1C20B8 9 1VBV2. 840B:8 ?@8 28:>@8AB0==V 0@8D<5B8:8 7 >1<565=>N B>G=VABN ?@>O2;ONBLAO 2 7<5=H5=V 70;8H:V2 ?@8 4V;5==V. &5 284=> ?@8 ?>@V2=O==V 7 B5>@5B8G=>N 5=B@>?VTN, O:0 282>48BL G0AB>B8 V7 ;VG8;L=8:V2, O:V B0:8< A0<5 G8=>< <0AHB01CNBLAO ?@8 :>4C20==V. "CB 2840B:8 =57=0G=V ?>@O4:C 10^-4 1VBV2 / A8<2>;. >40B:>2V 2840B:8 =0 <0AHB01C20==O ;VG8;L=8:V2 45I> 1V;LHV, 0;5 2A5 >4=> 4>A8BL <0;V. ;O :>@>B:8E B5:ABV2 (<5=H8E 2^14 109B) WE =5<0T. ;5 =02VBL 7 B5:AB0<8 2 10^5 10^6 109BV2 =0:;04=V 2840B:8, ?V4@0E>20=V 5:A?5@8<5=B0;L=>, A:;040NBL <5=H5 0,25% 2V4 @O4:0, H> :>4CTBLAO.40?B82=0 <>45;L 2 ?@>3@0<V, ?@8 703@>7V ?5@528I5==O 7030;L=>N AC<>N =0:>?8G5=8E G0AB>B 7=0G5==O Max_frequency, 7<5=HCT 2AV ;VG8;L=8:8. &5 ?@872>48BL 4> B>3>, I> 7206C20B8 >AB0==V ?>4VW 206G5, =V6 1V;LH @0==V. "0:8< G8=><, ?>:07=8:8 <0NBL B5=45=FVN ?@>A;V4:>2C20B8 7<V=8 C 2EV4=V9 ?>A;V4>2=>ABV, O:V <>4CBL 1CB8 4C65 :>@8A=8<8 (2V4><V 28?04:8, :>;8 >1<565==O ;VG8;L=8:V2 4> 6-7 1VBV2 4020;> :@0IV @57C;LB0B8, =V6 ?V428I5==O B>G=>ABV 0@8D<5B8:8). 28G09=>, F5 70;568BL 2V4 465@5;0, 4> O:>3> 70AB>A>2CTBLAO <>45;L.10. 0AB>AC20==O 0@8D<5B8G=>3> :>4C20==O.10.1 >4C20==O G>@=> 1V;8E 7>1@065=L.0AB>AC20==O 7 FVTN <5B>N 0@8D<5B8G=>3> :>4C20==O @>73;O40;>AO 0=34>=>< B0 8AA0=5=><, I> >B@8<0;8 ?@8 FL><C GC4>2V @57C;LB0B8 70 4>?><>3>N <>45;V, I> 28:>@8AB>2CT >FV=:C 9<>2V@=>ABV :>;1>@C B>G:8 2V4=>A=> 45O:>3> H01;>=C, I> WW >B>GCT. V= O2;OT A>1>N AC:C?=VABL 7 10 B>G>:, I> ;560BL 725@EC B0 A?5@54C 2V4 ?>B>G=>W, B><C ?@8 A:0=C20==V @0AB@C 2>=8 W9 ?5@54CNBL. &5 40T 1024 <>6;828E :>=B5:ABC, 2V4=>A=> O:8E, 9<>2V@=VABL G>@=>3> :>;V@C 2 40=V9 B>GFV >FV=NTBLAO 040?B82=> ?> <V@V ?5@53;O4C 7>1@065==O. VA;O G>3> :>6=0 ?>;O@=VABL B>G:8 :>4C20;0AO 0@8D<5B8G=8< <5B>4>< 2V4?>2V4=> 7 FVTN 9<>2V@=VABN. "0:89 ?V4EV4 ?>:@0I82 AB8A:0==O =0 20 30% ?>@V2=O=> 7 1V;LH @0==V<8 <5B>40<8. ;O 71V;LH5==O H284:>ABV :>4C20==O 0=34>= B0 8AA0=5= 70AB>AC20;8 ?@81;87=89 <5B>4 0@8D<5B8G=>3> :>4C20==O, O:89 >1V9H>2 >?5@0FVW <=>65==O H;OE>< ?@54AB02;5==O 9<>2V@=>AB59 2 283;O4V FV;8E ABC?5=V2 4@>1C 1/2/. >4C20==O %0DD<0=0 4;O FL>3> 28?04:C =5 <>65 1CB8 28:>@8AB0=> =0?@O<C, >A:V;L:8 2>=> =V:>;8 =5 28:>=CT AB8A=5==O 42>EA8<2>;L=>3> 0;D02VBC. =HC <>6;82VABL 4;O 0@8D<5B8G=>3> :>4C20==O, I> 70AB>A>2CTBLAO 4;O B0:>3> 0;D02VBC, 40T ?>?C;O@=89 <5B>4 :>4C20==O 4>268= B8@06V2 (run-length method). >45;L BCB ?@82>48BL 40=V 4> ?>A;V4>2=>ABV 4>268= A5@V9 >4=0:>28E A8<2>;V2 (=0?@8:;04, 7>1@065==O ?@54AB02;OTBLAO 4>268=0<8 ?>A;V4>2=>AB59 G>@=8E B>G>:, O:V 94CBL 70 1V;8<8, O:V A;V4CNBL 70 G>@=8<8, O:8< ?5@54CNBL 1V;8< V B. 4.). 2 @57C;LB0BV ?>28==0 1CB8 ?5@540=0 ?>A;V4>2=VABL 4>268=. !B0=40@B D0:A8<V;L=8E 0?0@0BV2 !!"" 1C4CT :>4 %0DD<0=0 =0 >A=>2V G0AB>B, 7 O:8<8 G>@=V V 1V;V ?>A;V4>2=>ABV @V7=8E 4>268= 7 O2;ONBLAO 2 7@07:0E 4>:C<5=BV2. $V:A>20=5 0@8D<5B8G=5 :>4C20==O, O:5 1C45 28:>@8AB>2C20B8 BV 6 A0<V G0AB>B8, 1C45 <0B8 :@0IV E0@0:B5@8AB8:8, 0 040?B0FVO B0:8E G0AB>B 4;O :>6=>3> >:@5<>3> 4>:C<5=BC 1C45 ?@0FN20B8 I5 :@0I5.10.2 >4C20==O 4>2V;L=> @>7?>4V;5=8E FV;8E G8A5;.>=> G0AB> @>73;O40TBLAO =0 >A=>2V 70AB>AC20==O 1V;LH A:;04=8E <>45;59 B5:ABV2, 7>1@065=OL 01> V=H8E 40=8E. >73;O=5<>, =0?@8:;04, ;>:0;L=> 040?B>20=C AE5<C AB8A:0==O 5=B;V B0 V=., 45 :>4C20==O B0 45:>4C20==O ?@0FNT 7 N >AB0==V<8 @V7=8<8 A;>20<8. !;>2>, I> 7=0E>48BLAO 2 :5H-1CD5@V, 287=0G0TBLAO ?> FV;>G8A5;L=><C V=45:AC 1CD5@0. !;>2>, O:5 2 =L><C =5 7=0E>48BLAO, ?5@540TBLAO 2 :5H-1CD5@ G5@57 ?5@5A8;0==O 9>3> <0@:5@0, O:89 945 =0ABC?=8< 70 A0<8<8 A8<2>;0<8 FL>3> A;>20. &5 GC4>20 <>45;L 4;O B5:ABC, 2 O:><C A;>20 G0AB> 28:>@8AB>2CNBLAO =0 ?@>BO7V 45O:>3> :>@>B:>3> G0AC, 0 ?>BV< 265 4>23> =5 28:>@8AB>2CNBLAO. E AB0BBO >13>2>@NT 45:V;L:0 :>4C20=L 7<V==>W 4>265=8 265 4;O FV;>G8A5;L=8E V=45:AV2 :5H-1CD5@0. O:>ABV >A=>28 4;O :>4V2 7<V==>W 4>268=8 0@VD<5B8G=89 <5B>4 4>72>;OT 28:>@8AB>2C20B8 1C4L-O:5 @>7?>4V;5==O 9<>2V@=>AB59, 2 B><C G8A;V A5@54 1030BL>E V=H8E 9 BV, O:V =02045=V BCB. @V< B>3>, 2V= 4>?CA:0T 4;O V=45:AV2 :5H-1CD5@0 70AB>AC20==O 040?B82=>W <>45;V, I> T 1060=8< C 28?04:C, :>;8 @>7?>4V;5==O 4>ABC?V2 4> :5H-1CD5@C 206:>?5@5410GC20=5.>40B>: 1. >2545==O 45:>4CNG>W =5@V2=>ABV. 2060T<>:EMBED Unknown01> V=H8<8 A;>20<8:EMBED Unknown45 range = high low + 1, EMBED Unknown (1)(>AB0==O =5@V2=VABL 28@07C (1) ?>E>48BL 2V4 B>3> D0:BC, I> cum_freq[symbol - 1] ?>28==5 1CB8 FV;8<). >BV< <8 E>G5<> ?>:070B8, I> low ( value ( high , 45 low i high T >=>2;5=V 7=0G5==O 4;O low i high O: F5 287=0G5=> =86G5.(0) low : EMBED Unknown 28@07C (1) <0T<>: EMBED Unknown, B><C low ( value, B><C I> V value, i low, i cum_freq [0] > 0.(0) high:EMBED Unknown 28@07C (1) <0T<>:EMBED Unknown.>40B>: 2. >1>G89 :>4 4;O 040?B82=>3> 0@8D<5B8G=>3> AB8A:0==O.Arithmetic_coding.h/*3>;>H5==O, =5>1EV4=V 4;O 0@8D<5B8G=>3>*//*:>4C20==O B0 45:>4C20==O*//*=B5@20; 7=0G5=L 0@8D<5B8G=>3> :>4C*/#define Code_value_bits 16typedef long code_value;#define Top_value (((long) 1 << Code_value_bits) - 1)/*:07V2=8:8 =0 A5@548=C V G5B25@BV V=B5@20;0 7=0G5==O :>4C*/#define First_qtr (Top_value/4 + 1)#define Half (2*First_qtr)#define Third_qtr (3*First_qtr)model.h/* =B5@D59A 7 <>45;;N *//* =>68=0 :>4CT<8E A8<2>;V2 */#define No_of_chars 256#define EOF_symbol (No_of_chars + 1)#define No_of_symbols (No_of_chars + 1)/* "01;8FV ?5@5:>4C20==O ?>G0B:>28E B0 @>1>G8E A8<2>;V2 */int char_to_index[No_of_chars];unsigned

---

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