Entry
In hierdie artikel sal ek praat oor die bekende Huffman-algoritme, sowel as die toepassing daarvan in datakompressie.
As gevolg hiervan sal ons 'n eenvoudige argiefhouer skryf. Dit was reeds , maar sonder praktiese implementering. Die teoretiese materiaal van die huidige pos is geneem uit skoolrekenaarwetenskaplesse en Robert Laforet se boek "Data Structures and Algorithms in Java". So, alles is onder die knie!
Bietjie refleksie
In 'n gewone tekslêer word een karakter met 8 bisse (ASCII-kodering) of 16 (Unicode-kodering) geënkodeer. Vervolgens sal ons die ASCII-kodering oorweeg. Neem byvoorbeeld die string s1 = "SUSIE SÊ DIT IS MAKLIK". In totaal is daar natuurlik 22 karakters in die reël, insluitend spasies en die nuwelynkarakter - 'n'. Die lêer wat hierdie lyn bevat sal 22*8 = 176 bisse weeg. Die vraag ontstaan dadelik: is dit rasioneel om al 8 bisse te gebruik om 1 karakter te enkodeer? Ons gebruik nie alle ASCII-karakters nie. Selfs as hulle was, sou dit meer rasioneel wees om die mees gereelde letter - S - die kortste moontlike kode te gee, en vir die skaarsste letter - T (of U, of 'n') - gee die kode meer outentiek. Dit is die Huffman-algoritme: jy moet die beste enkoderingsopsie vind, waarin die lêer van minimum gewig sal wees. Dit is heel normaal dat verskillende karakters verskillende kodelengtes sal hê - dit is die basis van die algoritme.
Kodering
Hoekom gee nie vir die karakter 'S' 'n kode nie, byvoorbeeld 1 bietjie lank: 0 of 1. Laat dit 1 wees. Dan die tweede mees voorkomende karakter - ' ' (spasie) - ons sal 0 gee. Stel jou voor, jy het begin om dekodeer jou boodskap - geënkodeerde string s1 - en jy sien dat die kode met 1 begin. So, wat om te doen: is dit die karakter S, of is dit 'n ander karakter, soos A? Daarom ontstaan 'n belangrike reël:
Geen kode moet 'n voorvoegsel van 'n ander wees nie
Hierdie reël is die sleutel tot die algoritme. Daarom begin die skepping van die kode met 'n frekwensietabel, wat die frekwensie (aantal voorkomste) van elke simbool aandui:
Die karakters met die meeste voorkomste moet met die minste geënkodeer word moontlik die aantal stukkies. Ek sal 'n voorbeeld gee van een van die moontlike kodetabelle:
Die geënkodeerde boodskap sal dus soos volg lyk:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Ek het die kode van elke karakter met 'n spasie geskei. Dit sal nie regtig in 'n saamgeperste lêer gebeur nie!
Die vraag ontstaan: hoe het hierdie nuweling met 'n kode vorendag gekom hoe om 'n kodetabel te skep? Dit sal hieronder bespreek word.
Bou 'n Huffman-boom
Dit is waar binêre soekbome tot die redding kom. Moenie bekommerd wees nie, jy sal nie die soek-, invoeg- en uitveemetodes hier nodig hê nie. Hier is die boomstruktuur 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;
}
...
}
Dit is nie die volledige kode nie, die volledige kode sal hieronder wees.
Hier is die algoritme om 'n boom te bou:
- Skep 'n Node-objek vir elke karakter uit die boodskap (reël s1). In ons geval sal daar 9 nodusse (Node-objekte) wees. Elke nodus bestaan uit twee datavelde: simbool en frekwensie
- Skep 'n Boom-objek (BinaryTree) vir elk van die Node-nodusse. Die knoop word die wortel van die boom.
- Plaas hierdie bome in die prioriteitsry. Hoe laer die frekwensie, hoe hoër die prioriteit. Wanneer dus onttrek word, word die boom met die laagste frekwensie altyd gekies.
Vervolgens moet u die volgende siklies doen:
- Haal twee bome uit die prioriteitsry en maak hulle kinders van 'n nuwe nodus ('n nuutgeskepte nodus sonder 'n letter). Die frekwensie van die nuwe nodus is gelyk aan die som van die frekwensies van die twee afstammelinge bome.
- Vir hierdie nodus, skep 'n boom wat by hierdie nodus gewortel is. Plaas hierdie boom terug in die prioriteitsry. (Aangesien die boom 'n nuwe frekwensie het, sal dit heel waarskynlik 'n nuwe plek in die tou betree)
- Gaan voort met stappe 1 en 2 totdat een boom in die tou oor is - die Huffman-boom
Oorweeg hierdie algoritme op reël s1:
Hier dui die simbool "lf" (lynaanvoer) 'n nuwe lyn aan, "sp" (spasie) is 'n spasie.
Wat is volgende?
Ons het die Huffman-boom gekry. OK. En wat om daarmee te doen? Hulle sal dit nie gratis neem nie. En dan moet jy alle moontlike paaie van die wortel tot by die blare van die boom naspoor. Ons stem in om 'n rand 0 te benoem as dit na die linker kind lei en 1 as dit na die regter een lei. Streng gesproke, in hierdie notasies, is die karakterkode die pad vanaf die wortel van die boom na die blaar wat dieselfde karakter bevat.
So het die tabel van kodes uitgedraai. Let daarop dat as ons hierdie tabel oorweeg, ons kan aflei oor die "gewig" van elke karakter - dit is die lengte van sy kode. Dan, in saamgeperste vorm, sal die bronlêer weeg: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bisse . Aanvanklik het dit 176 stukkies geweeg. Daarom het ons dit met soveel as 176/65 = 2.7 keer verminder! Maar dit is 'n utopie. So 'n verhouding sal waarskynlik nie verkry word nie. Hoekom? Dit sal 'n bietjie later bespreek word.
Dekodering
Wel, miskien is die eenvoudigste ding wat oorbly dekodering. Ek dink baie van julle het geraai dat dit onmoontlik is om bloot 'n saamgeperste lêer te skep sonder enige wenke oor hoe dit geënkodeer is - ons sal dit nie kan dekodeer nie! Ja, ja, dit was vir my moeilik om dit te besef, maar ek moet 'n tekslêer table.txt skep met 'n kompressietabel:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Tabelinskrywing in die vorm 'karakter'"karakterkode". Hoekom is 01110 sonder 'n simbool? Trouens, dit is met 'n simbool, net die java-nutsgoed wat ek gebruik wanneer ek na 'n lêer uitvoer, die nuwelynkarakter - 'n' - word omgeskakel na 'n nuwelyn (maak nie saak hoe dom dit klink nie). Daarom is die leë reël hierbo die karakter vir kode 01110. Vir kode 00 is die karakter 'n spasie aan die begin van die reël. Ek moet dadelik sê dat hierdie metode om die tafel te stoor kan beweer dat dit die mees irrasionele vir ons Khan-koëffisiënt is. Maar dit is maklik om te verstaan en te implementeer. Ek sal bly wees om jou aanbevelings in die kommentaar oor optimalisering te hoor.
Met hierdie tabel is dit baie maklik om te dekodeer. Kom ons onthou deur watter reël ons gelei is toe ons die enkodering geskep het:
Geen kode moet 'n voorvoegsel van 'n ander wees nie
Dit is hier waar dit 'n fasiliterende rol speel. Ons lees bietjie vir bietjie opeenvolgend, en sodra die resulterende string d, bestaande uit die lees stukkies, ooreenstem met die enkodering wat ooreenstem met die karakter karakter, weet ons dadelik dat die karakter karakter (en net dit!) geënkodeer is. Vervolgens skryf ons karakter na die dekodeerstring (die string wat die gedekodeerde boodskap bevat), stel die d-string terug en lees die geënkodeerde lêer verder.
Implementering
Dit is tyd om my kode te verneder deur 'n argiefhouer te skryf. Kom ons noem dit Kompressor.
Oorbegin. Eerstens skryf ons die Node-klas:
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;
}
}
Nou die boom:
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;
}
}
Prioriteitsry:
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 klas wat die Huffman-boom skep:
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 klas wat bevat wat enkodeer/dekodeer:
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("========================================================");
}
}
'n Klas wat die skryf van 'n lêer vergemaklik:
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();
}
}
'n Klas wat die lees van 'n lêer vergemaklik:
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();
}
}
Wel, en die hoofklas:
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());
}
}
Jy sal self die lêer met readme.txt-instruksies moet skryf 🙂
Gevolgtrekking
Ek dink dit is al wat ek wou sê. As jy iets te sê het oor my onbevoegdheid van verbeterings in die kode, algoritme, in die algemeen, enige optimalisering, skryf dan gerus. As ek iets nie verduidelik het nie, skryf asseblief ook. Ek hoor graag van jou in die kommentaar!
PS
Ja, ja, ek is nog hier, want ek het nie van die koëffisiënt vergeet nie. Vir die string s1 weeg die enkoderingstabel 48 grepe - baie meer as die oorspronklike lêer, en hulle het nie van die ekstra nulle vergeet nie (die aantal bygevoegde nulle is 7) => die kompressieverhouding sal minder as een wees: 176 /(65 + 48*8 + 7) = 0.38. As jy dit ook opgemerk het, dan is jy net nie in die gesig klaar nie. Ja, hierdie implementering sal uiters ondoeltreffend wees vir klein lêers. Maar wat gebeur met groot lêers? Die lêergroottes is baie groter as die enkoderingtabelgrootte. Dit is waar die algoritme werk soos dit moet! Byvoorbeeld, vir die argiefhouer gee 'n werklike (nie geïdealiseerde) koëffisiënt gelyk aan 1.46 - amper een en 'n half keer! En ja, die lêer was veronderstel om in Engels te wees.
Bron: will.com