La compresión sin pérdida está limitada por cuánta redundancia puede ver un método. La familia LZ y la codificación Huffman alcanzan cada una una meseta en texto ordinario.
El informe DEC de Burrows y Wheeler de 1994 describió una transformada de ordenación por bloques: enumerar todas las rotaciones del bloque, ordenarlas y emitir la última columna. Como las rotaciones comparten sufijos, los caracteres idénticos se agrupan, y una breve pasada de codificación por longitud de racha y move-to-front convierte eso en muy pocos símbolos.
La transformada es invertible, así que es una reordenación, no una pérdida. El resultado alimentó a bzip2, que comprimía texto con más eficacia que las herramientas contemporáneas e hizo de la técnica el estándar para la compresión lenta pero ajustada.
Ordenar las rotaciones del bloque para que los vecinos semejantes queden juntos
Ordenar las rotaciones junta símbolos idénticos donde el contexto es el mismo.
La codificación por longitud de racha y move-to-front encuentra entonces rachas largas y baratas.
La transformada es una permutación, así que la descompresión es exacta.
Funciona sobre cualquier estructura repetida, así que no está ajustada a un tipo de archivo.
Antes de comprimir, reordena los datos para que los símbolos idénticos queden uno al lado del otro. Una transformada que agrupa las partes predecibles puede hacer que un compresor ordinario sea drásticamente más potente.
La transformada de Burrows-Wheeler se convirtió en el motor de bzip2 y más tarde en la base del FM-index, que encuentra subcadenas y mapea genomas. La misma idea impulsa hoy herramientas de alineamiento bioinformático de alto rendimiento.
CONSULTA LAS PRUEBAS
Las fuentes
- A block-sorting lossless data compression algorithm DEC Systems Research Center Research Report 124 · web.stanford.edu
- Burrows-Wheeler transform Wikipedia · en.wikipedia.org