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ë. Kështu, , por pa realizimin praktik. Materiali teorik i postit aktual është marrë nga orët e informatikës në shkollë dhe nga libri i Robert Lafore "Strukturat e të Dhënave dhe Algoritmet në Java". Pra, le të fillojmë!
Pak reflektime
Në një skedë teksti të zakonshëm, një simbol kodifikohet me 8 bite (kodimi ASCII) ose 16 (kodimi Unicode). Më tej do të shqyrtojmë kodimin ASCII. Për shembull, le të marrim stringun s1 = «SUSIE SAYS IT IS EASYn». Në total, në string ka 22 simbole, natyrisht, duke përfshirë hapësirat dhe simbolin e kalimit në rresht të ri — ‘n’. Një skedë që përmban këtë string do të peshojë 22*8 = 176 bite. Menjëherë lind pyetja: a është e arsyeshme të përdoren të gjithë 8 bit për kodimin e 1 simbole? Ne nuk përdorim të gjithë simbolet e kodimit ASCII. Edhe po ta bënim, do të ishte më ekonomik të japim kodin më të shkurtër për shkronjën më të shpeshtë — S — dhe për shkronjën më të rrallë — T (ose U, ose ‘n’) — të japim një kod më të gjatë. Kjo është pikërisht ajo që bën algoritmi i Huffman-it: duhet të gjejmë variantin optimal të kodimit, sipas të cilit skeda do të jetë me peshën minimale. Është e natyrshme që simbolet e ndryshme të kenë gjatësira të ndryshme kodimesh — mbi këtë bazohet algoritmi.
Kodimi
Pse simboli 'S' nuk do të ketë një kod, për shembull, me gjatësi 1 bit: 0 ose 1. Le të jetë ky 1. Atëherë simbolit tjetër më shpesh të shfaqur — ‘ ‘ (hapësira) — t'i japim 0. Imagjinoni se keni filluar të dekodoni mesazhin tuaj — stringun e koduar s1 — dhe shihni se kodi fillon me 1. Çfarë duhet bërë: a është ky simbol S, apo një simbol tjetër, për shembull A? Prandaj ndodhet një rregull i rëndësishëm:
Asnjë kod nuk duhet të jetë prefiks i një tjetri
Ky rregull është thelbësor në algoritëm. Prandaj, krijimi i kodit fillon me tabelën e frekuencës, e cila tregon frekuencën (numrin e shfaqjeve) të çdo simboli:
Simbolet me numrin më të madh të shfaqjeve duhet të kodohen me sa më pak bitë të mundshme. Më lejoni t'ju jap një shembull të një prej tabelave të mundshme të kodit:
Pra, 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 Kodi i çdo simboli e kam ndarë me hapësirë. Në të vërtetë, në një file të kompresuar nuk do të ketë diçka të tillë!
Këtu lind pyetja: si e shpiku ky fillestar kodin për të krijuar tabelën e kodit? Kjo do të diskutohet më poshtë.
Ndërtimi i pemës së Huffman
Këtu ndihmojnë pemët binarë të kërkimit. Mos u shqetësoni, këtu metodat e kërkimit, shtimit dhe fshirjes nuk do të nevojiten. Ja struktura e pemës në 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;
}
...
}
Ky nuk është kodi i plotë, kodi i plotë do të vijë më poshtë.
Ja algoritmi për ndërtimin e pemës:
- Krijoni një objekt Node për çdo simbol nga mesazhi (stringu s1). Në rastin tonë, do të kemi 9 nyje (objekte Node). Çdo nyje përbëhet nga dy fusha të dhënash: simbol dhe frekuencë.
- Krijoni një objekt Peme (BinaryTree) për secilën nga nyjet Node. Nyja bëhet rrënja e pemës.
- Shtoni këto pemë në radhën prioritare. Sa më e vogël të jetë frekuenca, aq më shumë prioritet ka. Kështu, gjatë nxjerrjes gjithmonë zgjidhet pema me frekuencën më të vogël.
Më pas duhet të bëni ciklikisht si vijon:
- Nxirrni dy pemë nga radha prioritare dhe bëni ato pasardhës të një nyjeje të re (nyja e sapokrijuar pa shkronjë). Frekuenca e nyjes së re është shuma e frekuencave të dy pemëve-pasardhës.
- Për këtë nod, krijoni një pemë me rrënjë në këtë nod. Një këtë pemë futini përsëri në radhën prioritet. (Meqenëse pema ka një frekuencë të re, është e mundur që ajo të vendoset në një vend të ri në radhë)
- Vazhdoni të kryeni hapat 1 dhe 2, derisa në radhë të mbetet vetëm një pemë - pema e Huffmanit
Le t'i hedhim një vështrim këtij algoritmi në vargun s1:
Këtu, simboli «lf» (shkëputje) përfaqëson kalimin në një rresht të ri, ndërsa «sp» (hapësirë) - është një hapësirë.
Çfarë ndodh më pas?
Kemi marrë pemën e Huffmanit. Mirë, dhe çfarë do të bëjmë me të? As që e japin falas. Pas kësaj, duhet të ndiqni të gjitha rrugët e mundshme nga rrënja deri te gjethet e pemës. Le të pranojmë se një skaj 0 është nëse çon te pasardhësi i majtë dhe 1 - nëse te i djathti. Rreptësisht, në këto shenja, kodi i simbolit është rruga nga rrënja e pemës deri te gjethe, që përmban këtë simbol.
Në këtë mënyrë u krijua tabela e kodit. Vërejmë se nëse e shqyrtojmë këtë tabelë, mund të arrijmë në përfundimin për "peshën" e çdo simboli — kjo është gjatësia e kodit të tij. Atëherë, në format 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. Fillimisht, ai peshonte 176 bit. Prandaj, ne e kemi zvogëluar atë me një raport prej 176/65 = 2.7 herë! Por kjo është utopi. Një koeficient i tillë ndoshta nuk do të arrihet. Pse? Për këtë do të flasim pak më vonë.
Dekodimi
Epo, ndoshta ka mbetur më e thjeshta — dekodimi. Mendoj se shumë prej jush e keni kuptuar se nuk mund të krijosh një skedar të kompresuar pa ndonjë aluzion për mënyrën se si ai është koduar — nuk do të mund ta dekodojmë! Po, ishte e vështirë për mua ta kuptoja këtë, por do të duhet të krijojmë një skedar tekstual table.txt me tabelën e kompresimit:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Rekordimi i tabelës në formën ‘simbol’«kode simboli». Pse 01110 pa simbol? Në të vërtetë ka një simbol, thjesht mjetet java që përdora për të shkruar në skedar e kthejnë simbolin e kalimit në linjë - ‘n’ - në kalim në linjë (sa e çuditshme që tingëllon). Prandaj, linja e zbrazët sipër është simboli për kodin 01110. Për kodin 00, simboli është hapësira në fillim të linjës. Menjëherë po e them, që përkoeficientin tonë këtë mënyrë të ruajtjes së tabelës mund të pretendoni për më të pamundurin. Por është e thjeshtë për t'u kuptuar dhe implementuar. Me kënaqësi do të dëgjoj sugjerimet tuaja në komentet në lidhje me optimizimin.
Duke pasur këtë tabelë, është shumë e thjeshtë të dekodosh. Le të kujtojmë se çfarë rregulli ndjekim gjatë krijimit të kodimit:
Asnjë kod nuk duhet të jetë prefiks i kodit tjetër
Këtu është pikërisht ku ai luan një rol lehtësues. Ne lexojmë në mënyrë të vazhdueshme bit pas biti dhe, sa herë që stringu i marrë d, i përbërë nga bitët e lexuar, përputhet me kodimin përkatës të karakterit character, ne menjëherë e dimë se është koduar karakteri character (dhe vetëm ai!). Më pas shkruajmë karakterin character në stringun dekodues (stringu që përmban mesazhin e dekoduar), e nullojmë stringun d, dhe lexojmë më tej skedarin e koduar.
Realizimi
Ka ardhur koha për të poshtëruar kodin tim për të shkruar një arkivues. Ta quajmë Compressor.
Të fillojmë nga e para. Së pari, shkruajmë klasën Node:
public class Node {
private int frekuenca;\/\/frekuenca
private char shkronjë;\/\/shkronjë
private Node djaliMajtas;\/\/djali majtas
private Node djaliDjathtas;\/\/djali djathtas
public Node(char shkronjë, int frekuenca) { \/\/në fakt, konstruktori
this.shkronjë = shkronjë;
this.frekuenca = frekuenca;
}
public Node() {}\/\/mbingarkimi i konstruktori për nodet pa emër (shih më sipër në seksionin për ndërtimin e pemës Huffman)
public void shtoDjalë(Node djalëIri) {\/\/shto djalin
if (djaliMajtas == null)\/\/nëse majtas është bosh => djali djathtas gjithashtu është bosh => shto në majtas
djaliMajtas = djalëIri;
else {
if (djaliMajtas.getFrekuenca() <= djalëIri.getFrekuenca()) \/\/në përgjithësi, djali majtas
djaliDjathtas = djalëIri;\/\/do të jetë ai me më pak frekuencë
else {
djaliDjathtas = djaliMajtas;
djaliMajtas = djalëIri;
}
}
frekuenca += djalëIri.getFrekuenca();\/\/frekuenca totale
}
public Node getDjaliMajtas() {
return djaliMajtas;
}
public Node getDjaliDjathtas() {
return djaliDjathtas;
}
public int getFrekuenca() {
return frekuenca;
}
public char getShkronjë() {
return shkronjë;
}
public boolean ështëGjethe() {\/\/kontroll në gjethe
return djaliMajtas == null && djaliDjathtas == 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ënja() {
return rrënja;
}
}
Radhit e prioritetit:
import java.util.ArrayList;//po, radhit do të bazohet në një listë
class PriorityQueue {
private ArrayList<BinaryTree> data;//lista e radhës
private int nElems;//numri i elementeve në radhë
public PriorityQueue() {
data = new ArrayList<BinaryTree>();
nElems = 0;
}
public void insert(BinaryTree newTree) {//shtimi
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i < nElems; i++) {
if (data.get(i).getFrequence() > newTree.getFrequence()) {//nëse frekuenca e pemës së shtuar është më e vogël
data.add(i, newTree);//se sa frekuenca e aktualeve, atëherë lëvizim të gjitha pemët në pozitat e djathta një hap më tej
break;//pastaj vendosim pemën e re në pozitën e aktuales
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++;//rrit numrin e elementeve me 1
}
public BinaryTree remove() {//heqja nga radhë
BinaryTree tmp = data.get(0);//kopjojmë elementin që do të hiqet
data.remove(0);//në fakt, i heqim
nElems--;//ulen numri i elementeve me 1
return tmp;//kemi kthyer elementin e hequr (elementi me frekuencën më të vogël)
}
}
Klasa që krijon pemën e Huffmanit:
publike klas HuffmanTree {
private final byte TAVANI_I_TABELËS_SE_KODIMIT = 127; // gjatësia e tabelës së kodimit
private String myString; // mesazhi
private BinaryTree huffmanTree; // pemën e Huffman
private int[] freqArray; // tabela e frekuencave
private String[] encodingArray; // tabela e kodimit
// ----------------constructor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[TAVANI_I_TABELËS_SE_KODIMIT];
plotFrekuencënArray();
huffmanTree = merrHuffmanTree();
encodingArray = new String[TAVANI_I_TABELËS_SE_KODIMIT];
plotEncodingArray(huffmanTree.getRoot(), "", "");
}
// --------------------frekuencën array------------------------
private void plotFrekuencënArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrekuencënArray() {
return freqArray;
}
// ------------------------krijimi i pemës huffman------------------
private BinaryTree merrHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
// algoritmi i përshkruar më sipër
for (int i = 0; i < TAVANI_I_TABELËS_SE_KODIMIT; i++) {
if (freqArray[i] != 0) { // nëse simbolet ekzistojnë në vargun
Node newNode = new Node((char) i, freqArray[i]); // krijo një Node për të
BinaryTree newTree = new BinaryTree(newNode); // krijo një BinaryTree për Node
pq.insert(newTree); // fut në radhë
}
}
while (true) {
BinaryTree tree1 = pq.remove(); // nxjerr për të parën pemë nga radhë.
try {
BinaryTree tree2 = pq.remove(); // nxjerr për të dytën pemë nga radhë
Node newNode = new Node(); // krijo një Node të ri
newNode.addChild(tree1.getRoot()); // bëj si fëmijë të dy pemët e nxjerra
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode));
} catch (IndexOutOfBoundsException e) { // ka mbetur një pemë në radhë
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
// -------------------tabela e kodimit------------------
void plotEncodingArray(Node node, String codeBefore, String direction) { // plot kodin e tabelës
if (node.isLeaf()) {
encodingArray[(int)node.getLetter()] = codeBefore + direction;
} else {
plotEncodingArray(node.getLeftChild(), codeBefore + direction, "0");
plotEncodingArray(node.getRightChild(), codeBefore + direction, "1");
}
}
String[] getEncodingArray() {
return encodingArray;
}
public void displayEncodingArray() { // për debugging
plotEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Tabela e kodimit====================");
for (int i = 0; i < TAVANI_I_TABELËS_SE_KODIMIT; i++) {
if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
}
}
System.out.println("========================================================");
}
// -----------------------------------------------------
String getOriginalString() {
return myString;
}
}
Klasa që përmban kodin që kodon/dekodon:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127; // gjatësi e tabelës
private HuffmanTree mainHuffmanTree; // pema e Huffmanit (përdoret vetëm për kompresim)
private String myString; // mesazhi origjinal
private int[] freqArray; // tabela e frekuencës
private String[] encodingArray; // tabela e kodifikimit
private double ratio; // koeficienti i kompresimit
public HuffmanOperator(HuffmanTree MainHuffmanTree) { // për kompresion
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {} // për nxjerrje;
// ---------------------------------------kompresim-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = ""; // string ndërmjetës (pa zero shtesë)
// 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 zerove të shtuar në fund (një byte është mjaft: 0 <= counter < 8 < 127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) { // delta - numri i zerove të shtuar
intermidiate += "0";
}
// bashko numrin e zerove të shtuar në prezantimin 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;
}
// ---------------------------------------mbarimi i kompresimit----------------------------------------------------------------
// ------------------------------------------------------------nxjerrje-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
// displayEncodingArray();
// merr numrin e zerove të shtuar
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, sepse byte i parë është numri i zerove 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ë shtojmë elementin
current = ""; // dhe resetojmë stringun aktual
}
}
}
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 kodifikimit====================");
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("========================================================");
}
}
Klasë që lehtëson shkruarjen 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 gabuar, ose skedari nuk ekziston!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
Klasë 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) //kur është fundi i skedarit
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
Pra, 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 {//specify instruction using command line arguments
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 papërshtatshme ");
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, apo ky skedar nuk ekziston!");
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());
}
//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("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ë, skedari nuk do të mund 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 i vërtetë
System.out.println("Koeficienti ideal i kompresionit është " + idealRatio);
System.out.println("Koeficienti i kompresionit duke marrë parasysh 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];
//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("Rruga për skedarin e pakompresuar " + extractedFile.getAbsolutePath());
}
}
Ju ushtarëve përshkrimi readme.txt duhet ta shkruani vetë 🙂
Përfundimi
Ndoshta, kjo është gjithçka që doja të thosha. Nëse keni diçka për të thënë në lidhje me papërgjegjësinë time për përmirësimet në kod, algoritëm, apo ndonjë optimizim tjetër, mos hezitoni të shkruani. Nëse kam lënë diçka pa e shpjeguar, gjithashtu shkruani. Do të jem i lumtur të dëgjoj mendimet tuaja në komentet!
P.S.
Po, po, unë ende jam këtu, sepse nuk e kam harruar raportin. Për stringun s1, tabela e kodimit peshon 48 byte — shumë më tepër se skedari origjinal, dhe gjithashtu s'kemi harruar për zerot shtesë (numri i zerove shtesë është 7) => raporti i kompresionit do të jetë më i vogël se një: 176/(65 + 48*8 + 7)=0.38. Nëse ju e keni vënë re këtë, atëherë vetëm mos u bëni të mençur! Po, kjo implementim do të jetë jashtëzakonisht e pafavorshme për skedarët e vegjël. Por çfarë ndodh me skedarët e mëdhenj? Dimensionet e skedarit tejkalojnë ndjeshëm madhësinë e tabelës së kodimit. Këtu algoritmi funksionon si duhet! Për shembull, për arkivatori jep një raport real (jo idealizuar), i barabartë me 1.46 — pothuajse një herë e gjysmë! Dhe po, pritej që skedari të ishte në anglisht.
Burimi: habr.com
