eniro
En ĉi tiu artikolo, mi parolos pri la konata Huffman-algoritmo, kaj ankaŭ pri ĝia apliko en datuma kunpremo.
Kiel rezulto, ni skribos simplan arkiviston. Ĉi tio jam estis , sed sen praktika efektivigo. La teoria materialo de la nuna afiŝo estas prenita el lernejaj komputikaj lecionoj kaj la libro de Robert Laforet "Data Structures and Algorithms in Java". Do, ĉio estas sub la tranĉo!
Eta pripenso
En normala tekstdosiero, unu signo estas ĉifrita per 8 bitoj (ASCII-kodigo) aŭ 16 (Unikoda kodado). Poste, ni konsideros la ASCII-kodigon. Ekzemple, prenu la ĉenon s1 = "SUSIE Diras, ke ĜI ESTAS FACILEn". Entute, estas 22 signoj en la linio, kompreneble, inkluzive de spacoj kaj la novlinia signo - 'n'. La dosiero enhavanta ĉi tiun linion pezos 22*8 = 176 bitoj. Tuj aperas la demando: ĉu estas racie uzi ĉiujn 8 bitojn por kodi 1 signon? Ni ne uzas ĉiujn ASCII-signojn. Eĉ se ili estus, pli racie estus doni la plej oftan literon - S - la plej mallongan ebla kodon, kaj por la plej malofta litero - T (aŭ U, aŭ 'n') - doni la kodon pli aŭtentika. Ĉi tiu estas la Huffman-algoritmo: vi devas trovi la plej bonan kodan opcion, en kiu la dosiero havos minimuman pezon. Estas tute normale, ke malsamaj signoj havos malsamajn kodlongojn - ĉi tio estas la bazo de la algoritmo.
Kodigo
Kial ne doni al la signo 'S' kodon, ekzemple, 1 biton longa: 0 aŭ 1. Ĝi estu 1. Tiam la dua plej aperanta signo - ' ' (spaco) - ni donos 0. Imagu, vi komencis malkodi vian mesaĝon - kodita ĉeno s1 - kaj vi vidas ke la kodo komenciĝas per 1. Do, kion fari: ĉu ĝi estas la signo S, aŭ ĉu ĝi estas iu alia signo, kiel A? Tial, grava regulo ekestas:
Neniu kodo devas esti prefikso de alia
Ĉi tiu regulo estas la ŝlosilo al la algoritmo. Tial, la kreado de la kodo komenciĝas per frekvenca tabelo, kiu indikas la frekvencon (nombro da okazoj) de ĉiu simbolo:
La signoj kun la plej multaj okazoj estu koditaj kun la plej malmultaj ebla la nombro da bitoj. Mi donos ekzemplon de unu el la eblaj kodaj tabeloj:
Do la kodita mesaĝo aspektos jene:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Mi apartigis la kodon de ĉiu signo per spaco. Ĉi tio ne vere okazos en kunpremita dosiero!
La demando ŝprucas: kiel ĉi tiu novulo elpensis kodon kiel krei kodtabelon? Ĉi tio estos diskutita sube.
Konstruante Huffman Arbon
Ĉi tie estas kie binaraj serĉarboj venas al la savo. Ne maltrankviliĝu, vi ne bezonos la serĉajn, enmeti kaj forigi metodojn ĉi tie. Jen la arbstrukturo en 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;
}
...
}
Ĉi tio ne estas la kompleta kodo, la plena kodo estos sube.
Jen la algoritmo por konstrui arbon:
- Kreu Node-objekton por ĉiu signo el la mesaĝo (linio s1). En nia kazo, estos 9 nodoj (Nodaj objektoj). Ĉiu nodo konsistas el du datumkampoj: simbolo kaj frekvenco
- Kreu Arbobjekton (BinaryTree) por ĉiu el la Nodaj nodoj. La nodo fariĝas la radiko de la arbo.
- Enmetu ĉi tiujn arbojn en la prioritatvicon. Ju pli malalta la ofteco, des pli alta la prioritato. Tiel, ĉe eltiro, la arbo kun la plej malalta frekvenco ĉiam estas elektita.
Poste, vi devas cikle fari la jenon:
- Prenu du arbojn el la prioritata atendovico kaj faru ilin infanoj de nova nodo (novkreita nodo sen letero). La frekvenco de la nova nodo estas egala al la sumo de la frekvencoj de la du postaj arboj.
- Por ĉi tiu nodo, kreu arbon radikita ĉe ĉi tiu nodo. Enmetu ĉi tiun arbon reen en la prioritatvicon. (Ĉar la arbo havas novan frekvencon, ĝi plej verŝajne eniros novan lokon en la atendovico)
- Daŭrigu paŝojn 1 kaj 2 ĝis unu arbo restas en la atendovico - la Huffman-arbo
Konsideru ĉi tiun algoritmon sur linio s1:
Ĉi tie la simbolo "lf" (liniopaŝo) indikas novan linion, "sp" (spaco) estas spaco.
Kio sekvas?
Ni ricevis la Huffman-arbon. BONE. Kaj kion fari kun ĝi? Ili ne prenos ĝin senpage.Kaj poste, vi devas spuri ĉiujn eblajn vojojn de la radiko ĝis la folioj de la arbo. Ni konsentas etikedi laĝon 0 se ĝi kondukas al la maldekstra infano kaj 1 se ĝi kondukas al la dekstra. Strikte parolante, en ĉi tiuj notacioj, la signokodo estas la vojo de la radiko de la arbo ĝis la folio enhavanta ĉi tiun karakteron.
Tiel, la tabelo de kodoj rezultis. Notu, ke se ni konsideras ĉi tiun tabelon, ni povas konkludi pri la "pezo" de ĉiu signo - ĉi tiu estas la longo de ĝia kodo. Tiam, en kunpremita formo, la fontdosiero pezos: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bitoj . Komence ĝi pezis 176 bitojn. Tial ni reduktis ĝin je 176/65 = 2.7 fojojn! Sed ĉi tio estas utopio. Tia proporcio verŝajne ne estos akirita. Kial? Ĉi tio estos diskutita iom poste.
Malkodado
Nu, eble la plej simpla afero restanta estas malkodado. Mi pensas, ke multaj el vi divenis, ke estas neeble simple krei kunpremitan dosieron sen ajnaj sugestoj pri kiel ĝi estis kodita - ni ne povos malkodi ĝin! Jes, jes, estis malfacile por mi konstati tion, sed mi devas krei tekstdosieron table.txt kun kunprema tabelo:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Tabeleniro en la formo 'karaktero'"signo-kodo". Kial 01110 estas sen simbolo? Fakte, ĝi estas kun simbolo, nur la java-iloj, kiujn mi uzas dum eligo al dosiero, la novlinia signo - 'n' - estas konvertita al novlinio (ne gravas kiom stulte ĝi sonas). Tial, la malplena linio supre estas la signo por kodo 01110. Por kodo 00, la signo estas spaco ĉe la komenco de la linio. Mi devas tuj diri, ke ĉi tiu metodo de stokado de la tablo povas pretendi esti la plej neracia por nia ĥan-koeficiento. Sed ĝi estas facile kompreni kaj efektivigi. Mi ĝojos aŭdi viajn rekomendojn en la komentoj pri optimumigo.
Kun ĉi tiu tablo, ĝi estas tre facile malkodi. Ni memoru per kiu regulo ni estis gviditaj dum kreado de la kodado:
Neniu kodo devas esti prefikso de alia
Ĉi tie ĝi ludas faciligan rolon. Ni legas iom post iom sinsekve, kaj tuj kiam la rezulta ĉeno d, konsistanta el la legitaj bitoj, kongruas kun la kodigo responda al la signokaraktero, ni tuj scias, ke la signa signo (kaj nur ĝi!) estis kodita. Poste, ni skribas karakteron al la malkodita ĉeno (la ĉeno enhavanta la deĉifritan mesaĝon), restarigas la d-ĉenon kaj legas la ĉifritan dosieron plu.
Реализация
Estas tempo humiligi mian kodon skribante arkiviston. Ni nomu ĝin Kompresoro.
Komencu denove. Unue ni skribas la klason 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;
}
}
Nun la arbo:
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;
}
}
Prioratvico:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
La klaso kiu kreas la Huffman-arbon:
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;
}
}
La klaso enhavanta kiu kodas/malkodas:
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("========================================================");
}
}
Klaso kiu faciligas skribon al dosiero:
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();
}
}
Klaso kiu faciligas legadon de dosiero:
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();
}
}
Nu, kaj la ĉefa klaso:
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());
}
}
Vi devos mem skribi la dosieron kun readme.txt instrukcioj 🙂
konkludo
Mi supozas, ke tio estas ĉio, kion mi volis diri. Se vi havas ion por diri pri mia nekompetenteco de plibonigoj en la kodo, algoritmo, ĝenerale, ajna optimumigo, tiam bonvolu skribi. Se mi ne klarigis ion, bonvolu ankaŭ skribi. Mi ŝatus aŭdi de vi en la komentoj!
PS
Jes, jes, mi estas ankoraŭ ĉi tie, ĉar mi ne forgesis pri la koeficiento. Por la ĉeno s1, la kodotabelo pezas 48 bajtojn - multe pli ol la originala dosiero, kaj ili ne forgesis pri la kromaj nuloj (la nombro de aldonitaj nuloj estas 7) => la kunprema proporcio estos malpli ol unu: 176 /(65 + 48*8 + 7) = 0.38. Se vi ankaŭ rimarkis ĉi tion, tiam simple ne en la vizaĝo vi estas finita. Jes, ĉi tiu efektivigo estos ekstreme malefika por malgrandaj dosieroj. Sed kio okazas al grandaj dosieroj? La dosiergrandoj estas multe pli grandaj ol la grandeco de kodotabelo. Jen kie la algoritmo funkcias kiel ĝi devus! Ekzemple, por la arkivisto donas realan (ne idealigitan) koeficienton egalan al 1.46 - preskaŭ unufoje kaj duonon! Kaj jes, la dosiero devis esti en la angla.
fonto: www.habr.com