Open Library është një bibliotekë e hapur e informacionit arsimor. Teoria e informacionit

Tani ka shumë algoritme për kompresimin e informacionit. Shumica e tyre njihen gjerësisht, por ka edhe disa algoritme shumë efektive, por, megjithatë, pak të njohur. Ky artikull flet për metodën e kodimit aritmetik, e cila është më e mira nga ato të entropisë, por megjithatë shumë pak njerëz dinë për të.
Para se të flas për kodimin aritmetik, më duhet të them disa fjalë për algoritmin Huffman. Kjo metodë është efektive kur normat e simboleve janë proporcionale me 1/2 n (ku n është një numër i plotë pozitiv pozitiv). Kjo deklaratë bëhet e qartë kur kujtoni se kodet Huffman për çdo karakter gjithmonë përbëhen nga një numër i plotë bitash. Le të shqyrtojmë situatën kur frekuenca e shfaqjes së një simboli është 0.2, atëherë kodi optimal për kodimin e këtij simboli duhet të ketë një gjatësi prej –log 2 (0.2) = 2.3 bit. Është e qartë se kodi i prefiksit Huffman nuk mund të ketë këtë gjatësi, d.m.th. kjo përfundimisht çon në kompresim të dobët të të dhënave.
Kodimi aritmetik është krijuar për të zgjidhur këtë problem. Ideja kryesore është që të caktohen kodet jo për karakteret individuale, por për sekuencat e tyre.
Së pari, ne do të shikojmë idenë që qëndron pas algoritmit, më pas do të shohim një shembull të vogël praktik.
Si në të gjitha algoritmet e entropisë, ne kemi informacion për shpeshtësinë e përdorimit të çdo karakteri të alfabetit. Ky informacion është burimi për metodën e konsideruar. Tani le të prezantojmë konceptin e një segmenti fllanxhe. Një gjysmë-interval quhet punëtor. Sa numra heksadecimal treshifrorë ekzistojnë për të cilët do të ketë në të njëjtën kohë

Leksioni 13 Teknikat dhe metodat e punës me të dhëna të ngjeshura Ligjërues Art. mësuesi Coupeau A.N. Një tipar karakteristik i shumicës së llojeve të të dhënave "klasike" me të cilat njerëzit punojnë tradicionalisht është i sigurt

Institucioni Buxhetor Arsimor Federal Shtetëror i Arsimit të Lartë Profesional Povolzhskiy Universiteti Shtetëror i Telekomunikacionit dhe Informatikës Departamenti i SARS Caktimi dhe metodologjik

UDC 519.6 Veçoritë e kodimit të tekstit duke përdorur algoritmin Huffman Kizyanov Anton Olegovich Priamursky University State me emrin Sholem Aleichem Student Kuzmina Bogdana Sergeevna Priamursky

PUNA LABORATORIKE Metodat e vendosjes dhe karakteristikat themelore të kodeve konvolucionale Kodet konvolucionale përdoren gjerësisht në fusha të ndryshme të teknologjisë së transmetimit dhe ruajtjes së informacionit. Më ilustruese

UDC 004.8 APLIKIMI I NJË ALGORITMI GJENETIK PËR MENAXHIMIN E DIZAJNIT TË ORARIT SHKOLLOR Gushchina O. A. Algoritmi gjenetik (GA) algoritmi i kërkimit adaptiv i bazuar në faktorë evolucionar

Matematika diskrete Pjesa 2 Kochetov Yuri Andreevich http://www.math.nsc.ru/lbrt/k5/dm.html Leksion 1 Algoritmet, renditja, pemët AVL 1 Algoritmet dhe kompleksiteti i tyre Kompjuterët performojnë (deri më tani) vetëm saktë

Metoda e Huffman-it është e thjeshtë, por efektive vetëm kur probabilitetet e shfaqjes së simboleve janë të barabarta me numrat, ku është çdo numër i plotë pozitiv. Kjo është për shkak se kodi Huffman cakton një numër të plotë bitesh për çdo karakter në alfabet. Në të njëjtën kohë, në teorinë e informacionit dihet se, për shembull, kur probabiliteti i shfaqjes së një simboli është i barabartë me 0.4, në mënyrë ideale duhet t'i jepet një kod gjatësie. pak. Është e qartë se gjatë ndërtimit të kodeve Huffman, gjatësia e kodit nuk mund të vendoset në 1.32 bit, por vetëm në 1 ose 2 bit, gjë që do të rezultojë në kompresim të dobët të të dhënave. Kodimi aritmetik e zgjidh këtë problem duke i caktuar një kod të gjithë skedarit, zakonisht të madh, të transmetuar, në vend që të kodojë karaktere individuale.

