Entry
Katika makala hii nitazungumzia kuhusu algorithm maarufu ya Huffman, pamoja na matumizi yake katika ukandamizaji wa data.
Matokeo yake, tutaandika archiver rahisi. Hili tayari limejadiliwa , lakini bila utekelezaji wa vitendo. Nyenzo za kinadharia za chapisho la sasa zinachukuliwa kutoka kwa masomo ya sayansi ya kompyuta ya shule na kitabu cha Robert Laforet "Miundo ya Data na Algorithms katika Java". Kwa hiyo, kila kitu kinakatwa!
Mawazo machache
Katika faili ya maandishi ya kawaida, herufi moja imesimbwa na bits 8 (encoding ASCII) au 16 (encoding Unicode). Ifuatayo tutazingatia usimbuaji wa ASCII. Kwa mfano, chukua mstari s1 = "SUSIE ANASEMA NI RAHISI". Kuna jumla ya herufi 22 kwenye mstari, kwa kawaida, ikijumuisha nafasi na herufi mpya ya mstari - 'n'. Faili iliyo na mstari huu itakuwa na uzito wa 22 * 8 = 176 bits. Swali linatokea mara moja: ni busara kutumia bits zote 8 kusimba herufi 1? Hatutumii herufi zote za ASCII. Hata kama wangefanya hivyo, ingekuwa busara zaidi kwa herufi ya kawaida - S - kupewa msimbo mfupi iwezekanavyo, na kwa herufi adimu - T (au U, au 'n') - kupewa nambari ndefu zaidi. Hivi ndivyo algorithm ya Huffman inajumuisha: ni muhimu kupata chaguo mojawapo ya encoding ambayo faili itakuwa na uzito wa chini. Ni kawaida kabisa kwamba urefu wa nambari utatofautiana kwa alama tofauti - hii ndio msingi wa algorithm.
Kuweka msimbo
Kwa nini usimpe herufi 'S' msimbo, kwa mfano, urefu wa biti 1: 0 au 1. Hebu iwe 1. Kisha herufi ya pili inayojulikana zaidi - ' ' (nafasi) - toa 0. Fikiri umeanza kusimbua ujumbe wako - kamba iliyosimbwa s1 - na unaona kwamba msimbo unaanza na 1. Kwa hiyo, unafanya nini: hii ni tabia S, au ni tabia nyingine, kwa mfano A? Kwa hivyo, sheria muhimu inatokea:
Msimbo wowote haufai kuwa kiambishi awali cha mwingine
Sheria hii ni muhimu katika algorithm. Kwa hivyo, kuunda nambari huanza na jedwali la masafa, ambayo inaonyesha mzunguko (idadi ya matukio) ya kila ishara:
Herufi zilizo na matukio mengi zinapaswa kusimba kwa uchache inawezekana idadi ya bits. Nitatoa mfano wa moja ya jedwali za nambari zinazowezekana:
Kwa hivyo ujumbe uliosimbwa utaonekana kama hii:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Nilitenganisha nambari ya kila mhusika na nafasi. Hili halitafanyika katika faili iliyobanwa kweli!
Swali linatokea: kijana huyu mdogo alikujaje na kanuni ya kuunda jedwali la kanuni? Hii itajadiliwa hapa chini.
Kujenga mti wa Huffman
Hapa ndipo miti ya utafutaji ya binary huja kuwaokoa. Usijali, hutahitaji kutafuta, kuingiza, au kufuta mbinu hapa. Hapa kuna muundo wa mti katika 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;
}
...
}
Huu sio msimbo kamili, msimbo kamili utakuwa hapa chini.
Hapa kuna algorithm ya kuunda mti:
- Unda kitu cha Node kwa kila herufi kutoka kwa ujumbe (mstari s1). Kwa upande wetu kutakuwa na nodi 9 (Vitu vya Node). Kila nodi ina sehemu mbili za data: ishara na frequency
- Unda kitu cha Mti (BinaryTree) kwa kila Nodi. Node inakuwa mzizi wa mti.
- Ingiza miti hii kwenye foleni ya kipaumbele. Kiwango cha chini cha mzunguko, kipaumbele cha juu. Kwa hivyo, wakati wa kuchimba, dervo iliyo na mzunguko wa chini huchaguliwa kila wakati.
Ifuatayo unahitaji kufanya yafuatayo kwa mzunguko:
- Ondoa miti miwili kutoka kwenye foleni ya kipaumbele na uwafanye watoto wa nodi mpya (nodi mpya iliyoundwa bila barua). Mzunguko wa nodi mpya ni sawa na jumla ya masafa ya miti miwili ya uzao.
- Kwa nodi hii, tengeneza mti na mzizi kwenye nodi hii. Ingiza mti huu tena kwenye foleni ya kipaumbele. (Kwa kuwa mti una masafa mapya, uwezekano mkubwa utaonekana katika sehemu mpya kwenye foleni)
- Endelea hatua ya 1 na 2 hadi kuwe na mti mmoja tu kwenye foleni - mti wa Huffman
Fikiria algorithm hii kwenye mstari s1:
Hapa ishara "lf" (linefeed) ina maana ya mstari mpya, "sp" (nafasi) ni nafasi.
Nini kinafuata?
Tuna mti wa Huffman. SAWA. Na nini cha kufanya nayo? Hawatachukua hata bure.Na kisha, unahitaji kufuatilia njia zote zinazowezekana kutoka kwenye mizizi hadi majani ya mti. Wacha tukubaliane kuashiria makali 0 ikiwa inaongoza kwa mtoto wa kushoto na 1 ikiwa inaongoza kwa moja ya kulia. Kwa kweli, katika nukuu hii, msimbo wa ishara ni njia kutoka kwa mzizi wa mti hadi kwenye jani iliyo na ishara hii.
Hivi ndivyo jedwali la misimbo lilivyotokea. Kumbuka kwamba ikiwa tutazingatia jedwali hili, tunaweza kuhitimisha juu ya "uzito" wa kila ishara - huu ndio urefu wa nambari yake. Kisha, katika fomu iliyoshinikwa, faili ya asili itakuwa na uzito: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = bits 65 . Mwanzoni ilikuwa na uzito wa biti 176. Kwa hiyo, tuliipunguza kwa kiasi cha 176/65 = mara 2.7! Lakini hii ni utopia. Mgawo huo hauwezekani kupatikana. Kwa nini? Hili litajadiliwa baadaye kidogo.
Kusimbua
Kweli, labda jambo rahisi zaidi lililobaki ni kusimbua. Nadhani wengi wenu mmekisia kuwa hatuwezi kuunda faili iliyobanwa tu bila kidokezo chochote cha jinsi ilivyosimbwa - hatutaweza kuisimbua! Ndiyo, ndiyo, ilikuwa vigumu kwangu kutambua hili, lakini nitalazimika kuunda faili ya maandishi table.txt na jedwali la kubana:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Ingizo la jedwali katika fomu ya 'ishara' 'msimbo wa herufi'. Kwa nini 01110 bila ishara? Kwa kweli, iko na ishara, ni kwamba tu zana za java ninazotumia wakati wa kutoa faili, herufi mpya - 'n' - inabadilishwa kuwa laini mpya (haijalishi inaweza kuonekana kuwa ya kijinga). Kwa hiyo, mstari tupu juu ni tabia ya msimbo 01110. Kwa kanuni 00, tabia ni nafasi mwanzoni mwa mstari. Nitasema mara moja kwamba kwa mgawo wetu wa Khan, njia hii ya kuhifadhi meza inaweza kudai kuwa isiyo na maana zaidi. Lakini ni rahisi kuelewa na kutekeleza. Nitafurahi kusikia mapendekezo yako katika maoni kuhusu uboreshaji.
Kuwa na jedwali hili hurahisisha sana kusimbua. Wacha tukumbuke ni sheria gani tulifuata wakati wa kuunda usimbuaji:
Msimbo wowote haufai kuwa kiambishi awali cha mwingine
Hapa ndipo inapocheza jukumu la kuwezesha. Tunasoma sequentially kidogo na kidogo na, mara tu kamba inayotokana d, inayojumuisha bits zilizosomwa, inafanana na encoding inayofanana na tabia ya tabia, tunajua mara moja kwamba tabia ya tabia (na tu!) ilikuwa encoded. Ifuatayo, tunaandika tabia kwenye mstari wa decoding (mstari ulio na ujumbe uliopangwa), upya upya mstari d, na kisha usome faili iliyosimbwa.
Utekelezaji
Ni wakati wa kudhalilisha nambari yangu na kuandika kumbukumbu. Hebu tuite Compressor.
Anza tena. Kwanza kabisa, tunaandika darasa la 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;
}
}
Sasa mti:
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;
}
}
Foleni ya Kipaumbele:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Darasa ambalo huunda mti wa 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;
}
}
Darasa lililo na ambayo husimba/kusimbua:
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("========================================================");
}
}
Darasa ambalo hurahisisha kuandika kwa faili:
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();
}
}
Darasa ambalo hurahisisha kusoma kutoka kwa faili:
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();
}
}
Kweli, na darasa kuu:
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());
}
}
Utalazimika kuandika faili ya readme.txt mwenyewe :)
Hitimisho
Nadhani hiyo ndiyo yote nilitaka kusema. Ikiwa una chochote cha kusema kuhusu uzembe wangu katika kuboresha msimbo, algoriti, au uboreshaji wowote kwa ujumla, basi jisikie huru kuandika. Ikiwa sijaelezea chochote, tafadhali andika pia. Ningependa kusikia kutoka kwako kwenye maoni!
PS
Ndiyo, ndiyo, bado niko hapa, kwa sababu sikusahau kuhusu mgawo. Kwa kamba s1, jedwali la usimbaji lina uzito wa byte 48 - kubwa zaidi kuliko faili ya chanzo, na hatukusahau kuhusu sufuri za ziada (idadi ya zero zilizoongezwa ni 7) => uwiano wa compression utakuwa chini ya moja: 176/ (65 + 48*8 + 7) = 0.38. Ikiwa pia umeona hili, basi sio tu uso wako ni mzuri. Ndio, utekelezaji huu hautafaa sana kwa faili ndogo. Lakini nini kinatokea kwa faili kubwa? Ukubwa wa faili ni kubwa zaidi kuliko ukubwa wa jedwali la usimbaji. Hapa ndipo algorithm inafanya kazi kama inavyopaswa! Kwa mfano, kwa Jalada hutoa mgawo halisi (sio bora) wa 1.46 - karibu mara moja na nusu! Na ndio, faili ilipaswa kuwa kwa Kiingereza.
Chanzo: mapenzi.com