Entrada
Neste artigo, falarei do coñecido algoritmo de Huffman, así como da súa aplicación na compresión de datos.
Como resultado, escribiremos un arquivo simple. Isto xa foi , pero sen implementación práctica. O material teórico do presente post está tomado das clases de informática escolares e do libro de Robert Laforet "Data Structures and Algorithms in Java". Entón, todo está baixo o corte!
Unha pequena reflexión
Nun ficheiro de texto normal, un carácter está codificado con 8 bits (codificación ASCII) ou 16 (codificación Unicode). A continuación, consideraremos a codificación ASCII. Por exemplo, tome a cadea s1 = "SUSIE DICE QUE É FÁCILn". En total, hai 22 caracteres na liña, por suposto, incluíndo espazos e o carácter de nova liña - 'n'. O ficheiro que contén esta liña pesará 22*8 = 176 bits. Xorde inmediatamente a pregunta: é racional usar os 8 bits para codificar 1 carácter? Non usamos todos os caracteres ASCII. Aínda que o fosen, sería máis racional darlle á letra máis frecuente -S- o código máis curto posible, e á letra máis rara -T (ou U, ou 'n')- darlle o código máis auténtico. Este é o algoritmo de Huffman: cómpre atopar a mellor opción de codificación, na que o ficheiro terá un peso mínimo. É bastante normal que os distintos caracteres teñan diferentes lonxitudes de código: esta é a base do algoritmo.
Codificación
Por que non darlle ao carácter "S" un código, por exemplo, de 1 bit: 0 ou 1. Deixa que sexa 1. Entón o segundo carácter que máis aparece - " " (espazo) darémoslle 0. Imaxina que comezaches a decodifica a túa mensaxe -cadea codificada s1- e ves que o código comeza por 1. Entón, que facer: é o carácter S ou é algún outro carácter, como A? Polo tanto, xorde unha regra importante:
Ningún código debe ser un prefixo doutro
Esta regra é a clave do algoritmo. Polo tanto, a creación do código comeza cunha táboa de frecuencias, que indica a frecuencia (número de aparicións) de cada símbolo:
Os caracteres con máis ocorrencias deben codificarse coa menor cantidade posible o número de bits. Vou poñer un exemplo dunha das posibles táboas de códigos:
Entón, a mensaxe codificada terá o seguinte aspecto:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Separei o código de cada carácter cun espazo. Isto non ocorrerá realmente nun ficheiro comprimido!
Xorde a pregunta: como se lle ocorreu a este novato un código como crear unha táboa de códigos? Isto será discutido a continuación.
Construíndo unha árbore de Huffman
Aquí é onde as árbores de busca binarias veñen ao rescate. Non te preocupes, aquí non necesitarás os métodos de busca, inserción e eliminación. Aquí está a estrutura da árbore en 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;
}
...
}
Este non é o código completo, o código completo estará a continuación.
Aquí está o algoritmo para construír unha árbore:
- Crea un obxecto Node para cada carácter da mensaxe (liña s1). No noso caso, haberá 9 nodos (obxectos Node). Cada nodo consta de dous campos de datos: símbolo e frecuencia
- Cree un obxecto Tree (BinaryTree) para cada un dos nodos Node. O nodo convértese na raíz da árbore.
- Insira estas árbores na cola de prioridades. Canto menor sexa a frecuencia, maior será a prioridade. Así, ao extraer, sempre se selecciona a árbore coa frecuencia máis baixa.
A continuación, cómpre facer o seguinte:
- Recupera dúas árbores da cola de prioridades e convérteas fillos dun novo nodo (un nodo recén creado sen letra). A frecuencia do novo nodo é igual á suma das frecuencias das dúas árbores descendentes.
- Para este nodo, cree unha árbore enraizada neste nodo. Insira esta árbore de novo na cola de prioridades. (Xa que a árbore ten unha nova frecuencia, o máis probable é que entre nun lugar novo da cola)
- Continúa cos pasos 1 e 2 ata que quede unha árbore na cola: a árbore de Huffman
Considere este algoritmo na liña s1:
Aquí o símbolo "lf" (salida de liña) indica unha nova liña, "sp" (espazo) é un espazo.
Que hai seguinte?
Temos a árbore de Huffman. OK. E que facer con el? Non o levarán de balde. E entón, cómpre trazar todos os camiños posibles desde a raíz ata as follas da árbore. Acordamos etiquetar un borde 0 se conduce ao fillo esquerdo e 1 se conduce ao dereito. En rigor, nestas notacións, o código de carácter é o camiño desde a raíz da árbore ata a folla que contén este mesmo carácter.
Así, a táboa de códigos resultou. Teña en conta que se consideramos esta táboa, podemos concluír sobre o "peso" de cada carácter - esta é a lonxitude do seu código. Entón, en forma comprimida, o ficheiro fonte pesará: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits . Nun principio pesaba 176 bits. Polo tanto, reducimos ata 176/65 = 2.7 veces! Pero isto é unha utopía. É improbable que se obteña tal proporción. Por que? Isto será discutido un pouco máis tarde.
Decodificación
Ben, quizais o máis sinxelo que quede sexa decodificar. Creo que moitos de vós adiviñades que é imposible simplemente crear un ficheiro comprimido sen ningunha pista sobre como foi codificado - non poderemos decodificalo! Si, si, foime difícil entender isto, pero teño que crear un ficheiro de texto table.txt cunha táboa de compresión:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Entrada da táboa na forma "carácter" "código de carácter". Por que 01110 está sen símbolo? De feito, é cun símbolo, só as ferramentas java que uso cando saio a un ficheiro, o carácter de nova liña - 'n' - convértese nunha nova liña (por moi estúpido que pareza). Polo tanto, a liña baleira anterior é o carácter do código 01110. Para o código 00, o carácter é un espazo ao comezo da liña. Debo dicir de inmediato que este método de almacenar a táboa pode afirmar que é o máis irracional para o noso coeficiente khan. Pero é fácil de entender e implementar. Estarei encantado de escoitar as túas recomendacións nos comentarios sobre a optimización.
Con esta táboa, é moi doado decodificar. Lembremos por que regra nos guiou ao crear a codificación:
Ningún código debe ser un prefixo doutro
Aquí é onde xoga un papel facilitador. Lemos de forma secuencial bit a bit, e en canto a cadea resultante d, formada polos bits lidos, coincide coa codificación correspondente ao carácter carácter, inmediatamente sabemos que o carácter carácter (e só el!) foi codificado. A continuación, escribimos o carácter na cadea decodificada (a cadea que contén a mensaxe descodificada), restablecemos a cadea d e lemos máis adiante o ficheiro codificado.
Implantación
É hora de humillar o meu código escribindo un arquivador. Chamémoslle Compresor.
Comezar de novo. En primeiro lugar, escribimos a clase 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;
}
}
Agora a árbore:
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;
}
}
Fila 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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
A clase que crea a árbore de 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;
}
}
A clase que contén que 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("========================================================");
}
}
Unha clase que facilita a escritura nun ficheiro:
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();
}
}
Unha clase que facilita a lectura dun ficheiro:
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();
}
}
Ben, e a clase 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());
}
}
Terás que escribir o ficheiro coas instrucións readme.txt ti mesmo 🙂
Conclusión
Supoño que iso é todo o que quería dicir. Se ten algo que dicir sobre a miña incompetencia de melloras no código, algoritmo, en xeral, calquera optimización, entón non dubide en escribir. Se non expliquei algo, escriba tamén. Encantaríame saber de ti nos comentarios!
PS
Si, si, sigo aquí, porque non me esquecín do coeficiente. Para a cadea s1, a táboa de codificación pesa 48 bytes, moito máis que o ficheiro orixinal, e non se esqueceron dos ceros adicionais (o número de ceros engadidos é 7) => a relación de compresión será inferior a un: 176 /(65 + 48*8 + 7) = 0.38. Se tamén notaches isto, entón non estás de cara. Si, esta implementación será extremadamente ineficiente para ficheiros pequenos. Pero que pasa cos ficheiros grandes? Os tamaños dos ficheiros son moito máis grandes que o tamaño da táboa de codificación. Aquí é onde o algoritmo funciona como debería! Por exemplo, para o arquivador dá un coeficiente real (non idealizado) igual a 1.46 - case unha vez e media! E si, o ficheiro debía estar en inglés.
Fonte: www.habr.com