Sissejuhatus
Selles artiklis rÀÀgin ma tuntud Huffmani algoritmist ja selle rakendamisest andmete tihendamisel.
KokkuvÔttes kirjutame me lihtsa arhiivija. Sel teemal on juba olnud , kuid ilma praktilise teostuseta. KÀesoleva postituse teoreetiline materjal pÀrineb kooli infotehnoloogia tundidest ja Robert LaFore'i raamatust "Data Structures and Algorithms in Java". Nii et, kÔik allpool!
Veidi mÔtteid
Ăks tavatekstifailis kodeeritakse ĂŒks mĂ€rk 8 bittidega (ASCII kodeering) vĂ”i 16 bittidega (Unicode kodeering). Edasi vaatleme ASCII kodeeringut. NĂ€iteks vĂ”tame stringi s1 = «SUSIE SAYS IT IS EASYn». Kokku on stringis 22 mĂ€rki, sealhulgas tĂŒhikud ja ridade vahetamise sĂŒmbol â 'n'. Fail, mis sisaldab seda stringi, kaalub 22*8 = 176 bitti. Koheselt tekib kĂŒsimus: kas on mĂ”istlik kasutada kĂ”iki 8 bitti ĂŒhe mĂ€rgi kodeerimiseks? Me ju ei kasuta kĂ”iki ASCII kodeeringu mĂ€rke. Isegi kui me kasutaksime, oleks mĂ”istlikum kĂ”ige sagedasemale letterile â S â anda lĂŒhim vĂ”imalik kood, ja kĂ”ige haruldasemale letterile â T (vĂ”i U, vĂ”i 'n') â anda pikem kood. Just see on Haffmani algoritmi mĂ”te: tuleb leida optimaalne kodeering, mille puhul fail oleks vĂ”imalikult vĂ€ike. On tĂ€iesti normaalne, et erinevatel mĂ€rkidel on koodi pikkused erinevad â sellel pĂ”hineb algoritm.
Ălekanne
Miks ei vĂ”iks sĂŒmbolile 'S' anda nĂ€iteks ĂŒhes bitis koodi: 0 vĂ”i 1. Olgu see 1. Siis anname teisele kĂ”ige sagedamini esinevale sĂŒmbolile â ' ' (tĂŒhik) â 0. Kujutage ette, et olete alustanud oma sĂ”numi dekodeerimist â kodeeritud stringi s1 â ja nĂ€ete, et kood algab 1. Mis nĂŒĂŒd? Kas see on sĂŒmbol S vĂ”i mĂ”ni muu sĂŒmbol, nĂ€iteks A? SeetĂ”ttu tekib oluline reegel:
Ăkski kood ei tohi olla teise prefiks.
See reegel on algoritmi keskne. SeetĂ”ttu algab koodi loomine sagedustabelist, kus on kirjas iga sĂŒmboli sagedus (esinevuste arv):
SĂŒmbolid, millel on kĂ”ige rohkem esinemisi, peavad olema kodeeritud vĂ”imalikult vĂ€heste bitide arvuga. TĂ”in nĂ€ite ĂŒhest vĂ”imalikust koodide tabelist:
Seega nÀeb kodeeritud sÔnum vÀlja jÀrgmiselt:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Iga sĂŒmboli koodi eraldasin tĂŒhikuga. Tegelikult ei ole komprimeeritud failis sellist asja!
KĂŒsimus tekib: kuidas see algaja koodi mĂ”tles ja koodide tabeli koostas? Sellest juttu allpool.
Huffman'i puu loomine.
Siin tulevad appi binaarsed otsingupuud. Ărge muretsege, siinkohal otsingu-, sisestamise- ja kustutamismeetodeid ei vajata. Siin on puu struktuur Java keeles:
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;
}
...
}
See ei ole tÀiuslik kood, tÀiuslik kood tuleb allpool.
Siin on puu moodustamise algoritm:
- Loo Node objekt iga sĂ”numis (string s1) oleva sĂŒmboli jaoks. Meie juhul on 9 sĂ”lme (Node objekti). Iga sĂ”lm koosneb kahest andmevĂ€ljast: sĂŒmbol ja sagedus.
- Loo BinaryTree objekt iga Node sÔlme jaoks. SÔlm muutub puu juureks.
- Sisesta need puud prioriteedikotta. Mida madalam on sagedus, seda suurem on prioriteet. Nii et vÀljastamisel valitakse alati vÀhima sagedusega puu.
Edasi tuleb tsĂŒkliliselt jĂ€rgmist teha:
- Eemalda kaks puud prioriteedikotist ja tee neist uue sĂ”lme jĂ€rglased (just loodud sĂ”lm, mis pole sĂŒmbolit). Uue sĂ”lme sagedus vastab kahe jĂ€rglase puu sageduste summale.
- Selle sÔlme jaoks luuakse puu, mille juureks on see sÔlm. See puu lisatakse tagasi prioriteetide jÀrjekorda. (Kuna puul on uus sagedus, siis tÔenÀoliselt asub see jÀrjekorras uues kohas)
- JĂ€tka toimingute 1 ja 2 tĂ€itmist, kuni jĂ€rjekorras jÀÀb ĂŒks puu â Huffmani puu
KÀime selle algoritmi lÀbi stringil s1:
Siin sĂŒmbol «lf» (linefeed) tĂ€histab reavahetust, «sp» (space) â tĂŒhikut.
Ja mis edasi?
Oleme saanud Huffmani puu. Noh, okei. Ja mis sellega edasi teha? Seda ei soovita keegi isegi tasuta. Edasi tuleb jĂ€lgida kĂ”iki vĂ”imalikke teid puu juurest puu lehtedeni. Lepime kokku, et serv 0 tĂ€histab vasakut jĂ€reltulijat ja 1 â paremat. Rangelt öeldes, nende tĂ€histuste puhul on sĂŒmboli kood â tee puu juurest leheni, mis sisaldab just seda sĂŒmbolit.
Nii moodustub koodide tabel. TĂ”deda vĂ”ib, et kui seda tabelit uurida, saab jĂ€reldada iga sĂŒmboli "kaalu" â see on tema koodi pikkus. Niisiis, komprimeeritud kujul kaalub algne fail: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bitti. Alguses kaalus see 176 bitti. Seega oleme seda vĂ€hendanud kuni 176/65 = 2.7 korda! Kuid see on utoopia. Sellist koefitsienti on tĂ”enĂ€oliselt raske saavutada. Miks? Seda kĂ€sitleme veidi hiljem.
Dekodeerimine
Noh, arvatavasti on jÀÀnud kĂ”ige lihtsam â dekodeerimine. Ma arvan, et paljud teist on arvanud, et lihtsalt komprimeeritud faili loomine ilma igasuguste vihjeteta selle kodeerimise kohta ei ole vĂ”imalik â me ei suuda seda dekodeerida! Jah, see oli mulle raske mĂ”ista, aga peame looma tekstifaili table.txt koos kompressioonitabeliga:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Tabeli salvestamine kujul âsĂŒmbolâ«sĂŒmboli kood». Miks on 01110 ilma sĂŒmbolita? Tegelikult on tal sĂŒmbol, lihtsalt Java vahendid, mida kasutasin faili vĂ€ljastamiseks, muundavad rea vahetussĂŒmboli â ânâ â rea vahetuseks (kuigi see kĂ”lab rumalalt). Seega ĂŒlemine tĂŒhi rida ongi sĂŒmbol koodile 01110. Koodile 00 on sĂŒmboliks tĂŒhik rea alguses. Ătlen kohe, et meie koefitsiendile khan see tabeli salvestamise meetod vĂ”ib olla kĂ”ige ebaefektiivsem. Kuid see on arusaadav ja rakendatav. Ootan huviga teie soovitusi kommentaarides optimeerimise kohta.
Selle tabeliga on vÀga lihtne dekodeerida. Tuletame meelde, millise reegli alusel me kodeeringu lÔime:
Ăkski kood ei tohi olla teise prefiks.
Siin mĂ€ngib see kergendavat rolli. Me loeme jĂ€rjestikku bitti bitist ja niipea, kui saadud rida d, mis koosneb loetud bittidest, vastab kodeeringule, mis vastab sĂŒmbolile character, teame kohe, et sĂŒmbol character on kodeeritud (ja ainult tema!). JĂ€rgmiseks kirjutame character deĆĄifreerimise ritta (deĆĄifreeritud sĂ”numi sisaldav rida), nullime rea d ja loeme edasi kodeeritud faili.
Rakendus
On aeg alandada oma koodi, et kirjutada arhiveerija. Nimetame selle Compressoriks.
Alustame algusest. Esiteks kirjutame klassi Node:
public class Node {
private int frequence;// sagedus
private char letter;// tÀht
private Node leftChild;// vasak laps
private Node rightChild;// parem laps
public Node(char letter, int frequence) { // tegelikult, konstruktor
this.letter = letter;
this.frequence = frequence;
}
public Node() {}// konstruktor, mis ei vĂ”ta argumente (vt ĂŒlaltoodud jaotis Huffmani puu ehitamise kohta)
public void addChild(Node newNode) {// lisada laps
if (leftChild == null)// kui vasak on tĂŒhi => parem on ka tĂŒhi => lisame vasakule
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) // ĂŒldiselt, vasak laps
rightChild = newNode;// saab see, kellel on madalam sagedus
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence();// kogusagedus
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() {// lehe kontrollimine
return leftChild == null && rightChild == null;
}
}
NĂŒĂŒd puu:
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;
}
}
PrioriteetjÀrjekord:
import java.util.ArrayList;//jah, jah, jÀrjekord pÔhineb nimekirjal
class PriorityQueue {
private ArrayList<BinaryTree> andmed;//jÀrjekorra nimekiri
private int nElems;//elementide arv jÀrjekorras
public PriorityQueue() {
andmed = new ArrayList<BinaryTree>();
nElems = 0;
}
public void insert(BinaryTree uusPuud) {//lisamine
if (nElems == 0)
andmed.add(uusPuud);
else {
for (int i = 0; i < nElems; i++) {
if (andmed.get(i).getFrequence() > uusPuud.getFrequence()) {//kui lisatava puu sagedus on vÀiksem
andmed.add(i, uusPuud);//kui see on vĂ€iksem praegusest, nihutame kĂ”ik puud paremal positsioonil ĂŒhe koha vĂ”rra
break;//siis paneme uue puu praeguse positsiooni kohale
}
if (i == nElems - 1)
andmed.add(uusPuud);
}
}
nElems++;//suurendame elementide arvu ĂŒhe vĂ”rra
}
public BinaryTree remove() {//eemaldamine jÀrjekorrast
BinaryTree tmp = andmed.get(0);//kopeerime eemaldatava elemendi
andmed.remove(0);//kui selline, eemaldame
nElems--;//vĂ€hendame elementide arvu ĂŒhe vĂ”rra
return tmp;//tagastame eemaldatud elemendi (madalaima sagedusega elemendi)
}
}
Klass, mis loob Huffmani puu:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127; // kooditabeli pikkus
private String myString; // sÔnum
private BinaryTree huffmanTree; // Huffmani puu
private int[] freqArray; // sagedustabel
private String[] encodingArray; // kodeerimistabel
// ----------------konstruktor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[ENCODING_TABLE_SIZE];
fillFrequenceArray();
huffmanTree = getHuffmanTree();
encodingArray = new String[ENCODING_TABLE_SIZE];
fillEncodingArray(huffmanTree.getRoot(), "", "");
}
// --------------------sagedustabel------------------------
private void fillFrequenceArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrequenceArray() {
return freqArray;
}
// ------------------------Huffmani puu loomine------------------
private BinaryTree getHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
// algoritm on kirjeldatud ĂŒleval
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) { // kui sĂŒmbol eksisteerib sĂ”numis
Node newNode = new Node((char) i, freqArray[i]); // siis looge selle jaoks Node
BinaryTree newTree = new BinaryTree(newNode); // ja Node'i jaoks looge BinaryTree
pq.insert(newTree); // sisestage jÀrjekorda
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // eemaldage jÀrjekorrast esimene puu.
try {
BinaryTree tree2 = pq.remove(); // eemaldage jÀrjekorrast teine puu
Node newNode = new Node(); // looge uus Node
newNode.addChild(tree1.getRoot()); // tehke selleks jÀreltulijad kaks eemaldatud puu
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) { // jĂ€rjekorras on jÀÀnud vaid ĂŒks puu
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
// -------------------kodeerimistabel------------------
void fillEncodingArray(Node node, String codeBefore, String direction) { // tÀitke kodeerimistabel
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() { // silumiseks
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Kodeerimistabel====================");
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;
}
}
Klass, mis sisaldab koodi, mis kodeerib/dekodeerib:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // kooditabeli pikkus
private HuffmanTree mainHuffmanTree; // Huffmani puu (kasutatakse ainult kokkutÔmbamiseks)
private String myString; // algne sÔnum
private int[] freqArray; // sagedustabel
private String[] encodingArray; // kodeerimistabel
private double ratio; // kokkutÔmbamistegur
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // kokkutÔmbamiseks
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // dekompressiooniks;
// ---------------------------------------kokkuvÔte-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermediate = ""; // vahepealne string (ilma tÀiendavate nullideta)
// System.out.println("=============================Compression=======================");
// displayEncodingArray();
for (int i = 0; i
// tuleb lisada nullid lÔppu (vÔib 1, pole vahet)
byte counter = 0; // konto lisatud nullide (byte piisab: 0 <= counter < 8 < 127)
for (int length = intermediate.length(), delta = 8 - length % 8;
counter < delta ; counter++) { // delta - lisatud nullide arv
intermediate += "0";
}
// ĂŒhendame lisatud nullide arvu binaarses esituses ja vahepealse stringi
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermediate;
// ideaalne koefitsient
setCompressionRatio();
// System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { // arvuta ideaalne koefitsient
double sumA = 0, sumB = 0; // A-algsumma
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() { // lÔplik kokkutÔmbamine
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;
}
// ---------------------------------------kokkutÔmbamise lÔpp----------------------------------------------------------------
// ------------------------------------------------------------arvesta-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
// displayEncodingArray();
// saadud lisatud nullide arv
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, kuna esimeseks byte'iks on meil lisatud nullide arv
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { // kui sobib
decompressed += (char)j; // siis lisame elemendi
current = ""; // ja resetime praeguse stringi
}
}
}
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() { // edenemiseks
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("========================================================");
}
}
Klass, mis lihtsustab faili kirjutamist:
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("Vale tee, vÔi sellist faili ei eksisteeri!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Klass, mis lihtsustab faili lugemist:
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) // kui fail on lÔppenud
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Ja, ja peamine klass:
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 { // mÀÀrame kÀsu kÀsurea argumentide abil
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("Vigane argumentide sisendi formaat");
System.out.println("Lugege Readme.txt");
e.printStackTrace();
}
}
public static void compress(String stringPath) throws IOException {
List 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("Vale tee vÔi sellist faili ei eksisteeri!");
return;
} catch (MalformedInputException e) {
System.out.println("Faili praegune kodeering ei ole toetatud");
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());
}
// loo fail kodeerimisteabiga:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Teel on kompressitud fail: " + compressedFile.getAbsolutePath());
System.out.println("Teel on kodeerimistabel " + table.getAbsolutePath());
System.out.println("Ilma tabelita faili ei Ônnestu vÀlja vÔtta!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100; // idealiseeritud koefitsient
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100; // tÔeline koefitsient
System.out.println("Idealiseeritud tihenduskoefitsient on " + idealRatio);
System.out.println("Tihendamise koefitsient arvesse vÔttes kodeerimistabelit " + 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];
// loe kompressitud fail
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! kontrollige siin:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte(); // meetod naaseb EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
// --------------------
// loe kodeerimistabel:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine(); // looge esimene tĂŒhi rida
encodingArray[(byte)'n'] = fi.readLine(); // loe kood '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();
// vÀljavÔte:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Teel on lahti pakitud fail " + extractedFile.getAbsolutePath());
}
}
Teie ĂŒlesanne on ise kirjutada readme.txt faili juhised đ
KokkuvÔte
VÔib-olla see ongi kÔik, mida ma öelda tahtsin. Kui teil on midagi mulle öelda minu oskamatuse kohta koodi, algoritmi vÔi mis tahes optimeerimise osas, siis kirjutage julgelt. Kui ma midagi ei selgitanud, siis kirjutage ka. Ootan huviga teie kommentaare!
P.S.
Jah-jah, ma olen ikka veel siin, sest ma ei ole unustanud koefitsienti. Stringi s1 kodeeringutabel kaalub 48 bait, mis on palju rohkem kui algfail, ja Ă€rme unusta lisada nullide arvu (lisatud nullide arv on 7) => kokkutĂ”mbumise koefitsient jÀÀb alla ĂŒhe: 176/(65 + 48*8 + 7)=0.38. Kui te ka seda mĂ€rkisite, siis olge uhke. Jah, see rakendus on vĂ€ikeste failide puhul ÀÀrmiselt ebatĂ”hus. Aga mis juhtub suurte failidega? Faili suurused ĂŒletavad oluliselt kodeeringutabeli suurust. Just siin töötab algoritm nagu peab! NĂ€iteks arhivaatija annab reaalse (mitte idealiseeritud) koefitsiendi, mis on 1.46 â peaaegu poole vĂ”rra rohkem! Ja jah, eeldati, et fail on ingliskeelne.
Allikas: habr.com
