> mtf | move | front <
// Move-to-Front - Reordenação dinâmica de listas para melhor compressão
Auto-adaptativo
Adapta-se automaticamente aos padrões locais dos dados.
Explora a localidade
Símbolos recentes recebem índices menores para melhor compressão.
Parte do bzip2
Usado após a BWT no pipeline de compactação do bzip2.
>> informações técnicas
Como o MTF funciona:
O MTF mantém uma lista de todos os símbolos possíveis. Ao codificar um símbolo, ele emite a posição atual na lista e, em seguida, move o símbolo para a frente. Isso faz com que símbolos usados recentemente tenham índices menores, o que é melhor comprimido por codificadores de entropia subsequentes.
Exemplo de codificação:
Texto: "banana" Lista inicial: [a,b,c,d,...] "b": índice 1, mover b→frente [b,a,c,d,...] "a": índice 1, mover a→frente [a,b,c,d,...] "n": índice 13, mover n→frente [n,a,b,c,...] "a": índice 1, mover a→frente [a,n,b,c,...] "n": índice 1, mover n→frente [n,a,b,c,...] "a": índice 1, mover a→frente [a,n,b,c,...] Saída: [1,1,13,1,1,1]
Por que usar MTF:
- >Melhora a redundância local
- >Funciona bem com BWT
- >Implementação simples
- >Transformação reversível
- >Adapta-se aos padrões
>> perguntas frequentes
O que é codificação Move-to-Front?
MTF é um algoritmo de transformação de dados que codifica cada símbolo como o seu índice em uma lista atualizada dinamicamente. Após codificar cada símbolo, ele é movido para a frente da lista, fazendo com que símbolos frequentes tenham índices menores.
Por que usar MTF com BWT?
A BWT agrupa contextos semelhantes e cria repetições locais. O MTF transforma essas repetições em números pequenos (muitos 0 e 1), que se comprimem muito bem com codificação por comprimento de sequência ou com codificação de Huffman.
Como funciona a lista no MTF?
A lista começa com todos os 256 possíveis valores de byte em ordem. À medida que os símbolos são codificados, os valores usados são movidos para a frente. Símbolos usados recentemente permanecem perto do início com índices menores, enquanto símbolos pouco usados migram para índices maiores.
MTF versus outras transformações?
O MTF foi projetado especificamente para ser usado após a BWT. Isoladamente, não é tão eficaz, mas é excelente para transformar a saída da BWT em uma forma que se comprime bem. É mais simples do que a codificação aritmética, mas um pouco menos ideal.