Eintrag
In diesem Artikel werde ich über den bekannten Huffman-Algorithmus sowie seine Anwendung bei der Datenkomprimierung sprechen.
Als Ergebnis werden wir einen einfachen Archiver schreiben. Dies ist bereits geschehen , aber ohne praktische Umsetzung. Das theoretische Material des aktuellen Beitrags stammt aus dem schulischen Informatikunterricht und dem Buch „Data Structures and Algorithms in Java“ von Robert Laforet. Also, alles ist unter Kontrolle!
Ein kleiner Gedanke
In einer normalen Textdatei wird ein Zeichen mit 8 Bit (ASCII-Kodierung) oder 16 (Unicode-Kodierung) kodiert. Als nächstes betrachten wir die ASCII-Kodierung. Nehmen Sie zum Beispiel die Zeichenfolge s1 = „SUSIE SAYS IT IS EASYn“. Insgesamt enthält die Zeile natürlich 22 Zeichen, einschließlich Leerzeichen und dem Zeilenumbruchzeichen „n“. Die Datei, die diese Zeile enthält, wiegt 22*8 = 176 Bit. Es stellt sich sofort die Frage: Ist es sinnvoll, alle 8 Bits zum Codieren eines Zeichens zu verwenden? Wir verwenden nicht alle ASCII-Zeichen. Selbst wenn dies der Fall wäre, wäre es sinnvoller, dem häufigsten Buchstaben – S – den kürzestmöglichen Code zu geben und für den seltensten Buchstaben – T (oder U oder „n“) – einen authentischeren Code zu vergeben. Dies ist der Huffman-Algorithmus: Sie müssen die beste Codierungsoption finden, bei der die Datei das minimale Gewicht hat. Es ist völlig normal, dass verschiedene Zeichen unterschiedliche Codelängen haben – dies ist die Grundlage des Algorithmus.
Codierung
Warum geben Sie dem Zeichen „S“ nicht einen Code, zum Beispiel 1 Bit lang: 0 oder 1. Lassen Sie es 1 sein. Dann geben wir dem zweithäufigsten Zeichen – „“ (Leerzeichen) – 0. Stellen Sie sich vor, Sie haben damit begonnen Dekodieren Sie Ihre Nachricht – kodierte Zeichenfolge s1 – und Sie sehen, dass der Code mit 1 beginnt. Was also tun: Ist es das Zeichen S oder ist es ein anderes Zeichen, z. B. A? Daher ergibt sich eine wichtige Regel:
Kein Code darf ein Präfix eines anderen sein
Diese Regel ist der Schlüssel zum Algorithmus. Daher beginnt die Erstellung des Codes mit einer Häufigkeitstabelle, die die Häufigkeit (Anzahl des Vorkommens) jedes Symbols angibt:
Die Zeichen mit den meisten Vorkommen sollten mit den wenigsten codiert werden möglich die Anzahl der Bits. Ich werde ein Beispiel für eine der möglichen Codetabellen geben:
Die verschlüsselte Nachricht sieht also so aus:
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 Zeichens durch ein Leerzeichen getrennt. Dies wird in einer komprimierten Datei nicht wirklich passieren!
Es stellt sich die Frage: Wie ist dieser Neuling auf einen Code zum Erstellen einer Codetabelle gekommen? Dies wird weiter unten besprochen.
Einen Huffman-Baum bauen
Hier kommen binäre Suchbäume zur Rettung. Keine Sorge, Sie benötigen die Such-, Einfüge- und Löschmethoden hier nicht. Hier ist die Baumstruktur 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;
}
...
}
Dies ist nicht der vollständige Code, der vollständige Code finden Sie weiter unten.
Hier ist der Algorithmus zum Erstellen eines Baums:
- Erstellen Sie für jedes Zeichen aus der Nachricht ein Node-Objekt (Zeile s1). In unserem Fall gibt es 9 Knoten (Knotenobjekte). Jeder Knoten besteht aus zwei Datenfeldern: Symbol und Frequenz
- Erstellen Sie für jeden Node-Knoten ein Tree-Objekt (BinaryTree). Der Knoten wird zur Wurzel des Baums.
- Fügen Sie diese Bäume in die Prioritätswarteschlange ein. Je niedriger die Frequenz, desto höher die Priorität. Daher wird beim Extrahieren immer der Baum mit der niedrigsten Häufigkeit ausgewählt.
Als nächstes müssen Sie zyklisch Folgendes tun:
- Rufen Sie zwei Bäume aus der Prioritätswarteschlange ab und machen Sie sie zu Kindern eines neuen Knotens (eines neu erstellten Knotens ohne Buchstaben). Die Häufigkeit des neuen Knotens ist gleich der Summe der Häufigkeiten der beiden Nachkommenbäume.
- Erstellen Sie für diesen Knoten einen Baum, dessen Wurzel auf diesem Knoten basiert. Fügen Sie diesen Baum wieder in die Prioritätswarteschlange ein. (Da der Baum eine neue Häufigkeit hat, wird er höchstwahrscheinlich an einer neuen Stelle in der Warteschlange landen.)
- Fahren Sie mit den Schritten 1 und 2 fort, bis nur noch ein Baum in der Warteschlange übrig ist – der Huffman-Baum
Betrachten Sie diesen Algorithmus in Zeile s1:
Dabei bezeichnet das Symbol „lf“ (Linefeed) eine neue Zeile, „sp“ (Space) ist ein Leerzeichen.
Und was dann?
Wir haben den Huffman-Baum bekommen. OK. Und was tun damit? Sie nehmen es nicht umsonst. Und dann müssen Sie alle möglichen Wege von der Wurzel bis zu den Blättern des Baumes verfolgen. Wir vereinbaren, eine Kante mit 0 zu bezeichnen, wenn sie zum linken Kind führt, und mit 1, wenn sie zum rechten Kind führt. Streng genommen ist der Zeichencode in diesen Notationen der Pfad von der Wurzel des Baums bis zum Blatt, das genau dieses Zeichen enthält.
So entstand die Codetabelle. Beachten Sie, dass wir, wenn wir diese Tabelle betrachten, Rückschlüsse auf das „Gewicht“ jedes Zeichens ziehen können – dies ist die Länge seines Codes. Dann wiegt die Quelldatei in komprimierter Form: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 Bit . Anfangs wog es 176 Bit. Deshalb haben wir es um das 176/65 = 2.7-fache reduziert! Aber das ist eine Utopie. Es ist unwahrscheinlich, dass ein solches Verhältnis erreicht wird. Warum? Dies wird etwas später besprochen.
Dekodierung
Nun, das Einfachste, was noch übrig ist, ist vielleicht die Dekodierung. Ich denke, viele von Ihnen haben vermutet, dass es unmöglich ist, einfach eine komprimierte Datei ohne Hinweise darauf zu erstellen, wie sie kodiert wurde – wir werden sie nicht entschlüsseln können! Ja, ja, es war schwer für mich, das zu realisieren, aber ich muss eine Textdatei table.txt mit einer Komprimierungstabelle erstellen:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Tabelleneintrag in der Form 'character'"character code". Warum ist 01110 ohne Symbol? Tatsächlich ist es bei einem Zeichen so, dass nur die Java-Tools, die ich bei der Ausgabe in eine Datei verwende, das Newline-Zeichen – „n“ – in ein Newline-Zeichen umwandeln (egal wie dumm es klingt). Daher ist die leere Zeile oben das Zeichen für Code 01110. Für Code 00 ist das Zeichen ein Leerzeichen am Anfang der Zeile. Ich muss gleich sagen, dass diese Methode zur Speicherung der Tabelle als die irrationalste für unseren Khan-Koeffizienten gelten kann. Aber es ist leicht zu verstehen und umzusetzen. Ich freue mich über Ihre Empfehlungen in den Kommentaren zum Thema Optimierung.
Mit dieser Tabelle ist die Dekodierung sehr einfach. Erinnern wir uns an die Regel, an der wir uns bei der Erstellung der Kodierung orientiert haben:
Kein Code darf ein Präfix eines anderen sein
Hier spielt es eine unterstützende Rolle. Wir lesen nacheinander Stück für Stück, und sobald die resultierende Zeichenfolge d, bestehend aus den gelesenen Bits, mit der dem Zeichen entsprechenden Kodierung übereinstimmt, wissen wir sofort, dass das Zeichen (und nur es!) kodiert wurde. Als nächstes schreiben wir Zeichen in die Dekodierungszeichenfolge (die Zeichenfolge, die die dekodierte Nachricht enthält), setzen die d-Zeichenfolge zurück und lesen die kodierte Datei weiter.
Implementierung
Es ist Zeit, meinen Code zu demütigen, indem ich einen Archivierer schreibe. Nennen wir es Kompressor.
Von vorn anfangen. Zunächst schreiben wir die Node-Klasse:
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;
}
}
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;//да-да, очередь будет на базе списка
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Die Klasse, die den Huffman-Baum erstellt:
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;
}
}
Die Klasse, die Folgendes kodiert/dekodiert:
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("========================================================");
}
}
Eine 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("Неверный путь, или такого файла не существует!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Eine 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)//если закончился файл
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Nun, 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 {//указываем инструкцию с помощью аргументов командной строки
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());
}
}
Sie müssen die Datei mit den readme.txt-Anweisungen selbst schreiben 🙂
Abschluss
Ich denke, das ist alles, was ich sagen wollte. Wenn Sie etwas zu meiner Inkompetenz bei der Verbesserung des Codes, des Algorithmus oder einer Optimierung im Allgemeinen zu sagen haben, können Sie mir gerne schreiben. Wenn ich etwas nicht erklärt habe, schreiben Sie bitte auch. Ich würde mich freuen, von Ihnen in den Kommentaren zu hören!
PS
Ja, ja, ich bin immer noch hier, weil ich den Koeffizienten nicht vergessen habe. Für die Zeichenfolge s1 wiegt die Codierungstabelle 48 Bytes – viel mehr als die Originaldatei, und sie haben die zusätzlichen Nullen nicht vergessen (die Anzahl der hinzugefügten Nullen beträgt 7) => das Komprimierungsverhältnis wird kleiner als eins sein: 176 /(65 + 48*8 + 7) = 0.38. Wenn Ihnen das auch aufgefallen ist, dann sind Sie einfach nicht im Gesicht fertig. Ja, diese Implementierung wird für kleine Dateien äußerst ineffizient sein. Aber was passiert mit großen Dateien? Die Dateigrößen sind viel größer als die Größe der Kodierungstabelle. Hier funktioniert der Algorithmus wie er soll! Zum Beispiel, z der Archiver gibt einen realen (nicht idealisierten) Koeffizienten von 1.46 an – fast das Eineinhalbfache! Und ja, die Datei sollte auf Englisch sein.
Source: habr.com