Qual è lo stato attuale degli algoritmi di compressione di solo testo?

Question

In onore del Premio Hutter , quali sono gli algoritmi principali (e una breve descrizione di ciascuno) per la compressione del testo?

Nota: lo scopo di questa domanda è ottenere una descrizione degli algoritmi di compressione, non dei programmi di compressione.

Answer 1

I compressori che spingono i confini combinano algoritmi per risultati folli. Gli algoritmi comuni includono:

• La Burrows-Wheeler Transform e qui - riordina i caratteri (o altri blocchi di bit) con un algoritmo prevedibile per aumentare i blocchi ripetuti che facilitano la compressione della sorgente. La decompressione si verifica normalmente e il risultato non viene mischiato con la trasformazione inversa. Nota: BWT da solo non comprime nulla. Semplifica la compressione della fonte.
• Pronostico per corrispondenza parziale (PPM) - un'evoluzione di codifica aritmetica in cui il modello di previsione (contesto) viene creato sgretolando le statistiche sulla fonte rispetto all'utilizzo delle probabilità statiche. Anche se le sue radici sono nella codifica aritmetica, il risultato può essere rappresentato con la codifica Huffman o un dizionario, nonché con la codifica aritmetica.
• Miscelazione del contesto: la codifica aritmetica utilizza un contesto statico per la previsione, PPM sceglie dinamicamente un singolo contesto, la miscelazione del contesto utilizza molti contesti e pesa i loro risultati. PAQ utilizza il mixaggio di contesto. Ecco una panoramica di alto livello.
• Compressione dinamica di Markov - correlata a PPM ma utilizza contesti a livello di bit rispetto a byte o più a lungo.
• Inoltre, i concorrenti del premio Hutter possono sostituire il testo comune con voci a byte piccolo da dizionari esterni e differenziare il testo in maiuscolo e minuscolo con un simbolo speciale rispetto a due voci distinte. Ecco perché sono così bravi a comprimere il testo (in particolare il testo ASCII) e non altrettanto preziosi per la compressione generale.

Compressione massima è un sito di riferimento di compressione generale e testo piuttosto interessante. Matt Mahoney pubblica un altro benchmark . Mahoney potrebbe essere di particolare interesse perché elenca l'algoritmo primario utilizzato per voce.

Answer 2

C'è sempre lzip .

Scherzi a parte:

• Per quanto riguarda la compatibilità, PKZIP (algoritmo DEFLATE ) vince ancora.
• bzip2 è il miglior compromesso tra godere di una base di installazione relativamente ampia e un rapporto di compressione piuttosto buono, ma richiede un archiviatore separato.
• 7-Zip (algoritmo LZMA ) si comprime molto bene ed è disponibile per sotto la LGPL. Tuttavia, pochi sistemi operativi sono dotati di supporto integrato.
• rzip è una variante di bzip2 che a mio avviso merita più attenzione. Potrebbe essere particolarmente interessante per enormi file di registro che richiedono l'archiviazione a lungo termine. Richiede anche un archiviatore separato.

Answer 3

Se si desidera utilizzare PAQ come programma, è possibile installare il pacchetto zpaq su sistemi basati su debian. L'utilizzo è (vedi anche man zpaq )

zpaq c archivename.zpaq file1 file2 file3

La compressione era di circa 1/10 della dimensione di un file zip . (1,9 M contro 15 M)