trabalho sobre Lempel ziv

Lempel ziv

Lempel-Ziv a codificação representa um afastamento da visão clássica de um código como um mapeamento de um conjunto fixo de mensagens de fontes (letras, símbolos ou palavras) para um conjunto fixo de palavras-código.
É um universal de compressão de dados sem perdas , algoritmo criado por Abraham Lempel , Jacob Ziv e Terry Welch . O algoritmo foi projetado para ser rápido de implementar, mas geralmente não é ideal porque ele executa apenas uma análise limitada dos dados.Compressão de dados é uma forma de codificar um certo conjunto de informações de maneira que o código gerado seja menor que o fonte.Lempel-Ziv codificação define o conjunto de mensagens de origem, uma vez que analisa o conjunto.
Criada em 1977 por Abraham Lempel e Jacob Ziv, a compressão LZW é encontrada na compressão de texto e de programas. Os algoritmos de compressão LZ78 são usados na compressão de dados binários, como os bitmaps. Em 1984, Terry Welch modificou o compressor LZ78 paraa sua implementação em controladores de discos deelevado desempenho. O resultado foi o algoritmo LZW que é encontrado eusado nos nossos dias (como o ARJ, Gunzip,PKZIP/WinZip e o formato imagem GIF)Inicialmente o algoritmo era de domínio público,atualmente a patente é propriedade da Unisys.
Codificação LZW é baseada na construção de um dicionário de palavras (grupos de um ou mais caracteres) a partir do fluxo de entrada.Quando uma nova palavra é encontrada, a máquina de compressão adicionada ao dicionário e um valor que identifica a posição da frase no dicionário substitui a frase.Se a frase já foi registrada, ela é substituída pelo valor de posição no dicionário.
2156264080
Código de Shannon-Fano
No Código de Shannon-Fano as palavras a codificar devem ser ordenadas por ordem decrescente de probabilidades. Suponhamos, por exemplo, que temos as palavras x1, x2, x3, x4, x5 e x6, que ocorrem com as seguintes probabilidades:
1361121397
Ordenando os símbolos e dividindo-os sucessivamente em dois