Entrée
Dans cet article, je parlerai de l'algorithme bien connu de Huffman, ainsi que de son application dans la compression de données.
En conséquence, nous écrirons un simple archiveur. Cela a déjà été , mais sans mise en œuvre pratique. Le matériel théorique du poste actuel est tiré des cours d'informatique à l'école et du livre de Robert Laforet "Data Structures and Algorithms in Java". Donc, tout est sous la coupe !
Une petite pensée
Dans un fichier texte normal, un caractère est codé sur 8 bits (codage ASCII) ou 16 (codage Unicode). Ensuite, nous considérerons le codage ASCII. Par exemple, prenons la chaîne s1 = "SUSIE SAYS IT IS EASYn". Au total, il y a bien sûr 22 caractères dans la ligne, y compris les espaces et le caractère de nouvelle ligne – « n ». Le fichier contenant cette ligne pèsera 22*8 = 176 bits. La question se pose immédiatement : est-il rationnel d'utiliser les 8 bits pour coder 1 caractère ? Nous n'utilisons pas tous les caractères ASCII. Même s'ils l'étaient, il serait plus rationnel de donner à la lettre la plus fréquente - S - le code le plus court possible, et pour la lettre la plus rare - T (ou U, ou 'n') - de donner le code plus authentique. Il s'agit de l'algorithme de Huffman : vous devez trouver la meilleure option d'encodage, dans laquelle le fichier aura un poids minimum. Il est tout à fait normal que différents caractères aient des longueurs de code différentes - c'est la base de l'algorithme.
Codage
Pourquoi ne pas donner au caractère « S » un code, par exemple d'une longueur de 1 bit : 0 ou 1. Laissez-le être 1. Ensuite, le deuxième caractère le plus fréquent - " " (espace) - nous donnerons 0. Imaginez, vous avez commencé à décodez votre message - chaîne codée s1 - et vous voyez que le code commence par 1. Alors, que faire : est-ce le caractère S, ou est-ce un autre caractère, comme A ? Par conséquent, une règle importante s’impose :
Aucun code ne doit être le préfixe d'un autre
Cette règle est la clé de l'algorithme. Par conséquent, la création du code commence par un tableau de fréquence, qui indique la fréquence (nombre d'occurrences) de chaque symbole :
Les caractères avec le plus d'occurrences doivent être codés avec le moins d'occurrences. possible le nombre de bits. Je vais donner un exemple d'une des tables de codes possibles :
Le message codé ressemblera donc à ceci :
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
J'ai séparé le code de chaque caractère par un espace. Cela n’arrivera pas vraiment dans un fichier compressé !
La question se pose : comment ce débutant a-t-il trouvé un code pour créer une table de codes ? Ceci sera discuté ci-dessous.
Construire un arbre de Huffman
C'est là que les arbres de recherche binaires viennent à la rescousse. Ne vous inquiétez pas, vous n'aurez pas besoin des méthodes de recherche, d'insertion et de suppression ici. Voici l'arborescence 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;
}
...
}
Ce n'est pas le code complet, le code complet sera ci-dessous.
Voici l’algorithme pour construire un arbre :
- Créez un objet Node pour chaque caractère du message (ligne s1). Dans notre cas, il y aura 9 nœuds (objets Node). Chaque nœud se compose de deux champs de données : symbole et fréquence
- Créez un objet Tree (BinaryTree) pour chacun des nœuds Node. Le nœud devient la racine de l'arbre.
- Insérez ces arbres dans la file d'attente prioritaire. Plus la fréquence est basse, plus la priorité est élevée. Ainsi, lors de l’extraction, l’arbre ayant la fréquence la plus basse est toujours sélectionné.
Ensuite, vous devez effectuer cycliquement ce qui suit :
- Récupérez deux arbres de la file d'attente prioritaire et faites-en les enfants d'un nouveau nœud (un nœud nouvellement créé sans lettre). La fréquence du nouveau nœud est égale à la somme des fréquences des deux arbres descendants.
- Pour ce nœud, créez une arborescence enracinée sur ce nœud. Réinsérez cet arbre dans la file d'attente prioritaire. (Puisque l'arbre a une nouvelle fréquence, il occupera très probablement une nouvelle place dans la file d'attente)
- Continuez les étapes 1 et 2 jusqu'à ce qu'il reste un arbre dans la file d'attente : l'arbre de Huffman.
Considérez cet algorithme sur la ligne s1 :
Ici, le symbole "lf" (saut de ligne) désigne une nouvelle ligne, "sp" (espace) est un espace.
Et puis quoi?
Nous avons l'arbre de Huffman. D'ACCORD. Et qu'en faire ? Ils ne le prendront pas gratuitement. Et puis, il faut tracer tous les chemins possibles depuis la racine jusqu'aux feuilles de l'arbre. Nous acceptons d'étiqueter une arête 0 si elle mène à l'enfant de gauche et 1 si elle mène à celui de droite. À proprement parler, dans ces notations, le code du caractère est le chemin depuis la racine de l'arbre jusqu'à la feuille contenant ce même caractère.
Ainsi, le tableau des codes s'est avéré. Notez que si l'on considère ce tableau, nous pouvons conclure sur le "poids" de chaque caractère - c'est la longueur de son code. Ensuite, sous forme compressée, le fichier source pèsera : 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits . Au début, il pesait 176 bits. Par conséquent, nous l’avons réduit jusqu’à 176/65 = 2.7 fois ! Mais c'est une utopie. Il est peu probable qu’un tel ratio puisse être obtenu. Pourquoi? Cela sera discuté un peu plus tard.
Décodage
Eh bien, la chose la plus simple qui reste est peut-être le décodage. Je pense que beaucoup d'entre vous ont deviné qu'il est impossible de simplement créer un fichier compressé sans aucune indication sur la façon dont il a été encodé - nous ne pourrons pas le décoder ! Oui, oui, j'ai eu du mal à m'en rendre compte, mais je dois créer un fichier texte table.txt avec une table de compression :
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Entrée de table sous la forme 'caractère'"code de caractère". Pourquoi 01110 n'a-t-il pas de symbole ? En fait, c'est avec un symbole, juste les outils Java que j'utilise lors de la sortie dans un fichier, que le caractère de nouvelle ligne - 'n' - est converti en une nouvelle ligne (aussi stupide que cela puisse paraître). Par conséquent, la ligne vide ci-dessus est le caractère du code 01110. Pour le code 00, le caractère est un espace en début de ligne. Je dois dire tout de suite que cette méthode de stockage du tableau peut se targuer d'être la plus irrationnelle pour notre coefficient khan. Mais c’est facile à comprendre et à mettre en œuvre. Je serai heureux d'entendre vos recommandations dans les commentaires sur l'optimisation.
Avec ce tableau, il est très simple de décoder. Rappelons par quelle règle nous avons été guidés lors de la création de l'encodage :
Aucun code ne doit être le préfixe d'un autre
C'est là qu'il joue un rôle facilitateur. Nous lisons petit à petit de manière séquentielle, et dès que la chaîne résultante d, constituée des bits lus, correspond au codage correspondant au caractère caractère, nous savons immédiatement que le caractère caractère (et seulement lui !) a été codé. Ensuite, nous écrivons un caractère dans la chaîne de décodage (la chaîne contenant le message décodé), réinitialisons la chaîne d et lisons davantage le fichier codé.
exécution
Il est temps d'humilier mon code en écrivant un archiveur. Appelons-le Compresseur.
Recommencer. Tout d’abord, nous écrivons 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;
}
}
Maintenant l'arbre :
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;
}
}
File d'attente de priorité:
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 qui crée l'arbre 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;
}
}
La classe contenant which encode/décode :
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("========================================================");
}
}
Une classe qui facilite l'écriture dans un fichier :
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();
}
}
Une classe qui facilite la lecture à partir d'un fichier :
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();
}
}
Eh bien, et 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());
}
}
Vous devrez écrire vous-même le fichier avec les instructions readme.txt 🙂
Conclusion
Je suppose que c'est tout ce que je voulais dire. Si vous avez quelque chose à dire sur mon incompétence en matière d'améliorations du code, de l'algorithme, en général, de toute optimisation, alors n'hésitez pas à écrire. Si je n'ai pas expliqué quelque chose, écrivez-moi également. J'aimerais avoir de vos nouvelles dans les commentaires !
PS
Oui, oui, je suis toujours là, car je n'ai pas oublié le coefficient. Pour la chaîne s1, la table d'encodage pèse 48 octets - bien plus que le fichier original, et ils n'ont pas oublié les zéros supplémentaires (le nombre de zéros ajoutés est de 7) => le taux de compression sera inférieur à un : 176 /(65 + 48*8 + 7) = 0.38. Si vous avez également remarqué cela, alors ce n'est pas en face que vous avez fini. Oui, cette implémentation sera extrêmement inefficace pour les petits fichiers. Mais qu’arrive-t-il aux fichiers volumineux ? La taille des fichiers est bien supérieure à la taille de la table d'encodage. C’est là que l’algorithme fonctionne comme il se doit ! Par exemple, pour l'archiveur donne un coefficient réel (non idéalisé) égal à 1.46 - presque une fois et demie ! Et oui, le dossier était censé être en anglais.
Source: habr.com