El LZ77 y el LZ78 son los nombres para los dos algoritmos sin pérdidas de la compresión de datos publicados en papeles por el Abraham Lempel y el Jacob Ziv en el 1977 y el 1978 . También se conocen como LZ1 y LZ2 respectivamente. Estos dos algoritmos forman la base para la mayor parte de las variaciones de LZ incluyendo el LZW, el LZSS y otros. Son ambos codificadores mínimos desemejantes de la redundancia de los codificadores de diccionario . LZ77 es el " deslizar el window" algoritmo de compresión, que era más adelante demostrado para ser equivalente a la técnica explícita del diccionario primero dada en LZ78.
LZ77
Los algoritmos LZ77 alcanzan la compresión substituyendo las porciones de los datos por referencias a los datos que emparejan que han pasado ya a través de codificador y del decodificador. Un fósforo es codificado por un par de números llamados un par de la longitud-distancia del, que es equivalente al " de la declaración; cada uno de los carácteres siguientes de la longitud del es igual a los carácteres de la distancia carácter exactamente detrás de él en el stream." sin comprimir; (El " distance" a veces se llama el " offset" en lugar.)El codificador y el decodificador deben ambos no perder de vista una cierta cantidad de los datos más recientes, tales como kB pasado, 4 del kB de 2, o kB 32. La estructura en la cual se llevan a cabo estos datos se llama una ventana de desplazamiento del, que es porqué LZ77 a veces se llama la compresión de la ventana de desplazamiento del . El codificador necesita guardar estos datos para buscar fósforos, y el decodificador necesita guardar estos datos para interpretar los fósforos que el codificador se refiere. Esta es la razón por la cual el codificador puede utilizar una ventana de desplazamiento más pequeña del tamaño que el decodificador, pero no viceversa.
Muchos documentos que hablan de los algoritmos LZ77 describen un par de la longitud-distancia como comando al " copy" datos de la ventana de desplazamiento: " Van detrás los carácteres de la distancia del en el almacenador intermediario y copian carácteres de la longitud del, a partir de ése point." Mientras que ésos usados al programado imprescindible pueden encontrar este intuitivo modelo, puede también hacerlo duro entender una característica de la codificación LZ77: a saber, eso es no sólo aceptable pero con frecuencia útil para tener un par de la longitud-distancia donde la longitud excede realmente la distancia. Como comando de copia, esto está desconcertando: " Va detrás el carácter del uno en el almacenador intermediario y copia carácteres del siete, a partir de ése point." ¿Cómo se pueden siete carácteres copiar del almacenador intermediario cuando solamente uno de los carácteres especificados es realmente en el almacenador intermediario? La mirada de un par de la longitud-distancia como declaración de la identidad, sin embargo, aclara la confusión: cada uno de los siete carácteres siguientes es idéntico al carácter que viene uno antes de él. Esto significa que cada carácter puede ser determinado mirando detrás en el almacenador intermediario - incluso si el carácter mirado de nuevo a no era en el almacenador intermediario cuando el descifrar de los pares actuales comenzó. Puesto que por definición un par como esto repetirá una secuencia de tiempos múltiples de los carácteres de la distancia del, significa que LZ77 incorpora una forma flexible y fácil de la codificación de la Funcionar-longitud.
Aunque todos los algoritmos LZ77 trabajan por definición en el mismo principio de base, pueden variar extensamente en cómo hacen salir sus datos codificados - qué valores son posibles para las longitudes y las distancias, por ejemplo, y cómo los pares de la longitud-distancia son distinguidos de los literales (solos carácteres codificados como ellos mismos del, algo que como parte de un par de la longitud-distancia.) Algunos ejemplos:
El algoritmo ilustrado en papel de la original 1977 de Lempel y de Ziv hace salir todos sus datos tres valores a la vez: la longitud y la distancia del fósforo más largo encontraron en el almacenador intermediario, y el literal que siguió ese fósforo. Si dos carácteres sucesivos en el flujo de entradas se podrían codificar solamente como literales, la longitud sería 0.
En el formato de PalmDoc, un par de la longitud-distancia es codificado siempre por una secuencia de dos bytes. De los 16 pedacitos que componen éstos dos octetos, 11 pedacitos van a codificar la distancia, 3 van a codificar la longitud, y los dos restantes se utilizan para cerciorarse de que el decodificador puede identificar el primer octeto como el principio de una secuencia tan de dos bytes.
El en fecha 2004, el método basado LZ77 más popular de la compresión se llama DEFLATE ; combina LZ77 con la codificación de Huffman. Los literales, las longitudes, y un símbolo para indicar el extremo del bloque actual de datos todo se ponen juntos en un alfabeto. Las distancias se pueden poner con seguridad en un alfabeto separado; puesto que una distancia ocurre solamente enseguida después de una longitud, no puede ser confundida desde otra clase de símbolo o viceversa.
LZ78
Mientras que el algoritmo LZ77 trabaja encendido más allá de datos, el algoritmo LZ78 intenta trabajar en los datos futuros. Hace esto por la exploración delantera el almacenador intermediario de entrada y emparejarlo contra un diccionario que mantiene. Explorará en el almacenador intermediario hasta que no pueda encontrar un fósforo en el diccionario. A este punto hará salir la localización de la palabra en el diccionario, si uno está disponible, la longitud del fósforo y el carácter que causaron una falta del fósforo. La palabra resultante entonces se agrega al diccionario.Aunque inicialmente es popular, el renombre de LZ78 humedeció más adelante, posiblemente porque para las primeras décadas después de que fuera introducido, las partes de LZ78 eran la patente protegida en el Estados Unidos . La forma más popular de la compresión LZ78 era el algoritmo LZW, una modificación del algoritmo LZ78 hecho por el Terry galés.
| Random links: | Abbahu | Río de la paz | Sáhara español | Gualterio Doran | Araña del saco de Corinnid |