Pagpasok
Sa artikulong ito ay magsasalita ako tungkol sa sikat na Huffman algorithm, pati na rin ang aplikasyon nito sa data compression.
Bilang resulta, magsusulat kami ng isang simpleng archiver. Napag-usapan na ito , ngunit walang praktikal na pagpapatupad. Ang teoretikal na materyal ng kasalukuyang post ay kinuha mula sa mga aralin sa computer science sa paaralan at sa aklat ni Robert Laforet na "Data Structures and Algorithms in Java". Kaya, lahat ay pinutol!
Ilang mga pag-iisip
Sa isang regular na text file, ang isang character ay naka-encode na may 8 bits (ASCII encoding) o 16 (Unicode encoding). Susunod na isasaalang-alang namin ang pag-encode ng ASCII. Halimbawa, kunin ang linyang s1 = “SABI NI SUSIE NA MADALI N”. Mayroong kabuuang 22 character sa linya, natural, kasama ang mga puwang at ang bagong line character - 'n'. Ang file na naglalaman ng linyang ito ay tumitimbang ng 22*8 = 176 bits. Ang tanong ay agad na lumitaw: makatuwiran ba na gamitin ang lahat ng 8 bits upang i-encode ang 1 character? Hindi namin ginagamit ang lahat ng ASCII na character. Kahit na ginawa nila, mas makatuwiran para sa pinakakaraniwang titik - S - na mabigyan ng pinakamaikling posibleng code, at para sa pinakabihirang titik - T (o U, o 'n') - na mabigyan ng mas mahabang code. Ito ang binubuo ng Huffman algorithm: ito ay kinakailangan upang mahanap ang pinakamainam na opsyon sa pag-encode kung saan ang file ay magkakaroon ng pinakamababang timbang. Normal lang na mag-iiba ang mga haba ng code para sa iba't ibang simbolo - ito ang pinagbatayan ng algorithm.
Coding
Bakit hindi bigyan ng code ang character na 'S', halimbawa, 1 bit ang haba: 0 o 1. Hayaan itong maging 1. Pagkatapos ay ang pangalawang pinakakaraniwang character - ' ' (space) - bigyan ng 0. Isipin na sinimulan mo ang pag-decode ng iyong mensahe - ang naka-encode na string s1 - at nakikita mo na ang code ay nagsisimula sa 1. Kaya, ano ang gagawin mo: ito ba ang karakter na S, o ito ba ay ibang karakter, halimbawa A? Samakatuwid, lumitaw ang isang mahalagang panuntunan:
Ang alinman sa code ay hindi dapat maging prefix ng isa pa
Ang panuntunang ito ay susi sa algorithm. Samakatuwid, ang paglikha ng isang code ay nagsisimula sa isang talahanayan ng dalas, na nagpapahiwatig ng dalas (bilang ng mga paglitaw) ng bawat simbolo:
Ang mga character na may pinakamaraming paglitaw ay dapat na hindi naka-encode maaari bilang ng mga bit. Magbibigay ako ng isang halimbawa ng isa sa mga posibleng talahanayan ng code:
Kaya ang naka-encode na mensahe ay magiging ganito:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Pinaghiwalay ko ang code ng bawat karakter na may puwang. Hindi ito mangyayari sa isang tunay na naka-compress na file!
Ang tanong ay lumitaw: paano nakabuo ang batang ito ng code upang lumikha ng isang talahanayan ng mga code? Ito ay tatalakayin sa ibaba.
Paggawa ng puno ng Huffman
Dito nagliligtas ang mga binary search tree. Huwag mag-alala, hindi mo kakailanganin ang paghahanap, pagpasok, o pagtanggal ng mga pamamaraan dito. Narito ang istraktura ng puno sa 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;
}
...
}
Hindi ito ang kumpletong code, ang buong code ay nasa ibaba.
Narito ang algorithm para sa pagbuo ng puno:
- Gumawa ng Node object para sa bawat karakter mula sa mensahe (linya s1). Sa aming kaso magkakaroon ng 9 na mga node (mga bagay na Node). Ang bawat node ay binubuo ng dalawang field ng data: simbolo at dalas
- Gumawa ng Tree object (BinaryTree) para sa bawat Node. Ang node ay nagiging ugat ng puno.
- Ipasok ang mga punong ito sa priority queue. Kung mas mababa ang dalas, mas mataas ang priyoridad. Kaya, kapag nag-extract, palaging pinipili ang dervo na may pinakamababang frequency.
Susunod na kailangan mong gawin ang sumusunod na cyclically:
- Alisin ang dalawang puno sa priority queue at gawin silang mga anak ng bagong node (ang bagong likhang node na walang titik). Ang dalas ng bagong node ay katumbas ng kabuuan ng mga frequency ng dalawang descendant na puno.
- Para sa node na ito, lumikha ng isang puno na may ugat sa node na ito. Ipasok ang punong ito pabalik sa priority queue. (Dahil may bagong frequency ang puno, malamang na lalabas ito sa isang bagong lugar sa pila)
- Ipagpatuloy ang hakbang 1 at 2 hanggang sa isang puno na lang ang natitira sa pila - ang puno ng Huffman
Isaalang-alang ang algorithm na ito sa linya s1:
Dito ang simbolo na "lf" (linefeed) ay nangangahulugang isang bagong linya, "sp" (space) ay isang puwang.
At pagkatapos ay kung ano?
Nakakuha kami ng puno ng Huffman. OK. At ano ang gagawin dito? Hindi nila ito kukunin nang libre. At pagkatapos, kailangan mong subaybayan ang lahat ng posibleng daanan mula sa ugat hanggang sa mga dahon ng puno. Sumang-ayon tayo na tukuyin ang isang gilid 0 kung ito ay humahantong sa kaliwang bata at 1 kung ito ay humahantong sa kanan. Sa mahigpit na pagsasalita, sa notasyong ito, ang code ng isang simbolo ay ang landas mula sa ugat ng puno hanggang sa dahon na naglalaman ng mismong simbolo na ito.
Ganito ang naging talahanayan ng mga code. Tandaan na kung isasaalang-alang natin ang talahanayang ito, maaari nating tapusin ang tungkol sa "timbang" ng bawat simbolo - ito ang haba ng code nito. Pagkatapos, sa compressed form, ang orihinal na file ay titimbangin: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits . Sa una ay tumitimbang ito ng 176 bits. Dahil dito, binawasan namin ito ng hanggang 176/65 = 2.7 beses! Ngunit ito ay isang utopia. Ang ganitong koepisyent ay malamang na hindi makuha. Bakit? Ito ay tatalakayin sa ibang pagkakataon.
Pagde-decode
Well, marahil ang pinakasimpleng bagay na natitira ay ang pag-decode. Sa tingin ko marami sa inyo ang nahulaan na hindi kami basta-basta makakagawa ng naka-compress na file nang walang anumang pahiwatig kung paano ito na-encode - hindi namin ito ma-decode! Oo, oo, mahirap para sa akin na mapagtanto ito, ngunit kailangan kong gumawa ng text file table.txt na may compression table:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Entry ng talahanayan sa form na 'symbol' 'character code'. Bakit walang simbolo ang 01110? Sa katunayan, ito ay may isang simbolo, ito ay lamang na ang mga java tool na ginagamit ko kapag nag-output sa isang file, ang bagong linya na character - 'n' - ay na-convert sa isang bagong linya (kahit gaano ito katanga). Samakatuwid, ang walang laman na linya sa itaas ay ang character para sa code 01110. Para sa code 00, ang character ay isang puwang sa simula ng linya. Sasabihin ko kaagad na para sa aming Khan coefficient, ang pamamaraang ito ng pag-iimbak ng talahanayan ay maaaring mag-claim na ang pinaka-hindi makatwiran. Ngunit ito ay madaling maunawaan at ipatupad. Ikalulugod kong marinig ang iyong mga rekomendasyon sa mga komento tungkol sa pag-optimize.
Ang pagkakaroon ng talahanayang ito ay ginagawang napakadaling mag-decode. Tandaan natin kung anong panuntunan ang sinunod natin noong ginagawa ang pag-encode:
Ang alinman sa code ay hindi dapat maging prefix ng isa pa
Ito ay kung saan ito gumaganap ng isang facilitating papel. Nagbabasa kami ng sunud-sunod nang paunti-unti at, sa sandaling ang resultang string d, na binubuo ng mga read bit, ay tumugma sa pag-encode na naaayon sa character na character, agad naming malalaman na ang character na character (at ito lang!) ay na-encode. Susunod, nagsusulat kami ng character sa linya ng pag-decode (ang linya na naglalaman ng decoded na mensahe), i-reset ang linya d, at pagkatapos ay basahin ang naka-encode na file.
Pagpapatupad
Oras na para ipahiya ang aking code at magsulat ng archiver. Tawagin natin itong Compressor.
Magsimula muli. Una sa lahat, isinusulat namin ang klase ng 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;
}
}
Ngayon ang puno:
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;
}
}
Priority Queue:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Ang klase na lumilikha ng Huffman tree:
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 na naglalaman kung aling mga nag-encode/nagde-decode:
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("========================================================");
}
}
Isang klase na nagpapadali sa pagsulat sa isang file:
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();
}
}
Isang klase na nagpapadali sa pagbabasa mula sa isang file:
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();
}
}
Well, at ang pangunahing 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());
}
}
Kailangan mong isulat ang readme.txt file mismo :)
Konklusyon
Iyon lang yata ang gusto kong sabihin. Kung mayroon kang sasabihin tungkol sa aking kawalan ng kakayahan sa pagpapabuti ng code, algorithm, o anumang pag-optimize sa pangkalahatan, huwag mag-atubiling sumulat. Kung wala akong naipaliwanag, pakisulat din. Gusto kong marinig mula sa iyo sa mga komento!
PS
Oo, oo, nandito pa rin ako, dahil hindi ko nakalimutan ang tungkol sa coefficient. Para sa string s1, ang encoding table ay tumitimbang ng 48 bytes - mas malaki kaysa sa source file, at hindi namin nakalimutan ang tungkol sa mga karagdagang zero (ang bilang ng mga idinagdag na zero ay 7) => ang compression ratio ay mas mababa sa isa: 176/ (65 + 48*8 + 7) = 0.38. Kung napansin mo rin ito, hindi lang mukha mo ang maganda. Oo, ang pagpapatupad na ito ay magiging lubhang hindi epektibo para sa maliliit na file. Ngunit ano ang nangyayari sa malalaking file? Ang mga laki ng file ay mas malaki kaysa sa laki ng encoding table. Dito gumagana ang algorithm ayon sa nararapat! Halimbawa, para sa Ang archiver ay gumagawa ng isang tunay (hindi idealized) koepisyent ng 1.46 - halos isa at kalahating beses! At oo, ang file ay dapat na nasa Ingles.
Pinagmulan: www.habr.com