La codificació aritmètica (CA) és una forma de codificació d'entropia utilitzada en la compressió de dades sense pèrdues. Normalment, una cadena de caràcters es representa mitjançant un nombre fix de bits per caràcter, com en el codi ASCII. Quan una cadena es converteix a codificació aritmètica, els caràcters utilitzats amb freqüència s'emmagatzemen amb menys bits i els caràcters que no apareixen tan sovint s'emmagatzemen amb més bits, cosa que resulta en menys bits utilitzats en total. La codificació aritmètica difereix d'altres formes de codificació d'entropia, com ara la codificació de Huffman, en què en lloc de separar l'entrada en símbols components i substituir cadascun per un codi, la codificació aritmètica codifica tot el missatge en un sol nombre, una fracció de precisió arbitrària q, on . miniatura|400x400px|Un exemple de codificació aritmètica que assumeix una distribució de probabilitat fixa de tres símbols "A", "B" i "C". La probabilitat d'"A" és del 50%, la probabilitat de "B" és del 33% i la probabilitat de "C" és del 17%. A més, suposem que la profunditat de recursió és coneguda a cada pas. Al primer pas codifiquem "B", que es troba dins de l'interval [ 0,5, 0.83): El nombre binari "0.10 x " és el codi més curt que representa un interval que es troba completament dins de [ 0.5, 0.83). " x " significa una seqüència de bits arbitrària. Hi ha dos casos extrems: la x més petita representa zero, que representa el costat esquerre de l'interval representat. Aleshores, el costat esquerre de l'interval és dec(0.10) = 0,5. A l'altre extrem, x representa una seqüència finita d'uns que té el límit superior dec(0,11) = 0,75. Per tant, "0,10 x " representa l'interval [ 0,5, 0,75) que està dins de [ 0,5, 0,83). Ara podem ometre la part "0", ja que tots els intervals comencen amb "0." i podem ignorar la part " x " perquè independentment de la seqüència de bits que representi, ens quedarem dins de [ 0.5, 0,75).

Detalls i exemples d'implementació Probabilitats iguals En el cas més simple, la probabilitat que aparegui cada símbol és igual. Per exemple, considerem un conjunt de tres símbols, A, B i C, cadascun amb la mateixa probabilitat d'aparèixer. Codificar els símbols un per un requeriria 2 bits per símbol, cosa que és un malbaratament: una de les variacions de bits no s'utilitza mai. És a dir, els símbols A, B i C es podrien codificar respectivament com a 00, 01 i 10, amb 11 sense utilitzar.

Una solució més eficient és representar una seqüència d'aquests tres símbols com un nombre racional en base 3 on cada dígit representa un símbol. Per exemple, la seqüència "ABBCAB" podria convertir-se en 0,0112013, en la codificació aritmètica com un valor en l'interval [0,1). El següent pas és codificar aquest nombre ternari utilitzant un nombre binari de coma fixa amb prou precisió per recuperar-lo, com ara 0.00101100012 – això només són 10 bits; s'estalvien 2 bits en comparació amb la codificació de blocs naïve. Això és factible per a seqüències llargues perquè hi ha algorismes in situ eficients per convertir la base de nombres arbitràriament precisos. miniatura|300x300px|L'exemple anterior es visualitza com un cercle, els valors en vermell codifiquen "WIKI" i "KIWI"; a la imatge SVG, passeu el cursor per sobre d'un interval per ressaltar-lo i mostrar-ne les estadístiques. Per descodificar el valor, sabent que la cadena original tenia una longitud 6, simplement es pot tornar a la base 3, arrodoneix a 6 dígits i recupera la cadena.

Definició d'un model En general, els codificadors aritmètics poden produir una sortida gairebé òptima per a qualsevol conjunt de símbols i probabilitats. (El valor òptim és −log2 P bits per a cada símbol de probabilitat P; vegeu el teorema de la codificació font). Els algorismes de compressió que utilitzen la codificació aritmètica comencen determinant un model de les dades, bàsicament una predicció de quins patrons es trobaran als símbols del missatge. Com més precisa sigui aquesta predicció, més propera a l'òptima serà la sortida.

Exemple: un model simple i estàtic per descriure la sortida d'un instrument de monitorització concret al llarg del temps podria ser:

60% de probabilitat que el símbol sigui NEUTRE 20% de probabilitat que el símbol sigui POSITIU 10% de probabilitat que el símbol sigui NEGATIU 10% de probabilitat del símbol END-OF-DATA. (La presència d'aquest símbol significa que el flux serà "terminat internament", com és força habitual en la compressió de dades; quan aquest símbol apareix al flux de dades, el descodificador sabrà que s'ha descodificat tot el flux.)

