Iscrizione
In questo articolo parlerò del famoso algoritmo di Huffman e della sua applicazione nella compressione dei dati.
Di conseguenza, scriveremo un semplice archiviatore. Questo è già stato discusso , ma senza attuazione pratica. Il materiale teorico del presente post è tratto dalle lezioni di informatica scolastica e dal libro di Robert Laforet “Data Structures and Algorithms in Java”. Quindi è tutto tagliato!
Un piccolo pensiero
In un normale file di testo, un carattere è codificato con 8 bit (codifica ASCII) o 16 (codifica Unicode). Successivamente considereremo la codifica ASCII. Ad esempio, prendi la riga s1 = “SUSIE DICE CHE È FACILEn”. Ci sono un totale di 22 caratteri nella riga, naturalmente, inclusi gli spazi e il carattere di nuova riga - 'n'. Il file contenente questa riga peserà 22*8 = 176 bit. Sorge immediatamente la domanda: è razionale utilizzare tutti gli 8 bit per codificare 1 carattere? Non utilizziamo tutti i caratteri ASCII. Anche se lo facessero, sarebbe più razionale che alla lettera più comune - S - fosse assegnato il codice più breve possibile, e che alla lettera più rara - T (o U, o "n") - fosse assegnato un codice più lungo. Ecco in cosa consiste l'algoritmo di Huffman: è necessario trovare l'opzione di codifica ottimale in cui il file avrà il peso minimo. È abbastanza normale che la lunghezza del codice differisca per i diversi simboli: questo è ciò su cui si basa l'algoritmo.
codifica
Perché non dare al carattere 'S' un codice, ad esempio lungo 1 bit: 0 o 1. Lascia che sia 1. Poi il secondo carattere più comune - ' ' (spazio) - dai 0. Immagina di aver iniziato a decodificare il tuo messaggio - la stringa codificata s1 - e vedi che il codice inizia con 1. Allora, cosa fai: è questo il carattere S, o è qualche altro carattere, ad esempio A? Pertanto, emerge una regola importante:
Nessuno dei due codici dovrebbe essere il prefisso di un altro
Questa regola è fondamentale nell'algoritmo. Pertanto, la creazione di un codice inizia con una tabella di frequenza, che indica la frequenza (numero di occorrenze) di ciascun simbolo:
I caratteri con il maggior numero di occorrenze dovrebbero essere codificati meno possibile numero di bit. Darò un esempio di una delle possibili tabelle di codici:
Quindi il messaggio codificato sarà simile a questo:
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 ogni carattere con uno spazio. Ciò non accadrà in un file veramente compresso!
La domanda sorge spontanea: come ha fatto questo ragazzo a inventare il codice per creare una tabella di codici? Questo sarà discusso di seguito.
Costruire un albero di Huffman
È qui che gli alberi di ricerca binari vengono in soccorso. Non preoccuparti, non avrai bisogno dei metodi di ricerca, inserimento o eliminazione qui. Ecco la struttura ad 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à riportato di seguito.
Ecco l'algoritmo per costruire l'albero:
- Crea un oggetto Nodo per ogni carattere del messaggio (riga s1). Nel nostro caso ci saranno 9 nodi (oggetti Node). Ogni nodo è costituito da due campi dati: simbolo e frequenza
- Crea un oggetto Tree (BinaryTree) per ciascun nodo. Il nodo diventa la radice dell'albero.
- Inserisci questi alberi nella coda di priorità. Minore è la frequenza, maggiore è la priorità. Pertanto, durante l'estrazione, viene sempre selezionato il dervo con la frequenza più bassa.
Successivamente è necessario eseguire ciclicamente le seguenti operazioni:
- Rimuovi due alberi dalla coda di priorità e rendili figli del nuovo nodo (il nodo appena creato senza la lettera). La frequenza del nuovo nodo è pari alla somma delle frequenze dei due alberi discendenti.
- Per questo nodo, crea un albero con la radice in questo nodo. Reinserisci questo albero nella coda di priorità. (Poiché l'albero ha una nuova frequenza, molto probabilmente apparirà in una nuova posizione nella coda)
- Continua i passaggi 1 e 2 finché non rimane un solo albero in coda: l'albero di Huffman
Considera questo algoritmo sulla riga s1:
Qui il simbolo “lf” (linefeed) indica una nuova riga, “sp” (spazio) è uno spazio.
E poi cosa?
Abbiamo un albero di Huffman. OK. E cosa farne? Non lo prenderanno nemmeno gratis e poi bisogna tracciare tutti i percorsi possibili dalla radice alle foglie dell’albero. Concordiamo di denotare un arco 0 se conduce al figlio sinistro e 1 se conduce a quello destro. A rigor di termini, in questa notazione, il codice di un simbolo è il percorso dalla radice dell'albero alla foglia contenente proprio questo simbolo.
Ecco come è risultata la tabella dei codici. Nota che se consideriamo questa tabella, possiamo concludere sul "peso" di ciascun simbolo: questa è la 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 . All'inizio pesava 176 bit. Di conseguenza, lo abbiamo ridotto fino a 176/65 = 2.7 volte! Ma questa è un'utopia. È improbabile che si ottenga un coefficiente del genere. Perché? Questo sarà discusso un po' più tardi.
Decodifica
Bene, forse la cosa più semplice rimasta è la decodifica. Penso che molti di voi abbiano intuito che non possiamo semplicemente creare un file compresso senza alcun accenno a come è stato codificato: non saremo in grado di decodificarlo! Sì, sì, è stato difficile per me realizzarlo, ma dovrò creare un file di testo table.txt con una tabella di compressione:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Voce della tabella nella forma 'simbolo' 'codice carattere'. Perché 01110 è senza simbolo? In effetti, è con un simbolo, è solo che gli strumenti Java che utilizzo durante l'output in un file, il carattere di nuova riga - 'n' - viene convertito in una nuova riga (non importa quanto possa sembrare stupido). Pertanto la riga vuota in alto è il carattere per il codice 01110. Per il codice 00 il carattere è uno spazio all'inizio della riga. Dirò subito che per il nostro coefficiente Khan, questo metodo di memorizzazione della tabella può affermare di essere il più irrazionale. Ma è facile da capire e implementare. Sarò felice di ascoltare i tuoi consigli nei commenti riguardo all'ottimizzazione.
Avere questa tabella rende molto facile la decodifica. Ricordiamo quale regola abbiamo seguito durante la creazione della codifica:
Nessuno dei due codici dovrebbe essere il prefisso di un altro
È qui che svolge un ruolo di facilitazione. Leggiamo in sequenza bit per bit e, non appena la stringa risultante d, composta dai bit letti, corrisponde alla codifica corrispondente al carattere del carattere, sappiamo immediatamente che il carattere del carattere (e solo quello!) è stato codificato. Successivamente, scriviamo il carattere nella riga di decodifica (la riga contenente il messaggio decodificato), reimpostiamo la riga d e quindi leggiamo il file codificato.
implementazione
È ora di umiliare il mio codice e scrivere un archiviatore. Chiamiamolo Compressore.
Ricominciare. Prima di tutto scriviamo la classe Node:
public class Node {
private int frequence;//частота
private char letter;//буква
private Node leftChild;//левый потомок
private Node rightChild;//правый потомок
public Node(char letter, int frequence) { //собственно, конструктор
this.letter = letter;
this.frequence = frequence;
}
public Node() {}//перегрузка конструтора для безымянных узлов(см. выше в разделе о построении дерева Хаффмана)
public void addChild(Node newNode) {//добавить потомка
if (leftChild == null)//если левый пустой=> правый тоже=> добавляем в левый
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) //в общем, левым потомком
rightChild = newNode;//станет тот, у кого меньше частота
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence();//итоговая частота
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() {//проверка на лист
return leftChild == null && rightChild == null;
}
}
Ora l'albero:
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;//да-да, очередь будет на базе списка
class PriorityQueue {
private ArrayList<BinaryTree> data;//список очереди
private int nElems;//кол-во элементов в очереди
public PriorityQueue() {
data = new ArrayList<BinaryTree>();
nElems = 0;
}
public void insert(BinaryTree newTree) {//вставка
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i < nElems; i++) {
if (data.get(i).getFrequence() > newTree.getFrequence()) {//если частота вставляемого дерева меньше
data.add(i, newTree);//чем част. текущего, то cдвигаем все деревья на позициях справа на 1 ячейку
break;//затем ставим новое дерево на позицию текущего
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++;//увеличиваем кол-во элементов на 1
}
public BinaryTree remove() {//удаление из очереди
BinaryTree tmp = data.get(0);//копируем удаляемый элемент
data.remove(0);//собственно, удаляем
nElems--;//уменьшаем кол-во элементов на 1
return tmp;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
La classe che crea l'albero di Huffman:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127;//длина кодировочной таблицы
private String myString;//сообщение
private BinaryTree huffmanTree;//дерево Хаффмана
private int[] freqArray;//частотная таблица
private String[] encodingArray;//кодировочная таблица
//----------------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();
//алгоритм описан выше
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {//если символ существует в строке
Node newNode = new Node((char) i, freqArray[i]);//то создать для него Node
BinaryTree newTree = new BinaryTree(newNode);//а для Node создать BinaryTree
pq.insert(newTree);//вставить в очередь
}
}
while (true) {
BinaryTree tree1 = pq.remove();//извлечь из очереди первое дерево.
try {
BinaryTree tree2 = pq.remove();//извлечь из очереди второе дерево
Node newNode = new Node();//создать новый Node
newNode.addChild(tree1.getRoot());//сделать его потомками два извлеченных дерева
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) {//осталось одно дерево в очереди
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) {//заполнить кодировочную таблицу
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() {//для отладки
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Encoding table====================");
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 contenente quale codifica/decodifica:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127;//длина таблицы
private HuffmanTree mainHuffmanTree;//дерево Хаффмана (используется только для сжатия)
private String myString;//исходное сообщение
private int[] freqArray;//частотаная таблица
private String[] encodingArray;//кодировочная таблица
private double ratio;//коэффициент сжатия
public HuffmanOperator(HuffmanTree MainHuffmanTree) {//for compress
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {}//for extract;
//---------------------------------------compression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = "";//промежуточная строка(без добавочных нулей)
//System.out.println("=============================Compression=======================");
//displayEncodingArray();
for (int i = 0; i < myString.length(); i++) {
intermidiate += encodingArray[myString.charAt(i)];
}
//Мы не можем писать бит в файл. Поэтому нужно сделать длину сообщения кратной 8=>
//нужно добавить нули в конец(можно 1, нет разницы)
byte counter = 0;//количество добавленных в конец нулей (байта в полне хватит: 0<=counter<8<127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) {//delta - количество добавленных нулей
intermidiate += "0";
}
//склеить кол-во добавочных нулей в бинарном предаствлении и промежуточную строку
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
//идеализированный коэффициент
setCompressionRatio();
//System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() {//посчитать идеализированный коэффициент
double sumA = 0, sumB = 0;//A-the original sum
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() {//final compression
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();
//получить кол-во вставленных нулей
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, т.к. первым байтом у нас идет кол-во вставленных нулей
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) {//если совпало
decompressed += (char)j;//то добавляем элемент
current = "";//и обнуляем текущую строку
}
}
}
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() {//для отладки
System.out.println("======================Encoding table====================");
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("========================================================");
}
}
Una classe che semplifica la scrittura su un 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("Неверный путь, или такого файла не существует!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Una classe che semplifica la lettura da un 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)//если закончился файл
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Bene, e 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 {//указываем инструкцию с помощью аргументов командной строки
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("Неверный формат ввода аргументов ");
System.out.println("Читайте 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("Неверный путь, или такого файла не существует!");
return;
} catch (MalformedInputException e) {
System.out.println("Текущая кодировка файла не поддерживается");
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("Путь к сжатому файлу: " + compressedFile.getAbsolutePath());
System.out.println("Путь к кодировочной таблице " + table.getAbsolutePath());
System.out.println("Без таблицы файл будет невозможно извлечь!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100;//идеализированный коэффициент
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100;//настоящий коэффициент
System.out.println("Идеализированный коэффициент сжатия равен " + idealRatio);
System.out.println("Коэффициент сжатия с учетом кодировочной таблицы " + 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("Путь к распакованному файлу " + extractedFile.getAbsolutePath());
}
}
Dovrai scrivere tu stesso il file readme.txt :)
conclusione
Immagino che fosse tutto quello che volevo dire. Se hai qualcosa da dire sulla mia incompetenza nel migliorare il codice, l'algoritmo o qualsiasi ottimizzazione in generale, sentiti libero di scrivere. Se non vi ho spiegato nulla scrivete anche voi. Mi piacerebbe sentire la tua opinione nei commenti!
PS
Sì, sì, sono ancora qui, perché non mi sono dimenticato del coefficiente. Per la stringa s1, la tabella di codifica pesa 48 byte, molto più grande del file sorgente, e non abbiamo dimenticato gli zeri aggiuntivi (il numero di zeri aggiunti è 7) => il rapporto di compressione sarà inferiore a uno: 176/ (65 + 48*8 + 7) = 0.38. Se anche tu hai notato questo, allora non è solo il tuo viso ad essere bello. Sì, questa implementazione sarà estremamente inefficiente per file di piccole dimensioni. Ma cosa succede ai file di grandi dimensioni? Le dimensioni dei file sono molto maggiori delle dimensioni della tabella di codifica. È qui che l'algoritmo funziona come dovrebbe! Ad esempio, per L'archiviatore produce un coefficiente reale (non idealizzato) di 1.46 - quasi una volta e mezza! E sì, il file doveva essere in inglese.
Fonte: habr.com