Компресија података помоћу Хафмановог алгоритма

Улазак

У овом чланку ћу говорити о познатом Хафмановом алгоритму, као ио његовој примени у компресији података.

Као резултат тога, написаћемо једноставан архивер. Ово је већ било чланак о Хабреу, али без практичне имплементације. Теоријски материјал овог поста је преузет из школских часова информатике и књиге Роберта Лафорета "Структуре података и алгоритми у Јави". Дакле, све је испод реза!

Мало размишљања

У нормалној текстуалној датотеци, један знак је кодиран са 8 бита (АСЦИИ кодирање) или 16 (Уницоде кодирање). Затим ћемо размотрити АСЦИИ кодирање. На пример, узмите стринг с1 = "СУЗИЕ КАЖЕ ДА ЈЕ ЛАКО". Укупно, у реду има 22 знака, наравно, укључујући размаке и знак новог реда - 'н'. Датотека која садржи ову линију ће тежити 22*8 = 176 бита. Одмах се поставља питање: да ли је рационално користити свих 8 бита за кодирање 1 знака? Не користимо све АСЦИИ знакове. Чак и да јесу, било би рационалније дати најфреквентније слово - С - најкраћи могући код, а за најређе слово - Т (или У, или 'н') - дати шифру аутентичнији. Ово је Хафманов алгоритам: потребно је да пронађете најбољу опцију кодирања у којој ће датотека имати минималну тежину. Сасвим је нормално да ће различити знакови имати различите дужине кода - то је основа алгоритма.

Кодирање

Зашто не дате знаку 'С' код, на пример, дуг 1 бит: 0 или 1. Нека буде 1. Затим други најчешћи знак - ' ' (размак) - даћемо 0. Замислите, почели сте да декодирајте своју поруку - кодирани стринг с1 - и видите да код почиње са 1. Дакле, шта да радите: да ли је то знак С, или је то неки други знак, као што је А? Стога се поставља важно правило:

Ниједан код не сме бити префикс другог

Ово правило је кључ алгоритма. Стога, креирање кода почиње са табелом фреквенција, која указује на учесталост (број појављивања) сваког симбола:

Знакови са највише појављивања треба да буду кодирани са најмање могуће број битова. Даћу пример једне од могућих табела кодова:

Дакле, кодирана порука ће изгледати овако:

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

Одвојио сам код сваког знака размаком. Ово се заиста неће догодити у компримованој датотеци!
Поставља се питање: како је овај новајлија дошао до кода како да направи табелу кодова? О томе ће бити речи у наставку.

Изградња Хафмановог дрвета

Ту у помоћ прискачу стабла бинарног претраживања. Не брините, овде вам неће требати методе претраге, уметања и брисања. Ево структуре стабла у Јави:

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

Ово није комплетан код, цео код ће бити испод.

Ево алгоритма за прављење дрвета:

1. Креирајте објекат Ноде за сваки карактер из поруке (ред с1). У нашем случају биће 9 чворова (Ноде објецтс). Сваки чвор се састоји од два поља података: симбола и фреквенције
2. Креирајте објекат Трее (БинариТрее) за сваки чвор Чвора. Чвор постаје корен дрвета.
3. Уметните ова стабла у приоритетни ред. Што је фреквенција нижа, то је већи приоритет. Тако се приликом екстракције увек бира дрво са најнижом фреквенцијом.

Затим морате циклично да урадите следеће:

1. Преузми два стабла из реда приоритета и направи их потомцима новог чвора (новокреирани чвор без слова). Учесталост новог чвора једнака је збиру фреквенција два стабла потомака.
2. За овај чвор креирајте стабло укорењено на овом чвору. Вратите ово стабло у приоритетни ред. (Пошто дрво има нову фреквенцију, највероватније ће доћи на ново место у реду)
3. Наставите кораке 1 и 2 док једно дрво не остане у реду - Хафманово дрво

Размотрите овај алгоритам на линији с1:

Овде симбол "лф" (линефеед) означава нови ред, "сп" (размак) је размак.

И шта онда?

