LZW: diferència entre les revisions

''' LZW (Lempel-Ziv-Welch) ''' és un [[algorisme]] de [[compressió de dades|compressió]] sense pèrdua desenvolupat per [[Terry Welch]] aal [[1984]] com una versió millorada de l'algorisme [[LZ78]] desenvolupat per [[Abraham Lempel]] i [[Jacob Ziv]].

É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 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ò ena 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.

i el procés de compressió queda representat per la taula següent. Per interpretar-la, se suggereix ignorar la representació binària, que s'inclou simplement per comptabilitzar la mida del fitxer de sortida. Els codis de l'1 al 26 es corresponen amb caràcters individuals 1 = A, 2 = B, ... 26 = Z i 27 = "''fi de fitxer''". Del 28 en endavant cada codi representa més d'un caràcter.

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 dedel 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]] aal [[1987]]. Pot ser també usat, encara que opcionalment, en arxius [[TIFF]].

Diverses patents han estat concedides als Estats Units d'Amèrica i altres països per l'algoritme LZW i similars. El [[LZ78]] estava sota la patent 4.464.650, demanada per Lempel, Ziv, Cohn i Eastman i assignada a [[Sperry Corporation]], més tard [[Unisys Corporation]], el [[10 d'agost]] dedel [[1981]]. Dos patents dels Estats Units van ser creades per al LZW: la patent dels EUA 4.814.746 per [[Victor S. Miller]] i [[Mark N. Wegman]] i assignada a [[International Business Machines|IBM]], originalment l'[[1 de juny]] dedel [[1983]], i la patent nord-americana 4.558.302 per Welch, assignada a Sperry Corporation, més tard Unisys Corporation, el [[20 de juny]] dedel [[1983]].

La patent nord-americana 4.558.302 és la que ha causat la controvèrsia més gran. Unisys un cop va garantir llicències lliurea de patents als desenvolupadors de [[programari lliure]] i programari propietari [[freeware]] (gratuït, sense finalitats comercials). La companyia va finalitzar aquestes llicències a l'agost dedel [[1999]].

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]] dedel [[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 dedel [[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 dedel [[2004]] i la patent canadenca en [[juliol]] dedel [[2004]].

La patent d'IBM als EUA va expirar l'agost dedel [[2006]].