Els models també poden gestionar alfabets diferents del simple conjunt de quatre símbols escollit per a aquest exemple. També són possibles models més sofisticats: el modelatge d'ordre superior canvia la seva estimació de la probabilitat actual d'un símbol en funció dels símbols que el precedeixen (el context ), de manera que en un model per a text en anglès, per exemple, el percentatge de probabilitat de "u" seria molt més alt quan segueix una "Q" o una "q". Els models fins i tot poden ser adaptatius, de manera que canvien contínuament la seva predicció de les dades en funció del que realment conté el flux. El descodificador ha de tenir el mateix model que el codificador.

Codificació i descodificació: visió general En general, cada pas del procés de codificació, excepte l'últim, és el mateix; el codificador bàsicament només ha de tenir en compte tres dades:

El següent símbol que cal codificar L' interval actual (al principi del procés de codificació, l'interval està definit com a [0,1], però això canviarà) Les probabilitats que el model assigna a cadascun dels diversos símbols possibles en aquesta etapa (com s'ha esmentat anteriorment, els models d'ordre superior o adaptatius signifiquen que aquestes probabilitats no són necessàriament les mateixes a cada pas).

El codificador divideix l'interval actual en subintervals, cadascun dels quals representa una fracció de l'interval actual proporcional a la probabilitat d'aquest símbol en el context actual. L'interval que correspongui al símbol real que es codificarà a continuació esdevé l'interval que s'utilitzarà al pas següent.

Exemple: per al model de quatre símbols anterior:

l'interval per a NEUTRAL seria [0, 0,6) l'interval per a POSITIU seria [0,6, 0,8) l'interval per a NEGATIU seria [0,8, 0,9) L'interval per a END-OF-DATA seria [0.9, 1)

Quan tots els símbols s'han codificat, l'interval resultant identifica inequívocament la seqüència de símbols que l'han produït. Qualsevol persona que tingui el mateix interval final i el mateix model que s'està utilitzant pot reconstruir la seqüència de símbols que ha d'haver entrat al codificador per donar lloc a aquest interval final.

No cal transmetre l'interval final; només cal transmetre una fracció que es trobi dins d'aquest interval. En particular, només cal transmetre prou dígits (en qualsevol base) de la fracció perquè totes les fraccions que comencin amb aquests dígits caiguin a l'interval final; això garantirà que el codi resultant sigui un codi de prefix.

Codificació i descodificació: exemple miniatura|400x400px|Un diagrama que mostra la descodificació de 0.538 (el punt rodó) en el model d'exemple. La regió es divideix en subregions proporcionals a les freqüències de símbols i, a continuació, la subregió que conté el punt es subdivideix successivament de la mateixa manera. Considereu el procés per descodificar un missatge codificat amb el model de quatre símbols donat. El missatge es codifica en la fracció 0,538 (utilitzant decimal per a més claredat, en lloc de binari; assumint també que només hi ha tants dígits com calgui per descodificar el missatge).

El procés comença amb el mateix interval utilitzat pel codificador: [0,1), i utilitzant el mateix model, dividint-lo en els mateixos quatre subintervals que ha de tenir el codificador. La fracció 0,538 cau en el subinterval de NEUTRAL, [0, 0,6) ; això indica que el primer símbol que va llegir el codificador ha d'haver estat NEUTRAL, de manera que aquest és el primer símbol del missatge.

A continuació, dividiu l'interval [0, 0,6) en subintervals:

L'interval per a NEUTRAL seria [0, 0,36), 60% de [0, 0,6). L'interval per a POSITIU seria [0,36, 0,48), 20% de [0, 0,6). L'interval per a NEGATIU seria [0,48, 0,54), 10% de [0, 0,6). L'interval per a END-OF-DATA seria [0.54, 0.6), 10% de [0, 0.6).

Com que 0,538 es troba dins de l'interval [0,48, 0,54), el segon símbol del missatge ha d'haver estat NEGATIU.

De nou, dividim el nostre interval actual en subintervals:

L'interval per a NEUTRAL seria [0,48, 0,516). L'interval per a POSITIU seria [0,516, 0,528). L'interval per a NEGATIU seria [0,528, 0,534). L'interval per a END-OF-DATA seria [0.534, 0.540).

Ara 0,538 cau dins de l'interval del símbol END-OF-DATA; per tant, aquest ha de ser el següent símbol. Com que també és el símbol de terminació interna, significa que la descodificació s'ha completat. Si el flux no està terminat internament, cal que hi hagi alguna altra manera d'indicar on s'atura el flux. En cas contrari, el procés de descodificació podria continuar per sempre, llegint erròniament més símbols de la fracció que els que realment s'hi van codificar.

Referències

Categoria:Codificació Categoria:Compressió de dades