Имамо Хафманово дрво. ОК. И шта са тим? Неће га узети бесплатно, а онда треба да трасирате све могуће путеве од корена до лишћа дрвета. Слажемо се да ивицу означимо 0 ако води до левог детета и 1 ако води до десног. Строго говорећи, у овим нотацијама, код карактера је пут од корена дрвета до листа који садржи овај исти знак.

Тако се испоставила табела кодова. Имајте на уму да ако размотримо ову табелу, можемо закључити о "тежини" сваког знака - ово је дужина његовог кода. Затим, у компримованом облику, изворна датотека ће тежити: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 бита . У почетку је био тежак 176 бита. Дакле, смањили смо га за чак 176/65 = 2.7 пута! Али ово је утопија. Такав однос је мало вероватно да ће се добити. Зашто? О томе ће бити речи мало касније.

Декодирање

Па, можда је најједноставније што је остало је декодирање. Мислим да су многи од вас претпоставили да је немогуће једноставно креирати компримовани фајл без икаквих наговештаја о томе како је кодиран – нећемо моћи да га декодирамо! Да, да, било ми је тешко да ово схватим, али морам да направим текстуалну датотеку табле.ткт са табелом компресије:

01110
 00
A010
E1111
I110
S10
T0110
U01111
Y1110

Унос табеле у облику 'знак'"код карактера". Зашто је 01110 без симбола? У ствари, то је са симболом, само јава алати које користим приликом излаза у датотеку, знак новог реда - 'н' - се претвара у нови ред (ма колико глупо звучало). Према томе, празан ред изнад је знак за код 01110. За код 00, знак је размак на почетку реда. Морам одмах рећи да овај начин складиштења табеле може тврдити да је најирационалнији за наш кхан коефицијент. Али то је лако разумети и применити. Биће ми драго да чујем ваше препоруке у коментарима о оптимизацији.

Са овом табелом је врло лако декодирати. Подсетимо се којим правилом смо се руководили приликом креирања кодирања:

Ниједан код не сме бити префикс другог

Овде игра олакшавајућу улогу. Читамо бит по бит секвенцијално, и чим се резултујући низ д, који се састоји од прочитаних битова, поклопи са кодирањем које одговара карактерном карактеру, одмах знамо да је карактер карактера (и само он!) био кодиран. Затим уписујемо карактер у низ за декодирање (стринг који садржи декодирану поруку), ресетујемо д стринг и даље читамо кодирану датотеку.

Имплементација

Време је да понизим свој код писањем архиватора. Назовимо га Компресор.

Почети изнова. Пре свега, пишемо класу Ноде:

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

Сада дрво:

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

Приоритетни ред:

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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
    }
}

Класа која креира Хафманово дрво:

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

Класа која садржи који кодира/декодира:

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

Класа која олакшава писање у датотеку:

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

Класа која олакшава читање из датотеке:

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

Па, и главна класа:

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

Мораћете сами да напишете датотеку са упутствима реадме.ткт 🙂

Закључак

Ваљда је то све што сам хтео да кажем. Ако имате нешто да кажете о мојој неспособности побољшања кода, алгоритма, уопште, било какве оптимизације, онда слободно пишите. Ако нешто нисам објаснио, молим вас и напишите. Волео бих да чујем од вас у коментарима!

ПС

Да, да, још сам ту, јер нисам заборавио на коефицијент. За стринг с1, табела кодирања тежи 48 бајтова - много више од оригиналне датотеке, а нису заборавили на додатне нуле (број додатих нула је 7) => однос компресије ће бити мањи од један: 176 /(65 + 48*8 + 7) = 0.38. Ако сте и ви приметили ово, онда само не у лице добро сте урађени. Да, ова имплементација ће бити изузетно неефикасна за мале датотеке. Али шта се дешава са великим датотекама? Величине датотека су много веће од величине табеле кодирања. Овде алгоритам функционише како треба! На пример, за Фаустов монолог архивар даје реалан (не идеализован) коефицијент једнак 1.46 - скоро један и по пута! И да, фајл је требало да буде на енглеском.

Извор: ввв.хабр.цом