Ifihan
Ninu nkan yii Emi yoo sọrọ nipa olokiki Huffman algorithm, bakanna bi ohun elo rẹ ni funmorawon data.
Bi abajade, a yoo kọ akọọlẹ ti o rọrun kan. Eyi ti sọrọ tẹlẹ , ṣugbọn laisi imuse ti o wulo. Awọn ohun elo imọ-ọrọ ti ifiweranṣẹ lọwọlọwọ ni a mu lati awọn ẹkọ imọ-ẹrọ kọnputa ile-iwe ati iwe Robert Laforet "Awọn ilana data ati awọn alugoridimu ni Java”. Nitorina, ohun gbogbo ti ge!
Awọn ero diẹ
Ninu faili ọrọ deede, ohun kikọ kan wa ni koodu pẹlu awọn bit 8 (ASCII fifi koodu) tabi 16 (iyipada Unicode). Nigbamii ti a yoo ronu fifi koodu ASCII naa. Fun apẹẹrẹ, mu ila s1 = "SUSIE SỌ O RỌRỌRỌ". Apapọ awọn ohun kikọ 22 wa ninu laini, nipa ti ara, pẹlu awọn alafo ati kikọ laini tuntun - 'n'. Faili ti o ni laini yii yoo ṣe iwọn 22*8 = 176 die-die. Ibeere naa waye lẹsẹkẹsẹ: ṣe o jẹ onipin lati lo gbogbo awọn bit 8 lati fi koodu iwọle 1 kikọ bi? A ko lo gbogbo awọn ohun kikọ ASCII. Paapa ti wọn ba ṣe, yoo jẹ onipin diẹ sii fun lẹta ti o wọpọ julọ - S - lati fun ni koodu ti o kuru ju, ati fun lẹta ti o ṣọwọn - T (tabi U, tabi ‘n’) - lati fun ni koodu to gun. Eyi ni ohun ti Huffman algorithm ni: o jẹ dandan lati wa aṣayan fifi ẹnọ kọ nkan ti o dara julọ ninu eyiti faili naa yoo ni iwuwo to kere julọ. O jẹ deede pe awọn ipari koodu yoo yatọ fun awọn aami oriṣiriṣi - eyi ni ohun ti algorithm da lori.
Koodu
Kilode ti o ko fun ohun kikọ 'S' koodu kan, fun apẹẹrẹ, 1 bit gun: 0 tabi 1. Jẹ ki o jẹ 1. Lẹhinna ohun kikọ keji ti o wọpọ julọ - '' (aaye) - fun 0. Fojuinu pe o bẹrẹ iyipada ifiranṣẹ rẹ - okun koodu s1 - ati pe o rii pe koodu bẹrẹ pẹlu 1. Nitorina, kini o ṣe: eyi jẹ ohun kikọ S, tabi o jẹ ohun kikọ miiran, fun apẹẹrẹ A? Nitorina, ofin pataki kan waye:
Ko si koodu ko yẹ ki o jẹ ìpele ti omiiran
Ofin yii jẹ bọtini ni algorithm. Nitorinaa, ṣiṣẹda koodu kan bẹrẹ pẹlu tabili igbohunsafẹfẹ, eyiti o tọka igbohunsafẹfẹ (nọmba awọn iṣẹlẹ) ti aami kọọkan:
Awọn ohun kikọ pẹlu awọn iṣẹlẹ pupọ julọ yẹ ki o wa ni koodu o kere ju ṣee ṣe nọmba ti die-die. Emi yoo fun apẹẹrẹ ọkan ninu awọn tabili koodu ti o ṣeeṣe:
Nitorinaa ifiranṣẹ ti o ni koodu yoo dabi eyi:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Mo ya koodu ti ohun kikọ silẹ kọọkan pẹlu aaye kan. Eyi kii yoo ṣẹlẹ ninu faili fisinuirindigbindigbin nitootọ!
Ibeere naa waye: bawo ni ọdọmọkunrin yii ṣe wa pẹlu koodu lati ṣẹda tabili awọn koodu? Eleyi yoo wa ni sísọ ni isalẹ.
Ṣiṣeto igi Huffman kan
Eyi ni ibi ti awọn igi wiwa alakomeji wa si igbala. Maṣe yọ ara rẹ lẹnu, iwọ kii yoo nilo wiwa, fi sii, tabi paarẹ awọn ọna rẹ nibi. Eyi ni eto igi ni 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;
}
...
}
Eyi kii ṣe koodu pipe, koodu kikun yoo wa ni isalẹ.
Eyi ni algorithm fun ṣiṣe igi naa:
- Ṣẹda ohun Node fun ohun kikọ kọọkan lati ifiranṣẹ (ila s1). Ninu ọran wa awọn apa 9 yoo wa (Awọn nkan Node). Ipade kọọkan ni awọn aaye data meji: aami ati igbohunsafẹfẹ
- Ṣẹda nkan Igi (BinaryTree) fun Node kọọkan. Ipin naa di gbongbo igi naa.
- Fi awọn igi wọnyi sinu isinyi ayo. Isalẹ awọn igbohunsafẹfẹ, awọn ti o ga ni ayo. Nitorinaa, nigba yiyo, dervo pẹlu igbohunsafẹfẹ ti o kere julọ ni a yan nigbagbogbo.
Nigbamii o nilo lati ṣe atẹle ni cyclically:
- Yọ awọn igi meji kuro ni isinyi ayo ki o jẹ ki wọn jẹ ọmọ ti ipade tuntun (ipo tuntun ti a ṣẹda laisi lẹta). Awọn igbohunsafẹfẹ ti awọn titun ipade jẹ dogba si awọn apao ti awọn igbohunsafẹfẹ ti awọn meji arọmọdọmọ igi.
- Fun ipade yii, ṣẹda igi kan pẹlu gbongbo ni ipade yii. Fi igi yii pada si isinyi ayo. (Niwọn igba ti igi naa ni igbohunsafẹfẹ tuntun, o ṣee ṣe julọ yoo han ni aaye tuntun ni isinyi)
- Tẹsiwaju awọn igbesẹ 1 ati 2 titi ti igi kan yoo fi ku ninu isinyi - igi Huffman
Wo algorithm yii lori laini s1:
Nibi aami "lf" (linefeed) tumọ si laini tuntun, "sp" (aaye) jẹ aaye kan.
Kini atẹle?
A ni igi Huffman kan. O DARA. Ati kini lati ṣe pẹlu rẹ? Wọn kii yoo gba paapaa fun ọfẹ ati lẹhinna, o nilo lati wa gbogbo awọn ọna ti o ṣeeṣe lati gbongbo si awọn ewe igi naa. Jẹ ki a gba lati tọka si eti 0 ti o ba nyorisi ọmọ osi ati 1 ti o ba tọ si apa ọtun. Ni sisọ ni pipe, ninu akiyesi yii, koodu aami kan jẹ ọna lati gbongbo igi si ewe ti o ni aami yii gan-an ninu.
Eyi ni bi tabili awọn koodu ṣe tan. Ṣe akiyesi pe ti a ba gbero tabili yii, a le pari nipa “iwuwo” ti aami kọọkan - eyi ni ipari ti koodu rẹ. Lẹhinna, ni fọọmu fisinuirindigbindigbin, faili atilẹba yoo ṣe iwọn: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bits . Ni akọkọ o wọn 176 die-die. Nitoribẹẹ, a dinku nipasẹ bii 176/65 = awọn akoko 2.7! Ṣugbọn eyi jẹ utopia. Iru olùsọdipúpọ bẹẹ ko ṣeeṣe lati gba. Kí nìdí? Eleyi yoo wa ni sísọ kekere kan nigbamii.
Yiyipada
O dara, boya ohun ti o rọrun julọ ti o kù ni iyipada. Mo ro pe ọpọlọpọ awọn ti o ti kiye si ti a ko le nìkan ṣẹda a fisinuirindigbindigbin faili lai eyikeyi ofiri ti bi o ti a kooduopo - a yoo ko ni anfani lati decoded o! Bẹẹni, bẹẹni, o ṣoro fun mi lati mọ eyi, ṣugbọn emi yoo ni lati ṣẹda faili ọrọ table.txt pẹlu tabili funmorawon:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Akọsilẹ tabili ni fọọmu 'aami' 'koodu kikọ'. Kini idi ti 01110 laisi aami kan? Ni otitọ, o jẹ pẹlu aami kan, o kan jẹ pe awọn irinṣẹ java ti MO lo nigbati o ba njade jade si faili kan, ohun kikọ tuntun - 'n' - ti yipada si laini tuntun (laibikita bi omuwi ti le dun). Nitorina, ila ti o ṣofo ni oke ni ohun kikọ fun koodu 01110. Fun koodu 00, ohun kikọ jẹ aaye kan ni ibẹrẹ ti ila. Emi yoo sọ lẹsẹkẹsẹ pe fun olusọdipúpọ Khan wa, ọna yii ti titoju tabili le beere pe o jẹ alailoye julọ. Ṣugbọn o rọrun lati ni oye ati imuse. Emi yoo dun lati gbọ awọn iṣeduro rẹ ninu awọn asọye nipa iṣapeye.
Nini tabili yii jẹ ki o rọrun pupọ lati pinnu. Jẹ ki a ranti ofin wo ni a tẹle nigba ṣiṣẹda koodu:
Ko si koodu ko yẹ ki o jẹ ìpele ti omiiran
Eyi ni ibiti o ti ṣe ipa irọrun. A ka lẹsẹsẹ bit nipa bit ati, ni kete bi awọn Abajade okun d, ti o wa ninu awọn kika die-die, ibaamu awọn fifi koodu bamu si ohun kikọ silẹ, a lẹsẹkẹsẹ mọ pe awọn ohun kikọ silẹ (ati ki o nikan!) Ti a koodu. Nigbamii ti, a kọ ohun kikọ sinu laini iyipada (ila ti o ni ifiranṣẹ ti o ni iyipada), tun laini d, lẹhinna ka faili ti a fi koodu sii.
Imuse
O to akoko lati dojutini koodu mi ki o kọ iwe ipamọ kan. Jẹ ki a pe ni Compressor.
Lati ibere. Ni akọkọ, a kọ kilasi 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;
}
}
Bayi igi:
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;
}
}
Titẹ akọkọ:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Kilasi ti o ṣẹda igi 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;
}
}
Kilasi ti o ni awọn koodu koodu/iyipada ninu:
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("========================================================");
}
}
Kilasi ti o jẹ ki o rọrun lati kọ si faili kan:
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();
}
}
Kilasi ti o jẹ ki o rọrun lati ka lati faili kan:
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();
}
}
O dara, ati kilasi akọkọ:
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());
}
}
Iwọ yoo ni lati kọ faili readme.txt funrararẹ :)
ipari
Mo gboju pe iyẹn ni gbogbo ohun ti Mo fẹ sọ. Ti o ba ni ohunkohun lati sọ nipa ailagbara mi ni imudarasi koodu, algorithm, tabi eyikeyi iṣapeye ni gbogbogbo, lẹhinna lero ọfẹ lati kọ. Ti Emi ko ba ti ṣalaye ohunkohun, jọwọ kọ paapaa. Emi yoo nifẹ lati gbọ lati ọdọ rẹ ninu awọn asọye!
PS
Bẹẹni, bẹẹni, Mo wa sibi, nitori Emi ko gbagbe nipa iye-iye. Fun okun s1, tabili fifi koodu ṣe iwọn awọn baiti 48 - o tobi pupọ ju faili orisun lọ, ati pe a ko gbagbe nipa awọn afikun odo (nọmba awọn odo ti a ṣafikun jẹ 7) => ipin funmorawon yoo kere ju ọkan lọ: 176/ (65 + 48*8 + 7) = 0.38. Ti o ba tun ṣe akiyesi eyi, lẹhinna kii ṣe oju rẹ nikan ni o dara julọ. Bẹẹni, imuse yii yoo jẹ ailagbara pupọ fun awọn faili kekere. Ṣugbọn kini o ṣẹlẹ si awọn faili nla? Awọn iwọn faili tobi pupọ ju iwọn tabili fifi koodu lọ. Eyi ni ibi ti algorithm ṣiṣẹ bi o ti yẹ! Fun apẹẹrẹ, fun Ile ifipamọ ṣe agbejade gidi (kii ṣe apere) olùsọdipúpọ ti 1.46 - o fẹrẹẹ kan ati idaji awọn akoko! Ati bẹẹni, o yẹ ki faili naa wa ni Gẹẹsi.
orisun: www.habr.com