Compresión de datos de Huffman

Entrada


En este artículo hablaré sobre el conocido algoritmo Huffman, así como su aplicación en la compresión de datos.

Como resultado, escribiremos un archivador simple. Ya había un artículo al respecto sobre Habré , pero sin implementación práctica. El material teórico de la publicación actual está tomado de las lecciones de informática de la escuela y del libro de Robert Lafore "Estructuras de datos y algoritmos en Java". Entonces, ¡todo está por debajo!

Un poco de pensamiento


En un archivo de texto plano, un car√°cter est√° codificado con 8 bits (codificaci√≥n ASCII) o 16 (codificaci√≥n Unicode). Adem√°s consideraremos la codificaci√≥n ASCII. Por ejemplo, tome la l√≠nea s1 = "SUSIE DICE QUE ES F√ĀCIL \ n". En total, hay 22 caracteres en la l√≠nea, por supuesto, incluidos los espacios y el car√°cter de nueva l√≠nea - '\ n'. Un archivo que contiene esta l√≠nea pesar√° 22 * ‚Äč‚Äč8 = 176 bits. La pregunta surge de inmediato: ¬Ņes racional usar los 8 bits para codificar 1 car√°cter? No utilizamos todos los caracteres ASCII. Incluso si se usa, ser√≠a m√°s racional que la letra m√°s frecuente, S, diera el c√≥digo m√°s corto posible, y que la letra m√°s rara, T (o U, o '\ n'), diera un c√≥digo m√°s aut√©ntico. Este es el algoritmo de Huffman: necesita encontrar la mejor opci√≥n de codificaci√≥n, en la que el archivo tendr√° un peso m√≠nimo. Es bastante normal que las longitudes de los c√≥digos difieran para los diferentes caracteres; esta es la base del algoritmo.

Codificación


¬ŅPor qu√© no le da al car√°cter 'S' un c√≥digo, por ejemplo, 1 bit de longitud: 0 o 1. D√©jelo ser 1. Luego le daremos el segundo car√°cter m√°s encontrado - '' (espacio) - 0. Imag√≠nese, usted comenz√≥ a decodificar su mensaje - cadena codificada s1, y ve que el c√≥digo comienza con 1. Entonces, ¬Ņqu√© hacer? ¬ŅEs un car√°cter S, o es alg√ļn otro car√°cter, por ejemplo A? Por lo tanto, surge una regla importante:

Ning√ļn c√≥digo debe ser un prefijo de otro

Esta regla es la clave en el algoritmo. Por lo tanto, la creaci√≥n del c√≥digo comienza con la tabla de frecuencias, que indica la frecuencia (n√ļmero de ocurrencias) de cada car√°cter:

Los caracteres con m√°s ocurrencias deben codificarse con el menor n√ļmero posible de bits. Dar√© un ejemplo de una de las posibles tablas de c√≥digos:

Por lo tanto, el mensaje codificado se verá así:

10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 

Separé el código de cada personaje con un espacio. ¡Esto realmente no sucederá en un archivo comprimido!
Surge la pregunta: ¬Ņc√≥mo surgi√≥ esta salaga con un c√≥digo ? ¬ŅC√≥mo crear una tabla de c√≥digos? Esto se discutir√° a continuaci√≥n.

Construyendo un √°rbol huffman


Aqu√≠ los √°rboles de b√ļsqueda binarios vienen al rescate. No se preocupe, aqu√≠ no se requieren los m√©todos de b√ļsqueda, inserci√≥n y eliminaci√≥n. Aqu√≠ est√° la estructura de √°rbol 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 no es un código completo, el código completo estará debajo.

Aquí está el algoritmo de construcción del árbol en sí:

  1. Cree un objeto Nodo para cada carácter del mensaje (línea s1). En nuestro caso, habrá 9 nodos (objetos de nodo). Cada nodo consta de dos campos de datos: símbolo y frecuencia.
  2. Cree un objeto Tree (BinaryTree) para cada uno de los nodos Node. El nodo se convierte en la raíz del árbol.
  3. Pegue estos √°rboles en la cola de prioridad. Cuanto menor es la frecuencia, mayor es la prioridad. Por lo tanto, al extraer, el dervo siempre se selecciona con la frecuencia m√°s baja.

A continuación, debe hacer lo siguiente cíclicamente:

  1. Extraiga dos árboles de la cola de prioridad y conviértalos en descendientes del nuevo nodo (el nodo recién creado sin una letra). La frecuencia del nuevo nodo es igual a la suma de las frecuencias de dos árboles descendientes.
  2. Para este nodo, cree un árbol con una raíz en este nodo. Pegue este árbol nuevamente en la cola de prioridad. (Dado que el árbol tiene una nueva frecuencia, lo más probable es que llegue a un nuevo lugar en la cola)
  3. Contin√ļe los pasos 1 y 2 hasta que solo quede un √°rbol en la cola: el √°rbol Huffman

Considere este algoritmo en la línea s1:



Aquí, el símbolo "lf" (salto de línea) indica la transición a una nueva línea, "sp" (espacio) es un espacio.

