Вступ
У цій статті я розповім про відомий алгоритм Хаффмана, а також про його застосування у стисненні даних.
В результаті напишемо простенький архіватор. Про це вже була але без практичної реалізації. Теоретичний матеріал поточного посту взято зі шкільних уроків інформатики та книги Роберта Лафоре Data Structures and Algorithms in Java. Отже, все під кат!
Небагато роздумів
У звичайному текстовому файлі один символ кодується 8 бітами (кодування ASCII) або 16 (кодування Unicode). Далі розглядатимемо кодування ASCII. Наприклад візьмемо рядок s1 = «SUSIE SAYS IT IS EASYn». Усього в рядку 22 символи, природно, включаючи прогалини та символ переходу на новий рядок - 'n'. Файл, що містить цей рядок, важитиме 22*8 = 176 біт. Відразу постає питання: чи раціонально використовувати всі 8 біт для кодування 1 символу? Адже ми використовуємо не всі символи кодування ASCII. Навіть якби й використовували, раціональнішою було б найчастішою літерою - S - дати найкоротший можливий код, а для найрідкіснішої літери - T (або U, або 'n') - дати код довше. У цьому полягає алгоритм Хаффмана: необхідно знайти оптимальний варіант кодування, у якому файл буде мінімальної ваги. Цілком нормально, що різні символи довжини коду відрізнятимуться — на цьому й заснований алгоритм.
кодування
Чому б символу 'S' не дати код, наприклад, довжиною в 1 біт: 0 або 1. Нехай це буде 1. Тоді другому символу, що найбільш зустрічається, — ' (пробіл) — дамо 0. Уявіть собі, ви почали декодувати своє повідомлення — закодований рядок s1 — і бачите, що код починається з 1. Отже, що робити: це символ S, чи це якийсь інший символ, наприклад A? Тому виникає важливе правило:
Жоден код не повинен бути префіксом іншого
Це є ключовим в алгоритмі. Тому створення коду починається з частотної таблиці, в якій зазначено частоту (кількість входжень) кожного символу:
Символи з найбільшою кількістю входжень повинні кодуватись найменшим можливим кількістю бітів. Наведу приклад однієї з можливих таблиць кодів:
Таким чином, закодоване повідомлення виглядатиме так:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Код кожного символу я розділив пробілом. По-справжньому у стислому файлі такого не буде!
Випливає питання: як цей салага придумав код, як створити таблицю кодів? Про це йтиметься нижче.
Побудова дерева Хаффмана
Тут приходять на допомогу бінарні дерева пошуку. Не хвилюйтеся, тут методи пошуку, вставки та видалення не потрібні. Ось структура дерева на 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;
}
...
}
Це не повний код, повний код буде нижчим.
Ось сам алгоритм побудови дерева:
- Створити об'єкт Node для кожного символу з повідомлення (рядок s1). У нашому випадку буде 9 вузлів (об'єктів Node). Кожен вузол складається з двох полів даних: символ та частота
- Створити об'єкт Дерева (BinaryTree) для кожного з вузлів Node. Вузол стає коренем дерева.
- Вставити ці дерева у пріоритетну чергу. Чим менша частота, тим більший пріоритет. Таким чином, при витягуванні завжди вибирається дерво найменшою частотою.
Далі потрібно циклічно робити таке:
- Витягти два дерева з пріоритетної черги і зробити їх нащадками нового вузла (щойно створеного вузла без літери). Частота нового вузла дорівнює сумі частот двох дерев-нащадків.
- Для цього вузла створити дерево з коренем у цьому вузлі. Вставити це дерево назад у пріоритетну чергу. (Бо у дерева нова частота, то швидше за все вона стане на нове місце в черзі)
- Продовжувати виконання кроків 1 і 2, доки у черзі не залишиться одне дерево — дерево Хаффмана
Розглянемо цей алгоритм на рядку s1:
Тут символ lf (linefeed) позначає перехід на новий рядок, sp (space) - це пробіл.
А що далі?
Ми отримали дерево Haffman. Ну окей. І що з нею робити? Його і за безкоштовно не візьмуть. А далі, потрібно відстежити всі можливі шляхи від кореня до листя дерева. Умовимося позначити ребро 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 разів! Але це утопія. Такий коефіцієнт навряд чи буде отримано. Чому? Про це йтиметься трохи пізніше.
Декодування
Ну, мабуть, залишилося найпростіше декодування. Я думаю, багато хто з вас здогадався, що просто створити стислий файл без будь-яких натяків на те, як він був закодований, не можна - ми не зможемо його декодувати! Так-так, мені було важко це усвідомити, але доведеться створити текстовий файл table.txt з таблицею стиснення:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Запис таблиці у вигляді символ «код символу». Чому без символу 01110? Насправді він із символом, просто засоби java, що використовуються мною при виведенні у файл, символ переходу на новий рядок - 'n' -конвертують у перехід на новий рядок (як би це безглуздо не звучало). Тому порожній рядок зверху і є символом для коду 01110. Для коду 00 символом є пробіл на початку рядка. Відразу скажу, що нашому коефіцієнту хана цей спосіб зберігання таблиці може претендувати на найнераціональніший. Але він простий для розуміння та реалізації. Із задоволенням вислухаю Ваші рекомендації у коментарях щодо оптимізації.
Маючи цю таблицю дуже просто декодувати. Згадаймо, яким правилом ми керувалися при створенні кодування:
Жоден код не повинен бути префіксом іншого
Ось тут воно і грає полегшуючу роль. Ми читаємо послідовно біт за бітом і, як тільки отриманий рядок d, що складається з прочитаних бітів, збігається з кодуванням, що відповідає символу character, ми відразу знаємо, що був закодований символ character (і тільки він!). Далі записуємо character у декодувальний рядок (рядок, що містить декодоване повідомлення), обнуляємо рядок d, і читаємо далі закодований файл.
Реалізація
Настав час принижувати мій код писати архіватор. Назвемо його Compressor.
Почнемо спочатку. Насамперед пишемо клас 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;
}
}
Тепер деревце:
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());
}
}
Файл з інструкціями readme.txt належить вам написати самим 🙂
Висновок
Напевно, це все, що я хотів сказати. Якщо у вас є що сказати з приводу моєї некомпетентності покращень у коді, алгоритмі, взагалі будь-якої оптимізації, то сміливо пишіть. Якщо я щось недояснив, теж пишіть. Радий почути вас у коментарях!
PS
Так-так, я все ще тут, адже я не забув про коефіцієнт. Для рядка s1 кодувальна таблиця важить 48 байт - набагато більше вихідного файлу, але і про додаткові нулі не забули (кількість доданих нулів дорівнює 7) => коефіцієнт стиснення буде менше одиниці: 176 / (65 + 48 * 8 + 7) = 0.38. Якщо ви теж це помітили, то тільки не по обличчю молодець. Так, ця реалізація буде вкрай неефективною для малих файлів. Але що відбувається з великими файлами? Розміри файлу набагато перевищують розмір кодувальної таблиці. Ось тут алгоритм працює як треба! Наприклад, для архіватор видає реальний (не ідеалізований) коефіцієнт, що дорівнює 1.46 - майже в півтора рази! Так, передбачалося, що файл буде англійською мовою.
Джерело: habr.com