даромад
Дар ин мақола ман дар бораи алгоритми машҳури Huffman ва инчунин татбиқи он дар фишурдани додаҳо сӯҳбат мекунам.
Дар натиҷа, мо як архивгари оддӣ менависем. Ин аллакай муҳокима карда шудааст , вале бе ичрои амалй. Маводи назариявии мақолаи ҷорӣ аз дарсҳои информатикаи мактабӣ ва китоби Роберт Лафоре "Структураи додаҳо ва алгоритмҳо дар Java" гирифта шудааст. Пас, ҳама чиз бурида мешавад!
Якчанд фикр
Дар файли матнии муқаррарӣ як аломат бо 8 бит (рамзгузории ASCII) ё 16 (рамзгузории Юникод) рамзгузорӣ карда мешавад. Минбаъд мо рамзгузории ASCII-ро баррасӣ хоҳем кард. Масалан, сатри s1 = "SUSIE МЕГУЯД ИН ОСОН АСТ" -ро гиред. Табиист, ки дар сатр ҳамагӣ 22 аломат мавҷуд аст, аз ҷумла фосилаҳо ва аломати сатри нав - 'n'. Файли дорои ин сатр 22*8 = 176 бит вазн хоҳад дошт. Дарҳол савол ба миён меояд: оё истифодаи ҳама 8 бит барои рамзгузории 1 аломат оқилона аст? Мо ҳама аломатҳои ASCII-ро истифода намебарем. Ҳатто агар онҳо ин корро мекарданд, барои ҳарфи маъмултарин - S - рамзи кӯтоҳтарин дода мешавад ва барои ҳарфи камёб - T (ё U, ё 'n') - рамзи дарозтар дода мешавад. Ин аст, ки алгоритми Ҳуффман аз он иборат аст: бояд варианти оптималии рамзгузориро пайдо кард, ки дар он файл вазни минималӣ дошта бошад. Ин комилан муқаррарист, ки дарозии рамзҳо барои рамзҳои гуногун фарқ мекунанд - ин алгоритм ба он асос ёфтааст.
Рамзгузорӣ
Чаро ба аломати 'S' код надиҳед, масалан, 1 бит дароз: 0 ё 1. Бигзор он 1 бошад. Сипас аломати дуюми маъмултарин - ' ' (фосила) - 0 диҳед. Тасаввур кунед, ки шумо рамзкушоиши паёми худро оғоз кардаед - сатри рамзгузоришудаи s1 - ва шумо мебинед, ки рамз бо 1 оғоз мешавад. Пас, шумо чӣ кор мекунед: ин аломати S аст ё ин аломати дигар аст, масалан А? Аз ин рӯ, як қоидаи муҳим ба миён меояд:
Ҳеҷ яке аз рамзҳо набояд префикси дигаре бошанд
Ин қоида калид дар алгоритм аст. Аз ин рӯ, эҷоди код аз ҷадвали басомадҳо оғоз мешавад, ки басомади (шумораи рӯйдодҳои) ҳар як аломатро нишон медиҳад:
Аломатҳое, ки бештар дучор мешаванд, бояд ҳадди аққал рамзгузорӣ карда шаванд мумкин аст шумораи битҳо. Ман як мисоли яке аз ҷадвалҳои кодҳои имконпазирро медиҳам:
Ҳамин тавр, паёми рамзгузорӣ чунин хоҳад буд:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Ман рамзи ҳар як аломатро бо фосила ҷудо кардам. Ин дар файли воқеан фишурдашуда рӯй нахоҳад дод!
Саволе ба миён меояд: ин чавони чавон барои сохтани чадвали кодхо чй тавр кодро пайдо кардааст? Дар ин бора дар поён муҳокима карда мешавад.
Сохтмони дарахти Ҳуффман
Дар ин ҷо дарахтони бинарии ҷустуҷӯ ба наҷот меоянд. Парво накунед, ба шумо усулҳои ҷустуҷӯ, дохил кардан ё нест кардан дар ин ҷо лозим нест. Ин аст сохтори дарахт дар 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;
}
...
}
Ин рамзи пурра нест, рамзи пурра дар зер хоҳад буд.
Ин аст алгоритми сохтани дарахт:
- Барои ҳар як аломати паём объекти Node эҷод кунед (хати s1). Дар ҳолати мо 9 гиреҳ (Объектҳои гиреҳ) хоҳад буд. Ҳар як гиреҳ аз ду майдони маълумот иборат аст: рамз ва басомад
- Барои ҳар як гиреҳ объекти Tree (BinaryTree) эҷод кунед. Гиреҳ ба решаи дарахт табдил меёбад.
- Ин дарахтонро ба навбати афзалият гузоред. Чӣ қадаре ки басомад паст бошад, афзалият ҳамон қадар баландтар аст. Ҳамин тариқ, ҳангоми истихроҷ ҳамеша дерво бо басомади пасттарин интихоб карда мешавад.
Минбаъд шумо бояд давраҳои зеринро иҷро кунед:
- Ду дарахтро аз навбати афзалиятнок хориҷ кунед ва онҳоро фарзандони гиреҳи нав созед (гиреҳи навтаъсис бе ҳарф). Басомади гиреҳи нав ба ҷамъи басомадҳои ду дарахти насл баробар аст.
- Барои ин гиреҳ дарахте созед, ки реша дар ин гиреҳ дорад. Ин дарахтро дубора ба навбати авлавият гузоред. (Азбаски дарахт басомади нав дорад, он эҳтимолан дар ҷои нав дар навбат пайдо мешавад)
- Қадамҳои 1 ва 2-ро идома диҳед, то дар навбат танҳо як дарахт боқӣ монад - дарахти Ҳуффман
Ин алгоритмро дар хати s1 баррасӣ кунед:
Дар ин ҷо аломати “lf” (хаттӣ) маънои хати навро дорад, “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 бе аломат аст? Дар асл, ин бо рамз аст, танҳо он аст, ки асбобҳои java, ки ман ҳангоми баровардан ба файл истифода мебарам, аломати сатри нав - '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 - қариб якуним маротиба истеҳсол мекунад! Ва ҳа, файл бояд ба забони англисӣ бошад.
Манбаъ: will.com