Wprowadzenie
W tym artykule opowiem o znanym algorytmie Huffmana oraz jego zastosowaniu w kompresji danych.
W efekcie napiszemy prosty archiwizator. O tym już była , ale bez praktycznej realizacji. Materiał teoretyczny bieżącego posta pochodzi z lekcji informatyki w szkole oraz z książki Roberta Lafore'a „Struktury danych i algorytmy w Javie”. Zatem, wszystko pod kat!
Trochę refleksji
W zwykłym pliku tekstowym jeden znak kodowany jest 8 bitami (kodowanie ASCII) lub 16 (kodowanie Unicode). Dalsza analiza będzie dotyczyć kodowania ASCII. Dla przykładu weźmy ciąg s1 = „SUSIE SAYS IT IS EASYn”. W sumie w ciągu jest 22 znaki, oczywiście, wliczając spacje i symbol przejścia do nowej linii — 'n'. Plik zawierający ten ciąg ważyłby 22*8 = 176 bitów. Od razu pojawia się pytanie: czy rozsądne jest używać wszystkich 8 bitów do kodowania 1 znaku? W końcu nie wykorzystujemy wszystkich znaków kodowania ASCII. Nawet gdybyśmy je wykorzystali, rozsądniej byłoby najczęściej występującej literze — S — nadać najkrótszy możliwy kod, a najrzadszej literze — T (lub U, lub 'n') — nadać kod dłuższy. Oto na czym polega algorytm Huffmana: należy znaleźć optymalną wersję kodowania, w której plik będzie miał minimalną wagę. Jest całkiem normalne, że różne znaki mogą mieć różne długości kodów — na tym właśnie oparty jest algorytm.
Kodowanie
Czemu by literze ‘S’ nie nadać kodu, na przykład, o długości 1 bitu: 0 lub 1. Niech to będzie 1. Wtedy drugiemu najczęściej występującemu znakowi — ‘ ‘(spacja) — nadamy 0. Wyobraź sobie, że zaczynasz dekodować swoje wiadomości — zakodowany ciąg s1 — i widzisz, że kod zaczyna się od 1. Co zrobić: czy to znak S, czy może jakiś inny znak, na przykład A? Dlatego pojawia się ważna zasada:
Żaden kod nie powinien być prefiksem innego
Ta zasada jest kluczowa w algorytmie. Dlatego tworzenie kodu zaczyna się od tabeli częstotliwości, w której podano częstotliwość (liczba wystąpień) każdego znaku:
Znaki z największą liczba wystąpień powinny być kodowane najmniejszą możliwą liczbą bitów. Przykładem jednej z możliwych tabel kodów może być:
W ten sposób zakodowana wiadomość będzie wyglądać tak:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Kod każdego symbolu oddzieliłem spacją. W rzeczywistości w skompresowanym pliku takiego nie będzie!
Rodzi się pytanie: jak ten nowicjusz wymyślił kod do stworzenia tabeli kodów? O tym będzie mowa poniżej.
Budowanie drzewa Huffmana
Tutaj na ratunek przychodzą binarne drzewa poszukiwań. Nie martwcie się, metody wyszukiwania, wstawiania i usuwania nie będą potrzebne. Oto struktura drzewa w Javie:
public class Node {
private int frekwencja;
private char znak;
private Node lewyPotomek;
private Node prawyPotomek;
...
}
class BinaryTree {
private Node korzeń;
public BinaryTree() {
korzeń = new Node();
}
public BinaryTree(Node korzeń) {
this.korzeń = korzeń;
}
...
}
To nie jest pełny kod, pełny kod będzie poniżej.
Oto sam algorytm budowy drzewa:
- Stwórz obiekt Node dla każdego symbolu z wiadomości (ciąg s1). W naszym przypadku będzie 9 węzłów (obiektów Node). Każdy węzeł składa się z dwóch pól danych: symbol i częstotliwość.
- Stwórz obiekt drzewa (BinaryTree) dla każdego z węzłów Node. Węzeł staje się korzeniem drzewa.
- Wstaw te drzewa do kolejki priorytetowej. Im mniejsza częstotliwość, tym większy priorytet. Tak więc, przy wydobywaniu zawsze wybierane jest drzewo o najmniejszej częstotliwości.
Następnie należy cyklicznie wykonywać następujące kroki:
- Wyciągnąć dwa drzewa z kolejki priorytetowej i uczynić je potomstwem nowego węzła (dopiero co stworzonego węzła bez znaku). Częstotliwość nowego węzła jest równa sumie częstotliwości dwóch drzew-potomków.
- Dla tego węzła utwórz drzewo z korzeniem w danym węźle. Wstaw to drzewo z powrotem do kolejki priorytetowej. (Ponieważ drzewo ma nową częstotliwość, prawdopodobnie zajmie nowe miejsce w kolejce)
- Kontynuuj wykonywanie kroków 1 i 2, aż w kolejce zostanie tylko jedno drzewo — drzewo Huffmana.
Rozważmy ten algorytm na ciągu s1:
Tutaj symbol „lf” (linefeed) oznacza przejście do nowej linii, „sp” (space) — to spacja.
A co dalej?
Otrzymaliśmy drzewo Huffmana. No dobrze. A co z nim zrobić? Nawet za darmo go nie wezmą. A dalej, należy śledzić wszystkie możliwe ścieżki od korzenia do liści drzewa. Umówmy się oznaczyć krawędź 0, jeśli prowadzi do lewego potomka i 1 — jeśli do prawego. Ścisłe mówiąc, w tych oznaczeniach kod symbolu — to ścieżka od korzenia drzewa do liścia, zawierającego ten symbol.
W ten sposób powstała tabela kodów. Zauważmy, że jeśli spojrzymy na tę tabelę, możemy wyciągnąć wniosek o „wadze” każdego znaku — to długość jego kodu. Wtedy w skompresowanej formie oryginalny plik będzie ważyć: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bitów. Na początku ważył 176 bitów. Oznacza to, że zredukowaliśmy jego rozmiar aż w 176/65 = 2.7 razy! Ale to utopia. Taki współczynnik raczej nie będzie osiągalny. Dlaczego? O tym będzie mowa nieco później.
Dekodowanie
Cóż, chyba zostało najprostsze — dekodowanie. Myślę, że wielu z was domyśliło się, że nie można po prostu stworzyć skompresowanego pliku bez żadnych wskazówek dotyczących tego, jak został on zakodowany — nie będziemy mogli go dekodować! Tak, było mi trudno to zrozumieć, ale muszę stworzyć plik tekstowy table.txt z tabelą kompresji:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Zapis tabeli w formacie 'symbol'«kod symbolu». Dlaczego 01110 bez symbolu? W rzeczywistości ma symbol, po prostu narzędzia java, których użyłem do zapisu do pliku, konwertują znak przejścia na nową linię — 'n' - na przejście do nowej linii (jak głupio to nie brzmi). Dlatego pusta linia na górze to symbol dla kodu 01110. Dla kodu 00 symbolem jest spacja na początku linii. Od razu powiem, że nasz współczynnik już umiera — ten sposób przechowywania tabeli może pretendować do miana najmniej racjonalnego. Ale jest prosty do zrozumienia i wdrożenia. Z chęcią wysłucham waszych sugestii w komentarzach dotyczących optymalizacji.
Mając tę tabelę, dekodowanie jest bardzo proste. Przypomnijmy sobie, jaką zasadą kierowaliśmy się przy tworzeniu kodowania:
Żaden kod nie może być prefiksem innego
Tutaj to właśnie odgrywa ułatwiającą rolę. Czytamy kolejno bit po bicie i, gdy tylko uzyskany ciąg d, składający się z odczytanych bitów, pasuje do kodowania odpowiadającego symbolowi character, od razu wiemy, że został zakodowany symbol character (i tylko on!). Następnie zapisujemy character do ciągu dekodującego (ciągu zawierającego dekodowaną wiadomość), zerujemy ciąg d i czytamy dalej skompresowany plik.
Realizacja
Nadeszła pora, by poniżyć mój kod i napisać archiwizator. Nazwijmy go Compressor.
Zacznijmy od początku. Pierwszą rzeczą, którą piszemy, jest klasa Node:
public class Node {
private int frekwencja; // częstotliwość
private char litera; // litera
private Node lewyPotomek; // lewy potomek
private Node prawyPotomek; // prawy potomek
public Node(char litera, int frekwencja) { // konstruktor
this.litera = litera;
this.frekwencja = frekwencja;
}
public Node() {} // przeciążenie konstruktora dla bezimiennych węzłów (patrz wyżej w sekcji o budowie drzewa Huffmana)
public void dodajPotomka(Node nowyWęzeł) { // dodaj potomka
if (lewyPotomek == null) // jeśli lewy jest pusty => prawy też => dodajemy do lewego
lewyPotomek = nowyWęzeł;
else {
if (lewyPotomek.getFrekwencja() <= nowyWęzeł.getFrekwencja()) // lewy potomek
prawyPotomek = nowyWęzeł; // stanie się tym, który ma mniejszą częstotliwość
else {
prawyPotomek = lewyPotomek;
lewyPotomek = nowyWęzeł;
}
}
frekwencja += nowyWęzeł.getFrekwencja(); // łączna częstotliwość
}
public Node getLewyPotomek() {
return lewyPotomek;
}
public Node getPrawyPotomek() {
return prawyPotomek;
}
public int getFrekwencja() {
return frekwencja;
}
public char getLitera() {
return litera;
}
public boolean jestLiściem() { // sprawdzenie na liść
return lewyPotomek == null && prawyPotomek == null;
}
}
Teraz drzewo:
class BinaryTree {
private Node korzeń;
public BinaryTree() {
korzeń = new Node();
}
public BinaryTree(Node korzeń) {
this.korzeń = korzeń;
}
public int getFrekwencja() {
return korzeń.getFrekwencja();
}
public Node getKorzeń() {
return korzeń;
}
}
Kolejka priorytetowa:
import java.util.ArrayList; // tak, kolejka będzie oparta na liście
class PriorityQueue {
private ArrayList dane; // lista kolejki
private int nElementów; // liczba elementów w kolejce
public PriorityQueue() {
dane = new ArrayList();
nElementów = 0;
}
public void wstaw(BinaryTree nowaDrzewo) { // wstawienie
if (nElementów == 0)
dane.add(nowaDrzewo);
else {
for (int i = 0; i nowaDrzewo.getFrekwencja()) { // jeśli częstotliwość wstawianego drzewa jest mniejsza
dane.add(i, nowaDrzewo); // to przesuwamy wszystkie drzewa na prawych pozycjach o 1 komórkę
break; // następnie wstawiamy nowe drzewo na pozycję bieżącego
}
if (i == nElementów - 1)
dane.add(nowaDrzewo);
}
}
nElementów++; // zwiększamy liczbę elementów o 1
}
public BinaryTree usuń() { // usunięcie z kolejki
BinaryTree tmp = dane.get(0); // kopiowanie usuwanego elementu
dane.remove(0); // usunięcie
nElementów--; // zmniejszamy liczbę elementów o 1
return tmp; // zwracamy usunięty element (element o najmniejszej częstotliwości)
}
}
Klasa tworząca drzewo Huffmana:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127; // długość tabeli kodowania
private String myString; // wiadomość
private BinaryTree huffmanTree; // drzewo Huffmana
private int[] freqArray; // tabela częstotliwości
private String[] encodingArray; // tabela kodowania
//----------------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();
// algorytm opisany powyżej
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) { // jeśli symbol istnieje w ciągu
Node newNode = new Node((char) i, freqArray[i]); // tworzy dla niego Node
BinaryTree newTree = new BinaryTree(newNode); // a dla Node tworzy BinaryTree
pq.insert(newTree); // wstawia do kolejki
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // wyciąga z kolejki pierwsze drzewo.
try {
BinaryTree tree2 = pq.remove(); // wyciąga z kolejki drugie drzewo
Node newNode = new Node(); // tworzy nowy Node
newNode.addChild(tree1.getRoot()); // robi je potomkami dwa wyciągnięte drzewa
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) { // pozostało jedno drzewo w kolejce
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) { // wypełnij tabelę kodowania
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() { // do debugowania
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Tabela kodowania====================");
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;
}
}
Klasa, która koduje/dekoduje:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // długość tabeli
private HuffmanTree mainHuffmanTree; // drzewo Huffmana (używane tylko do kompresji)
private String myString; // oryginalna wiadomość
private int[] freqArray; // tabela częstotliwości
private String[] encodingArray; // tabela kodowania
private double ratio; // współczynnik kompresji
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // do kompresji
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // do ekstrakcji;
// ---------------------------------------kompresja-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; // pośrednia strona (bez dodatkowych zer)
// System.out.println("=============================Kompresja=======================");
// displayEncodingArray();
for (int i = 0; i
// musimy dodać zera na końcu (możemy 1, nie ma znaczenia)
byte counter = 0; // liczba dodanych zer na końcu (bait jest wystarczający: 0 <= counter < 8 < 127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta; counter++) { // delta - liczba dodanych zer
intermidiate += "0";
}
// połączenie liczby dodanych zer w binarnej reprezentacji i pośredniej strony
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
// zidealizowany współczynnik
setCompressionRatio();
// System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { // obliczyć zidealizowany współczynnik
double sumA = 0, sumB = 0; // A - oryginalna suma
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() { // finalna kompresja
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;
}
// ---------------------------------------koniec kompresji----------------------------------------------------------------
// ------------------------------------------------------------ekstrakcja-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
// displayEncodingArray();
// uzyskać liczbę wstawionych zer
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, ponieważ pierwszym bajtem jest liczba wstawionych zer
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { // jeśli pasuje
decompressed += (char)j; // dodaj element
current = ""; // i zeruj bieżący ciąg
}
}
}
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() { // do debugowania
System.out.println("======================Tabela kodowania====================");
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("========================================================");
}
}
Klasa ułatwiająca zapis do pliku:
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("Błędna ścieżka lub taki plik nie istnieje!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Klasa ułatwiająca odczyt z pliku:
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) // jeśli doszło do końca pliku
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
A oto główna klasa:
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 { // Wskazujemy instrukcję z wykorzystaniem argumentów wiersza poleceń
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("Nieprawidłowy format wejściowy argumentów");
System.out.println("Sprawdź 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("Nieprawidłowa ścieżka, lub taki plik nie istnieje!");
return;
} catch (MalformedInputException e) {
System.out.println("Bieżące kodowanie pliku nie jest obsługiwane");
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());
}
// Tworzymy plik z tabelą kodowania:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Ścieżka do skompresowanego pliku: " + compressedFile.getAbsolutePath());
System.out.println("Ścieżka do tabeli kodowania " + table.getAbsolutePath());
System.out.println("Bez tabeli plik będzie niemożliwy do wydobycia!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100; // Idealny współczynnik
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double) 100; // Rzeczywisty współczynnik
System.out.println("Idealny współczynnik kompresji wynosi " + idealRatio);
System.out.println("Współczynnik kompresji z uwzględnieniem tabeli kodowania " + 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];
// Odczytujemy skompresowany plik
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! sprawdź tutaj:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte(); // metoda zwraca EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
// --------------------
// Odczytujemy tabelę kodowania:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine(); // pomijamy pierwszy pusty wiersz
encodingArray[(byte)'n'] = fi.readLine(); // odczytujemy kod dla '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();
// Wydobycie:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Ścieżka do wypakowanego pliku " + extractedFile.getAbsolutePath());
}
}
Plik z instrukcjami readme.txt musicie napisać sami 🙂
Podsumowanie
Pewnie to wszystko, co chciałem powiedzieć. Jeżeli macie jakieś uwagi dotyczące mojej niekompetencji w poprawach kodu, algorytmu, czy jakiejkolwiek optymalizacji, śmiało piszcie. Jeśli coś było niejasne, również dajcie znać. Będę wdzięczny za usłyszenie Was w komentarzach!
P.S.
Tak, nadal tu jestem, nie zapomniałem o współczynniku. Dla ciągu s1 tabela kodowania waży 48 bajtów — znacznie więcej niż plik źródłowy, a o dodanych zerach nie zapomniano (liczba dodanych zer wynosi 7) => współczynnik kompresji będzie mniejszy od jedności: 176/(65 + 48*8 + 7)=0.38. Jeśli też to zauważyliście, to tylko nie łapcie urazy, jesteście świetni. Tak, ta implementacja będzie ekstremalnie nieefektywna dla małych plików. Ale co się dzieje z większymi plikami? Rozmiary pliku znacznie przewyższają rozmiar tabeli kodowania. Tutaj algorytm działa jak należy! Na przykład, dla program do archiwizacji daje rzeczywisty (nie idealizowany) współczynnik wynoszący 1.46 — prawie półtora razy! I tak, zakładano, że plik będzie w języku angielskim.
Źródło: habr.com
