Masuk
Pada artikel kali ini saya akan membahas tentang algoritma Huffman yang terkenal, serta penerapannya dalam kompresi data.
Sebagai hasilnya, kami akan menulis pengarsip sederhana. Hal ini sudah dibahas , tetapi tanpa implementasi praktis. Materi teori pada postingan kali ini diambil dari pelajaran ilmu komputer sekolah dan buku Robert Laforet “Data Structures and Algorithms in Java”. Jadi, semuanya terpotong!
Sedikit refleksi
Dalam file teks biasa, satu karakter dikodekan dengan 8 bit (pengkodean ASCII) atau 16 (pengkodean Unicode). Selanjutnya kita akan mempertimbangkan pengkodean ASCII. Misalnya, ambil baris s1 = “SUSIE SAYS IT IS EASYn”. Ada total 22 karakter dalam satu baris, tentu saja, termasuk spasi dan karakter baris baru - 'n'. File yang berisi baris ini akan berbobot 22*8 = 176 bit. Pertanyaan yang segera muncul: apakah rasional menggunakan semua 8 bit untuk menyandikan 1 karakter? Kami tidak menggunakan semua karakter ASCII. Bahkan jika mereka melakukannya, akan lebih rasional jika huruf yang paling umum – S – diberi kode yang sesingkat mungkin, dan untuk huruf yang paling langka – T (atau U, atau 'n') – diberi kode yang lebih panjang. Inilah yang terdiri dari algoritma Huffman: perlu untuk menemukan opsi pengkodean optimal di mana file akan memiliki bobot minimum. Wajar jika panjang kode berbeda untuk simbol yang berbeda - inilah yang menjadi dasar algoritme.
Coding
Mengapa tidak memberi kode pada karakter 'S', misalnya, panjang 1 bit: 0 atau 1. Biarlah 1. Kemudian karakter paling umum kedua - ' ' (spasi) - beri 0. Bayangkan Anda mulai memecahkan kode pesan Anda - string yang dikodekan s1 - dan Anda melihat bahwa kode tersebut dimulai dengan 1. Jadi, apa yang Anda lakukan: apakah ini karakter S, atau karakter lain, misalnya A? Oleh karena itu, muncul aturan penting:
Tidak ada kode yang boleh menjadi awalan dari kode lain
Aturan ini adalah kunci dalam algoritma. Oleh karena itu, pembuatan kode dimulai dengan tabel frekuensi, yang menunjukkan frekuensi (jumlah kemunculan) setiap simbol:
Karakter dengan kemunculan terbanyak harus dikodekan paling sedikit mungkin jumlah bit. Saya akan memberikan contoh salah satu tabel kode yang mungkin:
Jadi pesan yang dikodekan akan terlihat seperti ini:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Saya memisahkan kode setiap karakter dengan spasi. Ini tidak akan terjadi pada file yang benar-benar terkompresi!
Timbul pertanyaan: bagaimana pemuda ini menemukan kode untuk membuat tabel kode? Ini akan dibahas di bawah.
Membangun pohon Huffman
Di sinilah pohon pencarian biner membantu. Jangan khawatir, Anda tidak memerlukan metode pencarian, penyisipan, atau penghapusan di sini. Berikut adalah struktur pohon di 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;
}
...
}
Ini bukan kode lengkapnya, kode lengkapnya ada di bawah.
Berikut adalah algoritma untuk membangun pohon:
- Buat objek Node untuk setiap karakter dari pesan (baris s1). Dalam kasus kita akan ada 9 node (objek Node). Setiap node terdiri dari dua bidang data: simbol dan frekuensi
- Buat objek Pohon (BinaryTree) untuk setiap Node. Node tersebut menjadi akar pohon.
- Masukkan pohon-pohon ini ke dalam antrian prioritas. Semakin rendah frekuensinya, semakin tinggi prioritasnya. Jadi, saat mengekstraksi, dervo dengan frekuensi terendah selalu dipilih.
Selanjutnya Anda perlu melakukan hal berikut secara siklis:
- Hapus dua pohon dari antrian prioritas dan jadikan pohon tersebut sebagai anak dari node baru (node yang baru dibuat tanpa huruf). Frekuensi node baru sama dengan jumlah frekuensi dua pohon turunannya.
- Untuk simpul ini, buatlah pohon dengan akar pada simpul ini. Masukkan pohon ini kembali ke antrian prioritas. (Karena pohon memiliki frekuensi baru, kemungkinan besar pohon tersebut akan muncul di tempat baru dalam antrian)
- Lanjutkan langkah 1 dan 2 hingga hanya tersisa satu pohon di antrian, yaitu pohon Huffman
Pertimbangkan algoritma ini pada baris s1:
Disini simbol “lf” (linefeed) artinya baris baru, “sp” (spasi) artinya spasi.
Dan lalu apa?
Kami mendapat pohon Huffman. OKE. Dan apa yang harus dilakukan dengannya? Mereka bahkan tidak akan mengambilnya secara gratis. Dan kemudian, Anda perlu menelusuri semua kemungkinan jalur dari akar hingga daun pohon tersebut. Mari kita sepakat untuk menyatakan suatu sisi 0 jika mengarah ke anak kiri dan 1 jika mengarah ke anak kanan. Sebenarnya, dalam notasi ini, kode suatu simbol adalah jalur dari akar pohon ke daun yang memuat simbol tersebut.
Beginilah hasil tabel kodenya. Perhatikan bahwa jika kita mempertimbangkan tabel ini, kita dapat menyimpulkan tentang "bobot" setiap simbol - ini adalah panjang kodenya. Kemudian, dalam bentuk terkompresi, file aslinya akan berbobot: 2*3+2*4+3*3+6*2+1*4+1*5+2*4+4*2+1*5 = 65 bit . Awalnya beratnya 176 bit. Alhasil, kami menguranginya sebanyak 176/65 = 2.7 kali! Tapi ini adalah utopia. Koefisien seperti itu tidak mungkin diperoleh. Mengapa? Ini akan dibahas nanti.
Penguraian kode
Yah, mungkin hal paling sederhana yang tersisa adalah decoding. Saya pikir banyak dari Anda yang menebak bahwa kami tidak bisa begitu saja membuat file terkompresi tanpa petunjuk apa pun tentang cara pengkodeannya - kami tidak akan dapat memecahkan kodenya! Ya, ya, sulit bagi saya untuk menyadari hal ini, tetapi saya harus membuat file teks table.txt dengan tabel kompresi:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Entri tabel berupa 'simbol''kode simbol'. Mengapa 01110 tanpa simbol? Faktanya, ini dengan simbol, hanya alat java yang saya gunakan saat mengeluarkan ke file, karakter baris baru - 'n' - diubah menjadi baris baru (tidak peduli betapa bodohnya kedengarannya). Oleh karena itu, baris kosong di bagian atas adalah karakter untuk kode 01110. Untuk kode 00, karakternya adalah spasi di awal baris. Saya akan segera mengatakan bahwa untuk koefisien Khan kami, metode penyimpanan tabel ini bisa dikatakan paling tidak rasional. Namun mudah untuk dipahami dan diterapkan. Saya akan senang mendengar rekomendasi Anda di komentar mengenai optimasi.
Memiliki tabel ini membuatnya sangat mudah untuk didekode. Mari kita ingat aturan apa yang kita ikuti saat membuat pengkodean:
Tidak ada kode yang boleh menjadi awalan dari kode lain
Di sinilah peran fasilitatornya. Kita membaca secara berurutan sedikit demi sedikit dan, segera setelah string d yang dihasilkan, yang terdiri dari bit-bit yang dibaca, cocok dengan pengkodean yang sesuai dengan karakter karakter, kita segera mengetahui bahwa karakter karakter (dan hanya itu!) telah dikodekan. Selanjutnya, kita menulis karakter ke dalam baris decoding (baris yang berisi pesan yang didekode), reset baris d, dan kemudian membaca file yang disandikan.
Implementasi
Saatnya mempermalukan kode saya dan menulis pengarsip. Sebut saja Kompresor.
Mulai dari awal. Pertama-tama, kita menulis kelas Node:
public class Node {
private int frequence;//частота
private char letter;//буква
private Node leftChild;//левый потомок
private Node rightChild;//правый потомок
public Node(char letter, int frequence) { //собственно, конструктор
this.letter = letter;
this.frequence = frequence;
}
public Node() {}//перегрузка конструтора для безымянных узлов(см. выше в разделе о построении дерева Хаффмана)
public void addChild(Node newNode) {//добавить потомка
if (leftChild == null)//если левый пустой=> правый тоже=> добавляем в левый
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) //в общем, левым потомком
rightChild = newNode;//станет тот, у кого меньше частота
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence();//итоговая частота
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() {//проверка на лист
return leftChild == null && rightChild == null;
}
}
Sekarang pohonnya:
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;
}
}
Antrian Prioritas:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Kelas yang membuat pohon Huffman:
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;
}
}
Kelas yang berisi encode/decode:
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("========================================================");
}
}
Kelas yang memudahkan penulisan ke file:
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();
}
}
Kelas yang membuatnya lebih mudah untuk membaca dari suatu file:
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();
}
}
Nah, kelas utama:
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());
}
}
Anda harus menulis file readme.txt sendiri :)
Kesimpulan
Saya rasa hanya itu yang ingin saya katakan. Jika Anda ingin mengatakan sesuatu tentang ketidakmampuan saya dalam meningkatkan kode, algoritme, atau pengoptimalan apa pun secara umum, silakan menulis. Jika saya belum menjelaskan apa pun, silakan tulis juga. Saya ingin mendengar pendapat Anda di komentar!
PS
Ya, ya, saya masih di sini, karena saya tidak melupakan koefisiennya. Untuk string s1, tabel pengkodean berbobot 48 byte - jauh lebih besar dari file sumber, dan kami tidak melupakan nol tambahan (jumlah nol yang ditambahkan adalah 7) => rasio kompresi akan kurang dari satu: 176/ (65 + 48*8 + 7) = 0.38. Jika Anda juga memperhatikan hal ini, bukan hanya wajah Anda saja yang bagus. Ya, penerapan ini akan sangat tidak efisien untuk file kecil. Tapi apa yang terjadi pada file besar? Ukuran file jauh lebih besar daripada ukuran tabel pengkodean. Di sinilah algoritma bekerja sebagaimana mestinya! Misalnya untuk Pengarsip menghasilkan koefisien nyata (tidak ideal) sebesar 1.46 - hampir satu setengah kali lipat! Dan ya, file itu seharusnya dalam bahasa Inggris.
Sumber: www.habr.com