Codificação de entropia - Entropy coding

Na teoria da informação, uma codificação de entropia (ou codificação de entropia ) é um esquema de compressão de dados sem perdas que é independente das características específicas do meio.

Um dos principais tipos de codificação de entropia cria e atribui um código sem prefixo único para cada símbolo único que ocorre na entrada. Esses codificadores de entropia, então, compactam os dados substituindo cada símbolo de entrada de comprimento fixo pela palavra-código de saída livre de prefixo de comprimento variável correspondente. O comprimento de cada palavra-código é aproximadamente proporcional ao logaritmo negativo da probabilidade de ocorrência dessa palavra-código. Portanto, os símbolos mais comuns usam os códigos mais curtos.

De acordo com o teorema de codificação da fonte de Shannon , o comprimento de código ideal para um símbolo é , onde é o número de símbolos usados ​​para fazer códigos de saída e é a probabilidade do símbolo de entrada. ${\ displaystyle -log_ {b} (P)}$${\ displaystyle b}$${\ displaystyle P}$

Duas das técnicas de codificação de entropia mais comuns são a codificação de Huffman e a codificação aritmética . Se as características aproximadas de entropia de um fluxo de dados forem conhecidas com antecedência (especialmente para compressão de sinal ), um código estático mais simples pode ser útil. Esses códigos estáticos incluem códigos universais (como codificação gama de Elias ou codificação de Fibonacci ) e códigos de Golomb (como codificação unária ou codificação de Rice ).

Desde 2014, os compressores de dados começaram a usar a família Asymmetric Numeral Systems de técnicas de codificação de entropia, que permite a combinação da taxa de compressão da codificação aritmética com um custo de processamento semelhante à codificação de Huffman .

Entropia como medida de similaridade

Além de usar a codificação de entropia como uma forma de compactar dados digitais, um codificador de entropia também pode ser usado para medir a quantidade de similaridade entre fluxos de dados e classes de dados já existentes. Isso é feito gerando um codificador / compressor de entropia para cada classe de dados; dados desconhecidos são então classificados alimentando os dados não compactados para cada compressor e vendo qual compressor produz a maior compactação. O codificador com a melhor compactação é provavelmente o codificador treinado nos dados mais semelhantes aos dados desconhecidos.

Veja também

• Codificação aritmética
• Sistemas numéricos assimétricos (ANS)
• Codificação aritmética binária adaptável ao contexto (CABAC)
• Codificação Huffman
• Codificação de alcance

Referências

links externos

• Teoria da Informação, Inferência e Algoritmos de Aprendizagem , de David MacKay (2003), oferece uma introdução à teoria de Shannon e compressão de dados, incluindo a codificação de Huffman e a codificação aritmética .
• Source Coding , de T. Wiegand e H. Schwarz (2011).