條目
在這篇文章中，我將討論著名的霍夫曼算法，以及它在數據壓縮中的應用。
因此，我們將編寫一個簡單的歸檔器。 這已經是 ，但沒有實際實施。 當前帖子的理論材料取自學校計算機科學課程和 Robert Laforet 的書“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;
}
...
}
這不是完整的代碼，完整的代碼將在下面。
這是構建樹的算法：
- 為消息中的每個字符（第 s1 行）創建一個 Node 對象。 在我們的例子中，將有 9 個節點（Node 對象）。 每個節點由兩個數據字段組成：符號和頻率
- 為每個 Node 節點創建一個 Tree 對象（BinaryTree）。 該節點成為樹的根。
- 將這些樹插入優先級隊列。 頻率越低，優先級越高。 因此，在提取時，總是選擇頻率最低的樹。
接下來，您需要循環執行以下操作：
- 從優先級隊列中檢索兩棵樹，並使它們成為新節點（新創建的不帶字母的節點）的子節點。 新節點的頻率等於兩個後代樹的頻率之和。
- 對於該節點，創建一棵以此節點為根的樹。 將這棵樹插回到優先級隊列中。 （由於樹有新的頻率，它很可能會進入隊列中的新位置）
- 繼續步驟 1 和 2，直到隊列中剩下一棵樹 - 哈夫曼樹
考慮第 s1 行的算法：
這裡符號“lf”（換行）表示換行，“sp”（空格）是一個空格。
接下來是什麼？
我們得到了霍夫曼樹。 好的。 該怎麼辦？ 他們不會免費獲得它。然後，你需要追踪從樹根到葉子的所有可能路徑。 我們同意，如果一條邊通向左子節點，則將其標記為 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 與對應於該字符的編碼相匹配，我們立即知道該字符（而且只有它！）已被編碼。 接下來，我們將字符寫入解碼字符串（包含解碼消息的字符串），重置 d 字符串，並進一步讀取編碼文件。
履行
是時候通過編寫歸檔程序來羞辱我的代碼了。 我們稱之為壓縮機。
重來。 首先我們編寫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 說明編寫該文件 🙂
結論
我想這就是我想說的。 如果你對我在代碼、算法、一般情況下、任何優化方面的改進無能為力，請隨意寫。 如果我沒有解釋什麼，請也寫下來。 我很想在評論中聽到你的聲音！
聚苯乙烯
是的，是的，我還在這裡，因為我沒有忘記係數。 對於字符串 s1，編碼表重 48 個字節 - 比原始文件大得多，而且他們沒有忘記額外的零（添加的零的數量為 7）=> 壓縮比將小於 176：65 /(48 + 8 *7 + 0.38) = XNUMX。 如果您也注意到了這一點，那麼您就完成了。 是的，這種實現對於小文件來說效率極低。 但是大文件會發生什麼情況呢？ 文件大小遠大於編碼表大小。 這就是算法應該發揮作用的地方！ 例如，對於 存檔器給出的真實（非理想化）係數等於 1.46 - 幾乎是一倍半！ 是的，該文件應該是英文的。
來源： www.habr.com