Mynediad
Yn yr erthygl hon byddaf yn siarad am yr algorithm Huffman enwog, yn ogystal â'i gymhwysiad mewn cywasgu data.
O ganlyniad, byddwn yn ysgrifennu archifydd syml. Mae hyn eisoes wedi'i drafod , ond heb weithrediad ymarferol. Daw deunydd damcaniaethol y swydd bresennol o wersi cyfrifiadureg ysgolion a llyfr Robert Laforet “Data Structures and Algorithms in Java”. Felly, mae popeth wedi'i dorri!
Ychydig o feddyliau
Mewn ffeil testun arferol, mae un nod wedi'i amgodio ag 8 did (amgodio ASCII) neu 16 (amgodio Unicode). Nesaf byddwn yn ystyried yr amgodio ASCII. Er enghraifft, cymerwch y llinell s1 = “SUSIE DWEUD EI EASYn”. Mae cyfanswm o 22 nod yn y llinell, yn naturiol, gan gynnwys bylchau a nod y llinell newydd - 'n'. Bydd y ffeil sy'n cynnwys y llinell hon yn pwyso 22*8 = 176 did. Mae'r cwestiwn yn codi ar unwaith: a yw'n rhesymegol defnyddio pob un o'r 8 did i amgodio 1 nod? Nid ydym yn defnyddio pob nod ASCII. Hyd yn oed pe baent yn gwneud hynny, byddai'n fwy rhesymegol i'r llythyren fwyaf cyffredin - S - gael y cod byrraf posibl, ac i'r llythyren brinnaf - T (neu U, neu 'n') - gael cod hirach. Dyma beth mae algorithm Huffman yn ei gynnwys: mae angen dod o hyd i'r opsiwn amgodio gorau posibl lle bydd gan y ffeil y pwysau lleiaf. Mae'n eithaf normal y bydd hyd y cod yn wahanol ar gyfer gwahanol symbolau - dyma beth mae'r algorithm yn seiliedig arno.
Codio
Beth am roi cod i'r nod 'S', er enghraifft, 1 did o hyd: 0 neu 1. Gadewch iddo fod yn 1. Yna'r ail nod mwyaf cyffredin - ' ' (gofod) - rhowch 0. Dychmygwch eich bod wedi dechrau dadgodio'ch neges - y llinyn wedi'i amgodio s1 - ac rydych chi'n gweld bod y cod yn dechrau gyda 1. Felly, beth ydych chi'n ei wneud: ai dyma'r nod S, neu a yw'n gymeriad arall, er enghraifft A? Felly, mae rheol bwysig yn codi:
Ni ddylai'r naill god na'r llall fod yn rhagddodiad o un arall
Mae'r rheol hon yn allweddol yn yr algorithm. Felly, mae creu cod yn dechrau gyda thabl amlder, sy'n nodi amlder (nifer y digwyddiadau) pob symbol:
Dylid amgodio'r cymeriadau â'r mwyaf o ddigwyddiadau bosibl nifer o ddarnau. Rhoddaf enghraifft o un o'r tablau cod posibl:
Felly bydd y neges wedi'i hamgodio yn edrych fel hyn:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Gwahanais god pob cymeriad gyda bwlch. Ni fydd hyn yn digwydd mewn ffeil wirioneddol gywasgedig!
Mae'r cwestiwn yn codi: sut gwnaeth y dyn ifanc hwn y cod i greu tabl o godau? Bydd hyn yn cael ei drafod isod.
Adeiladu coeden Huffman
Dyma lle mae coed chwilio deuaidd yn dod i'r adwy. Peidiwch â phoeni, ni fydd angen y dulliau chwilio, mewnosod neu ddileu arnoch chi yma. Dyma strwythur y goeden yn 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;
}
...
}
Nid dyma'r cod cyflawn, bydd y cod llawn isod.
Dyma'r algorithm ar gyfer adeiladu'r goeden:
- Creu gwrthrych Node ar gyfer pob nod o'r neges (llinell s1). Yn ein hachos ni bydd 9 nod (gwrthrychau Node). Mae pob nod yn cynnwys dau faes data: symbol ac amlder
- Creu gwrthrych Coeden (BinaryTree) ar gyfer pob Nod. Daw'r nod yn wreiddyn y goeden.
- Rhowch y coed hyn yn y ciw blaenoriaeth. Po isaf yw'r amlder, yr uchaf yw'r flaenoriaeth. Felly, wrth echdynnu, mae'r dervo â'r amledd isaf bob amser yn cael ei ddewis.
Nesaf mae angen i chi wneud y canlynol yn gylchol:
- Tynnwch ddwy goeden o'r ciw blaenoriaeth a'u gwneud yn blant y nod newydd (y nod newydd heb y llythyren). Mae amlder y nod newydd yn hafal i swm amleddau'r ddwy goeden ddisgynnol.
- Ar gyfer y nod hwn, crëwch goeden gyda'r gwraidd yn y nod hwn. Rhowch y goeden hon yn ôl yn y ciw blaenoriaeth. (Gan fod gan y goeden amledd newydd, mae'n debygol y bydd yn ymddangos mewn lle newydd yn y ciw)
- Parhewch â chamau 1 a 2 nes mai dim ond un goeden sydd ar ôl yn y ciw - y goeden Huffman
Ystyriwch yr algorithm hwn ar-lein s1:
Yma mae'r symbol “lf” (llinell) yn golygu llinell newydd, “sp” (gofod) yw gofod.
Beth nesaf?
Cawsom goeden Huffman. IAWN. A beth i'w wneud ag ef? Ni fyddant hyd yn oed yn ei gymryd am ddim, ac yna, mae angen ichi olrhain pob llwybr posibl o'r gwreiddyn i ddail y goeden. Gadewch i ni gytuno i ddynodi ymyl 0 os yw'n arwain at y plentyn chwith ac 1 os yw'n arwain at yr un cywir. A siarad yn fanwl gywir, yn y nodiant hwn, cod symbol yw'r llwybr o wreiddyn y goeden i'r ddeilen sy'n cynnwys yr union symbol hwn.
Dyma sut y trodd y tabl codau allan. Sylwch, os ydym yn ystyried y tabl hwn, gallwn ddod i gasgliad ynghylch "pwysau" pob symbol - dyma hyd ei god. Yna, ar ffurf gywasgedig, bydd y ffeil wreiddiol yn pwyso: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 did . Ar y dechrau roedd yn pwyso 176 did. O ganlyniad, fe wnaethom ei leihau gymaint â 176/65 = 2.7 gwaith! Ond iwtopia yw hwn. Mae'n annhebygol y ceir cyfernod o'r fath. Pam? Bydd hyn yn cael ei drafod ychydig yn ddiweddarach.
Dadgodio
Wel, efallai mai'r peth symlaf sydd ar ôl yw dadgodio. Rwy'n meddwl bod llawer ohonoch wedi dyfalu na allwn greu ffeil gywasgedig heb unrhyw awgrym o sut y cafodd ei hamgodio - ni fyddwn yn gallu ei dadgodio! Oedd, ie, roedd yn anodd i mi sylweddoli hyn, ond bydd yn rhaid i mi greu tabled ffeil testun.txt gyda thabl cywasgu:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Cofnodi tabl yn y ffurflen 'symbol' 'cod nod'. Pam fod 01110 heb symbol? Mewn gwirionedd, gyda symbol, dim ond yr offer java rwy'n eu defnyddio wrth allbynnu i ffeil, mae'r nod llinell newydd - 'n' - yn cael ei drawsnewid yn llinell newydd (ni waeth pa mor dwp y mae'n swnio). Felly, y llinell wag ar y brig yw'r cymeriad ar gyfer cod 01110. Ar gyfer cod 00, gofod ar ddechrau'r llinell yw'r nod. Fe ddywedaf ar unwaith, ar gyfer ein cyfernod Khan, y gall y dull hwn o storio bwrdd honni mai hwn yw'r mwyaf afresymol. Ond mae'n hawdd ei ddeall a'i weithredu. Byddaf yn falch o glywed eich argymhellion yn y sylwadau ynghylch optimeiddio.
Mae cael y tabl hwn yn ei gwneud hi'n hawdd iawn dadgodio. Gadewch inni gofio pa reol a ddilynwyd gennym wrth greu'r amgodio:
Ni ddylai'r naill god na'r llall fod yn rhagddodiad o un arall
Dyma lle mae'n chwarae rôl hwyluso. Rydym yn darllen yn ddilyniannol fesul tipyn a, cyn gynted ag y bydd y llinyn canlyniadol d, sy'n cynnwys y darnau darllen, yn cyd-fynd â'r amgodio sy'n cyfateb i gymeriad y cymeriad, rydym yn gwybod ar unwaith bod y cymeriad nod (a dim ond ef!) wedi'i amgodio. Nesaf, rydym yn ysgrifennu cymeriad i'r llinell ddatgodio (y llinell sy'n cynnwys y neges wedi'i datgodio), ailosod llinell d, ac yna darllenwch y ffeil wedi'i hamgodio.
Gweithredu
Mae'n bryd bychanu fy nghod ac ysgrifennu archifydd. Gadewch i ni ei alw'n Cywasgydd.
Dechrau eto. Yn gyntaf oll, rydyn ni'n ysgrifennu'r dosbarth 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;
}
}
Nawr mae'r goeden:
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;
}
}
Ciw Blaenoriaeth:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Y dosbarth sy'n creu'r goeden 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;
}
}
Dosbarth sy'n cynnwys sy'n amgodio/datgodio:
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("========================================================");
}
}
Dosbarth sy'n ei gwneud hi'n haws ysgrifennu i ffeil:
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();
}
}
Dosbarth sy'n ei gwneud hi'n haws darllen o ffeil:
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();
}
}
Wel, a'r prif ddosbarth:
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());
}
}
Bydd rhaid i chi ysgrifennu'r ffeil readme.txt eich hun :)
Casgliad
Mae'n debyg mai dyna'r cyfan roeddwn i eisiau ei ddweud. Os oes gennych unrhyw beth i'w ddweud am fy anghymhwysedd wrth wella'r cod, yr algorithm, neu unrhyw optimeiddio yn gyffredinol, yna mae croeso i chi ysgrifennu. Os nad wyf wedi egluro unrhyw beth, ysgrifennwch hefyd. Byddwn wrth fy modd yn clywed gennych chi yn y sylwadau!
PS
Ydw, ydw, rydw i dal yma, oherwydd wnes i ddim anghofio am y cyfernod. Ar gyfer llinyn s1, mae'r tabl amgodio yn pwyso 48 beit - llawer mwy na'r ffeil ffynhonnell, ac ni wnaethom anghofio am y sero ychwanegol (7 yw nifer y sero ychwanegol) => bydd y gymhareb cywasgu yn llai nag un: 176/ (65 + 48*8 + 7) = 0.38 . Os gwnaethoch chi sylwi ar hyn hefyd, yna nid eich wyneb chi yn unig sy'n wych. Bydd, bydd y gweithrediad hwn yn hynod aneffeithlon ar gyfer ffeiliau bach. Ond beth sy'n digwydd i ffeiliau mawr? Mae maint y ffeiliau yn llawer mwy na maint y tabl amgodio. Dyma lle mae'r algorithm yn gweithio fel y dylai! Er enghraifft, ar gyfer Mae'r archifydd yn cynhyrchu cyfernod real (nid delfrydol) o 1.46 - bron unwaith a hanner! Ac ie, roedd y ffeil i fod yn Saesneg.
Ffynhonnell: hab.com