Relação de Entropia para Lossless Compression Rate

Question

A partir Fonte de Shannon Codificação Teorema sabemos que a entropia de uma string comprimida é delimitada pela entropia da cadeia original assim:

H(X) <= L < H(X) + 1/N 

H em que (X) é a entropia da cadeia de origem, N é o comprimento da cadeia de origem, e L é o comprimento esperado da cadeia comprimida.

Isto significa necessariamente que há um limite para compressão sem perdas.

O que eu gostaria de saber é:

• Podemos relacionar diretamente entropia para alguns taxa de compressão esperado?

• Podemos usar a entropia de encontrar algum limite superior para a taxa de compressão?

Answer 1

Você não pode se relacionar diretamente entropia a taxa de compressão sem saber o comprimento da cadeia de origem, mas você pode ver o limite teórico para a taxa de compressão máxima, resolvendo para o menor valor possível de L. Você pode usar esse limite como uma métrica para a eficiência de seus algoritmos de compressão, embora uma má métrica não significa que um algoritmo de melhor foi descoberto ou mesmo existe.

Então, sim. Você pode usar entropia para encontrar a taxa de compressão máxima sem perdas teórica, mas não, você não pode usá-lo para determinar a sua taxa de compressão esperado para qualquer algoritmo de compressão de dado.

Answer 2

Teorema de Shannon é definido em termos de dados aleatórios e probabilidades. Da mesma forma, o entropia de uma corda só é definida para seqüências aleatórias - a entropia é uma propriedade da distribuição, não das próprias cordas. Assim, podemos reafirmar Teorema de Shannon informalmente como:

Se você selecionar aleatoriamente uma corda de uma determinada distribuição de probabilidade, então a melhor taxa de compressão média podemos obter para a cadeia é dada pela taxa de entropia da distribuição de probabilidade.

Dado qualquer seqüência aleatória, eu posso facilmente escrever um algoritmo de compressão que irá comprimir que para baixo string em 1 bit, mas meu algoritmo irá necessariamente aumentar o comprimento de algumas outras cordas. Meu algoritmo de compressão funciona da seguinte maneira:

1. Se a cadeia de entrada é igual a alguns seqüência aleatória pré-escolhido , a saída é a cadeia de 1-bit "0"
2. Caso contrário, a saída é a cadeia + 1 bits N de "1", seguido pela cadeia de entrada

O algoritmo de descompressão correspondente é:

1. Se a entrada for "0", a saída é nossa pré-escolhido anterior seqüência aleatória
2. Caso contrário, a saída é tudo, exceto para o primeiro bit de entrada

A chave aqui é que não pode escrever um algoritmo que, para todas as seqüências de uma dada distribuição, comprime-los todas a uma taxa elevada, em média. Há apenas muitas cordas.

Se tivermos uma determinada distribuição de probabilidade de cordas, podemos calcular a taxa de entropia da distribuição, e em seguida, se escolher aleatoriamente uma corda de acordo com a distribuição e tentativa de comprimi-lo usando qualquer algoritmo, o tamanho relativo da corda comprimido irá, em média, nunca será inferior à taxa de entropia. Isto é o que o Teorema de Shannon diz.

Answer 3

Sim. O taxa de entropia do idioma Inglês é frequentemente citado como 1,5 bits por caractere (mais ou menos). codificações típicas usar 8 bits por caractere. Assim, um texto maximamente comprimido deve ser de 1,5 / 8 (~ 19%) o tamanho do original. Os resultados reais para a versão de texto simples de Jane Austin Pride and Prejudice:. orig = 701K, bzip2 = 178K, para ~ 25%

Answer 4

Sim! Acho este papel iria apontá-lo na direção certa.

ETA parece que você precisa para ser um membro do IEEE para ler o papel real. Se alguém pudesse encontrar um recurso disponível ao público (ou explicar a matemática aqui), que seria muito melhor, é claro!