ورود
در این مقاله در مورد الگوریتم معروف هافمن و همچنین کاربرد آن در فشرده سازی اطلاعات صحبت خواهم کرد.
در نتیجه، یک بایگانی کننده ساده خواهیم نوشت. این قبلا بوده است ، اما بدون اجرای عملی. مطالب نظری پست حاضر برگرفته از درس علوم کامپیوتر مدرسه و کتاب رابرت لافورت "ساختارها و الگوریتم های داده در جاوا" است. بنابراین، همه چیز زیر برش است!
کمی تامل
در یک فایل متنی معمولی، یک کاراکتر با 8 بیت (رمزگذاری ASCII) یا 16 (رمزگذاری یونیکد) کدگذاری می شود. در مرحله بعد، رمزگذاری ASCII را در نظر خواهیم گرفت. به عنوان مثال، رشته s1 = "SUSIE SAYS IT IS EASYn" را در نظر بگیرید. در مجموع، 22 کاراکتر در خط وجود دارد، البته شامل فاصله ها و کاراکتر خط جدید - 'n'. فایل حاوی این خط 22*8 = 176 بیت وزن خواهد داشت. بلافاصله این سؤال مطرح می شود: آیا استفاده از هر 8 بیت برای رمزگذاری 1 کاراکتر منطقی است؟ ما از همه کاراکترهای ASCII استفاده نمی کنیم. حتی اگر آنها بودند، منطقی‌تر بود که بیشترین حرف را - S - کوتاه‌ترین کد ممکن، و برای کمیاب‌ترین حرف - T (یا U، یا 'n') - کد را معتبرتر بدهید. این الگوریتم هافمن است: شما باید بهترین گزینه رمزگذاری را پیدا کنید که در آن فایل دارای حداقل وزن باشد. کاملاً طبیعی است که کاراکترهای مختلف طول کد متفاوتی داشته باشند - این اساس الگوریتم است.
برنامه نویسی
چرا به کاراکتر 'S' یک کد نمی دهیم، به عنوان مثال، 1 بیت طولانی: 0 یا 1. بگذارید 1 باشد. سپس دومین کاراکتر متداول - ' ' (فضا) - ما 0 را می دهیم. تصور کنید، شما شروع به پیام خود را رمزگشایی کنید - رشته رمزگذاری شده s1 - و می بینید که کد با 1 شروع می شود. بنابراین، چه باید کرد: آیا کاراکتر S است یا کاراکتر دیگری مانند A؟ بنابراین، یک قانون مهم مطرح می شود:
هیچ کدی نباید پیشوند دیگری باشد
این قانون کلید الگوریتم است. بنابراین، ایجاد کد با یک جدول فرکانس شروع می شود که نشان دهنده فراوانی (تعداد وقوع) هر نماد است:
کاراکترهایی که بیشترین تکرار را دارند باید با کمترین کدگذاری شوند ممکن تعداد بیت ها من مثالی از یکی از جداول کد ممکن می زنم:
بنابراین پیام کدگذاری شده به شکل زیر خواهد بود:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
کد هر کاراکتر را با فاصله جدا کردم. این واقعا در یک فایل فشرده اتفاق نمی افتد!
این سوال پیش می‌آید: چگونه این تازه‌کار کدی برای ایجاد جدول کد ایجاد کرد؟ در ادامه به این موضوع پرداخته خواهد شد.
ساختن درخت هافمن
اینجاست که درختان جستجوی دودویی به کمک می آیند. نگران نباشید، در اینجا به روش های جستجو، درج و حذف نیازی نخواهید داشت. در اینجا ساختار درختی در جاوا آمده است:
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;
}
...
}
این کد کامل نیست، کد کامل در زیر خواهد بود.
الگوریتم ساخت درخت در اینجا آمده است:
- برای هر کاراکتر از پیام یک شی Node ایجاد کنید (خط s1). در مورد ما، 9 گره (اشیاء Node) وجود خواهد داشت. هر گره از دو فیلد داده تشکیل شده است: نماد و فرکانس
- یک شی Tree (BinaryTree) برای هر یک از گره های Node ایجاد کنید. گره به ریشه درخت تبدیل می شود.
- این درخت ها را در صف اولویت قرار دهید. هرچه فرکانس کمتر باشد، اولویت بیشتر است. بنابراین، هنگام استخراج، درختی با کمترین فرکانس همیشه انتخاب می شود.
در مرحله بعد، باید به صورت چرخه ای موارد زیر را انجام دهید:
- دو درخت را از صف اولویت بازیابی کنید و آنها را فرزندان یک گره جدید (گره تازه ایجاد شده بدون حرف) کنید. فرکانس گره جدید برابر است با مجموع فرکانس های دو درخت زاده.
- برای این گره، یک درخت با ریشه در این گره ایجاد کنید. این درخت را دوباره در صف اولویت قرار دهید. (از آنجایی که درخت فرکانس جدیدی دارد، به احتمال زیاد در یک مکان جدید در صف قرار می گیرد)
- مراحل 1 و 2 را ادامه دهید تا یک درخت در صف باقی بماند - درخت هافمن
این الگوریتم را در خط s1 در نظر بگیرید:
در اینجا نماد "lf" (linefeed) یک خط جدید را نشان می دهد، "sp" (فضا) یک فاصله است.
و بعد چه؟
درخت هافمن را گرفتیم. خوب. و با آن چه باید کرد؟ آنها آن را رایگان نخواهند گرفت و سپس، شما باید تمام مسیرهای ممکن را از ریشه تا برگ درخت ردیابی کنید. ما موافقت می کنیم که یک یال را در صورتی که به سمت چپ منتهی شود، 0 و اگر به سمت راست منتهی شود، 1 بگذاریم. به بیان دقیق، در این نمادها، کد کاراکتر مسیری از ریشه درخت تا برگ حاوی همین کاراکتر است.
بنابراین، جدول کدها معلوم شد. توجه داشته باشید که اگر این جدول را در نظر بگیریم، می توانیم در مورد "وزن" هر کاراکتر نتیجه گیری کنیم - این طول کد آن است. سپس، به صورت فشرده، فایل منبع وزن خواهد داشت: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 بیت . در ابتدا 176 بیت وزن داشت. بنابراین، ما آن را به اندازه 176/65 = 2.7 برابر کاهش دادیم! اما این یک مدینه فاضله است. چنین نسبتی بعید است به دست آید. چرا؟ در این مورد کمی بعد بحث خواهد شد.
رمزگشایی
خب، شاید ساده ترین چیز باقی مانده رمزگشایی باشد. من فکر می کنم بسیاری از شما حدس زده اید که ایجاد یک فایل فشرده بدون هیچ اشاره ای در مورد نحوه کدگذاری آن غیرممکن است - ما قادر به رمزگشایی آن نخواهیم بود! بله، بله، درک این موضوع برای من سخت بود، اما باید یک فایل متنی table.txt با جدول فشرده سازی ایجاد کنم:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
ورود جدول به شکل "شخصیت" "کد کاراکتر". چرا 01110 بدون نماد است؟ در واقع، با یک نماد، فقط ابزارهای جاوا که من هنگام خروجی به یک فایل استفاده می کنم، کاراکتر خط جدید - 'n' - به خط جدید تبدیل می شود (هرچقدر هم که احمقانه به نظر برسد). بنابراین، خط خالی بالا کاراکتر کد 01110 است. برای کد 00، کاراکتر یک فاصله در ابتدای خط است. فوراً باید بگویم که این روش ذخیره جدول می تواند ادعا کند که برای ضریب خان ما غیر منطقی ترین است. اما درک و اجرای آن آسان است. خوشحال می شوم توصیه های شما را در نظرات درباره بهینه سازی بشنوم.
با این جدول رمزگشایی بسیار آسان است. بیایید به یاد بیاوریم که هنگام ایجاد رمزگذاری بر اساس چه قاعده ای هدایت شدیم:
هیچ کدی نباید پیشوند دیگری باشد
اینجاست که نقش تسهیل کننده را ایفا می کند. بیت به بیت متوالی می خوانیم و به محض اینکه رشته d حاصل از بیت های خوانده شده با رمزگذاری مربوط به کاراکتر منطبق شود، بلافاصله متوجه می شویم که کاراکتر (و فقط آن!) کدگذاری شده است. سپس، کاراکتر را در رشته رمزگشایی (رشته حاوی پیام رمزگشایی شده) می نویسیم، رشته d را بازنشانی می کنیم و فایل رمزگذاری شده را بیشتر می خوانیم.
اجرا
وقت آن رسیده است که با نوشتن یک آرشیو کد خود را تحقیر کنم. بیایید آن را کمپرسور بنامیم.
از نو شروع کن ابتدا کلاس 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;
}
}
حالا درخت:
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;
}
}
صف اولویت:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
کلاسی که درخت هافمن را ایجاد می کند:
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;
}
}
کلاسی که شامل کدگذاری/رمزگشایی می شود:
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("========================================================");
}
}
کلاسی که نوشتن در یک فایل را تسهیل می کند:
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();
}
}
کلاسی که خواندن از روی یک فایل را تسهیل می کند:
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();
}
}
خوب، و کلاس اصلی:
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());
}
}
باید خودتان فایل را با دستورالعمل readme.txt بنویسید 🙂
نتیجه
حدس می زنم این تمام چیزی است که می خواستم بگویم. اگر در مورد بی کفایتی من در بهبود کد، الگوریتم، به طور کلی، هر بهینه سازی چیزی برای گفتن دارید، در صورت تمایل بنویسید. اگر چیزی را توضیح ندادم لطفا بنویسید. من دوست دارم از شما در نظرات بشنوم!
PS
بله، بله، من هنوز اینجا هستم، زیرا ضریب را فراموش نکردم. برای رشته s1، وزن جدول رمزگذاری 48 بایت است - بسیار بیشتر از فایل اصلی، و آنها صفرهای اضافی را فراموش نکردند (تعداد صفرهای اضافه شده 7 است) => نسبت فشرده سازی کمتر از یک خواهد بود: 176 /(65 + 48*8 + 7) = 0.38. اگر شما نیز متوجه این موضوع شده اید، پس فقط در صورت شما تمام شده است. بله، این پیاده سازی برای فایل های کوچک بسیار ناکارآمد خواهد بود. اما برای فایل های حجیم چه اتفاقی می افتد؟ اندازه فایل بسیار بزرگتر از اندازه جدول رمزگذاری است. اینجاست که الگوریتم آنطور که باید کار می کند! به عنوان مثال، برای آرشیو ضریب واقعی (نه ایده آل) برابر با 1.46 - تقریباً یک و نیم بار را می دهد! و بله، قرار بود فایل به زبان انگلیسی باشد.
منبع: www.habr.com