Biblioteca deschisă - o bibliotecă deschisă de informații educaționale. Pentru Coderz - Codare aritmetică
Codare aritmetică
Cu codificarea aritmetică, spre deosebire de metodele pe care le-am luat în considerare, când simbolul codificat (sau grupul de simboluri) este înlocuit cu codul corespunzător, rezultatul codificării întregului mesaj este reprezentat de unul sau o pereche de numere reale în intervalul de la 0 la 1. Pe măsură ce textul sursă este codificat, intervalul care îl reprezintă scade, iar numărul de cifre zecimale (sau binare) folosite pentru a-l reprezenta crește. Următoarele caractere ale textului de intrare reduc valoarea intervalului pe baza valorilor probabilităților lor determinate de model. Caracterele mai probabile fac acest lucru într-o măsură mai mică decât cele mai puțin probabile și, prin urmare, adaugă mai puține cifre la rezultat codificare aritmetică folosind un exemplu simplu. Să presupunem că trebuie să codificăm următoarele șir de text: RADIO VISOR
Înainte ca codificatorul să înceapă să funcționeze, intervalul inițial corespunzător textului codificat este . De fapt, pentru decodificare fără ambiguitate Acum este suficient să cunoașteți o singură limită a intervalului - inferioară sau superioară, adică rezultatul codificării poate fi începutul intervalului final - 0,8030349772. Pentru a fi și mai precis, orice număr conținut interior acest interval este decodat în mod unic în mesajul original. De exemplu, aceasta poate fi testată cu numărul 0.80303498 care îndeplinește aceste condiții. În acest caz, ultimul număr are un număr mai mic de zecimale decât numerele corespunzătoare limitelor inferioare și superioare ale intervalului și, prin urmare, poate fi reprezentat printr-un număr mai mic de locuri binare.
Este ușor de verificat că, cu cât intervalul final este mai larg, cu atât poate fi reprezentat mai puține cifre zecimale (și, prin urmare, binare). Lățimea intervalului depinde de distribuția de probabilitate a simbolurilor codificate - simbolurile mai probabile îngustează intervalul într-o măsură mai mică și, prin urmare, adaugă mai puțini biți la rezultatul codificării. Să o arătăm mai departe exemplu simplu.
Să presupunem că trebuie să codificăm rândul următor personaje:
A A A A A A A A A #
, unde este probabilitatea literei A
este 0,9. Procedura de codificare a acestui șir și rezultatul rezultat vor arăta astfel în acest caz:
Simbol de intrare Limită inferioară Limită superioară
A 0,0 0,9
A 0,0 0,81
A 0,0 0,729
A 0,0 0,6561
A 0,0 0,59049
A 0,0 0,531441
A 0,0 0,4782969
A 0,0 0,43046721
A 0,0 0,387420489
# 0,3486784401 0,387420489
Rezultatul codificării poate fi acum, de exemplu, numărul 0,35, care se încadrează în întregime în intervalul final 0,3486784401 – 0,387420489. Pentru a reprezenta acest număr în binar avem nevoie de 7 biți (doi zecimale corespund aproximativ șapte binare), în timp ce pentru reprezentarea binară a rezultatelor de codificare din exemplul anterior - 0.80303498 - sunt necesari 27 de biți!!!
Când decodificăm, presupunem că tot ceea ce știe decodorul despre text este intervalul final. Decodorul, ca și codificatorul, cunoaște și tabelul de distribuție a intervalelor alocate alfabetului. El înțelege imediat că primul caracter codificat este R , deoarece rezultatul codificării se află în întregime în intervalul Câte numere hexazecimale din trei cifre există pentru care vor exista simultan
Cursul 13 Tehnici și metode de lucru cu date comprimate Lector St. profesorul Kupo A.N. O trăsătură caracteristică a majorității tipurilor de date „clasice” cu care oamenii lucrează în mod tradițional este certă
Statul federal pentru educație instituția bugetară de învățământ profesional superior Regiunea Volga Universitatea de stat de telecomunicații și informatică Departamentul de SARS Atribuire și metodologie
UDC 519.6 Caracteristici ale codificării textului folosind algoritmul Huffman Kizyanov Anton Olegovich Sholom Aleichem Priamur Studentă la Universitatea de Stat Kuzmina Bogdana Sergeevna Priamursky
LUCRĂRI DE LABORATOR Metode de precizare și caracteristici principale ale codurilor convoluționale Codurile convoluționale sunt utilizate pe scară largă într-o mare varietate de domenii ale tehnologiei pentru transmiterea și stocarea informațiilor. Cel mai evident
UDC 004.8 APLICAREA ALGORITMULUI GENETIC PENTRU GESTIONAREA PROIECTULUI ORARULUI SCOLAR Gushchina O. A. Algoritm de căutare adaptivă al algoritmului genetic (GA) bazat pe factori evolutivi
Matematică discretă Partea 2 Kochetov Yuri Andreevich http://www.math.nsc.ru/lbrt/k5/dm.html Curs 1 Algoritmi, sortare, arbori AVL 1 Algoritmi și complexitatea lor Calculatoarele funcționează (până acum) doar corect
