Existe algum algoritmo de compressão ideal teoricamente comprovado?

7

A codificação de Huffman é sempre ideal, pois usa as idéias de Shanon? E quanto a texto, imagem, vídeo, ... compressão?

Esse assunto ainda está ativo no campo? Que referências clássicas ou modernas devo ler?

algorithms information-theory data-compression Zeta.Investigator
fonte
2
Você pode ver en.wikipedia.org/wiki/Kolmogorov_complexity
Dávid Natingga
O link de DavidToth é a resposta. Em suma "não". Você não pode provar qualquer dados são compactados minimamente (o que naturalmente faz com que seja impossível provar um algoritmo optimal)
EDA-qa mort-ora-y
2
@ edA-qamort-ora-y: "Você não pode provar que nenhum dado está compactado minimamente" - isso não é verdade. Cf. o problema da parada, que em geral é indecidível, mas é claro que existem alguns programas para os quais podemos provar que ele para ou para. Cf. também a função de castor ocupado; alguns valores da função são conhecidos.
Jukka Suomela
@JukkaSuomela, sim, meu fraseado não foi completo a esse respeito. Obviamente, é possível ter conjuntos de dados específicos que podem ser mostrados como compactados de maneira ideal. Meu palpite, porém, é que o tamanho desses dados é extremamente pequeno.
EdA-qa mort-ora-y
Uma métrica interessante em que você pode estar interessado é a distância de compressão normalizada (NCD). Vitanyi e Li, entre outros, têm documentos sobre isso. Em resumo, funciona muito bem para todos os tipos de dados e aprimora todas as outras métricas em um sentido. Verifique o livro Vitanyi & Li sobre a complexidade de Kolmogorov para uma boa iniciação, se quiser.
Juho

Respostas:

9

A codificação de Huffman é ideal para uma codificação de símbolo a símbolo, onde as probabilidades de cada símbolo são independentes e conhecidas de antemão. No entanto, quando essas condições não são satisfeitas (como na imagem, vídeo), outras técnicas de codificação, como LZW, JPEG, etc. são usadas. Para mais detalhes, você pode ler o livro "Introdução à compactação de dados", de Khalid Sayood.

Arani
fonte
Além de dados puramente aleatórios, acho que nenhum tipo de dado atende a essas condições.
edA-qa mort-ora-y
2
Mas as outras técnicas não são de símbolo para símbolo. É assim que eles alcançam uma melhor compactação. E é também por isso que a codificação Huffman raramente é usada por si só.
svick
6

Existe uma versão do algoritmo Lempel-Ziv que é ideal em alguns cenários. Nomeadamente, se a entrada vier de uma cadeia ergódica de Markov, a taxa assintótica do algoritmo Lempel-Ziv será igual à entropia. Para saber mais, dê uma olhada no Capítulo 13 de Cover e Thomas.

Yuval Filmus
fonte
6

A compactação de Huffman, com certas suposições que geralmente não se aplicam a arquivos reais, pode ser provada como ideal.

Vários algoritmos de compactação compactam alguns tipos de arquivos menores que o algoritmo de Huffman , portanto, Huffman não é o ideal. Esses algoritmos exploram uma ou outra das advertências na prova de otimização de Huffman.

Sempre que temos (a) codificamos cada símbolo independentemente em um número inteiro de bits e (b) cada símbolo é "não relacionado" aos outros símbolos que transmitimos (nenhuma informação mútua, independente estatisticamente, etc.) e (c) o receptor conhece a distribuição de probabilidade de todos os símbolos possíveis, então a compactação de Huffman é ideal (produz os menores arquivos compactados).

(a) símbolo por símbolo: relaxando a restrição binária de Huffman de que cada símbolo de entrada deve ser codificado como um número inteiro de bits, vários algoritmos de compactação, como codificação de intervalo, nunca são piores do que o padrão de Huffman .

(b) símbolos não relacionados: a maioria dos arquivos de dados reais possui algumas informações mútuas entre os símbolos. Pode-se fazer melhor do que simples Huffman "correlacionando" os símbolos e, em seguida, usando o algoritmo Huffman nesses símbolos correlacionados.

(c) distribuição de probabilidade conhecida: Normalmente, o receptor não sabe a distribuição exata de probabilidade. Os algoritmos de compactação típicos de Huffman enviam uma tabela de frequência primeiro e depois os dados compactados. Vários algoritmos de compactação "adaptáveis", como a codificação em árvore Polar, podem obter melhor compactação do que Huffman, porque convergem na distribuição de probabilidade ou se adaptam a uma distribuição de probabilidade variável, sem nunca enviar explicitamente uma tabela de frequências.

Livros e documentos discutindo essa compressão melhor do que Huffman:

David Cary
fonte
2

A taxa ótima de compactação está relacionada à entropia dos dados.

No artigo da Wikipedia http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem :

As variáveis ​​aleatórias do zero, cada uma com entropia H (X), podem ser compactadas em mais de bits NH (X) com risco insignificante de perda de informações, pois N tende ao infinito; por outro lado, se forem compactados em menos de bits NH (X), é praticamente certo que as informações serão perdidas.

user1149913
fonte
por que isso é prejudicado?
Sasho Nikolov