Ideja e kodimit aritmetik ilustrohet më së miri me një shembull të thjeshtë. Supozoni se është e nevojshme të kodohen tre karaktere të rrymës hyrëse, për saktësi, ky është vargu SWISS_MISS me frekuencat e specifikuara të karaktereve: S - 0.5, W - 0.1, I - 0.2, M - 0.1 dhe _ - 0, 1. Në një kodues aritmetik, çdo karakter përfaqësohet nga një interval në një varg numrash), dhe intervali për simbolin e i-të të rrymës së koduar si; B [c]), duke përfshirë 0.341. Duke numëruar të gjitha simbolet e mundshme sipas tabelës së mësipërme, gjejmë se vetëm intervali është (fti-j - li-i); përshëndetje= li.!+ b ■ (hi.! - li.i); nëse ((l t<= value) && (value < përshëndetje)) pushim; ); DataFile.WriteSymbol (c ^);

ku vlera është numri (fraksioni) i lexuar nga rryma, dhe me - karaktere të papaketuara të shkruara në rrjedhën dalëse. Kur përdorni një alfabet prej 256 karakteresh Cj laku i brendshëm kërkon shumë kohë për t'u përfunduar, por ju mund ta shpejtoni atë. Vini re se që nga B [c ^ (\ = a; II delitel = 10

First_qtr - (h 0 + l) / 4; // - 16384

Gjysma = First_qtr * 2; // - 32768

Third_qtr - First_qtr * 3; // = 49152

bit_për_ndjekim = 0; // Sa bit për të pastruar

