Entry
Dalam artikel ini saya akan bercakap tentang algoritma Huffman yang terkenal, serta aplikasinya dalam pemampatan data.
Akibatnya, kami akan menulis arkib mudah. Perkara ini telah pun dibincangkan , tetapi tanpa pelaksanaan praktikal. Bahan teori jawatan semasa diambil dari pelajaran sains komputer sekolah dan buku Robert Laforet "Struktur Data dan Algoritma di Jawa". Jadi, semuanya dipotong!
Sedikit pemikiran
Dalam fail teks biasa, satu aksara dikodkan dengan 8 bit (pengekodan ASCII) atau 16 (pengekodan Unikod). Seterusnya kita akan mempertimbangkan pengekodan ASCII. Sebagai contoh, ambil baris s1 = "SUSIE KATA ITU MUDAHn". Terdapat sejumlah 22 aksara dalam baris, secara semula jadi, termasuk ruang dan aksara baris baharu - 'n'. Fail yang mengandungi baris ini akan mempunyai berat 22*8 = 176 bit. Persoalan segera timbul: adakah rasional untuk menggunakan semua 8 bit untuk mengekod 1 aksara? Kami tidak menggunakan semua aksara ASCII. Walaupun mereka melakukannya, adalah lebih rasional untuk huruf yang paling biasa - S - diberi kod yang sesingkat mungkin, dan untuk huruf yang paling jarang - T (atau U, atau 'n') - diberi kod yang lebih panjang. Inilah yang terdiri daripada algoritma Huffman: adalah perlu untuk mencari pilihan pengekodan optimum di mana fail akan mempunyai berat minimum. Ia adalah perkara biasa bahawa panjang kod akan berbeza untuk simbol yang berbeza - ini adalah asas algoritma.
Pengekodan
Mengapa tidak berikan kod aksara 'S', sebagai contoh, 1 bit panjang: 0 atau 1. Biarkan 1. Kemudian aksara kedua paling biasa - ' ' (ruang) - berikan 0. Bayangkan anda mula menyahkod mesej anda - rentetan yang dikodkan s1 - dan anda melihat bahawa kod itu bermula dengan 1. Jadi, apa yang anda lakukan: adakah ini aksara S, atau adakah ia watak lain, contohnya A? Oleh itu, peraturan penting timbul:
Kedua-dua kod tidak sepatutnya menjadi awalan yang lain
Peraturan ini adalah kunci dalam algoritma. Oleh itu, mencipta kod bermula dengan jadual kekerapan, yang menunjukkan kekerapan (bilangan kejadian) setiap simbol:
Aksara dengan kejadian terbanyak hendaklah dikodkan paling sedikit mungkin bilangan bit. Saya akan memberikan contoh salah satu jadual kod yang mungkin:
Jadi mesej yang dikodkan akan kelihatan 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 kod setiap aksara dengan ruang. Ini tidak akan berlaku dalam fail yang benar-benar dimampatkan!
Timbul persoalan: bagaimana lelaki muda ini menghasilkan kod untuk mencipta jadual kod? Ini akan dibincangkan di bawah.
Membina pokok Huffman
Di sinilah pokok carian binari datang untuk menyelamatkan. Jangan risau, anda tidak perlu mencari, memasukkan atau memadam kaedah di sini. Berikut ialah struktur pokok 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 kod lengkap, kod penuh akan ada di bawah.
Berikut ialah algoritma untuk membina pokok:
- Cipta objek Nod untuk setiap aksara daripada mesej (baris s1). Dalam kes kami akan ada 9 nod (objek Nod). Setiap nod terdiri daripada dua medan data: simbol dan kekerapan
- Cipta objek Pokok (BinaryTree) untuk setiap Nod. Nod menjadi akar pokok.
- Masukkan pokok ini ke dalam baris gilir keutamaan. Lebih rendah kekerapan, lebih tinggi keutamaan. Oleh itu, apabila mengekstrak, dervo dengan frekuensi terendah sentiasa dipilih.
Seterusnya anda perlu melakukan perkara berikut secara kitaran:
- Keluarkan dua pepohon daripada barisan keutamaan dan jadikan ia anak-anak daripada nod baharu (nod yang baru dibuat tanpa huruf). Kekerapan nod baharu adalah sama dengan jumlah frekuensi dua pokok keturunan.
- Untuk nod ini, buat pokok dengan akar pada nod ini. Masukkan pokok ini kembali ke dalam baris gilir keutamaan. (Memandangkan pokok mempunyai kekerapan baharu, ia berkemungkinan besar akan muncul di tempat baharu dalam baris gilir)
- Teruskan langkah 1 dan 2 sehingga hanya tinggal satu pokok dalam baris gilir - pokok Huffman
Pertimbangkan algoritma ini pada baris s1:
Di sini simbol "lf" (linefeed) bermaksud baris baharu, "sp" (ruang) ialah ruang.
Kemudian apa?
Kami mendapat pokok Huffman. OKEY. Dan apa yang perlu dilakukan dengannya? Mereka tidak akan mengambilnya secara percuma. Kemudian, anda perlu mengesan semua laluan yang mungkin dari akar hingga ke daun pokok. Mari kita bersetuju untuk menandakan kelebihan 0 jika ia menuju ke anak kiri dan 1 jika ia menuju ke kanan. Tegasnya, dalam tatatanda ini, kod simbol ialah laluan dari akar pokok ke daun yang mengandungi simbol ini.
Ini adalah bagaimana jadual kod ternyata. Ambil perhatian bahawa jika kita mempertimbangkan jadual ini, kita boleh membuat kesimpulan tentang "berat" setiap simbol - ini ialah panjang kodnya. Kemudian, dalam bentuk termampat, fail asal akan menimbang: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bit . Pada mulanya ia mempunyai berat 176 bit. Akibatnya, kami mengurangkannya sebanyak 176/65 = 2.7 kali ganda! Tetapi ini adalah utopia. Pekali sedemikian tidak mungkin diperolehi. kenapa? Ini akan dibincangkan sedikit kemudian.
Penyahkodan
Nah, mungkin perkara paling mudah yang tinggal ialah penyahkodan. Saya rasa ramai di antara anda telah meneka bahawa kami tidak boleh mencipta fail termampat tanpa sebarang petunjuk tentang cara ia dikodkan - kami tidak akan dapat menyahkodnya! Ya, ya, sukar untuk saya menyedari perkara ini, tetapi saya perlu mencipta fail teks table.txt dengan jadual mampatan:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Entri jadual dalam bentuk 'simbol' 'kod aksara'. Mengapa 01110 tanpa simbol? Sebenarnya, ia adalah dengan simbol, cuma alat java yang saya gunakan semasa mengeluarkan ke fail, aksara baris baharu - 'n' - ditukar kepada baris baharu (tidak kira betapa bodohnya bunyi itu). Oleh itu, baris kosong di bahagian atas ialah aksara untuk kod 01110. Untuk kod 00, aksara ialah ruang pada permulaan baris. Saya akan katakan dengan segera bahawa untuk pekali Khan kami, kaedah menyimpan jadual ini boleh mendakwa sebagai yang paling tidak rasional. Tetapi ia mudah difahami dan dilaksanakan. Saya akan gembira mendengar cadangan anda dalam ulasan mengenai pengoptimuman.
Имея эту таблицу, очень просто декодировать. Вспомним, каким правилом мы руководствовались, при создании кодировки:
Kedua-dua kod tidak sepatutnya menjadi awalan yang lain
Di sinilah ia memainkan peranan pemudah cara. Kami membaca secara berurutan sedikit demi sedikit dan, sebaik sahaja rentetan d yang terhasil, yang terdiri daripada bit baca, sepadan dengan pengekodan yang sepadan dengan watak watak, kami serta-merta mengetahui bahawa watak watak (dan hanya itu!) telah dikodkan. Seterusnya, kami menulis aksara ke dalam baris penyahkod (baris yang mengandungi mesej yang dinyahkod), set semula baris d, dan kemudian baca fail yang dikodkan.
Реализация
Sudah tiba masanya untuk memalukan kod saya dan menulis pengarkib. Mari kita panggil ia Compressor.
Mula semula. Pertama sekali, kami 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 pokok itu:
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;
}
}
Barisan Keutamaan:
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 mencipta pokok 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 mengandungi mengekod/menyahkod:
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 untuk menulis ke fail:
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 memudahkan untuk membaca daripada fail:
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, dan 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 perlu menulis sendiri fail readme.txt :)
Kesimpulan
Saya rasa itu sahaja yang saya ingin katakan. Jika anda mempunyai apa-apa untuk diperkatakan tentang ketidakcekapan saya dalam menambah baik kod, algoritma atau sebarang pengoptimuman secara umum, maka jangan ragu untuk menulis. Jika saya tidak menjelaskan apa-apa, sila tulis juga. Saya ingin mendengar daripada anda dalam komen!
PS
Ya, ya, saya masih di sini, kerana saya tidak lupa tentang pekali. Untuk rentetan s1, jadual pengekodan mempunyai berat 48 bait - jauh lebih besar daripada fail sumber, dan kami tidak lupa tentang sifar tambahan (bilangan sifar tambahan ialah 7) => nisbah mampatan akan kurang daripada satu: 176/ (65 + 48*8 + 7) = 0.38. Jika anda juga perasan ini, maka bukan hanya wajah anda yang hebat. Ya, pelaksanaan ini akan menjadi sangat tidak cekap untuk fail kecil. Tetapi apa yang berlaku kepada fail besar? Saiz fail jauh lebih besar daripada saiz jadual pengekodan. Di sinilah algoritma berfungsi sebagaimana mestinya! Sebagai contoh, untuk Arkib menghasilkan pekali sebenar (tidak ideal) 1.46 - hampir satu setengah kali! Dan ya, fail itu sepatutnya dalam bahasa Inggeris.
Sumber: www.habr.com