Que sigue


Tenemos un √°rbol Huffman. Bien ¬ŅY qu√© hacer con eso? No lo tomar√°n gratis. Y luego, debes rastrear todos los caminos posibles desde la ra√≠z hasta las hojas del √°rbol. Aceptemos designar el borde 0 si conduce al descendiente izquierdo y 1 si al derecho. Estrictamente hablando, en estas anotaciones, el c√≥digo del s√≠mbolo es la ruta desde la ra√≠z del √°rbol hasta la hoja que contiene este mismo s√≠mbolo.



Así, la tabla de códigos resultó. Tenga en cuenta que si consideramos esta tabla, podemos concluir sobre el "peso" de cada carácter: esta es la longitud de su código. Entonces el archivo comprimido pesará: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits. Inicialmente, pesaba 176 bits. ¡Por lo tanto, lo redujimos hasta 176/65 = 2.7 veces! Pero esto es utopía. Es poco probable que se obtenga dicho coeficiente. Por qué Esto se discutirá un poco más tarde.

Decodificación


Bueno, quiz√°s lo m√°s simple que queda es la decodificaci√≥n. Creo que muchos de ustedes adivinaron que es imposible crear simplemente un archivo comprimido sin ning√ļn indicio de c√≥mo se codific√≥; ¬°no podremos decodificarlo! S√≠, fue dif√≠cil para m√≠ darme cuenta de esto, pero tuve que crear un archivo de texto table.txt con una tabla de compresi√≥n:

 01110 00 A010 E1111 I110 S10 T0110 U01111 Y1110 

Registre la tabla en forma de "car√°cter" "c√≥digo de car√°cter". ¬ŅPor qu√© es 01110 sin un personaje? De hecho, es con un car√°cter, solo las herramientas de Java que utilizo cuando imprimo en un archivo, el car√°cter de nueva l√≠nea es '\ n' -convertir a una nueva l√≠nea (no importa cu√°n est√ļpido suene). Por lo tanto, la l√≠nea vac√≠a en la parte superior es el car√°cter para el c√≥digo 01110. Para el c√≥digo 00, el car√°cter es un espacio al comienzo de la l√≠nea. Debo decir de inmediato que nuestro m√©todo para almacenar esta tabla puede ser el m√°s irracional. Pero es simple de entender e implementar. Estar√© encantado de escuchar sus recomendaciones en los comentarios sobre la optimizaci√≥n.

Tener esta mesa es muy fácil de decodificar. Recuerde qué regla nos guió al crear la codificación:

Ning√ļn c√≥digo debe anteponer otro

Aquí es donde juega un papel facilitador. Leemos secuencialmente bit a bit y, tan pronto como la cadena d recibida, que consiste en bits de lectura, coincide con la codificación correspondiente al carácter del carácter, inmediatamente sabemos que el carácter del carácter fue codificado (¡y solo eso!). A continuación, escribimos caracteres en la línea de decodificación (la línea que contiene el mensaje decodificado), ponemos a cero la línea d y luego leemos el archivo codificado.

Implementación


Es hora de humillar mi código escribiendo un archivador. Llamémoslo compresor.

Comencemos desde el principio. Primero, escribimos la 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; } } 

Ahora el arbol:

 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; } } 

Cola 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 clase que crea el √°rbol 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; } } 

Clase que contiene qué 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("========================================================"); } } 

Clase que facilita la escritura en un archivo:

 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(); } } 

Clase que facilita la lectura de un archivo:

 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(); } } 

Bueno, y la 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()); } } 

El archivo de instrucciones readme.txt depende de usted para escribir usted mismo :-)

Conclusión


Esto es probablemente todo lo que quería decir. Si tiene algo que decir sobre mi incompetencia de las mejoras en el código, el algoritmo y cualquier optimización en general, no dude en escribir. Si entendí mal algo, también escriba. Estaré encantado de saber de usted en los comentarios!

PS


S√≠, s√≠, todav√≠a estoy aqu√≠, porque no me olvid√© del coeficiente. Para la cadena s1, la tabla de codificaci√≥n pesa 48 bytes, mucho m√°s que el archivo original, y no se olvidaron de ceros adicionales (el n√ļmero de ceros agregados es 7) => la relaci√≥n de compresi√≥n ser√° menor que uno: 176 / (65 + 48 * 8 + 7) = 0.38. Si tambi√©n te diste cuenta de esto, simplemente no est√°s bien hecho. S√≠, esta implementaci√≥n ser√° extremadamente ineficiente para archivos peque√Īos. Pero, ¬Ņqu√© pasa con los archivos grandes? Los tama√Īos de archivo superan con creces el tama√Īo de la tabla de codificaci√≥n. ¬°Aqu√≠ el algoritmo funciona como deber√≠a! Por ejemplo, para el mon√≥logo de Fausto, el archivador proporciona un coeficiente real (no idealizado) igual a 1,46, ¬°casi una vez y media! Y s√≠, se supon√≠a que el archivo estaba en ingl√©s.

Source: https://habr.com/ru/post/438512/


All Articles