ndërsa (jo DataFile.EOFO) (

c = DataFile.ReadSymbol (); // Lexoni simbolin
j= IndexForSymbol (s); i ++; // Gjeni indeksin e tij
li= li.j + b * (h i. 1 - li-x+ l) / delitel;
përshëndetje= li.!+ b;
First_qtr = (h 0 + l) / 4; // = 16384

Gjysma = First_qtr * 2; // = 32768

Third_qtr = First_qtr * 3; // = 49152

vlera = CompressedFile.Readl6Bit ();

për (i = l; i< CompressedFile.DataLengthO; i++){

frekuencë = ((vlera-2 i. 1 + l) * delitel-l) / (h i. I - 1 ±. NS+ 1) ;

për (j = l; b<=freq; j++); // Поиск символа

li = 1y+ blj-l] * (bi.!- li- u + l) / delitel;

përshëndetje= Une jam+ b * (h i. 1 - li.!+ l) / delitel - 1;

për (;;) (// Opsionet e procesit

nëse (përshëndetje< Half) // переполнения

; // Asgjë tjetër ifdi> = Gjysma) (

2i- = Gjysma; hi- = Gjysma; vlera- = Gjysma; )

ndryshe nëse (di> = First_qtr) && (hi< Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2 i; hi+= hi+1;

vlera + = vlera + CompressedFile.ReadBit (); } DataFile.WriteSymbol (c);

Ushtrimi. Sugjeroni shembuj të sekuencave të ngjeshura nga algoritmi me koeficientët maksimal dhe minimal.

Siç mund ta shihni, ne luftojmë me pasaktësitë aritmetike duke kryer operacione të veçanta në /, dhe A, në mënyrë sinkronike në kompresor dhe dekompresor.

Humbje e parëndësishme e saktësisë (fraksione të përqindjes për një skedar mjaftueshëm të madh) dhe, në përputhje me rrethanat, një rënie në raportin e kompresimit në krahasim me algoritmin ideal ndodh gjatë operacionit të ndarjes, kur frekuencat relative rrumbullakosen në një numër të plotë, kur i fundit bit janë shkruar në skedar. Algoritmi mund të përshpejtohet duke paraqitur frekuencat relative në mënyrë që pjesëtuesi të jetë një fuqi prej dy (d.m.th., duke zëvendësuar ndarjen me një veprim zhvendosjeje bit).

Për të vlerësuar raportin e kompresimit me algoritmin aritmetik të një vargu të caktuar, duhet të gjeni numrin minimal N, e tillë që gjatësia e intervalit të punës gjatë ngjeshjes së karakterit të fundit të zinxhirit do të ishte më e vogël se 1/2 ^ .. Ky kriter do të thotë se brenda intervalit tonë sigurisht që ekziston të paktën një numër në paraqitjen binar të të cilit pas N-ro do të ketë vetëm shenja 0. Gjatësia e intervalit është e lehtë për t'u lexuar, pasi është e barabartë me produktin e probabiliteteve të të gjitha simboleve.

Merrni parasysh shembullin e mëparshëm të një vargu me dy karaktere l dhe B me probabilitete 253/256 dhe 3/256. Gjatësia e intervalit të fundit të punës për një varg 256 karakteresh a dhe B me probabilitetet e treguara të barabarta. Është e lehtë të llogaritet se nevoja N = 24 (1/2 24 = 5.96-10 "8), pasi 23 jep një interval shumë të madh (2 herë më të gjerë), dhe 25 nuk është minimale një numër që plotëson kriterin. Më sipër u tregua se algoritmi Huffman e kodon këtë varg në 256 bit. Kjo do të thotë, për shembullin e konsideruar, algoritmi aritmetik jep një avantazh dhjetëfish mbi algoritmin Huffman dhe kërkon më pak se 0.1 bit për karakter.

Ushtrimi. Llogaritni vlerësimin e raportit të ngjeshjes për linjën "COV.KOROBA".

Duhet thënë disa fjalë për algoritmin e kompresimit aritmetik adaptiv. Ideja e tij është të rindërtojë tabelën e probabilitetit b [f] gjatë paketimit dhe shpaketimit menjëherë pas marrjes së personazhit tjetër. Një algoritëm i tillë nuk kërkon ruajtjen e vlerave të probabiliteteve të karaktereve në skedarin e daljes dhe, si rregull, jep një raport të lartë kompresimi. Kështu, për shembull, një skedar si një skedar 1000 £ 1000 me 1000 b / 1000 (ku shkalla nënkupton numrin e përsëritjeve të një karakteri të caktuar) algoritmi adaptiv do të jetë në gjendje të kompresojë në mënyrë më efikase sesa të shpenzojë 2 bit për karakter. Algoritmi i mësipërm thjesht shndërrohet në një përshtatës. Më parë, ne e ruanim tabelën e diapazoneve në një skedar, dhe tani ne llogarisim drejtpërdrejt në rrjedhën e kompresorit dhe dekompresorit, rillogaritim frekuencat relative, duke rregulluar tabelën e diapazonit në përputhje me to. Është e rëndësishme që ndryshimet në tabelë të ndodhin në kompresor dhe dekompresor në mënyrë sinkrone, d.m.th., për shembull, pas kodimi zinxhirët me gjatësi 100, tabela e diapazonit duhet të jetë saktësisht e njëjtë si pas dekodimi zinxhirë me gjatësi 100. Ky kusht plotësohet lehtë nëse ndryshon tabelën pas kodimi dhe deshifrimi i karakterit të ardhshëm. Për më shumë detaje mbi algoritmet adaptive, shihni Ch. 4.

Karakteristikat e algoritmit aritmetik:

Raporti më i mirë dhe më i keq i kompresimit: më i miri> 8 (është i mundur kodimi i më pak se një bit për simbol), më i keqi - 1.

Të mirat e algoritmit: Ofron një raport më të mirë kompresimi se ritmi Algo-I Huffman (në të dhënat tipike me 1-10%).

Karakteristikat: si dhe kodimi Huffman, ai nuk rrit madhësinë e të dhënave origjinale në rastin më të keq.

Kodimi i intervalit

Ndryshe nga algoritmi klasik, kodimi i intervalit supozon se kemi të bëjmë me vlera të plota diskrete që mund të marrin një numër të kufizuar vlerash. Siç u përmend tashmë, intervali fillestar në aritmetikën e numrave të plotë shkruhet si [OD) ose, ku N- numri i vlerave të mundshme për variablin e përdorur për të ruajtur kufijtë e intervalit.

Për të kompresuar të dhënat në mënyrë më efikase, ne duhet të kodojmë çdo karakter s nëpërmjet -log 2 (Ј) bit, ku f,- frekuenca e simboleve s. Sigurisht, në praktikë, një saktësi e tillë është e paarritshme, por ne mundemi për çdo personazh s caktoni një varg vlerash në një interval , Prev_freq [c], 10);