Einleitung
In diesem Artikel werde ich ĂŒber den bekannten Huffman-Algorithmus sprechen und seine Anwendung bei der Datenkompression erlĂ€utern.
Am Ende werden wir einen einfachen Kompressor schreiben. DarĂŒber gab es bereits , aber ohne praktische Umsetzung. Das theoretische Material dieses Beitrags stammt aus dem Informatikunterricht und aus dem Buch von Robert Lafore âData Structures and Algorithms in Javaâ. Also, alles unter dem Cut!
Einige Ăberlegungen
In einer normalen Textdatei wird ein Zeichen mit 8 Bits (ASCII-Codierung) oder 16 Bits (Unicode-Codierung) kodiert. Wir werden uns nun die ASCII-Codierung ansehen. Zum Beispiel nehmen wir die Zeichenfolge s1 = âSUSIE SAYS IT IS EASYnâ. Insgesamt enthĂ€lt die Zeichenfolge 22 Zeichen, einschlieĂlich Leerzeichen und dem Zeilenumbruchzeichen â ânâ. Die Datei, die diese Zeichenfolge enthĂ€lt, wird 22 * 8 = 176 Bits wiegen. Sofort stellt sich die Frage: Ist es sinnvoll, 8 Bits fĂŒr die Kodierung eines Zeichens zu verwenden? Wir verwenden schlieĂlich nicht alle Zeichen der ASCII-Codierung. Selbst wenn wir das tĂ€ten, wĂ€re es sinnvoller, dem hĂ€ufigsten Buchstaben â S â den kĂŒrzest möglichen Code zu geben, und dem seltensten Buchstaben â T (oder U, oder ânâ) â einen lĂ€ngeren Code. Darin besteht der Huffman-Algorithmus: Wir mĂŒssen die optimale Kodierungsvariante finden, bei der die Datei das geringste Gewicht hat. Es ist ganz normal, dass verschiedene Zeichen unterschiedliche Code-LĂ€ngen haben â darauf basiert der Algorithmus.
Kodierung
Warum sollte dem Zeichen âSâ nicht ein Code von beispielsweise 1 Bit: 0 oder 1 zugewiesen werden? Lassen Sie es uns als 1 ansehen. Dann geben wir dem zweit hĂ€ufigsten Zeichen â â â (Leerzeichen) â 0. Stellen Sie sich vor, Sie beginnen, Ihre Nachricht â die kodierte Zeichenfolge s1 â zu dekodieren und sehen, dass der Code mit 1 beginnt. Was soll das bedeuten: Ist das das Zeichen S oder ein anderes Zeichen, beispielsweise A? Daher gibt es eine wichtige Regel:
Kein Code darf ein PrÀfix eines anderen sein
Diese Regel ist der SchlĂŒssel zum Algorithmus. Deshalb beginnt die Erstellung eines Codes mit einer HĂ€ufigkeitstabelle, in der die HĂ€ufigkeit (Anzahl der Vorkommen) jedes Zeichens aufgefĂŒhrt ist:
Zeichen mit den meisten Vorkommen sollten mit der geringsten möglichen Anzahl an Bits kodiert werden. Hier ist ein Beispiel fĂŒr eine mögliche Codetabelle:
Daher 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 Ich habe den Code jedes Symbols durch ein Leerzeichen getrennt. In einer komprimierten Datei wird es so etwas nicht geben!
Die Frage stellt sich: Wie hat dieser AnfĂ€nger den Code zum Erstellen einer Codesammlung erfunden? DarĂŒber wird im Folgenden gesprochen.
Aufbau eines Huffman-Baumes
Hier kommen binĂ€re SuchbĂ€ume ins Spiel. Keine Sorge, hier sind die Methoden zum Suchen, EinfĂŒgen und Löschen nicht erforderlich. Hier ist die Baumstruktur in Java:
public class Node {
private int frequenz;
private char buchstabe;
private Node linkesKind;
private Node rechtesKind;
...
}
class BinaryTree {
private Node wurzel;
public BinaryTree() {
wurzel = new Node();
}
public BinaryTree(Node wurzel) {
this.wurzel = wurzel;
}
...
}
Das ist nicht der vollstÀndige Code, der komplette Code wird weiter unten bereitgestellt.
Hier ist der Algorithmus zum Erstellen des Baumes:
- Erstellen Sie ein Node-Objekt fĂŒr jedes Zeichen aus der Nachricht (String s1). In unserem Fall wird es 9 Knoten (Node-Objekte) geben. Jeder Knoten besteht aus zwei Datenfeldern: Zeichen und Frequenz.
- Ein BinaryTree-Objekt fĂŒr jeden Node-Knoten erstellen. Der Knoten wird zur Wurzel des Baumes.
- Diese BĂ€ume in eine PrioritĂ€tswarteschlange einfĂŒgen. Je geringer die Frequenz, desto höher die PrioritĂ€t. So wird beim Abruf immer der Baum mit der geringsten Frequenz ausgewĂ€hlt.
AnschlieĂend mĂŒssen Sie wiederholt Folgendes tun:
- Ziehen Sie zwei BÀume aus der PrioritÀtswarteschlange und machen Sie sie zu Nachkommen des neuen Knotens (eines gerade neu erstellten Knotens ohne Buchstaben). Die Frequenz des neuen Knotens entspricht der Summe der Frequenzen der beiden Nachfolger-BÀume.
- FĂŒr diesen Knoten ein Baum mit der Wurzel in diesem Knoten erstellen. FĂŒgen Sie diesen Baum wieder in die PrioritĂ€tswarteschlange ein. (Da der Baum eine neue Frequenz hat, wird er wahrscheinlich einen neuen Platz in der Warteschlange einnehmen.)
- Setzen Sie die Schritte 1 und 2 fort, bis nur noch ein Baum in der Warteschlange verbleibt â der Huffman-Baum.
Betrachten wir diesen Algorithmus anhand des Strings s1:
Hier steht das Zeichen âlfâ (Zeilenumbruch) fĂŒr einen Ăbergang zu einer neuen Zeile, âspâ (Leerzeichen) ist ein Leerzeichen.
Und was kommt als NĂ€chstes?
Wir haben einen Huffman-Baum erhalten. Naja, und was sollen wir damit machen? Man wird ihn nicht einmal umsonst nehmen. Im Weiteren muss man alle möglichen Wege vom Wurzel bis zu den BlĂ€ttern des Baumes nachverfolgen. Wir vereinbaren, eine Kante mit 0 zu kennzeichnen, wenn sie zum linken Nachkommen fĂŒhrt, und mit 1, wenn sie zum rechten fĂŒhrt. Streng genommen ist in diesen Bezeichnungen der Code des Zeichens der Weg von der Wurzel des Baumes zum Blatt, das dieses Zeichen enthĂ€lt.
So entstand die Codes-Tabelle. Beachten Sie, dass wir, wenn wir diese Tabelle betrachten, den "Gewicht" jedes Symbols ableiten können â das ist die LĂ€nge seines Codes. In komprimierter Form wĂŒrde die ursprĂŒngliche Datei wie folgt wiegen: 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. Folglich haben wir sie um 176/65 = 2,7 Mal reduziert! Aber das ist eine Utopie. Ein solches VerhĂ€ltnis wird wahrscheinlich nicht erreicht werden. Warum? DarĂŒber werden wir gleich sprechen.
Dekodierung
Nun, was bleibt noch ĂŒbrig â die Dekodierung. Ich denke, viele von Ihnen haben bereits erraten, dass es nicht möglich ist, einfach eine komprimierte Datei ohne Hinweise darauf zu erstellen, wie sie kodiert wurde â wir können sie nicht dekodieren! Ja, ich fand es schwer, das zu akzeptieren, aber wir mĂŒssen eine Textdatei table.txt mit der Kompressionstabelle erstellen:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Die Aufzeichnung der Tabelle in der Form 'Symbol'«Code des Symbols». Warum 01110 ohne Symbol? TatsĂ€chlich hat es ein Symbol, aber die Java-Mittel, die ich beim Ausgeben in die Datei verwendet habe, konvertieren das Zeilenumbruchzeichen â 'n' â in einen Zeilenumbruch (so seltsam es auch klingt). 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 sage gleich, dass unser VerhĂ€ltnis in dieser Art der Abspeicherung der Tabelle auf die irrationalste Weise abzielt. Aber sie ist einfach zu verstehen und umzusetzen. Ich freue mich ĂŒber Ihre Empfehlungen in den Kommentaren zur Optimierung.
Mit dieser Tabelle ist die Dekodierung sehr einfach. Denken wir daran, welches Regelwerk wir bei der Erstellung der Kodierung befolgt haben:
Kein Code darf ein PrÀfix eines anderen sein.
Hier spielt es eine erleichternde Rolle. Wir lesen bitweise und sobald die erhaltene Zeichenfolge d, die aus den gelesenen Bits besteht, mit der Kodierung ĂŒbereinstimmt, die dem Symbol character entspricht, wissen wir sofort, dass das Symbol character (und nur das!) kodiert wurde. Dann zeichnen wir character in die Dekodierungszeichenfolge (die Zeichenfolge mit der dekodierten Nachricht) auf, setzen die Zeichenfolge d auf null zurĂŒck und lesen weiter die kodierte Datei.
Implementierung
Es ist an der Zeit, meinen Code zu beschÀmen und einen Kompressor zu schreiben. Nennen wir ihn Compressor.
Fangen wir von vorne an. Zuerst schreiben wir die Klasse Node:
public class Node {
private int frequence; // Frequenz
private char letter; // Buchstabe
private Node leftChild; // linkes Kind
private Node rightChild; // rechtes Kind
public Node(char letter, int frequence) { // Der Konstruktor
this.letter = letter;
this.frequence = frequence;
}
public Node() {} // Ăberladung des Konstruktors fĂŒr namenlose Knoten (siehe oben im Abschnitt ĂŒber den Aufbau des Huffman-Baums)
public void addChild(Node newNode) { // fĂŒge Kind hinzu
if (leftChild == null) // wenn links leer => auch rechts => fĂŒgen wir links hinzu
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) // im Allgemeinen, als linkes Kind
rightChild = newNode; // wird der, dessen Frequenz geringer ist
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence(); // endgĂŒltige Frequenz
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() { // ĂberprĂŒfung auf Blatt
return leftChild == null && rightChild == null;
}
}
Jetzt der Baum:
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;
}
}
PrioritÀtswarteschlange:
import java.util.ArrayList; // Ja, die Warteschlange wird auf Listenbasis sein
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 eingefĂŒgten Baumes kleiner ist
data.add(i, newTree); // als die Frequenz des aktuellen, verschieben wir alle BĂ€ume auf den rechten Positionen um 1
break; // dann setzen wir den neuen Baum an die Position des aktuellen
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++; // Anzahl der Elemente um 1 erhöhen
}
public BinaryTree remove() { // Entfernen aus der Warteschlange
BinaryTree tmp = data.get(0); // Kopieren des zu entfernenden Elements
data.remove(0); // entfernt es
nElems--; // die Anzahl der Elemente um 1 reduzieren
return tmp; // gibt das entfernte Element zurĂŒck (das Element mit der geringsten Frequenz)
}
}
Klasse, die einen Huffman-Baum erstellt:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127; // LĂ€nge der Kodierungstabelle
private String myString; // Nachricht
private BinaryTree huffmanTree; // Huffmanbaum
private int[] freqArray; // Frequenztabelle
private String[] encodingArray; // Kodierungstabelle
// ----------------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();
// 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]); // Erstelle einen Node fĂŒr das Zeichen
BinaryTree newTree = new BinaryTree(newNode); // Erstelle einen BinaryTree fĂŒr den Node
pq.insert(newTree); // In die Warteschlange einfĂŒgen
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // Erhalte das erste Baum aus der Warteschlange.
try {
BinaryTree tree2 = pq.remove(); // Erhalte das zweite Baum aus der Warteschlange
Node newNode = new Node(); // Erstelle einen neuen Node
newNode.addChild(tree1.getRoot()); // Mach die beiden entnommenen BĂ€ume zu Nachkommen
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode));
} catch (IndexOutOfBoundsException e) { // Es bleibt nur ein Baum in der Warteschlange
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
// -------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) { // FĂŒlle 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;
}
}
Die Klasse, die codiert / decodiert:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // LĂ€nge der Tabelle
private HuffmanTree mainHuffmanTree; // Huffman-Baum (wird nur fĂŒr die Kompression verwendet)
private String myString; // UrsprĂŒngliche Nachricht
private int[] freqArray; // HĂ€ufigkeitstabelle
private String[] encodingArray; // Codierungstabelle
private double ratio; // Kompressionsrate
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // fĂŒr die Kompression
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // fĂŒr die Extraktion;
// ---------------------------------------Kompression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; // Zwischenstring (ohne zusÀtzliche Nullen)
// System.out.println("=============================Kompression=======================");
// displayEncodingArray();
for (int i = 0; i
// Nullen am Ende hinzufĂŒgen (es können 1 sein, spielt keine Rolle)
byte counter = 0; // Anzahl der am Ende hinzugefĂŒgten Nullen (ein Byte reicht völlig: 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 binĂ€rer Darstellung und Zwischenstring zusammenfĂŒgen
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
// Idealisiertes VerhÀltnis
setCompressionRatio();
// System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { // idealisierten Koefizienten 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 eingefĂŒ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 eingefĂŒgten Nullen ist
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { // wenn Ăbereinstimmung
decompressed += (char) j; // dann Element hinzufĂŒgen
current = ""; // und den aktuellen String zurĂŒcksetzen
}
}
}
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() { // zur Fehlersuche
System.out.println("======================Codierungstabelle====================");
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("========================================================");
}
}
Eine Klasse zur Erleichterung des Schreibens in eine Datei:
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 Datei existiert nicht!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Eine Klasse zur Erleichterung des Lesens aus einer Datei:
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) // wenn die Datei zu Ende ist
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Und 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 { //gib den Befehl ĂŒ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 Argumentformat ");
System.out.println("Bitte lesen Sie 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 Datei existiert nicht!");
return;
} catch (MalformedInputException e) {
System.out.println("Aktuelle Dateicodierung 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 die 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 ist die Datei nicht extrahierbar!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100; //idealisierter Quotient
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100; //tatsÀchlicher Quotient
System.out.println("Der idealisierte Kompressionsquotient betrÀgt " + idealRatio);
System.out.println("Der Kompressionsquotient 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];
//komprimierte Datei lesen
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!hier ĂŒberprĂŒfen:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte(); //Methode gibt EOFException zurĂŒck
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
//--------------------
//Kodierungstabelle lesen:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine(); //erste leere Zeile ĂŒberspringen
encodingArray[(byte)'n'] = fi.readLine(); //Code fĂŒr 'n' lesen
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();
//extrahieren:
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 schreiben đ
Fazit
Das ist wahrscheinlich alles, was ich sagen wollte. Wenn Sie etwas zu meiner UnzulĂ€nglichkeit bei der Verbesserung des Codes, des Algorithmus oder ĂŒberhaupt bei jeglicher Optimierung zu sagen haben, dann zögern Sie nicht, es mir mitzuteilen. Wenn ich etwas nicht ausreichend erklĂ€rt habe, können Sie das auch gerne schreiben. Ich freue mich darauf, von Ihnen in den Kommentaren zu hören!
P.S.
Ja, ja, ich bin immer noch hier, denn ich habe den Koeffizienten nicht vergessen. FĂŒr die Zeichenkette s1 wiegt die Kodiertabelle 48 Byte â deutlich mehr als die ursprĂŒngliche Datei, und die zusĂ€tzlichen Nullen sind auch nicht vergessen worden (die Anzahl der hinzugefĂŒgten Nullen betrĂ€gt 7) => der Kompressionskoeffizient wird kleiner als eins sein: 176/(65 + 48*8 + 7)=0.38. Wenn Sie das auch bemerkt haben, dann herzlichen GlĂŒckwunsch, Sie sind schlau. Ja, diese Implementierung wird fĂŒr kleine Dateien Ă€uĂerst ineffizient sein. Aber was ist mit groĂen Dateien? Die DateigröĂen ĂŒbersteigen bei weitem die GröĂe der Kodiertabelle. Hier funktioniert der Algorithmus wie er soll! Zum Beispiel fĂŒr gibt der Komprimierer einen realen (nicht idealisierten) Koeffizienten von 1.46 aus â fast anderthalb Mal! Und ja, es war vorgesehen, dass die Datei in englischer Sprache ist.
Quelle: habr.com
