Introduzione
In questo articolo parlerò del noto algoritmo di Huffman e del suo utilizzo nella compressione dei dati.
Di conseguenza, realizzeremo un semplice arquiviatore. Ne ho già parlato , ma senza una realizzazione pratica. Il materiale teorico di questo post proviene dalle lezioni scolastiche di informatica e dal libro di Robert Lafore "Data Structures and Algorithms in Java". Quindi, tutto sotto!
Alcune riflessioni
In un normale file di testo, un carattere è codificato in 8 bit (codifica ASCII) o 16 (codifica Unicode). In seguito, considereremo la codifica ASCII. Prendiamo ad esempio la stringa s1 = «SUSIE SAYS IT IS EASYn». Ci sono in totale 22 caratteri nella stringa, ovviamente inclusi spazi e il carattere di ritorno a capo — ‘n’. Il file contenente questa stringa peserà 22*8 = 176 bit. Subito si pone la domanda: è razionale utilizzare tutti e 8 i bit per codificare 1 carattere? Non utilizziamo tutti i caratteri della codifica ASCII. Anche se lo facessimo, sarebbe più razionale dare alla lettera più frequente — S — il codice più corto possibile, mentre alla lettera meno frequente — T (o U, o ‘n’) — un codice più lungo. Questo è il principio dell'algoritmo di Huffman: trovare l'opzione ottimale di codifica in cui il file avrà il peso minimo. È del tutto normale che la lunghezza del codice per diversi caratteri vari — è proprio su questo che si basa l'algoritmo.
Codifica
Perché non dare al carattere ‘S’ un codice, ad esempio, di 1 bit: 0 o 1. Supponiamo che sia 1. Allora daremo a ‘ ‘(spazio), il secondo carattere più frequente, 0. Immagina di aver iniziato a decodificare il tuo messaggio — la stringa codificata s1 — e vedi che il codice inizia con 1. Allora, cosa devi fare: è il carattere S, o è un altro carattere, come A? Pertanto, sorge una regola importante:
Nessun codice deve essere un prefisso di un altro
Questa regola è fondamentale nell'algoritmo. Pertanto, la creazione di un codice inizia con una tabella delle frequenze, in cui è indicata la frequenza (il numero di occorrenze) di ciascun carattere:
I caratteri con il maggior numero di occorrenze devono essere codificati con il minor numero possibile di bit. Ecco un esempio di una possibile tabella dei codici:
Pertanto, il messaggio codificato apparirà così:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Ho separato il codice di ciascun carattere con uno spazio. In un file compresso non ci sarà davvero nulla di tutto ciò!
Sorge la domanda: come ha fatto questo principiante a inventare un codice e a creare una tabella dei codici? Di questo parleremo più avanti.
Costruzione dell'albero di Huffman
Qui entrano in gioco gli alberi binari di ricerca. Non preoccuparti, non saranno necessari metodi di ricerca, inserimento o cancellazione. Ecco la struttura dell'albero in java:
public class Node {
private int frequence;
private char letter;
private Node leftChild;
private Node rightChild;
...
}
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
...
}
Questo non è il codice completo, il codice completo sarà fornito più avanti.
Ecco l'algoritmo stesso per costruire l'albero:
- Creare un oggetto Node per ogni carattere del messaggio (stringa s1). Nel nostro caso ci saranno 9 nodi (oggetti Node). Ogni nodo consiste in due campi dati: carattere e frequenza.
- Creare un oggetto Albero (BinaryTree) per ciascuno dei nodi Node. Il nodo diventa la radice dell'albero.
- Inserire questi alberi in una coda di priorità. Più bassa è la frequenza, maggiore è la priorità. Così facendo, viene sempre scelto l'albero con la frequenza più bassa.
Dopodiché, è necessario eseguire ciclicamente quanto segue:
- Estrarre due alberi dalla coda di priorità e farli diventare figli di un nuovo nodo (il nodo appena creato senza lettera). La frequenza del nuovo nodo è uguale alla somma delle frequenze dei due alberi figli.
- Per questo nodo, creare un albero con la radice in questo nodo. Inserire di nuovo questo albero nella coda di priorità. (Poiché l'albero ha una nuova frequenza, è probabile che assuma una nuova posizione nella coda.)
- Continuare a eseguire i passi 1 e 2 finché nella coda non rimane un solo albero — l'albero di Huffman.
Consideriamo questo algoritmo sulla stringa s1:
Qui il simbolo «lf» (linefeed) indica il passaggio a una nuova riga, «sp» (space) — è uno spazio.
E poi?
Abbiamo ottenuto l'albero di Huffman. Bene, e cosa farne? Non lo prendono nemmeno gratuitamente. E poi, dobbiamo tracciare tutti i possibili percorsi dalla radice alle foglie dell'albero. Concordiamo di indicare il bordo 0 se va al figlio sinistro e 1 — se va al destro. In termini rigorosi, in queste designazioni, il codice del simbolo è il percorso dalla radice dell'albero alla foglia che contiene proprio quel simbolo.
In questo modo abbiamo ottenuto la tabella dei codici. Notiamo che, esaminando questa tabella, possiamo trarre la conclusione sul "peso" di ogni simbolo: si tratta della lunghezza del suo codice. Quindi, in forma compressa, il file originale peserà: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bit. Inizialmente pesava 176 bit. Di conseguenza, lo abbiamo ridotto a ben 176/65 = 2.7 volte! Ma questa è utopia. È difficile che tale coefficiente venga raggiunto. Perché? Ne parleremo più avanti.
Decodifica
Bene, rimane l'operazione più semplice: la decodifica. Penso che molti di voi avranno capito che non si può semplicemente creare un file compresso senza alcun riferimento su come è stato codificato: non saremo in grado di decodificarlo! Sì, è stato difficile da accettare, ma dovremo creare un file di testo table.txt con la tabella di compressione:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Registrazione della tabella nella forma 'simbolo'«codice simbolo». Perché 01110 è senza simbolo? In realtà, ha un simbolo; solo che gli strumenti java che utilizzo per l'output nel file convertono il carattere di ritorno a capo - 'n' - in un salto di riga (per quanto possa sembrare sciocco). Pertanto, la riga vuota in alto è il simbolo per il codice 01110. Per il codice 00, il simbolo è uno spazio all'inizio della riga. Dico subito che il nostro coefficiente ha dei problemi: questo modo di memorizzare la tabella può essere considerato il meno razionale. Ma è semplice da capire e implementare. Sarò felice di ascoltare i vostri suggerimenti nei commenti riguardo all'ottimizzazione.
Con questa tabella, è molto semplice decodificare. Ricordiamo quale regola abbiamo seguito durante la creazione della codifica:
Nessun codice deve essere un prefisso di un altro.
Ed è proprio qui che questa regola semplifica le cose. Leggiamo bit per bit, e non appena la stringa d, composta dai bit letti, corrisponde alla codifica associata al simbolo character, sappiamo immediatamente che è stato codificato il simbolo character (e solo lui!). Successivamente, registriamo character nella stringa decodificata (la stringa contenente il messaggio decodificato), azzeriamo la stringa d e continuiamo a leggere il file codificato.
Implementazione
È giunto il momento di mettere alla prova il mio codice e scrivere un compressore. Lo chiameremo Compressor.
Iniziamo dall'inizio. La prima cosa è scrivere la classe Node:
public class Node {
private int frequence; // frequenza
private char letter; // lettera
private Node leftChild; // figlio sinistro
private Node rightChild; // figlio destro
public Node(char letter, int frequence) { // costruttore
this.letter = letter;
this.frequence = frequence;
}
public Node() {} // sovraccarico del costruttore per nodi anonimi (vedi sopra nella sezione sulla costruzione dell'albero di Huffman)
public void addChild(Node newNode) { // aggiungere un nodo figlio
if (leftChild == null) // se il sinistro è vuoto => anche il destro è vuoto => aggiungiamo a sinistra
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) // in generale, diventa il nodo figlio destro
rightChild = newNode; // diventerà quel che ha frequenza inferiore
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence(); // frequenza totale
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() { // verifica se è un foglia
return leftChild == null && rightChild == null;
}
}
Ora per l'alberello:
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
public int getFrequence() {
return root.getFrequence();
}
public Node getRoot() {
return root;
}
}
Coda prioritaria:
import java.util.ArrayList; // sì, la coda sarà basata su una lista
class PriorityQueue {
private ArrayList data; // lista della coda
private int nElems; // numero di elementi nella coda
public PriorityQueue() {
data = new ArrayList();
nElems = 0;
}
public void insert(BinaryTree newTree) { // inserimento
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i newTree.getFrequence()) { // se la frequenza dell'albero inserito è inferiore
data.add(i, newTree); // spostiamo tutti gli alberi a destra di una cella
break; // poi mettiamo il nuovo albero nella posizione dell'attuale
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++; // aumentiamo il numero di elementi di 1
}
public BinaryTree remove() { // rimozione dalla coda
BinaryTree tmp = data.get(0); // copiamo l'elemento da rimuovere
data.remove(0); // in effetti, rimuoviamo
nElems--; // diminuiamo il numero di elementi di 1
return tmp; // restituiamo l'elemento rimosso (l'elemento con la frequenza più bassa)
}
}
Classe che crea l'albero di Huffman:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127; // lunghezza della tabella di codifica
private String myString; // messaggio
private BinaryTree huffmanTree; // albero di Huffman
private int[] freqArray; // tabella delle frequenze
private String[] encodingArray; // tabella di codifica
//----------------constructor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[ENCODING_TABLE_SIZE];
fillFrequenceArray();
huffmanTree = getHuffmanTree();
encodingArray = new String[ENCODING_TABLE_SIZE];
fillEncodingArray(huffmanTree.getRoot(), "", "");
}
//--------------------frequence array------------------------
private void fillFrequenceArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrequenceArray() {
return freqArray;
}
//------------------------huffman tree creation------------------
private BinaryTree getHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
// algoritmo descritto sopra
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) { // se il simbolo esiste nella stringa
Node newNode = new Node((char) i, freqArray[i]); // allora creare un Node per esso
BinaryTree newTree = new BinaryTree(newNode); // e creare un BinaryTree per il Node
pq.insert(newTree); // inserire nella coda
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // estrarre il primo albero dalla coda.
try {
BinaryTree tree2 = pq.remove(); // estrarre il secondo albero dalla coda
Node newNode = new Node(); // creare un nuovo Node
newNode.addChild(tree1.getRoot()); // rendere figli i due alberi estratti
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode));
} catch (IndexOutOfBoundsException e) { // rimane un solo albero nella coda
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) { // riempi la tabella di codifica
if (node.isLeaf()) {
encodingArray[(int)node.getLetter()] = codeBefore + direction;
} else {
fillEncodingArray(node.getLeftChild(), codeBefore + direction, "0");
fillEncodingArray(node.getRightChild(), codeBefore + direction, "1");
}
}
String[] getEncodingArray() {
return encodingArray;
}
public void displayEncodingArray() { // per il debug
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Tabella di codifica====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
}
}
System.out.println("========================================================");
}
//-----------------------------------------------------
String getOriginalString() {
return myString;
}
}
Classe che contiene la codifica/decodifica:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // dimensione della tabella
private HuffmanTree mainHuffmanTree; // albero di Huffman (utilizzato solo per la compressione)
private String myString; // messaggio originale
private int[] freqArray; // tabella delle frequenze
private String[] encodingArray; // tabella di codifica
private double ratio; // coefficiente di compressione
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // per comprimere
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // per estrarre;
// ---------------------------------------compression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; // stringa intermedia (senza zeri aggiuntivi)
// System.out.println("=============================Compression=======================");
// displayEncodingArray();
for (int i = 0; i
// dobbiamo aggiungere zeri alla fine (uno può bastare, non fa differenza)
byte counter = 0; // numero di zeri aggiunti alla fine (un byte è sufficiente: 0<=counter<8<127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta; counter++) { // delta - numero di zeri aggiunti
intermidiate += "0";
}
// unire la quantità di zeri aggiunti nella rappresentazione binaria e la stringa intermedia
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
// coefficiente idealizzato
setCompressionRatio();
// System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { // calcolare il coefficiente idealizzato
double sumA = 0, sumB = 0; // A - somma originale
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
sumA += 8 * freqArray[i];
sumB += encodingArray[i].length() * freqArray[i];
}
}
ratio = sumA / sumB;
}
public byte[] getBytedMsg() { // compressione finale
StringBuilder compressedString = new StringBuilder(getCompressedString());
byte[] compressedBytes = new byte[compressedString.length() / 8];
for (int i = 0; i < compressedBytes.length; i++) {
compressedBytes[i] = (byte) Integer.parseInt(compressedString.substring(i * 8, (i + 1) * 8), 2);
}
return compressedBytes;
}
// ---------------------------------------end of compression----------------------------------------------------------------
// ------------------------------------------------------------extract-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
// displayEncodingArray();
// ottenere il numero di zeri aggiunti
for (int i = 0; i < 8; i++)
delta += compressed.charAt(i);
int ADDED_ZEROES = Integer.parseInt(delta, 2);
for (int i = 8, l = compressed.length() - ADDED_ZEROES; i < l; i++) {
// i = 8, poiché il primo byte contiene il numero di zeri aggiunti
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { // se corrisponde
decompressed += (char)j; // allora aggiungiamo l'elemento
current = ""; // e resettiamo la stringa corrente
}
}
}
return decompressed;
}
public String getEncodingTable() {
String enc = "";
for (int i = 0; i < encodingArray.length; i++) {
if (freqArray[i] != 0)
enc += (char)i + encodingArray[i] + 'n';
}
return enc;
}
public double getCompressionRatio() {
return ratio;
}
public void displayEncodingArray() { // per il debug
System.out.println("======================Tabella di codifica====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
// if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
// }
}
System.out.println("========================================================");
}
}
Classe che facilita la scrittura su file:
import java.io.File;
import java.io.PrintWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.Closeable;
public class FileOutputHelper implements Closeable {
private File outputFile;
private FileOutputStream fileOutputStream;
public FileOutputHelper(File file) throws FileNotFoundException {
outputFile = file;
fileOutputStream = new FileOutputStream(outputFile);
}
public void writeByte(byte msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeBytes(byte[] msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeString(String msg) {
try (PrintWriter pw = new PrintWriter(outputFile)) {
pw.write(msg);
} catch (FileNotFoundException e) {
System.out.println("Percorso non valido o file inesistente!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Classe che facilita la lettura da file:
import java.io.FileInputStream;
import java.io.EOFException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
public class FileInputHelper implements Closeable {
private FileInputStream fileInputStream;
private BufferedReader fileBufferedReader;
public FileInputHelper(File file) throws IOException {
fileInputStream = new FileInputStream(file);
fileBufferedReader = new BufferedReader(new InputStreamReader(fileInputStream));
}
public byte readByte() throws IOException {
int cur = fileInputStream.read();
if (cur == -1) // se il file è finito
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException {
fileInputStream.close();
}
}
E infine, la classe principale:
import java.io.File;
import java.nio.charset.MalformedInputException;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.NoSuchFileException;
import java.nio.file.Paths;
import java.util.List;
import java.io.EOFException;
public class Main {
private static final byte ENCODING_TABLE_SIZE = 127;
public static void main(String[] args) throws IOException {
try {//specific instruction involves command-line arguments
if (args[0].equals("--compress") || args[0].equals("-c"))
compress(args[1]);
else if ((args[0].equals("--extract") || args[0].equals("-x"))
&& (args[2].equals("--table") || args[2].equals("-t"))) {
extract(args[1], args[3]);
}
else
throw new IllegalArgumentException();
} catch (ArrayIndexOutOfBoundsException | IllegalArgumentException e) {
System.out.println("Formato di input argomenti non valido ");
System.out.println("Controlla Readme.txt");
e.printStackTrace();
}
}
public static void compress(String stringPath) throws IOException {
List<String> stringList;
File inputFile = new File(stringPath);
String s = "";
File compressedFile, table;
try {
stringList = Files.readAllLines(Paths.get(inputFile.getAbsolutePath()));
} catch (NoSuchFileException e) {
System.out.println("Percorso non valido o il file non esiste!");
return;
} catch (MalformedInputException e) {
System.out.println("La codifica attuale del file non è supportata");
return;
}
for (String item : stringList) {
s += item;
s += 'n';
}
HuffmanOperator operator = new HuffmanOperator(new HuffmanTree(s));
compressedFile = new File(inputFile.getAbsolutePath() + ".cpr");
compressedFile.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(compressedFile)) {
fo.writeBytes(operator.getBytedMsg());
}
//create file with encoding table:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Percorso del file compresso: " + compressedFile.getAbsolutePath());
System.out.println("Percorso della tabella di codifica " + table.getAbsolutePath());
System.out.println("Senza tabella, il file non può essere estratto!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100;//coefficiente ideale
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100;//coefficiente reale
System.out.println("Il coefficiente ideale di compressione è " + idealRatio);
System.out.println("Il coefficiente di compressione tenendo conto della tabella di codifica " + realRatio);
}
public static void extract(String filePath, String tablePath) throws FileNotFoundException, IOException {
HuffmanOperator operator = new HuffmanOperator();
File compressedFile = new File(filePath),
tableFile = new File(tablePath),
extractedFile = new File(filePath + ".xtr");
String compressed = "";
String[] encodingArray = new String[ENCODING_TABLE_SIZE];
//read compressed file
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!check here:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte();//method returns EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
//--------------------
//read encoding table:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine();//skip first empty string
encodingArray[(byte)'n'] = fi.readLine();//read code for 'n'
while (true) {
String s = fi.readLine();
if (s == null)
throw new EOFException();
encodingArray[(byte)s.charAt(0)] = s.substring(1, s.length());
}
} catch (EOFException ignore) {}
extractedFile.createNewFile();
//extract:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Percorso del file estratto " + extractedFile.getAbsolutePath());
}
}
Dovrete scrivere voi stessi il file di istruzioni readme.txt 🙂
Conclusione
Probabilmente è tutto ciò che volevo dire. Se avete qualcosa da dire riguardo alla mia incompetenza in miglioramenti del codice, algoritmi o in qualsiasi ottimizzazione, non esitate a scrivere. Se qualcosa non è chiaro, scrivetelo. Sarò felice di sentirvi nei commenti!
P.S.
Sì, sì, sono ancora qui, perché non ho dimenticato il coefficiente. Per la stringa s1, la tabella di codifica pesa 48 byte, molto più del file originale, e non dimentichiamo gli zeri aggiuntivi (il numero di zeri aggiunti è pari a 7) => il coefficiente di compressione sarà inferiore a uno: 176/(65 + 48*8 + 7)=0.38. Se anche voi lo avete notato, complimenti, non vi è sfuggito. Sì, questa implementazione sarà estremamente inefficace per file piccoli. Ma cosa succede con file grandi? Le dimensioni del file superano di gran lunga la dimensione della tabella di codifica. Qui l'algoritmo funziona come dovrebbe! Per esempio, per il compressore fornisce un rapporto reale (non ideale) pari a 1.46, quasi un uno e mezzo! Ed era previsto che il file fosse in inglese.
Fonte: habr.com
