Intrare
În acest articol voi vorbi despre celebrul algoritm Huffman, precum și despre aplicarea lui în compresia datelor.
Ca rezultat, vom scrie un arhivator simplu. Acest lucru a fost deja discutat , dar fără implementare practică. Materialul teoretic al postului actual este preluat din lecțiile școlare de informatică și din cartea lui Robert Laforet „Data Structures and Algorithms in Java”. Deci, totul este tăiat!
Puțină reflecție
Într-un fișier text obișnuit, un caracter este codificat cu 8 biți (codare ASCII) sau 16 (codare Unicode). În continuare vom lua în considerare codificarea ASCII. De exemplu, luați linia s1 = „SUSIE SAYS IT IS EASYn”. Există un total de 22 de caractere în linie, desigur, inclusiv spații și caracterul de linie nouă - „n”. Fișierul care conține această linie va cântări 22*8 = 176 biți. Apare imediat întrebarea: este rațional să folosiți toți cei 8 biți pentru a codifica 1 caracter? Nu folosim toate caracterele ASCII. Chiar dacă ar fi făcut-o, ar fi mai rațional ca celei mai comune litere - S - să i se atribuie cel mai scurt cod posibil, iar celei mai rare litere - T (sau U, sau „n”) - să i se dea un cod mai lung. În asta constă algoritmul Huffman: este necesar să găsim opțiunea optimă de codificare în care fișierul să aibă greutatea minimă. Este destul de normal ca lungimile codului să difere pentru diferite simboluri - pe care se bazează algoritmul.
Codificare
De ce să nu dați caracterului „S” un cod, de exemplu, de 1 bit: 0 sau 1. Să fie 1. Apoi al doilea cel mai frecvent caracter - „ " (spațiu) - dați 0. Imaginați-vă că ați început să vă decodați mesajul - șirul codificat s1 - și vezi că codul începe cu 1. Deci, ce faci: acesta este caracterul S sau este un alt caracter, de exemplu A? Prin urmare, apare o regulă importantă:
Niciun cod nu trebuie să fie un prefix al altuia
Această regulă este cheia în algoritm. Prin urmare, crearea unui cod începe cu un tabel de frecvență, care indică frecvența (numărul de apariții) fiecărui simbol:
Caracterele cu cele mai multe apariții ar trebui să fie codificate cel puțin posibil număr de biți. Voi da un exemplu de unul dintre posibilele tabele de coduri:
Deci, mesajul codificat va arăta astfel:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Am separat codul fiecărui caracter cu un spațiu. Acest lucru nu se va întâmpla într-un fișier cu adevărat comprimat!
Apare întrebarea: cum a venit acest tânăr cu codul pentru a crea un tabel de coduri? Acest lucru va fi discutat mai jos.
Construirea unui copac Huffman
Aici vin în ajutor arborii binari de căutare. Nu vă faceți griji, nu veți avea nevoie de metodele de căutare, inserare sau ștergere aici. Iată structura arborelui în 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;
}
...
}
Acesta nu este codul complet, codul complet va fi mai jos.
Iată algoritmul pentru construirea arborelui:
- Creați un obiect Node pentru fiecare caracter din mesaj (linia s1). În cazul nostru vor fi 9 noduri (obiecte Node). Fiecare nod este format din două câmpuri de date: simbol și frecvență
- Creați un obiect Tree (BinaryTree) pentru fiecare Nod. Nodul devine rădăcina arborelui.
- Introduceți acești arbori în coada de prioritate. Cu cât frecvența este mai mică, cu atât prioritatea este mai mare. Astfel, la extracție, dervo cu cea mai joasă frecvență este întotdeauna selectat.
În continuare, trebuie să faceți următoarele în mod ciclic:
- Scoateți doi arbori din coada de prioritate și faceți-i copii ai noului nod (nodul creat fără litera). Frecvența noului nod este egală cu suma frecvențelor celor doi arbori descendenți.
- Pentru acest nod, creați un arbore cu rădăcina la acest nod. Inserați acest arbore înapoi în coada de prioritate. (Deoarece arborele are o frecvență nouă, cel mai probabil va apărea într-un loc nou din coadă)
- Continuați pașii 1 și 2 până când rămâne un singur copac în coadă - arborele Huffman
Luați în considerare acest algoritm pe linia s1:
Aici simbolul „lf” (linefeed) înseamnă o linie nouă, „sp” (spațiu) este un spațiu.
Și apoi ce?
Avem un copac Huffman. BINE. Și ce să faci cu ea? Nici măcar nu o vor lua gratuit Și apoi, trebuie să urmăriți toate căile posibile de la rădăcină până la frunzele copacului. Să fim de acord să notăm o muchie 0 dacă duce la copilul stâng și 1 dacă duce la cel drept. Strict vorbind, în această notație, codul unui simbol este calea de la rădăcina copacului până la frunza care conține chiar acest simbol.
Așa a rezultat tabelul de coduri. Rețineți că, dacă luăm în considerare acest tabel, putem concluziona despre „greutatea” fiecărui simbol - aceasta este lungimea codului său. Apoi, în formă comprimată, fișierul original va cântări: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 de biți . La început cântărea 176 de biți. În consecință, am redus-o cu până la 176/65 = 2.7 ori! Dar aceasta este o utopie. Este puțin probabil să se obțină un astfel de coeficient. De ce? Acest lucru va fi discutat puțin mai târziu.
Decodare
Ei bine, poate cel mai simplu lucru rămas este decodarea. Cred că mulți dintre voi ați ghicit că nu putem crea pur și simplu un fișier comprimat fără nici un indiciu despre cum a fost codificat - nu vom putea să-l decodificăm! Da, da, mi-a fost greu să realizez acest lucru, dar va trebui să creez un fișier text table.txt cu un tabel de compresie:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Intrare în tabel sub forma „simbol” „cod caracter”. De ce este 01110 fără simbol? De fapt, este cu un simbol, doar că instrumentele java pe care le folosesc la ieșire într-un fișier, caracterul newline - 'n' - este convertit într-o newline (oricât de stupid ar suna). Prin urmare, linia goală din partea de sus este caracterul pentru codul 01110. Pentru codul 00, caracterul este un spațiu la începutul liniei. Voi spune imediat că pentru coeficientul nostru Khan, această metodă de stocare a unui tabel se poate pretinde a fi cea mai irațională. Dar este ușor de înțeles și implementat. Voi fi bucuros să aud recomandările dumneavoastră în comentarii privind optimizarea.
Având acest tabel, este foarte ușor de decodat. Să ne amintim ce regulă am urmat când am creat codificarea:
Niciun cod nu trebuie să fie un prefix al altuia
Aici joacă un rol facilitator. Citim secvențial bit cu bit și, de îndată ce șirul rezultat d, format din biții citiți, se potrivește cu codificarea corespunzătoare caracterului caracter, știm imediat că caracterul caracter (și numai el!) a fost codificat. Apoi, scriem caracterul în linia de decodare (linia care conține mesajul decodat), resetam linia d și apoi citim fișierul codificat.
punerea în aplicare
Este timpul să-mi umilesc codul și să scriu un arhivator. Să-i spunem Compresor.
Începe de la capăt. În primul rând, scriem clasa 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;
}
}
Acum copacul:
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;
}
}
Coada prioritară:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Clasa care creează arborele 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;
}
}
Clasa care conține care codifică/decodifică:
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("========================================================");
}
}
O clasă care facilitează scrierea într-un fișier:
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();
}
}
O clasă care facilitează citirea dintr-un fișier:
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();
}
}
Ei bine, și clasa principală:
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());
}
}
Va trebui să scrieți singur fișierul readme.txt :)
Concluzie
Cred că asta e tot ce am vrut să spun. Dacă aveți ceva de spus despre incompetența mea de a îmbunătăți codul, algoritmul sau orice optimizare în general, atunci nu ezitați să scrieți. Daca nu ti-am explicat nimic, te rog sa scrii si tu. Mi-ar plăcea să aud de la tine în comentarii!
PS
Da, da, mai sunt aici, pentru că nu am uitat de coeficient. Pentru șirul s1, tabelul de codare cântărește 48 de octeți - mult mai mare decât fișierul sursă, și nu am uitat de zerourile suplimentare (numărul de zerouri adăugate este 7) => raportul de compresie va fi mai mic de unu: 176/ (65 + 48*8 + 7) = 0.38. Dacă și tu ai observat acest lucru, atunci nu doar fața ta este grozavă. Da, această implementare va fi extrem de ineficientă pentru fișierele mici. Dar ce se întâmplă cu fișierele mari? Dimensiunile fișierelor sunt mult mai mari decât dimensiunea tabelului de codificare. Aici algoritmul funcționează așa cum ar trebui! De exemplu, pentru Arhivatorul produce un coeficient real (nu idealizat) de 1.46 - aproape o dată și jumătate! Și da, dosarul trebuia să fie în engleză.
Sursa: www.habr.com