Hyrje
Në këtë artikull do të flas për algoritmin e njohur Huffman, si dhe për aplikimin e tij në kompresimin e të dhënave.
Si rezultat, do të shkruajmë një arkivues të thjeshtë. Kjo çështje ka qenë tashmë , por pa realizimin praktik. Materiali teorik i kësaj postimi është marrë nga mësimet shkollore të informatikës dhe libri i Robert Lafore «Struktura të Të Dhënave dhe Algoritmet në Java». Pra, gjithçka është e gatshme!
Disa refleksione
Në një skedar të zakonshëm tekstual, një karakter kodifikohet me 8 bit (kodimi ASCII) ose 16 (kodimi Unicode). Më pas do të shqyrtojmë kodimin ASCII. Për shembull, le të marrim vargun s1 = «SUSIE SAYS IT IS EASYn». Ka gjithsej 22 karaktere në varg, natyrisht duke përfshirë hapësirat dhe simbolin e kalimit në rresht të ri - ‘n’. Një skedar që përmban këtë varg do të peshojë 22*8 = 176 bit. Menjëherë lind pyetja: a është racional të përdorim të gjithë 8 bit për kodifikimin e 1 karakteri? Ne nuk po përdorim të gjitha karakteret e kodimit ASCII. Edhe nëse do të ishim duke i përdorur, do të ishte më racional t'i jepnim shkronjës më të shpeshtë - S - kodin më të shkurtër të mundshëm, ndërsa shkronjës më të rrallë - T (ose U, ose ‘n’) - një kod më të gjatë. Kjo është thelbi i algoritmit Huffman: nevojitet të gjejmë variantin optimal të kodifikimit, ku skedari do të jetë me peshën më minimale. Është plotësisht normale që për karaktere të ndryshme, gjatësia e kodit të ndryshojë - mbi këtë bazohet algoritmi.
Kodifikimi
Pse t’i japim shkronjës ‘S’ një kod, për shembull, me gjatësi 1 bit: 0 ose 1. Le të jetë ky 1. Atëherë, dyti karakter më i shpeshtë - ‘ ‘(hapësira) - do t’i japim 0. Imagjinoni se keni filluar të dekodoni mesazhin tuaj - vargun e koduar s1 - dhe shihni se kodi fillon me 1. Pra, çfarë duhet bërë: a është ky karakteri S, apo ndonjë karakter tjetër, për shembull A? Prandaj, ka një rregull të rëndësishëm:
Asnjë kod nuk duhet të jetë prefiks i tjetrit
Ky rregull është kyç në algoritmë. Prandaj, krijimi i kodit fillon me tabelën e frekuencës, ku tregohet frekuenca (numri i shfaqjeve) të çdo karakteri:
Karakteret me numrin më të madh të shfaqjeve duhet të kodifikohen me numrin më të vogël të mundshëm të bitëve. Ja një shembull i një prej tabelave të mundshme të kodit:
Kështu, mesazhi i koduar do të duket kështu:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Kodet e çdo karakteri i kam ndarë me hapësirë. Në të vërtetë, në skedarin e kompresuar një gjë e tillë nuk do të ndodhë!
Këtu lind pyetja: si e shpiku ky fillestar kodi për të krijuar një tabelë kodash? Për këtë do të flasim më poshtë.
Konstruktimi i pemës së Huffman-it
Këtu ndihmojnë pemët binarë të kërkimit. Mos u shqetësoni, këtu nuk do të nevojiten metodat e kërkimit, inserimit dhe fshirjes. Ja struktura e pemës në java:
public class Node {
private int frekuenca;
private char shkronjë;
private Node fëmijaEMajtë;
private Node fëmijaEDjathtë;
...
}
class BinaryTree {
private Node rrënja;
public BinaryTree() {
rrënja = new Node();
}
public BinaryTree(Node rrënja) {
this.rrënja = rrënja;
}
...
}
Ky nuk është kodi i plotë, kodi i plotë do të vijë më poshtë.
Ja vetë algoritmi i ndërtimit të pemës:
- Krijoni një objekt Node për çdo simbol nga mesazhi (string s1). Në rastin tonë do të ketë 9 nodus (objekte Node). Çdo nodus përbëhet nga dy fusha të dhënash: simboli dhe frekuenca.
- Krijoni një objekt Peme (BinaryTree) për çdo një nga nodet Node. Nodus bëhet rrënja e pemës.
- Shtoni këto pemë në radhën e prioritetit. Sa më e vogël të jetë frekuenca, aq më i madh është prioriteti. Kështu, kur nxirret, gjithmonë zgjidhet pema me frekuencën më të vogël.
Më pas, duhet të bëni në mënyrë ciklike këtë:
- Nxirrni dy pemë nga radhë e prioritetit dhe bëni ato pasardhës të një nodusi të ri (nodusi që sapo është krijuar pa shkronjë). Frekuenca e nodusit të ri është e barabartë me shumën e frekuencave të dy pemëve pasardhëse.
- Për këtë nodus krijoni një pemë me rrënjën në këtë nodus. Shtoni këtë pemë përsëri në radhë e prioritetit. (Duke qenë se pema ka frekuencë të re, është e mundur që ajo të pozicionohet në një vend të ri në radhë.)
- Vazhdoni të ekzekutoni hapat 1 dhe 2, derisa në radhë të mbetet vetëm një peme — pema e Huffman-it.
Le ta shqyrtojmë këtë algoritëm në stringun s1:
Këtu simboli «lf» (linefeed) nënkupton kalimin në një linjë të re, «sp» (space) është një hapësirë.
Çfarë ndodh më tej?
Ne kemi marrë pemën e Huffman-it. Mirë, dhe çfarë të bëjmë me të? As falas nuk e marrin. Më tej, duhet të ndjekim të gjitha rrugët e mundshme nga rrënja në gjethet e pemës. Le të binim dakord që të shënojmë skajin 0, nëse ai çon tek pasardhësi i majtë dhe 1 — nëse çon tek ai i djathtë. Me të vërtetë, sipas këtyre shënimeve, kodi i simbolit është rruga nga rrënja e pemës deri në gjethe, që përmban atë simbol.
Në këtë mënyrë u përgatit tabela e kodeve. Vëmendje, nëse e shqyrtojmë këtë tabelë, mund të nxjerrim një përfundim mbi 'peshën' e çdo simboli - kjo është gjatësia e kodit të tij. Kështu që në formë të kompresuar, skedari origjinal do të peshojë: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bit. Në fillim ai peshoi 176 bit. Prandaj, ne e reduktuam atë në 176/65 = 2.7 herë! Por kjo është një utopi. Një koeficient i tillë vështirë se do të arrihet. Pse? Këtë do ta diskutojmë pak më vonë.
Dekodimi
Tani, me siguri, ka mbetur gjëja më e thjeshtë - dekodimi. Mendoj se shumë prej jush e kanë kuptuar se nuk mund të krijohet një skedar i kompresuar pa asnjë aluzion mbi se si ishte koduar - nuk do të jemi në gjendje ta dekodojmë! Po, ishte e vështirë për t’u pranuar, por do të na duhej të krijonim një skedar tekstual table.txt me tabelën e kompresimit:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Shënimi i tabelës në formën 'simbol'«kodi i simbolit». Pse 01110 pa simbol? Në të vërtetë, ai ka një simbol, thjesht mjetet java që përdora në shfaqjen në skedar e konvertojnë simbolin e kalimit në një rresht të ri - ‘n’ në kalimin në një rresht të ri (sikur të mos tingëllojë se kjo është qesharake). Prandaj, rreshti bosh sipër është simboli për kodin 01110. Për kodin 00 simboli është hapsira në fillim të rreshtit. Menjëherë duhet thënë se koeficienti ynë ka vdekur - ky mënyrë ruajtje e tabelës mund të pretendojë për më të pambrojtur. Por ai është i thjeshtë për t'u kuptuar dhe zbatuar. Me kënaqësi do të dëgjoj rekomandimet tuaja në komente për optimizimin.
Duke pasur këtë tabelë, është shumë e thjeshtë të dekodosh. Le ta kujtojmë se cilës rregull jemi drejtuar gjatë krijimit të kodimit:
Asnjë kod nuk duhet të jetë prefiks i një tjetri.
Këtu vërtet luan një rol lehtësues. Ne lexojmë rresht pas rreshti bit për bit, dhe sa herë që stringu i marrë d, që përbëhet nga bitët e lexuar, përputhet me kodimin përkatës të simbolit character, ne menjëherë e dimë se simboli character u kodua (dhe vetëm ai!). Më pas, shkruajmë character në stringun dekodues (stringu që përmban mesazhin e dekoduar), e zbrazim stringun d, dhe lexojmë më tutje skedarin e koduar.
Implementimi
Ka ardhur koha të poshtëroj kodin tim dhe të shkruaj një arkivues. Ta quajmë atë Compressor.
Le të fillojmë nga fillimi. Gjëja e parë që shkruajmë është klasa Node:
public class Node {
private int frekuenca; //frequence
private char letra; //letter
private Node fëmijaMajtas; //left child
private Node fëmijaDjathtas; //right child
public Node(char letra, int frekuenca) { //constructor
this.letra = letra;
this.frekuenca = frekuenca;
}
public Node() {} //constructor overload for unnamed nodes (see above in the Huffman tree construction section)
public void shtoFëmijën(Node nodeINdritë) { //add child
if (fëmijaMajtas == null) //if left is empty => right is also empty => add to left
fëmijaMajtas = nodeINdritë;
else {
if (fëmijaMajtas.getFrekuenca() <= nodeINdritë.getFrekuenca()) //basically, left child
fëmijaDjathtas = nodeINdritë; //will be the one with lesser frequency
else {
fëmijaDjathtas = fëmijaMajtas;
fëmijaMajtas = nodeINdritë;
}
}
frekuenca += nodeINdritë.getFrekuenca(); //final frequency
}
public Node getFëmijaMajtas() {
return fëmijaMajtas;
}
public Node getFëmijaDjathtas() {
return fëmijaDjathtas;
}
public int getFrekuenca() {
return frekuenca;
}
public char getLetra() {
return letra;
}
public boolean ështëGjethe() { //check for leaf
return fëmijaMajtas == null && fëmijaDjathtas == null;
}
}
Tani pemën:
class BinaryTree {
private Node rrënja;
public BinaryTree() {
rrënja = new Node();
}
public BinaryTree(Node rrënja) {
this.rrënja = rrënja;
}
public int getFrekuenca() {
return rrënja.getFrekuenca();
}
public Node getRrëna() {
return rrënja;
}
}
Rradha me prioritet:
import java.util.ArrayList; //yes, the queue will be based on a list
class PriorityQueue {
private ArrayList të dhënat; //queue list
private int nElemente; //number of elements in the queue
public PriorityQueue() {
të dhënat = new ArrayList();
nElemente = 0;
}
public void inserto(BinaryTree pemëERe) { //insertion
if (nElemente == 0)
të dhënat.add(pemëERe);
else {
for (int i = 0; i pemëERe.getFrekuenca()) { //if the frequency of the inserted tree is lesser
të dhënat.add(i, pemëERe); //than the current freq., shift all trees to the right by 1
break; //then place the new tree at the position of the current
}
if (i == nElemente - 1)
të dhënat.add(pemëERe);
}
}
nElemente++; //increase the number of elements by 1
}
public BinaryTree heq() { //removal from queue
BinaryTree tmp = të dhënat.get(0); //copy the element to be removed
të dhënat.remove(0); //remove it
nElemente--; //decrease the number of elements by 1
return tmp; //return the removed element (the one with the lowest frequency)
}
}
Klasi që krijon pemën e Huffman-it:
publik klase HuffmanTree {
private final byte SIZE_TABELËS_SEKRETE = 127; // gjatësi e tabelës së kodimit
private String unëString; // mesazhi
private BinaryTree huffmanTree; // pema Huffman
private int[] freqArray; // tabela e frekuencës
private String[] encodingArray; // tabela e kodimit
// ----------------constructor----------------------
publik HuffmanTree(String newString) {
unëString = newString;
freqArray = new int[SIZE_TABELËS_SEKRETE];
mbushFrekuencënArray();
huffmanTree = merrHuffmanTree();
encodingArray = new String[SIZE_TABELËS_SEKRETE];
mbushEncodingArray(huffmanTree.getRoot(), "", "");
}
// --------------------tabela e frekuencës------------------------
private void mbushFrekuencënArray() {
për (int i = 0; i < unëString.length(); i++) {
freqArray[(int)unëString.charAt(i)]++;
}
}
publik int[] merrFrekuencënArray() {
return freqArray;
}
// ------------------------krijimi i pemës huffman------------------
private BinaryTree merrHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
// algoritmi i përshkruar më lart
për (int i = 0; i < SIZE_TABELËS_SEKRETE; i++) {
nëse (freqArray[i] != 0) { // nëse simboli ekziston në varg
Node newNode = new Node((char) i, freqArray[i]); // atëherë krijo një Node për të
BinaryTree newTree = new BinaryTree(newNode); // dhe për Node krijo një BinaryTree
pq.insert(newTree); // futni në radhë
}
}
ndërsa (true) {
BinaryTree tree1 = pq.remove(); // nxirre nga radhë të parën pemë.
përpiqem {
BinaryTree tree2 = pq.remove(); // nxirre nga radhë të dytën pemë
Node newNode = new Node(); // krijo një Node të ri
newNode.addChild(tree1.getRoot()); // bëji fëmijët dy pemët e nxjerra
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} kapërcej (IndexOutOfBoundsException e) { // mbeti një pemë në radhë
kthehu tree1;
}
}
}
publik BinaryTree merrPemën() {
return huffmanTree;
}
// -------------------tabela e kodimit------------------
void mbushEncodingArray(Node node, String codeBefore, String direction) { // mbush tabelën e kodimit
nëse (node.isLeaf()) {
encodingArray[(int)node.getLetter()] = codeBefore + direction;
} tjetër {
mbushEncodingArray(node.getLeftChild(), codeBefore + direction, "0");
mbushEncodingArray(node.getRightChild(), codeBefore + direction, "1");
}
}
String[] merrEncodingArray() {
return encodingArray;
}
publik void shfaqEncodingArray() { // për debuggim
mbushEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Tabela e kodimit====================");
për (int i = 0; i < SIZE_TABELËS_SEKRETE; i++) {
nëse (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
}
}
System.out.println("========================================================");
}
// -----------------------------------------------------
String merrStringunOrigjinal() {
return unëString;
}
}
Klasa, e cila kodon/dekodon:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; //gjerësia e tabelës
private HuffmanTree mainHuffmanTree; //pema e Huffman-it (kështu përdoret vetëm për kompresim)
private String myString; //mesazhi origjinal
private int[] freqArray; //tabela e frekuencës
private String[] encodingArray; //tabela e kodimit
private double ratio; //koeficienti i kompresimit
public HuffmanOperator(HuffmanTree MainHuffmanTree) { //për kompresim
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} //për nxjerrje;
//---------------------------------------kompresimi-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; //string ndërmjetës (pa të shtuar zero)
//System.out.println("=============================Kompresimi=======================");
//displayEncodingArray();
for (int i = 0; i
//duhet të shtojmë zero në fund (mund të jetë 1, nuk ka rëndësi)
byte counter = 0; //numri i zero-ve të shtuar në fund (1 byte është i mjaftueshëm: 0 <= counter < 8 < 127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) { //delta - numri i zero-ve të shtuar
intermidiate += "0";
}
//bashko numrin e zero-ve të shtuar në përfaqësimin binar dhe stringun ndërmjetës
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
//koeficienti ideal
setCompressionRatio();
//System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() { //llogarit koeficientin ideal
double sumA = 0, sumB = 0; //A-shuma origjinale
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() { //kompresimi përfundimtar
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;
}
//---------------------------------------fundi i kompresimit----------------------------------------------------------------
//------------------------------------------------------------nxjerrje-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
//displayEncodingArray();
//merr numrin e zero-ve të futur
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, pasi bajti i parë është numri i zero-ve të shtuar
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) { //nëse përputhet
decompressed += (char)j; //atëherë shto elementin
current = ""; //dhe reset bëj aktualin
}
}
}
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() { //për debug
System.out.println("======================Tabela e kodimit====================");
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("========================================================");
}
}
Klasi që lehtëson shkruajtjen në skedar:
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("Rruga e pavlefshme, ose skedari nuk ekziston!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Klasi që lehtëson leximin nga skedari:
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) // nëse skedari përfundon
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Dhe klasa kryesore:
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 { // ne tregoni udhëzimin përmes argumenteve të vijës së komandës
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("Forma e hyrjes së argumenteve është e gabuar ");
System.out.println("Lexoni 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("Rruga e gabuar ose nuk ekziston një skedar i tillë!");
return;
} catch (MalformedInputException e) {
System.out.println("Kodimi aktual i skedarit nuk mbështetet");
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());
}
// krijoni një skedar me tabelën e kodimit:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Rruga për skedarin e kompresuar: " + compressedFile.getAbsolutePath());
System.out.println("Rruga për tabelën e kodimit " + table.getAbsolutePath());
System.out.println("Pa tabelën skedari do të jetë e pamundur të nxirret!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100; // koeficienti ideal
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100; // koeficienti real
System.out.println("Koeficienti i kompresionit ideal është " + idealRatio);
System.out.println("Koeficienti i kompresionit me tabelën e kodimit " + 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];
// lexoni skedarin e kompresuar
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! kontrolloni këtu:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte(); // metoda kthen EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
// --------------------
// lexoni tabelën e kodimit:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine(); // kaloni stringun e parë të zbrazët
encodingArray[(byte)'n'] = fi.readLine(); // lexoni kodin për '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();
// nxirrni:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Rruga për skedarin e shpërbërë " + extractedFile.getAbsolutePath());
}
}
Skedha me udhëzime readme.txt do ta shkruani vetë 🙂
Përfundim
Mendoj se kjo është gjithçka që doja të thoja. Nëse keni diçka për të thënë rreth paqartësisë sime në përmirësimet e kodit, algoritmit, ose ndonjë optimizimi, mos hezitoni të shkruani. Nëse kam lënë diçka të paqartë, gjithashtu shkruani. Do të jem i lumtur të dëgjoj mendimet tuaja në komentet!
P.S.
Po, po, kam ende këtu, sepse nuk e kam harruar koeficientin. Për vargun s1, tabela e kodimit peshon 48 byte — shumë më tepër se skedha origjinale, dhe nuk harrojmë për zero të shtuar (numri i zerove të shtuar është 7) => koeficienti i kompresimit do të jetë më i vogël se një: 176/(65 + 48*8 + 7)=0.38. Nëse e vëreni këtë, atëherë nuk jeni vetëm një fytyrë e mirë. Po, kjo realizim do të ishte jashtëzakonisht joefikase për skedarët e vegjël. Por çfarë ndodh me skedarët e mëdhenj? Dimensionet e skedarëve tejkalojnë shumë madhësinë e tabelës së kodimit. Këtu algoritmi funksionon ashtu siç duhet! Për shembull, për arkivatori jep një koeficient real (jo idealizuar), i barabartë me 1.46 — pothuajse një herë e gjysmë! Dhe po, ishte parashikuar që skedha do të ishte në anglisht.
Burimi: habr.com
