komo
Ma kēiaʻatikala e kamaʻilio wau e pili ana i ka algorithm Huffman kaulana, a me kāna noi i ka hoʻopili ʻikepili.
ʻO ka hopena, e kākau mākou i kahi waihona maʻalahi. Ua kūkākūkā mua ʻia kēia , akā me ka hoʻokō pono ʻole. Lawe ʻia ka ʻatikala o ka pou o kēia manawa mai nā haʻawina ʻepekema kamepiula kula a me ka puke a Robert Laforet "Data Structures and Algorithms in Java". No laila, ua ʻoki ʻia nā mea a pau!
He mau manaʻo
Ma ka waihona kikokikona maʻamau, hoʻopili ʻia kekahi ʻano me 8 bits (ASCII encoding) a i ʻole 16 (Unicode encoding). A laila e noʻonoʻo mākou i ka hoʻopili ASCII. No ka laʻana, e lawe i ka laina s1 = "ʻŌlelo mai ʻo SUSIE HE MAʻalahin". He 22 ka nui o ka laina, ma ke ano, me na hakahaka a me ke ano laina hou - 'n'. ʻO ke kaumaha o ka faila i loko o kēia laina he 22*8 = 176 mau bits. Piʻi koke ka nīnau: he mea kūpono ke hoʻohana i nā 8 bits a pau e hoʻopaʻa i ka ʻano 1? ʻAʻole mākou hoʻohana i nā huaʻōlelo ASCII āpau. ʻOiai inā lākou i hana, ʻoi aku ka maikaʻi o ka leka maʻamau - S - e hāʻawi ʻia i ke code pōkole loa, a no ka leka loa loa - T (a i ʻole U, a i ʻole 'n') - e hāʻawi ʻia i kahi code lōʻihi. ʻO kēia ka mea o ka Huffman algorithm: pono e ʻimi i ke koho hoʻopono maikaʻi loa kahi e loaʻa ai i ka faila ke kaumaha haʻahaʻa. He mea maʻamau ka ʻokoʻa o ka lōʻihi o ke code no nā hōʻailona like ʻole - ʻo ia ka mea i hoʻokumu ʻia ai ka algorithm.
Hoʻopaʻa inoa
No ke aha e hāʻawi ʻole ai i ke ʻano 'S' i code, no ka laʻana, 1 bit ka lōʻihi: 0 a i ʻole 1. E waiho ʻia ʻo 1. A laila ʻo ka lua o ka mea maʻamau - ' ' (space) - hāʻawi i 0. E noʻonoʻo ʻoe ua hoʻomaka ʻoe e wehe i kāu leka - ke kaula i hoʻopaʻa ʻia s1 - a ʻike ʻoe e hoʻomaka ana ke code me 1. No laila, he aha kāu e hana ai: ʻo ia ke ʻano S, a i ʻole kekahi ʻano ʻē aʻe, no ka laʻana A? No laila, kū mai kahi lula koʻikoʻi:
ʻAʻole pono kekahi code i prefix o kekahi
He mea nui kēia lula i ka algorithm. No laila, hoʻomaka ka hoʻokumu ʻana i kahi code me kahi papa kuhikuhi, e hōʻike ana i ke alapine (helu o nā hanana) o kēlā me kēia hōʻailona:
Pono e hoʻopaʻa inoa ʻia nā huaʻōlelo me ka hapa nui hiki helu o nā bits. E hāʻawi wau i kahi laʻana o kekahi o nā papa code hiki ke hiki:
No laila e like me kēia ka memo i hoʻopaʻa ʻia:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Ua hoʻokaʻawale au i ke code o kēlā me kēia ʻano me kahi hakahaka. ʻAʻole e hana ʻia kēia ma kahi faila i hoʻopili maoli ʻia!
Ke ala mai nei ka nīnau: pehea i hiki mai ai kēia kanaka ʻōpio i ke code e hana i kahi papa o nā code? E kūkākūkā ʻia kēia ma lalo nei.
Ke kūkulu ʻana i kahi lāʻau Huffman
ʻO kēia kahi e hoʻopakele ai nā kumulāʻau huli binary. Mai hopohopo, ʻaʻole pono ʻoe i ka ʻimi, hoʻokomo, a holoi paha i nā ala ma aneʻi. Eia ke ʻano lāʻau ma 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;
}
...
}
ʻAʻole kēia ka code piha, aia ka code piha ma lalo.
Eia ka algorithm no ke kūkulu ʻana i ka lāʻau:
- E hana i kahi mea Node no kēlā me kēia ʻano mai ka memo (laina s1). I kā mākou hihia, aia nā 9 nodes (Node objects). Loaʻa i kēlā me kēia node ʻelua kahua ʻikepili: hōʻailona a me ka pinepine
- E hana i kahi mea lāʻau (BinaryTree) no kēlā me kēia Node. Lilo ka node i ke kumu o ka laau.
- E hoʻokomo i kēia mau lāʻau i loko o ka laina koho. ʻO ka haʻahaʻa o ke alapine, ʻoi aku ka kiʻekiʻe o ka mea nui. No laila, i ka unuhi ʻana, koho mau ʻia ka dervo me ka haʻahaʻa haʻahaʻa.
A laila pono ʻoe e hana i kēia cyclically:
- Wehe i nā lāʻau ʻelua mai ka pila koʻikoʻi a hoʻolilo iā lākou i mau keiki o ka node hou (ka node i hana ʻia me ka ʻole o ka leka). Ua like ke alapine o ka node hou me ka huina o na alapine o na laau mamo elua.
- No kēia node, e hana i kumulāʻau me ke aʻa ma kēia puʻu. E hoʻokomo hou i kēia lāʻau i loko o ka pila koʻikoʻi. (No ka mea he alapine hou ka lāʻau, e ʻike ʻia paha ia ma kahi hou o ka pila)
- E hoʻomau i ka ʻanuʻu 1 a me 2 a hoʻokahi wale nō lāʻau i koe i ka lālani - ʻo ka lāʻau Huffman
E noʻonoʻo i kēia algorithm ma ka laina s1:
Eia ka hōʻailona "lf" (linefeed) he laina hou, "sp" (space) he hakahaka.
He aha aʻe?
Loaʻa iā mākou kahi lāʻau Huffman. OK. A he aha ka hana me ia? ʻAʻole lākou e lawe manuahi, a laila, pono ʻoe e ʻimi i nā ala āpau mai ke kumu a hiki i nā lau o ka lāʻau. E ʻae kākou e hōʻike i ka ʻaoʻao 0 inā alakaʻi i ke keiki hema a me 1 inā alakaʻi i ka ʻākau. ʻO ka ʻōlelo koʻikoʻi, ma kēia notation, ʻo ke code o kahi hōʻailona ke ala mai ke kumu o ka lāʻau a i ka lau i loaʻa kēia hōʻailona.
ʻO kēia ke ʻano o ka papa o nā code. E hoʻomaopopo inā inā mākou e noʻonoʻo i kēia papa, hiki iā mākou ke hoʻoholo e pili ana i ka "kaumaha" o kēlā me kēia hōʻailona - ʻo ia ka lōʻihi o kāna code. A laila, ma ke ʻano i hoʻopaʻa ʻia, e kaupaona ka faila kumu: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits . I ka wā mua, he 176 bits kona kaumaha. No laila, ua hōʻemi mākou iā ia e like me 176/65 = 2.7 manawa! Akā, he utopia kēia. ʻAʻole hiki ke loaʻa ia ʻano coefficient. No ke aha mai? E kūkākūkā ʻia kēia ma hope.
Wehewehewehe
ʻAe, ʻo ka mea maʻalahi paha i koe ka decoding. Manaʻo wau ua manaʻo ka nui o ʻoukou ʻaʻole hiki iā mākou ke hana i kahi faila i hoʻopaʻa ʻia me ka ʻole o ke ʻano o ka hoʻopili ʻana - ʻaʻole hiki iā mākou ke hoʻokaʻawale! ʻAe, ʻae, ua paʻakikī iaʻu ke hoʻomaopopo i kēia, akā pono wau e hana i kahi faila kikokikona table.txt me kahi papa kōmike:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Hoʻokomo papa ma ke ʻano 'hōʻailona' 'ʻano code'. No ke aha ka 01110 me ka hōʻailona ʻole? ʻO ka ʻoiaʻiʻo, aia me kahi hōʻailona, ʻo nā mea hana java wale nō aʻu e hoʻohana ai i ka wā e hoʻopuka ai i kahi faila, ua hoʻololi ʻia ke ʻano laina hou - 'n' - i kahi laina hou (no ka naʻaupō paha. No laila, ʻo ka laina kaʻawale ma luna ke ʻano no ke code 01110. No ke code 00, ʻo ke ʻano he hakahaka ma ka hoʻomaka o ka laina. E ʻōlelo koke wau no kā mākou Khan coefficient, hiki i kēia ʻano o ka mālama ʻana i kahi papaʻaina ke ʻōlelo ʻo ia ka mea noʻonoʻo loa. Akā, maʻalahi ke hoʻomaopopo a hoʻokō. E hauʻoli wau e lohe i kāu mau manaʻo i nā manaʻo e pili ana i ka optimization.
ʻO ka loaʻa ʻana o kēia pākaukau he mea maʻalahi loa ia e hoʻokaʻawale. E hoʻomanaʻo mākou i ke kānāwai a mākou i hahai ai i ka hana ʻana i ka hoʻopili:
ʻAʻole pono kekahi code i prefix o kekahi
ʻO kēia kahi e pāʻani ai i kahi hana maʻalahi. Heluhelu mākou ma ke ʻano liʻiliʻi a, i ka manawa e hoʻohālikelike ʻia ai ka string d, ʻo ia hoʻi nā ʻāpana heluhelu, i ka hoʻopili ʻana e pili ana i ke ʻano o ke ʻano, ʻike koke mākou ua hoʻopili ʻia ke ʻano o ke ʻano (a ʻo ia wale nō!). A laila, kākau mākou i ke ʻano i ka laina decoding (ka laina i loaʻa ka memo decoded), hoʻonohonoho hou i ka laina d, a laila heluhelu i ka faila i hoʻopaʻa ʻia.
Ka hoʻokō
ʻO ka manawa kēia e hoʻohaʻahaʻa ai i kaʻu code a kākau i kahi waihona. Kāhea kākou iā Compressor.
E hoʻomaka hou. ʻO ka mea mua, kākau mākou i ka papa 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;
}
}
Ano ka laau:
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;
}
}
Ka Lālani Manaʻo:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
ʻO ka papa i hana i ka lāʻau 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;
}
}
Papa i hoʻopaʻa ʻia/decodes:
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("========================================================");
}
}
He papa e maʻalahi ke kākau i kahi faila:
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();
}
}
He papa e maʻalahi ka heluhelu ʻana mai kahi 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();
}
}
ʻAe, a me ka papa nui:
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());
}
}
Pono ʻoe e kākau i ka faila readme.txt iā ʻoe iho :)
hopena
Manaʻo wau ʻo ia wale nō kaʻu i makemake ai e ʻōlelo. Inā loaʻa iā ʻoe kekahi mea e ʻōlelo ai e pili ana i koʻu hemahema i ka hoʻomaikaʻi ʻana i ke code, algorithm, a i ʻole kekahi optimization ma ka laulā, e ʻoluʻolu e kākau. Inā ʻaʻole au i wehewehe i kekahi mea, e ʻoluʻolu e kākau pū. Makemake wau e lohe mai iā ʻoe ma nā manaʻo!
PS
ʻAe, ʻae, aia nō wau ma ʻaneʻi, no ka mea, ʻaʻole wau i poina i ka coefficient. No ka string s1, he 48 bytes ke kaumaha o ka papa hoʻopāpā - ʻoi aku ka nui ma mua o ka waihona kumu, a ʻaʻole mākou i poina e pili ana i nā zeros hou (ʻo ka helu o nā zeros i hoʻohui ʻia he 7) => e emi ana ka ratio hoʻoemi ma mua o hoʻokahi: 176/ (65 + 48*8 + 7) = 0.38. Inā ʻoe i ʻike i kēia, ʻaʻole ʻo kou helehelena wale nō ka maikaʻi. ʻAe, ʻaʻole pono kēia hoʻokō no nā faila liʻiliʻi. Akā he aha ka hopena i nā faila nui? ʻOi aku ka nui o nā faila ma mua o ka nui o ka papa hoʻopā. ʻO kēia kahi e hana ai ka algorithm e like me ka mea e pono ai! No ka laʻana, no Hoʻopuka ka waihona waihona i ka helu maoli (ʻaʻole i hoʻohālikelike ʻia) o 1.46 - kokoke i hoʻokahi a me ka hapa manawa! A ʻae, ua manaʻo ʻia ka faila ma ka ʻōlelo Pelekania.
Source: www.habr.com