Einleitung
In diesem Artikel werde ich den bekannten Huffman-Algorithmus vorstellen und seine Anwendung in der Datenkompression erlÀutern.
Das Ziel ist es, einen einfachen Archivator zu entwickeln. Beispielsweise wurde bereits darĂŒber gesprochen, , jedoch ohne praktische Umsetzung. Das theoretische Material dieses Beitrags stammt aus Informatikunterricht und dem Buch von Robert Lafore âDatenstrukturen und Algorithmen in Javaâ. Also, alles nach dem Klick!
Einige Ăberlegungen
In einer normalen Textdatei wird ein Zeichen entweder mit 8 Bit (ASCII-Codierung) oder 16 Bit (Unicode-Codierung) kodiert. Lassen Sie uns nun die ASCII-Codierung betrachten. Nehmen wir als Beispiel die Zeichenkette s1 = âSUSIE SAYS IT IS EASYnâ. Insgesamt enthĂ€lt die Zeichenkette 22 Zeichen, einschlieĂlich Leerzeichen und des Zeilenumbruchzeichens - ânâ. Eine Datei mit dieser Zeichenkette wĂŒrde 22 * 8 = 176 Bit wiegen. Sofort stellt sich die Frage: Ist es sinnvoll, alle 8 Bit zur Kodierung eines Zeichens zu verwenden? Wir nutzen ja nicht alle Zeichen der ASCII-Codierung. Selbst wenn wir es tĂ€ten, wĂ€re es sinnvoller, dem hĂ€ufigsten Buchstaben - S - den kĂŒrzest möglichen Code zuzuweisen, wĂ€hrend dem seltensten Buchstaben - T (oder U oder ânâ) - ein lĂ€ngerer Code zugewiesen werden sollte. Genau hierin besteht der Huffman-Algorithmus: Es mĂŒssen optimale Kodierungsvarianten gefunden werden, bei denen die Datei das geringste Gewicht hat. Es ist völlig normal, dass die Code-LĂ€ngen fĂŒr verschiedene Zeichen unterschiedlich sind â darauf basiert der Algorithmus.
Kodierung
Warum geben wir dem Zeichen âSâ nicht einen Code von beispielsweise 1 Bit LĂ€nge: 0 oder 1? Lassen wir es 1 sein. Dann geben wir dem zweitmeist vorkommenden Zeichen â ââ (Leerzeichen) â 0. Stellen Sie sich vor, Sie beginnen, Ihre Nachricht â die kodierte Zeichenkette s1 â zu dekodieren und sehen, dass der Code mit 1 beginnt. Was tun Sie also: Handelt es sich um das Zeichen S oder um ein anderes Zeichen, wie A? Daher ergibt sich eine wichtige Regel:
Kein Code sollte ein PrÀfix eines anderen sein.
Diese Regel ist entscheidend fĂŒr den Algorithmus. Daher beginnt die Erstellung eines Codes mit einer HĂ€ufigkeitstabelle, in der die HĂ€ufigkeit (Anzahl der Vorkommen) jedes Zeichens angegeben ist:
Zeichen mit der höchsten HĂ€ufigkeit sollten mit der kleinsten möglichen Anzahl an Bits kodiert werden. Hier ist ein Beispiel fĂŒr eine mögliche Tabelle von Codes:
Somit wird die kodierte Nachricht so aussehen:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Den Code jedes Zeichens habe ich durch ein Leerzeichen getrennt. In einer komprimierten Datei wird es so etwas nicht geben!
Es stellt sich die Frage: Wie hat dieser AnfÀnger den Code erfunden, um eine Codetabelle zu erstellen? Darum wird es im Folgenden gehen.
Der Aufbau des Huffman-Baums
Hier kommen SuchbĂ€ume ins Spiel. Keine Sorge, hier sind keine Such-, EinfĂŒge- oder Löschmethoden erforderlich. Hier ist die Struktur des Baums in 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;
}
...
}
Das ist nicht der vollstÀndige Code, der vollstÀndige Code folgt weiter unten.
Hier ist der Algorithmus zum Aufbau des Baums:
- Erstellen Sie ein Node-Objekt fĂŒr jedes Zeichen aus der Nachricht (Zeichenfolge s1). In unserem Fall werden es 9 Knoten (Node-Objekte) sein. Jeder Knoten besteht aus zwei Datenfeldern: Zeichen und Frequenz.
- Erstellen Sie ein Baumobjekt (BinaryTree) fĂŒr jeden der Node-Knoten. Der Knoten wird zur Wurzel des Baums.
- FĂŒgen Sie diese BĂ€ume in eine PrioritĂ€tswarteschlange ein. Je geringer die Frequenz, desto höher die PrioritĂ€t. So wird beim Entnehmen immer der Baum mit der geringsten Frequenz ausgewĂ€hlt.
Als nĂ€chstes mĂŒssen Sie zyklisch Folgendes tun:
- Entfernen Sie zwei BÀume aus der PrioritÀtswarteschlange und machen Sie sie zu Nachkommen eines neuen Knotens (gerade erstellten Knotens ohne Buchstaben). Die Frequenz des neuen Knotens entspricht der Summe der Frequenzen der beiden NachkommenbÀume.
- FĂŒr diesen Knoten erstellen Sie einen Baum mit dieser Knoten als Wurzel. FĂŒgen Sie diesen Baum zurĂŒck in die PrioritĂ€tswarteschlange ein. (Da der Baum eine neue Frequenz hat, wird er wahrscheinlich an eine neue Stelle in der Warteschlange eintreten)
- Fahren Sie mit den Schritten 1 und 2 fort, bis in der Warteschlange nur noch ein Baum ĂŒbrig bleibt â der Huffman-Baum
Betrachten wir diesen Algorithmus anhand der Zeichenkette s1:
Hier steht das Symbol âlfâ (linefeed) fĂŒr den Zeilenumbruch, âspâ (space) â fĂŒr ein Leerzeichen.
Und wie geht es weiter?
Wir haben den Huffman-Baum erstellt. Na gut. Und was sollen wir jetzt damit machen? Das nimmt nicht einmal jemand umsonst. AuĂerdem mĂŒssen wir alle möglichen Wege vom Wurzelknoten zu den BlĂ€ttern des Baumes verfolgen. Lassen Sie uns eine Kante mit 0 kennzeichnen, wenn sie zu einem linken Nachkommen fĂŒhrt, und mit 1, wenn sie zu einem rechten fĂŒhrt. Streng genommen ist in dieser Notation der Code eines Symbols der Weg vom Wurzelknoten zu dem Blatt, das dieses Symbol enthĂ€lt.
So entstand die Code-Tabelle. Wenn wir diese Tabelle betrachten, können wir den "Gewicht" jedes Symbols ableiten â das ist die LĂ€nge seines Codes. Somit wĂŒrde die komprimierte Version der ursprĂŒnglichen Datei wie folgt gewichtet: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 Bit. Zuvor wog sie 176 Bit. Das bedeutet, wir haben sie um 176/65 = 2,7-mal reduziert! Aber das ist Utopie. Ein solcher Faktor wird kaum erreicht werden. Warum? DarĂŒber sprechen wir gleich.
Dekodierung
Nun, das Einfachste steht noch bevor â die Dekodierung. Ich denke, viele von Ihnen haben bereits erkannt, dass es unmöglich ist, eine komprimierte Datei ohne Hinweise auf ihre Kodierung zu erstellen â andernfalls können wir sie nicht dekodieren! Ja, es war schwer fĂŒr mich, das zu akzeptieren, aber wir mĂŒssen eine Textdatei namens table.txt mit der Komprimierungstabelle erstellen:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Die Speicherung einer Tabelle als 'Symbol'«Symbolcode». Warum ist 01110 ohne Symbol? TatsĂ€chlich hat es ein Symbol, aber die verwendeten Java-Toolmittel konvertieren das Zeilenumbruchzeichen - 'n' - in einen Zeilenumbruch (so seltsam das auch klingen mag). Daher ist die leere Zeile oben das Symbol fĂŒr den Code 01110. FĂŒr den Code 00 ist das Symbol ein Leerzeichen am Anfang der Zeile. Ich möchte gleich sagen, dass diese Methode der Speicherung der Tabelle möglicherweise die ineffizienteste ist. Aber sie ist leicht verstĂ€ndlich und umsetzbar. Ich freue mich auf Ihre Empfehlungen zur Optimierung in den Kommentaren.
Mit dieser Tabelle ist es sehr einfach, zu dekodieren. Erinnern wir uns an die Regel, die wir beim Erstellen der Kodierung befolgt haben:
Kein Code sollte ein PrÀfix eines anderen Codes sein.
Hier spielt es eine erleichternde Rolle. Wir lesen die Bits nacheinander und sobald die erhaltene Zeichenkette d, die aus den gelesenen Bits besteht, mit der Kodierung ĂŒbereinstimmt, die dem Zeichen character entspricht, wissen wir sofort, dass das Zeichen character (und nur dieses!) kodiert wurde. Dann fĂŒgen wir character zur Dekodierungszeichenkette (die Zeichenkette, die die decodierte Nachricht enthĂ€lt) hinzu, setzen die Zeichenkette d zurĂŒck und lesen die kodierte Datei weiter.
Implementierung
Es ist Zeit, meinen Code zu erniedrigen und einen Kompressor zu schreiben. Nennen wir ihn Compressor.
Fangen wir von vorne an. Als Erstes schreiben wir die Klasse Node:
public class Node {
private int frequenz; // Frequenz
private char buchstabe; // Buchstabe
private Node linkerNachkomme; // linker Nachkomme
private Node rechterNachkomme; // rechter Nachkomme
public Node(char buchstabe, int frequenz) { // Konstruktor
this.buchstabe = buchstabe;
this.frequenz = frequenz;
}
public Node() {} // Ăberladung des Konstruktors fĂŒr anonyme Knoten (siehe oben im Abschnitt ĂŒber den Aufbau des Huffman-Baums)
public void addChild(Node newNode) { // HinzufĂŒgen eines Nachkommens
if (linkerNachkomme == null) // Wenn der linke leer ist => der rechte ist auch leer => in den linken hinzufĂŒgen
linkerNachkomme = newNode;
else {
if (linkerNachkomme.getFrequenz() <= newNode.getFrequenz()) // Im Allgemeinen, linker Nachkomme
rechterNachkomme = newNode; // Wird der, der geringere Frequenz hat
else {
rechterNachkomme = linkerNachkomme;
linkerNachkomme = newNode;
}
}
frequenz += newNode.getFrequenz(); // Gesamte Frequenz
}
public Node getLeftChild() {
return linkerNachkomme;
}
public Node getRightChild() {
return rechterNachkomme;
}
public int getFrequenz() {
return frequenz;
}
public char getLetter() {
return buchstabe;
}
public boolean isLeaf() { // ĂberprĂŒfung, ob Blatt
return linkerNachkomme == null && rechterNachkomme == null;
}
}
Jetzt zum Baum:
class BinaryTree {
private Node wurzel;
public BinaryTree() {
wurzel = new Node();
}
public BinaryTree(Node wurzel) {
this.wurzel = wurzel;
}
public int getFrequenz() {
return wurzel.getFrequenz();
}
public Node getRoot() {
return wurzel;
}
}
PrioritÀtswarteschlange:
import java.util.ArrayList; // Ja, die Warteschlange basiert auf einer Liste
class PriorityQueue {
private ArrayList data; // Liste der Warteschlange
private int nElems; // Anzahl der Elemente in der Warteschlange
public PriorityQueue() {
data = new ArrayList();
nElems = 0;
}
public void insert(BinaryTree newTree) { // EinfĂŒgen
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i newTree.getFrequence()) { // Wenn die Frequenz des einzufĂŒgenden Baums kleiner ist
data.add(i, newTree); // Verschiebe alle BĂ€ume rechts um eins
break; // Setze den neuen Baum an die Position des aktuellen
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++; // Erhöhe die Anzahl der Elemente um 1
}
public BinaryTree remove() { // Entfernen aus der Warteschlange
BinaryTree tmp = data.get(0); // Kopiere das Element, das entfernt werden soll
data.remove(0); // Entferne es wirklich
nElems--; // Verringere die Anzahl der Elemente um 1
return tmp; // Gib das entfernte Element (Element mit der geringsten Frequenz) zurĂŒck
}
}
Klasse zur Erstellung eines Huffman-Baums:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127; // GröĂe der Kodierungstabelle
private String myString; // Nachricht
private BinaryTree huffmanTree; // Huffman-Baum
private int[] freqArray; // HĂ€ufigkeitstabelle
private String[] encodingArray; // Kodierungstabelle
//----------------Konstruktor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[ENCODING_TABLE_SIZE];
fillFrequenceArray();
huffmanTree = getHuffmanTree();
encodingArray = new String[ENCODING_TABLE_SIZE];
fillEncodingArray(huffmanTree.getRoot(), "", "");
}
//--------------------HĂ€ufigkeitstabelle------------------------
private void fillFrequenceArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrequenceArray() {
return freqArray;
}
//------------------------Huffman-Baum erstellen------------------
private BinaryTree getHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
// Algorithmus wie oben beschrieben
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) { // Wenn das Zeichen in der Zeichenkette existiert
Node newNode = new Node((char) i, freqArray[i]); // dann erstelle einen Node
BinaryTree newTree = new BinaryTree(newNode); // und fĂŒr den Node einen BinaryTree
pq.insert(newTree); // in die Warteschlange einfĂŒgen
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // das erste Baum aus der Warteschlange extrahieren.
try {
BinaryTree tree2 = pq.remove(); // das zweite Baum aus der Warteschlange extrahieren
Node newNode = new Node(); // einen neuen Node erstellen
newNode.addChild(tree1.getRoot()); // die beiden extrahierten BĂ€ume als Kinder hinzufĂŒgen
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) { // Wenn nur noch ein Baum in der Warteschlange bleibt
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------Kodierungstabelle------------------
void fillEncodingArray(Node node, String codeBefore, String direction) { // FĂŒllt die Kodierungstabelle
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() { // FĂŒr Debugging
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Kodierungstabelle====================");
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;
}
}
Klasse, die den folgenden Code codiert/dekodiert:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // GröĂe der Tabelle
private HuffmanTree mainHuffmanTree; // Huffman-Baum (nur fĂŒr Kompression verwendet)
private String myString; // ursprĂŒngliche Nachricht
private int[] freqArray; // HĂ€ufigkeitstabelle
private String[] encodingArray; // Kodierungstabelle
private double ratio; // KompressionsverhÀltnis
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // fĂŒr Kompression
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // fĂŒr Extraktion;
// ---------------------------------------Kompression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; // Zwischenablage (ohne zusÀtzliche Nullen)
// System.out.println("=============================Kompression=======================");
// displayEncodingArray();
for (int i = 0; i
// Es mĂŒssen Nullen am Ende hinzugefĂŒgt werden (eine reicht, es macht keinen Unterschied)
byte counter = 0; // Anzahl der am Ende hinzugefĂŒgten Nullen (ein Byte ist ausreichend: 0 <= counter < 8 < 127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) { // delta - Anzahl der hinzugefĂŒgten Nullen
intermidiate += "0";
}
// Anzahl der hinzugefĂŒgten Nullen in der binĂ€ren Darstellung an die Zwischenablage anhĂ€ngen
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
// Idealisierter Faktor
setCompressionRatio();
// System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { // Idealisierter Faktor berechnen
double sumA = 0, sumB = 0; // A-die ursprĂŒngliche Summe
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() { // finale Kompression
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;
}
// ---------------------------------------Ende der Kompression----------------------------------------------------------------
// ------------------------------------------------------------Extraktion-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
// displayEncodingArray();
// Anzahl der hinzugefĂŒgten Nullen erhalten
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, da das erste Byte die Anzahl der hinzugefĂŒgten Nullen darstellt
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { // wenn es ĂŒbereinstimmt
decompressed += (char)j; // dann fĂŒgen wir das Element hinzu
current = ""; // und setzen die aktuelle Zeichenkette zurĂŒck
}
}
}
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() { // fĂŒr Debugging
System.out.println("======================Kodierungstabelle====================");
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("========================================================");
}
}
Klasse, die das Schreiben in eine Datei erleichtert:
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("UngĂŒltiger Pfad oder die Datei existiert nicht!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Klasse, die das Lesen aus einer Datei erleichtert:
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) // EOF erreicht
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Und hier die Hauptklasse:
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 { // Geben Sie die Anweisungen ĂŒber die Befehlszeilenargumente an
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("UngĂŒltiges Format der Eingabeargumente");
System.out.println("Lesen Sie die Readme.txt");
e.printStackTrace();
}
}
public static void compress(String stringPath) throws IOException {
List 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("UngĂŒltiger Pfad oder die Datei existiert nicht!");
return;
} catch (MalformedInputException e) {
System.out.println("Die aktuelle Dateikodierung wird nicht unterstĂŒtzt");
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());
} // Erstellen Sie eine Datei mit der Kodierungstabelle:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Pfad zur komprimierten Datei: " + compressedFile.getAbsolutePath());
System.out.println("Pfad zur Kodierungstabelle " + table.getAbsolutePath());
System.out.println("Ohne Tabelle kann die Datei nicht extrahiert werden!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100; // idealisierter Koeffizient
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100; // tatsÀchlicher Koeffizient
System.out.println("Der idealisierte Kompressionskoeffizient betrÀgt " + idealRatio);
System.out.println("Der Kompressionskoeffizient unter BerĂŒcksichtigung der Kodierungstabelle " + 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];
// Lesen Sie die komprimierte Datei
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ĂberprĂŒfen Sie hier:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte(); // Die Methode gibt EOFException zurĂŒck
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
// --------------------
// Lesen Sie die Kodierungstabelle:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine(); // Ăberspringen Sie die erste leere Zeile
encodingArray[(byte)'n'] = fi.readLine(); // Lesen Sie den Code fĂŒr '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();
// Extraktion:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Pfad zur entpackten Datei " + extractedFile.getAbsolutePath());
}
}
Die Datei mit den Anweisungen readme.txt mĂŒssen Sie selbst erstellen đ
Fazit
Das ist wahrscheinlich alles, was ich sagen wollte. Wenn Sie Anmerkungen zu meiner UnfÀhigkeit zur Verbesserung des Codes, des Algorithmus oder jeglicher Optimierung haben, schreiben Sie mir gerne. Wenn ich etwas unklar erklÀrt habe, lassen Sie es mich ebenfalls wissen. Ich freue mich auf Ihre Kommentare!
P.S.
Ja, ja, ich bin immer noch hier, denn ich habe den Koeffizienten nicht vergessen. FĂŒr die Zeichenkette s1 wiegt die Kodierungstabelle 48 Byte â das ist viel mehr als die ursprĂŒngliche Datei, und wir haben die hinzugefĂŒgten Nullen nicht vergessen (die Anzahl der hinzugefĂŒgten Nullen betrĂ€gt 7) => der Kompressionsfaktor liegt also unter eins: 176/(65 + 48*8 + 7)=0,38. Wenn Sie das auch bemerkt haben, sind Sie wirklich gut! Ja, diese Implementierung wird fĂŒr kleine Dateien Ă€uĂerst ineffizient sein. Aber was passiert mit groĂen Dateien? Die DateigröĂen ĂŒbersteigen die GröĂe der Kodierungstabelle bei weitem. Hier funktioniert der Algorithmus genau richtig! Zum Beispiel fĂŒr gibt der Kompressor einen realen (nicht idealisierten) Koeffizienten von 1,46 aus â fast anderthalb Mal! Und ja, es wurde angenommen, dass die Datei auf Englisch sein wĂŒrde.
Quelle: habr.com
