Ieraksts
Šajā rakstā es runāšu par labi zināmo Hafmena algoritmu, kā arī tā pielietojumu datu saspiešanā.
Rezultātā mēs uzrakstīsim vienkāršu arhivētāju. Tas jau ir bijis , bet bez praktiskas īstenošanas. Pašreizējā ieraksta teorētiskais materiāls ņemts no skolas informātikas stundām un Roberta Laforeta grāmatas "Datu struktūras un algoritmi Java valodā". Tātad, viss ir zem griezuma!
Mazliet pārdomas
Parastā teksta failā viena rakstzīme ir kodēta ar 8 bitiem (ASCII kodējums) vai 16 (unikoda kodējums). Tālāk mēs apsvērsim ASCII kodējumu. Piemēram, ņemiet virkni s1 = "SUSIE SAYS IT IS EASYn". Kopumā rindā ir 22 rakstzīmes, protams, ieskaitot atstarpes un jaunrindas rakstzīmi - 'n'. Fails, kurā ir šī rinda, svērs 22 * 8 = 176 biti. Uzreiz rodas jautājums: vai ir racionāli izmantot visus 8 bitus, lai kodētu 1 rakstzīmi? Mēs neizmantojam visas ASCII rakstzīmes. Pat ja tie būtu, racionālāk būtu biežākajam burtam - S - piešķirt īsāko iespējamo kodu, bet retākajam burtam - T (vai U, vai 'n') - piešķirt kodu autentiskāku. Šis ir Hafmena algoritms: jums jāatrod vislabākā kodēšanas opcija, kurā failam būs minimāls svars. Tas ir diezgan normāli, ka dažādām rakstzīmēm būs atšķirīgs koda garums – tas ir algoritma pamatā.
Kodēšana
Kāpēc gan neiedot rakstzīmei 'S' kodu, piemēram, 1 bitu garu: 0 vai 1. Lai tas būtu 1. Tad otrajai visbiežāk sastopamajai rakstzīmei - ' ' (atstarpe) - mēs iedosim 0. Iedomājieties, jūs sākāt atšifrējiet savu ziņojumu — kodētā virkne s1 — un redzat, ka kods sākas ar 1. Tātad, ko darīt: vai tā ir rakstzīme S, vai tā ir kāda cita rakstzīme, piemēram, A? Tāpēc rodas svarīgs noteikums:
Neviens kods nedrīkst būt cita prefikss
Šis noteikums ir algoritma atslēga. Tāpēc koda izveide sākas ar biežuma tabulu, kurā norādīts katra simbola biežums (atbilstību skaits):
Rakstzīmes, kurās ir visvairāk atgadījumu, ir jākodē ar vismazāko gadījumu iespējams bitu skaits. Es sniegšu piemēru vienai no iespējamām kodu tabulām:
Tātad kodētais ziņojums izskatīsies šādi:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Katras rakstzīmes kodu atdalīju ar atstarpi. Tas tiešām nenotiks saspiestā failā!
Rodas jautājums: kā šis debitants izdomāja kodu, kā izveidot kodu tabulu? Tas tiks apspriests tālāk.
Hafmena koka būvēšana
Šeit palīgā nāk binārie meklēšanas koki. Neuztraucieties, šeit nav nepieciešamas meklēšanas, ievietošanas un dzēšanas metodes. Šeit ir koka struktūra 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;
}
...
}
Šis nav pilns kods, pilns kods būs zemāk.
Šeit ir koka veidošanas algoritms:
- Katrai ziņojuma rakstzīmei izveidojiet objektu Node (rindiņa s1). Mūsu gadījumā būs 9 mezgli (Node objekti). Katrs mezgls sastāv no diviem datu laukiem: simbola un frekvences
- Izveidojiet koka objektu (BinaryTree) katram mezgla mezglam. Mezgls kļūst par koka sakni.
- Ievietojiet šos kokus prioritārajā rindā. Jo zemāka frekvence, jo augstāka prioritāte. Tādējādi, ekstrahējot, vienmēr tiek izvēlēts koks ar zemāko frekvenci.
Tālāk jums cikliski jāveic šādas darbības:
- Izgūt divus kokus no prioritārās rindas un padarīt tos par jauna mezgla (jaunizveidota mezgla bez burta) bērniem. Jaunā mezgla frekvence ir vienāda ar divu pēcnācēju koku frekvenču summu.
- Šim mezglam izveidojiet koku, kas sakņojas šajā mezglā. Ievietojiet šo koku atpakaļ prioritārajā rindā. (Tā kā kokam ir jauna frekvence, visticamāk, tas nonāks jaunā vietā rindā)
- Turpiniet 1. un 2. darbību, līdz rindā paliek viens koks — Hafmena koks
Apsveriet šo algoritmu rindā s1:
Šeit simbols "lf" (rindas plūsma) apzīmē jaunu rindiņu, bet "sp" (atstarpe) ir atstarpe.
Un tad?
Mēs ieguvām Huffman koku. LABI. Un ko ar to darīt? Viņi to neņems par velti. Un tad jums ir jāizseko visi iespējamie ceļi no koka saknēm līdz lapām. Mēs piekrītam apzīmēt malu ar 0, ja tā ved uz kreiso bērnu, un 1, ja tā ved uz labo. Stingri runājot, šajos apzīmējumos rakstzīmju kods ir ceļš no koka saknes līdz lapai, kurā ir šī pati rakstzīme.
Tādējādi kodu tabula izrādījās. Ņemiet vērā, ka, ņemot vērā šo tabulu, mēs varam secināt par katras rakstzīmes "svaru" - tas ir tā koda garums. Pēc tam saspiestā formā avota fails sver: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 biti . Sākumā tas svēra 176 bitus. Tāpēc mēs to samazinājām pat 176/65 = 2.7 reizes! Bet tā ir utopija. Šāda attiecība, visticamāk, netiks iegūta. Kāpēc? Tas tiks apspriests nedaudz vēlāk.
Dekodēšana
Varbūt visvienkāršākā lieta ir atšifrēt. Es domāju, ka daudzi no jums ir uzminējuši, ka nav iespējams vienkārši izveidot saspiestu failu bez mājieniem par to, kā tas tika kodēts - mēs to nevarēsim atšifrēt! Jā, jā, man bija grūti to saprast, bet man ir jāizveido teksta fails table.txt ar saspiešanas tabulu:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Tabulas ieraksts formā 'rakstzīme'"rakstzīmju kods". Kāpēc 01110 ir bez simbola? Patiesībā tas ir ar rakstzīmi, tikai ar java rīkiem, ko izmantoju, izvadot failu, jaunās rindas rakstzīme - "n" - tiek pārveidota par jaunu rindiņu (lai cik stulbi tas izklausītos). Tāpēc tukšā rinda augšpusē ir koda 01110 rakstzīme. Kodam 00 rakstzīme ir atstarpe rindas sākumā. Uzreiz jāsaka, ka šī tabulas glabāšanas metode var pretendēt uz mūsu khan koeficienta visneracionālāko. Bet to ir viegli saprast un īstenot. Priecāšos dzirdēt jūsu ieteikumus komentāros par optimizāciju.
Izmantojot šo tabulu, to ir ļoti viegli atšifrēt. Atcerēsimies, pēc kāda noteikuma vadījāmies, veidojot kodējumu:
Neviens kods nedrīkst būt cita prefikss
Šeit tai ir veicinoša loma. Mēs lasām bitu pa bitam secīgi, un, tiklīdz iegūtā virkne d, kas sastāv no nolasītajiem bitiem, sakrīt ar kodējumu, kas atbilst rakstzīmes rakstzīmei, mēs uzreiz zinām, ka rakstzīmes rakstzīme (un tikai tā!) ir kodēta. Pēc tam mēs ierakstām rakstzīmi dekodēšanas virknē (virknē, kurā ir dekodēts ziņojums), atiestatām d virkni un tālāk lasām kodēto failu.
Ieviešana
Ir pienācis laiks pazemot manu kodu, rakstot arhivētāju. Sauksim to par kompresoru.
Sāciet no jauna. Pirmkārt, mēs rakstām Node klasi:
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;
}
}
Tagad koks:
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;
}
}
Prioritārā rinda:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Klase, kas izveido Hafmena koku:
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;
}
}
Klase, kas kodē/dekodē:
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("========================================================");
}
}
Klase, kas atvieglo rakstīšanu 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();
}
}
Klase, kas atvieglo lasīšanu no faila:
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 un galvenā klase:
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());
}
}
Fails ar readme.txt instrukcijām būs jāraksta pašam 🙂
Secinājums
Laikam tas ir viss, ko gribēju pateikt. Ja jums ir kas sakāms par manu neprasmi uzlabot kodu, algoritmu, vispār, jebkādu optimizāciju, tad droši rakstiet. Ja kaut ko neesmu paskaidrojis, lūdzu arī uzrakstiet. Es labprāt dzirdētu no jums komentāros!
PS
Jā, jā, es joprojām esmu šeit, jo neesmu aizmirsis par koeficientu. Virknei s1 kodēšanas tabula sver 48 baitus - daudz vairāk nekā sākotnējais fails, un viņi neaizmirsa par papildu nullēm (pievienoto nulles skaits ir 7) => saspiešanas pakāpe būs mazāka par vienu: 176 /(65 + 48*8 + 7) = 0.38. Ja arī jūs to pamanījāt, tad tikai ne pa seju esat pabeidzis. Jā, šī ieviešana būs ārkārtīgi neefektīva maziem failiem. Bet kas notiek ar lieliem failiem? Failu izmēri ir daudz lielāki nekā kodēšanas tabulas izmēri. Lūk, kur algoritms darbojas kā nākas! Piemēram, priekš arhivators dod reālu (neidealizētu) koeficientu, kas vienāds ar 1.46 - gandrīz pusotru reizi! Un jā, failam bija jābūt angļu valodā.
Avots: www.habr.com