エントリー
この記事では、有名なハフマン アルゴリズムと、データ圧縮におけるその応用について説明します。
結果として、単純なアーカイバーを作成します。 これについてはすでに議論されています 、しかし実際の実装はありません。 現在の投稿の理論的資料は、学校のコンピューター サイエンスの授業と Robert Laforet の著書「Data Structures and Algorithms in Java」から引用しています。 ということで、すべてカットです！
少し考えた
通常のテキスト ファイルでは、8 文字は 16 ビット (ASCII エンコーディング) または 1 ビット (Unicode エンコーディング) でエンコードされます。 次に、ASCII エンコードについて考えます。 たとえば、s22 = 「SUSIE SAYS IT IS EASYn」という行を考えてみましょう。 この行には、スペースと改行文字「n」を含めて、合計 22 文字が含まれています。 この行を含むファイルの重さは 8*176 = 8 ビットになります。 すぐに疑問が生じます。1 文字をエンコードするのに XNUMX ビットすべてを使用するのは合理的でしょうか? すべての ASCII 文字を使用するわけではありません。 たとえそうしていたとしても、最も一般的な文字である S には可能な限り短いコードを与え、最も珍しい文字である T (または U、または 'n') にはより長いコードを与える方が合理的です。 ハフマン アルゴリズムは次のように構成されています。ファイルの重みが最小になる最適なエンコード オプションを見つける必要があります。 コード長がシンボルごとに異なるのはごく普通のことです。アルゴリズムはこれに基づいています。
コーディング
たとえば、文字「S」にコードを与えてみませんか。たとえば、1 ビット長の 0 または 1。それを 1 にします。次に、0 番目に一般的な文字である「 」 (スペース) に 1 を与えます。メッセージのデコードを開始したと想像してください。エンコードされた文字列 s1 - コードが XNUMX で始まることがわかります。それで、どうすればよいでしょうか。これは文字 S ですか、それとも他の文字 (A など) ですか? したがって、次の重要なルールが生じます。
どちらのコードも別のコードのプレフィックスであってはなりません
このルールはアルゴリズムの鍵となります。 したがって、コードの作成は、各シンボルの頻度 (出現数) を示す頻度表から始まります。
最も多く出現する文字は最も少なくエンコードする必要があります 可能 ビット数。 考えられるコード テーブルの XNUMX つの例を示します。
したがって、エンコードされたメッセージは次のようになります。
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 オブジェクト) があります。 各ノードは、シンボルと周波数の XNUMX つのデータ フィールドで構成されます。
- 各ノードに Tree オブジェクト (BinaryTree) を作成します。 ノードがツリーのルートになります。
- これらのツリーを優先キューに挿入します。 周波数が低いほど優先度が高くなります。 したがって、抽出時には、常に最も低い周波数を持つ dervo が選択されます。
次に、以下を周期的に実行する必要があります。
- 優先キューから XNUMX つのツリーを削除し、それらを新しいノード (文字のない新しく作成されたノード) の子にします。 新しいノードの頻度は、XNUMX つの子孫ツリーの頻度の合計に等しくなります。
- このノードについては、このノードをルートとするツリーを作成します。 このツリーを優先キューに挿入し直します。 (ツリーには新しい頻度があるため、キュー内の新しい場所に表示される可能性が高くなります)
- キューに 1 つのツリー (ハフマン ツリー) だけが残るまで、ステップ 2 と XNUMX を続けます。
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 ファイルは自分で作成する必要があります:)
まとめ
私が言いたかったのはそれだけだと思います。 コード、アルゴリズム、または最適化全般の改善における私の無能について何か言いたいことがあれば、お気軽にお書きください。 何も説明していない場合は、それも書いてください。 コメントでぜひご意見をお待ちしています！
PS
はい、はい、係数のことを忘れていないので、まだここにいます。 文字列 s1 の場合、エンコード テーブルの重さは 48 バイトです。これはソース ファイルよりもはるかに大きく、追加のゼロも忘れませんでした (追加されたゼロの数は 7 です) => 圧縮率は 176 未満になります: 65/ (48 + 8*7 + 0.38) = XNUMX。 あなたもこれに気づいたなら、素晴らしいのはあなたの顔だけではありません。 はい、この実装は小さなファイルに対しては非常に非効率的になります。 しかし、大きなファイルはどうなるのでしょうか? ファイル サイズは、エンコード テーブルのサイズよりもはるかに大きくなります。 ここでアルゴリズムが正常に機能します。 たとえば、 アーカイバーは、実際の (理想化されていない) 係数 1.46、つまりほぼ XNUMX 倍を生成します。 はい、ファイルは英語であるはずでした。
出所： habr.com