Como calcular os parâmetros ideais para um esquema de codificação start-step-stop?

Question

Um código start-step-stop é uma técnica de compactação de dados usada para compactar números relativamente pequenos.

O código funciona da seguinte maneira:Possui três parâmetros, start, step e stop.Start determina a quantidade de bits usados ​​para calcular os primeiros números.Step determina quantos bits adicionar à codificação quando acabarmos e stop determina a quantidade máxima de bits usados ​​para codificar um número.

Portanto, o comprimento de uma codificação é dado por l = start + step * i.

O valor "i" de um código específico é codificado usando unário.Ou seja, um número de bits 1 seguido por um bit 0 final.Se chegarmos ao stop, podemos eliminar o bit 0 final.Se i for zero, escrevemos apenas o bit 0.

Portanto, um código start-step-stop (1, 2, 5) funcionaria da seguinte maneira:

Valor 0, codificado como:0 0
Valor 1, codificado como:0 1
Valor 2, codificado como:10.000
Valor 9, codificado como:10 111
Valor 10, codificado como:11 00000
Valor 41, codificado como:11 11111

Então, dado um arquivo contendo vários números, como podemos calcular os códigos de início-passo-parada ideais para esse arquivo?Os parâmetros ideais são definidos como aqueles que resultarão na maior taxa de compressão.

Answer 1

Esses códigos "start-step-stop" parecem uma maneira diferente de chamar Códigos de Huffman.Veja o técnica básica para obter um esboço do pseudocódigo para calculá-los.

Essencialmente, é isso que o algoritmo faz:

Antes de iniciar a codificação Huffman, você precisa reunir as estatísticas de cada símbolo que irá compactar (sua frequência total no arquivo a ser compactado).

Depois de fazer isso, você cria um árvore binária usando essas informações de forma que os símbolos usados ​​com mais frequência estejam no topo da árvore (e, portanto, usem menos bits) e de modo que nenhuma codificação tenha um código de prefixo.Pois se uma codificação tiver um prefixo comum pode haver ambiguidades na descompactação.

No final da codificação de Huffman, seu valor inicial será a profundidade do nó folha mais raso, seu passo sempre será 1 (logicamente isso faz sentido, por que você forçaria mais bits do que o necessário, basta adicionar um de cada vez) e seu valor de parada será a profundidade do nó folha mais profundo.

Se as estatísticas de frequência não estiverem classificadas, será necessário O (nlog n) para fazer; se forem classificadas por frequência, isso poderá ser feito em O (n).

Os códigos Huffman têm a garantia de ter a melhor compactação média para este tipo de codificação:

Huffman foi capaz de projetar o máximo método de compressão eficiente deste tipo:nenhum outro mapeamento de indivíduo símbolos de origem para cadeias de caracteres exclusivas de bits produzirão uma média menor tamanho de saída quando o símbolo real frequências coincidem com as frequências utilizadas para Crie o código.

Isso deve ajudá-lo a implementar a solução ideal para o seu problema.

Editar: Embora semelhante, não era isso que o OP estava procurando.

Esse trabalho acadêmico do criador desses códigos descreve uma generalização dos códigos start-step-stop, códigos start-stop.No entanto, o autor descreve brevemente como obter o start-step-stop ideal próximo ao final da seção 2.Envolve o uso de uma variável estatística aleatória ou o financiamento de força bruta, a melhor combinação.Sem qualquer conhecimento prévio do arquivo, o algoritmo é O((log n)^3).

Espero que isto ajude.

Answer 2

A abordagem que usei foi uma solução simples de força bruta.O algoritmo seguiu estas etapas básicas:

1. Conte a frequência de cada número no arquivo.Na mesma passagem, calcule a quantidade total de números no arquivo e determine o maior número como maxNumber.

2. Calcule a probabilidade de cada número como sua frequência dividida pela quantidade total de números no arquivo.

3. Determine "optimalStop" como igual a log2(maxNumber).Este é o número ideal de bits que deve ser usado para representar maxNumber como na teoria da informação de Shannon e, portanto, uma estimativa razoável da quantidade máxima ideal de bits usados ​​na codificação de um número específico.

4. Para cada valor "inicial" de 1 a "optimalStop", repita as etapas 5 a 7:

5. Para cada valor de "etapa" de 1 a ("optimalStop" - "start") / 2, repita as etapas 6 e 7:

6. Calcule o valor "stop" mais próximo de "optimalStop" que satisfaça stop = start + step * i para algum número inteiro i.

7. Calcule o número médio de bits que seriam usados ​​por esta codificação.Isso pode ser calculado como a probabilidade de cada número multiplicada pelo comprimento do bit na codificação fornecida.

8. Escolha a codificação com o menor número médio de bits.