> 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.
// Exemplo resolvido
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// Exemplos de código
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> Mais perguntas
P: Para que serve o Move-to-Front?
R: MTF não é compressão em si, mas uma transformação: símbolos recentes recebem índices pequenos. Surgem muitos 0 e 1, que um codificador de entropia (Huffman, aritmético) comprime bem.
P: Qual a relação com a transformada de Burrows-Wheeler?
R: A BWT agrupa caracteres iguais em sequências. O MTF as converte em números pequenos, sobretudo 0. A cadeia BWT → MTF → RLE → Huffman é a do bzip2.
P: O MTF é sem perdas e reversível?
R: Sim. O decodificador começa com a mesma lista inicial e segue os mesmos movimentos. A lista inicial (alfabeto e ordem) deve ser idêntica nos dois lados.