Codificació per diccionari

La codificació per diccionari és una classe de compressió sense pèrdua que busca coincidències entre el text a comprimir i un grup de cadenes de caràcters en una estructura denominada diccionari administrada per l'algoritme codificador. Quan este algoritme troba una coincidència substituïx la referència a la posició de la cadena en l'estructura de senyes.

Métodos i aplicacions

Alguns codificadores usen un 'diccionari estàtic', el qual no és modificat durant el procés de codificació, sino que es manté des d'abans d'escomençar el procés, se sol utilisar quan el mensage a codificar és gran pero fix com per eixemple una aplicació per a celulars que almagasena el contingut d'un llibre en un espai d'almagasenament reduït.

En els métodos més comuns el diccionari comença en un estat predeterminat pero el contingut canvia durant el procés de codificació tenint en conte les senyes que ya han segut codificats. Els algoritmes LZ77 i LZ78 usen este principi.

En el LZ77, hi ha un ''buffer' circular cridat finestra deslizante (sliding window) que conté els últims bytes processats. Esta finestra servix com a diccionari puix almagasena cada subcadena, que apareix en eixos últims bytes com a entrades de diccionari, en lloc d'usar simples índexs, per a açò requerix de dos valors: el desplaçament i el llarc, el desplaçament és la distància a la que es troba l'inici de la cadena des del text actual i el llarc indica la cantitat de caràcters que conté eixa cadena.

Eixemple

El text a comprimir escomença en "MANGOTANGO". En els primers sis passos de codificació, es recorre M, A, N, G, O, T, i s'agreguen entrades per a MA, AN, NG, GO, OT, TA. En el sèptim pas, escomencem en "ANGO", l'entrada més gran que tenim és "AN". Llavors enviem l'índex per a "AN", i agreguem en el diccionari una entrada per a "ANG". En l'octau pas, enviem l'índex per a "GO", i suponem que un espai seguix a MANGOTANGO, aixina que agreguem una entrada per a "GO " en el diccionari. Si despuix en el text trobem una atra volta la paraula "MANGOTANGO", podríem codificar-la com esta volta (assumint que va escomençar en la M) en sol 5 índexs: MA, NG, OT, ANG, O.

Codificant MANGOTANGO
M	M
A	MA
N	AN
G	NG
O	GO
T	OT
A	TA
N	-- (AN ya està en el diccionari)
G	ANG
O	NGO (no interessa)