> bwt | transformar | comprimir <
// Burrows-Wheeler Transform - transformação de texto reversível para melhorar a compressão
>> recursos
Totalmente reversível
Transformação sem perdas que pode ser revertida exatamente.
Agrupamento de caracteres
Agrupa caracteres semelhantes para facilitar a compressão em etapas posteriores.
Núcleo do bzip2
Base de muitos esquemas de compressão inspirados no bzip2.
>> informações técnicas
Como o BWT funciona
A transformada de Burrows-Wheeler gera todas as rotações cíclicas da cadeia de entrada, ordena-as lexicograficamente e devolve a última coluna da matriz ordenada junto com o índice da cadeia original. O resultado tende a agrupar caracteres semelhantes, o que proporciona excelente compressão com RLE, Move-to-Front e outros codificadores.
Exemplo de BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Por que usar BWT
- Melhora a capacidade de compressão dos dados
- É totalmente reversível
- Agrupa contextos semelhantes
- Base do algoritmo de compressão bzip2
- Pré-processamento eficiente para outros codificadores
>> perguntas frequentes
O que é a transformada de Burrows-Wheeler?
A transformada de Burrows-Wheeler (BWT) é um algoritmo reversível que reorganiza uma cadeia de caracteres para produzir sequências com muitos símbolos repetidos. Proposta por Michael Burrows e David Wheeler em 1994, é usada como etapa de pré-processamento em compressores como o bzip2 para melhorar as taxas de compressão.
Por que o BWT melhora a compressão?
O BWT agrupa caracteres que aparecem em contextos semelhantes, de forma que muitas ocorrências do mesmo símbolo fiquem próximas na saída. Essas sequências comprimem muito bem com codificação por comprimento de execução, transformada Move-to-Front e codificadores entrópicos como Huffman.
O que é o marcador EOF?
O marcador EOF (fim de arquivo), normalmente o símbolo '$' ou outro caractere único, garante que todas as rotações sejam distintas e permite recuperar a posição da cadeia original. Sem esse marcador, algumas cadeias não teriam representação única. No passo inverso, o marcador é removido.
O BWT comprime por conta própria?
Não. O BWT não é um compressor completo, mas uma transformação que torna os dados mais fáceis de comprimir. Em esquemas como o bzip2, ele é combinado com Move-to-Front, RLE e codificação de Huffman.