Revisió del 10:40, 1 des 2014 modifica Mumitta (discussió \| contribucions) 484 edits Articles i puntuació. ← Edició anterior		Revisió del 21:44, 10 maig 2015 modifica desfés Mrosach (discussió \| contribucions) 492 edits Cap resum de modificació Etiqueta: editor visual Edició següent →
Línia 1: {{millorar redacció\|data=març de 2014}} ''' LZW (Lempel-Ziv-Welch) ''' és un [[algorisme]] de [[compressió de dades\|compressió]] sense pèrdua, desenvolupat per [[Terry Welch]] alel [[1984]] com una versió millorada de l'algorisme [[LZ78]], desenvolupat per [[Abraham Lempel]] i [[Jacob Ziv]].▼ ~~{{millorar ortografia\|data=març de 2014}}~~ ▲''' LZW (Lempel-Ziv-Welch) ''' és un [[algorisme]] de [[compressió de dades\|compressió]] sense pèrdua desenvolupat per [[Terry Welch]] al [[1984]] com una versió millorada de l'algorisme [[LZ78]] desenvolupat per [[Abraham Lempel]] i [[Jacob Ziv]]. == Descripció de l'algorisme == La majoria dels mètodes de compressió es basen en una anàlisi inicial del text per identificar cadenes repetides per armar un diccionari d'equivalències, assignant codis breus a aquestes cadenes. En una segona etapa, es converteix el text utilitzant els codis equivalents per a les cadenes repetides. Això requereix dues etapes, una d'anàlisi i una segona de conversió i també requereix que el diccionari es trobi juntament amb el text codificat, incrementant la mida del fitxer de sortida. La clau del mètode LZW ~~és que és~~es ~~possible~~pot crear sobre la marxa, de manera automàtica i en una única passada d'un diccionari de cadenes que es trobin dins del text a comprimir, mentre alque ~~mateix~~-a la ~~temps~~vegada- es procedeix a la seva codificació. Aquest diccionari no és transmès amb el text comprimit, ja que el descompressor pot reconstruir-lo usant la mateixa lògica amb què ho fa el compressor i, si està codificat correctament, tindrà exactament les mateixes cadenes que el diccionari del compressor tenia. El diccionari comença precarregat amb 256 entrades, una per a cada caràcter (byte) i és possible més d'un codi predefinit per indicar el final d'arxiu. A aquesta taula se li van afegint successius codis numèrics per cada nou parell de caràcters consecutius que es llegeixin (això no és literalment cert, segons es descriu tot seguit), encara que ~~encara~~ no sigui possible preveure si aquest codi es reutilitzarà més endavant o no. És en aquest detall on es troba la brillantor del mètode: en armar el diccionari sobre la marxa s'evita fer dues passades sobre el text, una analitzant i l'altra codificant. ~~i atès~~Atès que la regla d'armat del diccionari és tan simple, el descompressor pot reconstruir a partir del text comprimit mentre el llegeix, evitant així incloure el diccionari dins del text comprimit. Es pot objectar que el diccionari estarà ple de codis que no s'utilitzaran, i per tant, serà innecessàriament gran, però a la pràctica el diccionari no creix massa i encara si ho fes, no importa molt perquè l'objectiu és que l'arxiu comprimit sigui petit encara que els processos de compressió i descompressió poguessin ocupar molta memòria amb el diccionari. Les entrades del diccionari poden representar seqüències de caràcters simples o seqüències de codis de tal manera que un codi pot representar dos caràcters o pot representar seqüències d'altres codis prèviament carregats que al seu torn representen, cada un d'ells, altres codis o caràcters simples, o sigui que un codi pot representar des d'un a un nombre indeterminat de caràcters. En realitat, l'algoritme no discrimina entre codis i caràcters simples, ja que el diccionari es carrega inicialment de codis que representen els primers 256 caràcters simples per la qual cosa aquests no són més que altres codis dins del mateix diccionari. Cada vegada que es llegeix un nou caràcter es revisa el diccionari per veure si forma part d'alguna entrada prèvia. Tots els caràcters estan inicialment predefinits al diccionari així que sempre hi haurà almenys una coincidència, però, el que es busca és la cadena més llarga possible. Si el caràcter llegit no forma part de més d'una cadena més llarga, llavors s'emet la més llarga que s'hagués trobat i s'agrega al diccionari una entrada formada per qualsevol que hagués estat el codi previ i aquest nou codi. Si el caràcter llegit sisí forma part de més d'una cadena del diccionari, es llegeix un nou caràcter per veure si la seqüència formada pel caràcter previ i el nou és alguna de les trobades en el diccionari. Mentre els caràcters successius que es vagin llegint ofereixin més d'una entrada possible al diccionari, se segueixen llegint caràcters. Quan la cadena només té una entrada al diccionari, llavors s'emet el codi corresponent a aquesta entrada i s'incorpora al diccionari una nova entrada que representa l'últim codi emès i el nou. Una altra característica important de l'algorisme és que els codis a la sortida es representen per cadenes de bits variables. El diccionari conté inicialment 257 codis, 256 codis per als 256 caràcters simples possibles de 8 bits i un codi que representa la fi d'arxiu. Per això serien necessaris codis de 9 bits, la qual cosa vol dir que encara hi ha disponibles 255 codis de 9 bits per representar cadenes de caràcters. Quan s'omplen aquestes 255 entrades del diccionari, s'amplien els codis amb un nou bit, la qual cosa permet 512 noves entrades. Quan es completen aquestes 512 entrades, s'afegeix un bit i es disposen de 1.024 noves entrades i així successivament. A la pràctica, es verifica que les primeres entrades, corresponents a codis de 12 bits de longitud (4.096 entrades) s'omplen ràpidament pel que és habitual començar el procés no amb codis de 9 bits sinó directament amb codis de 12 bits. Linha 20 ⟶ 19: Al seu torn, s'ha comprovat empíricament que la informació en un fitxer presenta 'regionalitat', és a dir, que diferents regions d'un mateix arxiu presenten diferents regularitats, la qual cosa fa que el diccionari que s'hagués format per una regió d'un arxiu pugui no ser útil en una altra regió diferent. L'algoritme preveu que, quan una cadena fora a forçar l'ampliació del diccionari a 17 bits, el diccionari s'esborri del tot, s'inicialitzi novament amb els 256 codis inicials més el codi de fi d'arxiu i es reprengui el procés. Observeu que donat aquest límit de codis de 16 bits, això vol dir que un diccionari mai no podrà contenir més de 65.536 entrades, cadascuna d'elles de 2 codis de 16 bits, és a dir quatre octets per entrada. El diccionari, llavors, s'arma com una taula on el codi és l'índex i les cadenes que representa són les entrades d'aquesta taula. Cal advertir que el codi ~~en si~~ no s'emmagatzema a la taula, sinó que és l'índex de la mateixa per la qual cosa no s'emmagatzema sinó que es calcula per la posició a la taula. En total, una taula plena ocupa 65.536 entrades de 4 bytes cadascuna, és a dir, 262.144 caràcters (256 kbytes) el que és absurdament poc per als ordinadors actuals. Que la mida dels índexs pugui ser ~~incrementat~~incrementada de manera variable és una de les contribucions de Welch. Una altra d'elles va ser especificar una [[estructura de dades]] eficient per guardar el diccionari. === Un exemple simple de l'algoritme LZW de compressió === Linha 54 ⟶ 53: El text original, està compost de 25 caràcters que poden representar-se amb 5 bits cada un i ens donaria 125 bits. El resultat comprimit produeix 5 codis de 5 bits més 12 codis de 6 bits, la qual cosa resulta en 97 bits, una reducció a menys del 78% de l'original. Noteu que cada caràcter llegit genera una nova entrada al diccionari, independentment de si es farà servir o no. Aquesta simplicitat per part de l'algorisme de compressió permet que el descompressor pugui reconstruir el diccionari sense errors. Quan es comença a utilitzar 6 bits per codi, tots els codis s'emeten amb 6 bits, fins i tot els que originalment només usessin 5 bits, completant amb zeros per esquerra. == Usos == El mètode va arribar a ser utilitzat de forma moderada, però en tota la seva amplitud en el programa '' [[compress]] '' que va arribar a ser més o menys la utilitat estàndard de compressió en sistemes [[Unix]] al voltant del 1986 (ara ha desaparegut pràcticament tant per assumptes legals com tècnics). Altres utilitats de compressió també utilitzen aquest mètode o altres relativament propers. Es va usar àmpliament des que es va convertir en part del format gràfic [[GIF]] all'any [[1987]]. Pot ser també usat, encara que opcionalment, en arxius [[TIFF]]. La compressió LZW proporcionava una relació de compressió millor en moltes aplicacions que altres mètodes de compressió coneguts en aquesta època. Va arribar a convertir-se en el primer mètode de propòsit general de compressió de dades utilitzat àmpliament. En textos llargs, comprimeix aproximadament a la meitat de la mida original. Altres tipus de dades són també comprimits útilment en molts casos. Linha 73 ⟶ 72: Molts experts en lleis conclouen que la patent no cobreix dispositius que només descomprimim LZW i no puguin comprimir dades usant-lo, per aquesta raó el popular programa [[gzip]] pot llegir arxius. Z però no escriure'ls. Es va informar a [http://www.debian.org/News/weekly/2002/45/Debian Weekly News] d'acord amb un fil de [http://groups.google.com/groups?&threadm=a5aa8dd0.0208271613.3cd18da6 % 40posting.google.com comp.compression thread], que la patent d'Unisys als EUA va expirar a [[desembre]] del [[2002]] - 17 anys i 10 dies després de ser patentat. No obstant això, la majoria de les fonts informen que va expirar el juny del [[2003]], 20 anys després de ser arxivada, perquè [http://www.law.cornell.edu/uscode/35/154.html 35 USC § 154 (c) (1)] especifica que les patents subsisteixen 20 anys després de l'[[Uruguai Round Agreements Act]]. No obstant això, la majoria de les fonts informen que va expirar el juny del [[2003]], 20 anys després de ser arxivada, perquè [http://www.law.cornell.edu/uscode/35/154.html 35 USC § 154 (c) (1)] especifica que les patents subsisteixen 20 anys després del [[Uruguai Round Agreements Act]]. D'acord amb una declaració a la web de Unisys, les patents de LZW al [[Regne Unit]], [[França]], [[Alemanya]], [[Itàlia]] i [[Japó]] han expirat en juny del [[2004]] i la patent canadenca en [[juliol]] del [[2004]]. La patent d'IBM als EUA va expirar l'agost del [[2006]]. ~~La patent d'IBM als EUA va expirar l'agost del [[2006]].~~ == Lempel-Ziv-Welch vs. Ziv-Lempel-Welch == Tot i que l'[[acrònim]] LZW ~~òbviament~~es fadeu, òbviament, als inventors com Lempel, Ziv i Welch, alguna gent opina que el dret de [[propietat intel·lectual]] va a Ziv primer, de manera que el mètode s'ha d'anomenar '' algorisme Ziv - Lempel-Welch '', i no l''' algorisme Lempel-Ziv-Welch ''. == Enllaços externs == * [http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=4, 558,302. WKU. & OS = PN/4.558.302 & RS = PN/4.558.302 United States Patent 4.558.302]. * [http://www.dogma.net/markn/articles/lzw/lzw.htm "LZW Data Compression", by Mark Nelson] (DDJ Article amb codi font). * [http://www.kyz.uklinux.net/giflzw.php Sad day ... GIF patent dead at 20] (Article curt i possiblement amb una simplificació de la veritable història~~, que~~; es pot trobar alguna cosa més detallada a la pàgina de [[GIF]]). * [http://software.newsforge.com/software/05/06/23/2150233.shtml?tid=130 '' Bringing back LZW compression '' per Nathan Willis]. * [http://www.compression-links.info/LZW List of LZW libraries, papers and other resources]. [[Categoria:Acrònims d'informàtica]]

LZW: diferència entre les revisions