Codificació de longitud variable

En teoria de codificació, la codificació de longitud variable és un tipus d'esquema de codificació de caràcters en què s'utilitzen codis de diferents longituds per codificar un conjunt de caràcters (un repertori de símbols) per a la seva representació en un ordinador. El concepte equivalent en informàtica és cadena de bits.

Els codis de longitud variable permeten comprimir i descomprimir fonts amb zero errors (compressió de dades sense pèrdues) i, tot i així, llegir-les símbol per símbol. Una font independent i distribuïda de manera idèntica es pot comprimir gairebé arbitràriament a prop de la seva entropia. Això contrasta amb els mètodes de codificació de longitud fixa, per als quals la compressió de dades només és possible per a grans blocs de dades, i qualsevol compressió més enllà del logaritme del nombre total de possibilitats té una probabilitat de fallada finita (encara que potser arbitràriament petita).

Per aquestes raons, de vegades s'utilitzaven per empaquetar text en anglès en menys bytes en jocs d'aventures per als primers microordinadors. Tanmateix, els discs, l'augment de la memòria de l'ordinador i els algorismes de compressió d'ús general han fet que aquests mètodes siguin obsolets.

Les codificacions multibyte solen ser el resultat de la necessitat d'augmentar el nombre de caràcters que es poden codificar sense trencar la compatibilitat amb versions anteriors amb una restricció existent. Per exemple, amb un byte (8 bits) per caràcter, es poden codificar 256 caràcters possibles; per codificar més de 256 caràcters, l'opció òbvia seria utilitzar dos o més bytes per unitat de codificació, dos bytes (16 bits) permetria 65.536 caràcters possibles, però aquest canvi trencaria la compatibilitat amb els sistemes existents i, per tant, podria no ser factible en absolut.

Són símbols d'origen improbables, però se'ls poden assignar paraules de codi més llargues i als símbols d'origen probables se'ls poden assignar paraules de codi més curtes, donant així una longitud de paraula de codi esperada baixa. Alguns exemples d'estratègies de codificació de longitud variable conegudes són la codificació de Huffman, la codificació de Lempel-Ziv, la codificació aritmètica i la codificació de longitud variable adaptativa al context.

Estructura general

Un sistema de codificació multibyte minimitza la interrupció del programari existent mantenint alguns caràcters com a codis d'una sola unitat, mentre que d'altres requereixen diverses unitats. Això crea tres tipus d'unitats: singletons (que consisteixen en una sola unitat), unitats inicials (que apareixen primer en una seqüència de diverses unitats) i unitats finals (que apareixen després en una seqüència de diverses unitats). Els sistemes d'entrada i visualització han de gestionar aquestes estructures, tot i que la majoria d'altres programes no ho fan.

Per exemple, la cadena de quatre caràcters "I♥NY" està codificat en UTF-8 així (mostrat com a valors de bytes hexadecimals): de les sis unitats d'aquesta seqüència 49 E2 99 A5 4E 59 són singletons (per a I, N i Y), E2 és una unitat principal 99 i A5 són unitats de rastreig. El símbol del cor està representat per la combinació de la unitat principal i les dues unitats de rastreig.

L'UTF-8 distingeix clarament els singletons, els leads i els trails amb rangs de valors que no se superposen. En canvi, les codificacions més antigues sovint reutilitzen valors, cosa que dificulta l'anàlisi correcta del text. Això pot provocar falsos positius en les cerques o fer que un byte corrupte interrompi seqüències llargues. En codificacions ben dissenyades com l'UTF-8, la cerca funciona de manera fiable i la corrupció només afecta el caràcter que conté la unitat incorrecta.

Codis i les seves extensions

L'extensió d'un codi és el mapatge de seqüències font de longitud finita a cadenes de bits de longitud finita, que s'obté concatenant per a cada símbol de la seqüència font la paraula de codi corresponent produïda pel codi original. Utilitzant termes de la teoria del llenguatge formal, la definició matemàtica precisa és la següent: Sigui $S$ i $T$ siguin dos conjunts finits, anomenats alfabets d'origen i de destinació, respectivament. Un codi $C:S\to T^{*}$ és una funció total que mapeja cada símbol de $S$ a una seqüència de símbols sobre $T$, i l'extensió de $C$ a un homomorfisme de $S^{*}$ en $T^{*}$, que mapeja naturalment cada seqüència de símbols d'origen a una seqüència de símbols de destinació, es coneix com a extensió.

Els codis de longitud variable es poden imbricar estrictament en ordre de generalitat decreixent com a codis no singulars, codis descodificables de manera única i codis de prefix. Els codis de prefix sempre són descodificables de manera única i, al seu torn, sempre són no singulars:

Codis no singulars

Un codi és no singular si cada símbol font es mapa a una cadena de bits diferent no buida; és a dir, el mapatge dels símbols font a les cadenes de bits és injectiu .

Codis descodificables de manera única

Un codi és descodificable de manera única si la seva extensió és § no singular. L'algorisme de Sardinas-Patterson pot decidir si un codi determinat és descodificable de manera única.

Codis de prefixos

Un codi és un codi de prefix si cap cadena de bits de destinació del mapatge és un prefix de la cadena de bits de destinació d'un símbol font diferent del mateix mapatge. Això significa que els símbols es poden descodificar instantàniament després de rebre tota la seva paraula de codi. Altres noms que s'utilitzen habitualment per a aquest concepte són codi sense prefix, codi instantani o codi sense context . Un cas especial de codis de prefix són els codis de bloc, LEB128 i els codis de quantitat de longitud variable (VLQ).