हफ़मैन डेटा संपीड़न

प्रविष्टि

इस लेख में मैं जाने-माने हफ़मैन एल्गोरिथ्म के बारे में बात करूंगा, साथ ही साथ डेटा कंप्रेशन में इसके एप्लिकेशन भी।

नतीजतन, हम एक साधारण अभिलेखागार लिखेंगे। हैबे पर इसके बारे में पहले से ही एक लेख था, लेकिन व्यावहारिक कार्यान्वयन के बिना। वर्तमान पोस्ट की सैद्धांतिक सामग्री स्कूल कंप्यूटर विज्ञान के पाठ और रॉबर्ट लॉर की पुस्तक "डेटा स्ट्रक्चर्स एंड अल्गोरिद्म इन जावा" से ली गई है। तो, सब कुछ कटौती के तहत है!

थोड़ा सोचा

एक सादे पाठ फ़ाइल में, एक वर्ण 8 बिट्स (ASCII एन्कोडिंग) या 16 (यूनिकोड एन्कोडिंग) के साथ एन्कोड किया गया है। इसके अलावा हम ASCII एन्कोडिंग पर विचार करेंगे। उदाहरण के लिए, लाइन s1 = "SUSIE SAYS IT IS EASY \ n" को लें। कुल मिलाकर, लाइन में 22 अक्षर हैं, ज़ाहिर है, जिसमें रिक्त स्थान और न्यूलाइन वर्ण शामिल हैं - '\ n'। इस लाइन वाली फाइल का वजन 22 * ​​8 = 176 बिट्स होगा। प्रश्न तुरंत उठता है: क्या 1 वर्ण को एनकोड करने के लिए सभी 8 बिट्स का उपयोग करना तर्कसंगत है? हम सभी ASCII वर्णों का उपयोग नहीं करते हैं। यहां तक ​​कि अगर इस्तेमाल किया जाता है, तो यह सबसे अधिक बार पत्र के लिए अधिक तर्कसंगत होगा - एस - कम से कम संभव कोड देने के लिए, और दुर्लभ पत्र के लिए - टी (या यू, या 'एन') - और अधिक प्रामाणिक कोड देने के लिए। यह हफ़मैन एल्गोरिथ्म है: आपको सबसे अच्छा एन्कोडिंग विकल्प खोजने की आवश्यकता है, जिसमें फ़ाइल न्यूनतम वजन की होगी। यह बिल्कुल सामान्य है कि कोड की लंबाई अलग-अलग वर्णों के लिए अलग-अलग होगी - यह एल्गोरिथ्म का आधार है।

कोडिंग

वर्ण को 'S' कोड क्यों नहीं दिया जाता है, उदाहरण के लिए, 1 बिट लंबा: 0 या 1. इसे 1. होने दें। फिर हम दूसरा सबसे ज्यादा दिया जाने वाला वर्ण देंगे - '' (स्पेस) - 0. कल्पना कीजिए, आपने अपना संदेश डिकोड करना शुरू कर दिया है - एन्कोडेड स्ट्रिंग s1 - और आप देखते हैं कि कोड 1 से शुरू होता है। तो क्या करें: क्या यह एक चरित्र S है, या यह कुछ अन्य वर्ण है, उदाहरण के लिए A? इसलिए, एक महत्वपूर्ण नियम उत्पन्न होता है:

कोई भी कोड दूसरे का उपसर्ग नहीं होना चाहिए

यह नियम एल्गोरिथ्म की कुंजी है। इसलिए, कोड का निर्माण आवृत्ति तालिका से शुरू होता है, जो प्रत्येक वर्ण की आवृत्ति (घटनाओं की संख्या) को इंगित करता है:

सबसे अधिक घटनाओं वाले पात्रों को बिट्स की सबसे छोटी संभव संख्या के साथ एन्कोड किया जाना चाहिए। मैं संभावित कोड तालिकाओं में से एक का उदाहरण दूंगा:

इस प्रकार, एन्कोडेड संदेश इस तरह दिखेगा:

10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 

मैंने प्रत्येक वर्ण के कोड को एक स्थान के साथ अलग कर दिया। यह वास्तव में एक संपीड़ित फ़ाइल में नहीं होगा!
सवाल उठता है: यह सलागा एक कोड के साथ कैसे आया ? एक कोड तालिका कैसे बनाएं? इस पर नीचे चर्चा की जाएगी।

हफमैन पेड़ का निर्माण

यहां बाइनरी सर्च ट्री बचाव के लिए आते हैं। चिंता न करें, यहां खोज, सम्मिलन और हटाने के तरीकों की आवश्यकता नहीं है। यहाँ जावा में पेड़ की संरचना है:

 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; } ... } 

यह एक पूर्ण कोड नहीं है, पूर्ण कोड नीचे होगा।

यहाँ ट्री बिल्डिंग एल्गोरिथम है:

1. संदेश (पंक्ति s1) से प्रत्येक वर्ण के लिए एक नोड ऑब्जेक्ट बनाएं। हमारे मामले में, 9 नोड्स (नोड ऑब्जेक्ट) होंगे। प्रत्येक नोड में दो डेटा फ़ील्ड होते हैं: प्रतीक और आवृत्ति
2. प्रत्येक नोड नोड्स के लिए ट्री ऑब्जेक्ट (बाइनरीट्री) बनाएं। नोड वृक्ष की जड़ बन जाता है।
3. इन पेड़ों को प्राथमिकता कतार में चिपकाएं। आवृत्ति जितनी कम होगी, प्राथमिकता उतनी ही अधिक होगी। इस प्रकार, जब निकालने, dervo हमेशा सबसे कम आवृत्ति के साथ चुना जाता है।

अगला, आपको निम्नलिखित चक्रवात करने की आवश्यकता है:

1. प्राथमिकता कतार से दो पेड़ निकालें और उन्हें नए नोड (एक पत्र के बिना नव निर्मित नोड) के वंशज बनाएं। नए नोड की आवृत्ति दो वंशज पेड़ों की आवृत्तियों के योग के बराबर है।
2. इस नोड के लिए, इस नोड में एक जड़ के साथ एक पेड़ बनाएं। इस पेड़ को प्राथमिकता कतार में वापस चिपकाएँ। (चूंकि पेड़ में एक नई आवृत्ति होती है, तो सबसे अधिक संभावना है कि यह कतार में एक नए स्थान पर पहुंच जाएगा)
3. चरण 1 और 2 को जारी रखें जब तक कि कतार में केवल एक ही पेड़ न बचा हो - हफ़मैन पेड़

लाइन s1 पर इस एल्गोरिथ्म पर विचार करें:



यहाँ, प्रतीक "lf" (लाइनफीड) एक नई लाइन में संक्रमण को इंगित करता है, "sp" (स्पेस) एक स्पेस है।

आगे क्या है?

हमें हफ़मैन का पेड़ मिला। अच्छा, ठीक है। और इसके साथ क्या करना है? वे इसे मुफ्त में नहीं ले सकते। और फिर, आपको रूट से लेकर पेड़ की पत्तियों तक सभी संभावित रास्तों को ट्रैक करना होगा। आइए हम किनारे को नामित करने के लिए सहमत हों 0 यदि यह बाएं वंशज की ओर जाता है और 1 अगर दाईं ओर। कड़ाई से बोलते हुए, इन सूचनाओं में, प्रतीक कोड पेड़ की जड़ से चादर तक का मार्ग है जिसमें यह समान प्रतीक है।



इस प्रकार, कोड की तालिका बदल गई। ध्यान दें कि यदि हम इस तालिका पर विचार करते हैं, तो हम प्रत्येक वर्ण के "वजन" के बारे में निष्कर्ष निकाल सकते हैं - यह उसके कोड की लंबाई है। फिर संपीड़ित फ़ाइल का वजन होगा: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 बिट्स। शुरू में इसका वजन 176 बिट्स था। इसलिए, हमने इसे 176/65 = 2.7 गुना तक घटा दिया! लेकिन यह यूटोपिया है। ऐसा गुणांक प्राप्त होने की संभावना नहीं है। क्यों? इस पर थोड़ी देर बाद चर्चा की जाएगी।

डिकोडिंग

खैर, शायद सबसे सरल बात छोड़ दी गई है। मुझे लगता है कि आप में से कई लोगों ने अनुमान लगाया है कि बिना किसी संकेत के केवल एक संपीड़ित फ़ाइल बनाना असंभव है, जिसे कूटबद्ध किया गया था - हम इसे डिकोड नहीं कर पाएंगे! हां, यह महसूस करना मेरे लिए कठिन था, लेकिन मुझे एक टेक्स्ट फाइल टेबल बनाना पड़ा। एक कम्प्रेशन टेबल के साथ।

 01110 00 A010 E1111 I110 S10 T0110 U01111 Y1110 

तालिका को 'चरित्र' "वर्ण कोड" के रूप में रिकॉर्ड करें। एक वर्ण के बिना 01110 क्यों है? वास्तव में, यह एक प्रतीक के साथ है, बस मेरे द्वारा उपयोग किए जाने वाले जावा उपकरण जब एक फ़ाइल के लिए आउटपुट करते हैं, तो newline वर्ण - '\ n' - को एक नई पंक्ति में बदल दिया जाता है (कोई फर्क नहीं पड़ता कि यह कितना बेवकूफ लगता है)। इसलिए, शीर्ष पर खाली रेखा कोड 01110 के लिए वर्ण है। कोड 00 के लिए, वर्ण पंक्ति की शुरुआत में एक स्थान है। मुझे तुरंत कहना होगा कि इस तालिका को संग्रहीत करने का हमारा तरीका सबसे तर्कहीन हो सकता है। लेकिन इसे समझना और लागू करना सरल है। अनुकूलन के संबंध में टिप्पणियों में आपकी सिफारिशें सुनकर मुझे प्रसन्नता होगी।

इस तालिका को डिकोड करना बहुत आसान है। एन्कोडिंग बनाते समय हमें किस नियम द्वारा निर्देशित किया गया था उसे याद करें:

किसी भी कोड को दूसरा उपसर्ग नहीं करना चाहिए

यह वह जगह है जहाँ यह एक सुविधाजनक भूमिका निभाता है। हम क्रमिक रूप से बिट द्वारा पढ़ते हैं और, जैसे ही प्राप्त स्ट्रिंग डी, रीड बिट्स से मिलकर बनता है, चरित्र चरित्र के अनुरूप एन्कोडिंग से मेल खाता है, हम तुरंत जानते हैं कि चरित्र चरित्र एन्कोडेड था (और केवल यह!)। इसके बाद, हम डिकोडिंग लाइन (डिकोड किए गए संदेश वाली लाइन) में वर्ण लिखते हैं, लाइन d को शून्य करते हैं, और फिर एन्कोडेड फ़ाइल को पढ़ते हैं।

कार्यान्वयन

यह एक अभिलेखागार लिखकर मेरे कोड को अपमानित करने का समय है। चलो इसे कंप्रेसर कहते हैं।

शुरू से शुरू करते हैं। सबसे पहले, हम नोड वर्ग लिखते हैं:

 public class Node { private int frequence;// private char letter;// private Node leftChild;//  private Node rightChild;//  public Node(char letter, int frequence) { //,  this.letter = letter; this.frequence = frequence; } public Node() {}//    (.       ) public void addChild(Node newNode) {//  if (leftChild == null)//  =>  =>    leftChild = newNode; else { if (leftChild.getFrequence() <= newNode.getFrequence()) // ,   rightChild = newNode;// ,     else { rightChild = leftChild; leftChild = newNode; } } frequence += newNode.getFrequence();//  } public Node getLeftChild() { return leftChild; } public Node getRightChild() { return rightChild; } public int getFrequence() { return frequence; } public char getLetter() { return letter; } public boolean isLeaf() {//   return leftChild == null && rightChild == null; } } 

अब पेड़:

 class BinaryTree { private Node root; public BinaryTree() { root = new Node(); } public BinaryTree(Node root) { this.root = root; } public int getFrequence() { return root.getFrequence(); } public Node getRoot() { return root; } } 

प्राथमिकता कतार:

 import java.util.ArrayList;//-,      class PriorityQueue { private ArrayList<BinaryTree> data;//  private int nElems;//-    public PriorityQueue() { data = new ArrayList<BinaryTree>(); nElems = 0; } public void insert(BinaryTree newTree) {// if (nElems == 0) data.add(newTree); else { for (int i = 0; i < nElems; i++) { if (data.get(i).getFrequence() > newTree.getFrequence()) {//     data.add(i, newTree);// . ,  c       1  break;//       } if (i == nElems - 1) data.add(newTree); } } nElems++;// -   1 } public BinaryTree remove() {//   BinaryTree tmp = data.get(0);//   data.remove(0);//,  nElems--;// -   1 return tmp;//  (   ) } } 

वह वर्ग जो हफ़मैन वृक्ष बनाता है:

 public class HuffmanTree { private final byte ENCODING_TABLE_SIZE = 127;//   private String myString;// private BinaryTree huffmanTree;//  private int[] freqArray;//  private String[] encodingArray;//  //----------------constructor---------------------- public HuffmanTree(String newString) { myString = newString; freqArray = new int[ENCODING_TABLE_SIZE]; fillFrequenceArray(); huffmanTree = getHuffmanTree(); encodingArray = new String[ENCODING_TABLE_SIZE]; fillEncodingArray(huffmanTree.getRoot(), "", ""); } //--------------------frequence array------------------------ private void fillFrequenceArray() { for (int i = 0; i < myString.length(); i++) { freqArray[(int)myString.charAt(i)]++; } } public int[] getFrequenceArray() { return freqArray; } //------------------------huffman tree creation------------------ private BinaryTree getHuffmanTree() { PriorityQueue pq = new PriorityQueue(); //   for (int i = 0; i < ENCODING_TABLE_SIZE; i++) { if (freqArray[i] != 0) {//     Node newNode = new Node((char) i, freqArray[i]);//    Node BinaryTree newTree = new BinaryTree(newNode);//  Node  BinaryTree pq.insert(newTree);//   } } while (true) { BinaryTree tree1 = pq.remove();//    . try { BinaryTree tree2 = pq.remove();//     Node newNode = new Node();//  Node newNode.addChild(tree1.getRoot());//      newNode.addChild(tree2.getRoot()); pq.insert(new BinaryTree(newNode); } catch (IndexOutOfBoundsException e) {//     return tree1; } } } public BinaryTree getTree() { return huffmanTree; } //-------------------encoding array------------------ void fillEncodingArray(Node node, String codeBefore, String direction) {//   if (node.isLeaf()) { encodingArray[(int)node.getLetter()] = codeBefore + direction; } else { fillEncodingArray(node.getLeftChild(), codeBefore + direction, "0"); fillEncodingArray(node.getRightChild(), codeBefore + direction, "1"); } } String[] getEncodingArray() { return encodingArray; } public void displayEncodingArray() {//  fillEncodingArray(huffmanTree.getRoot(), "", ""); System.out.println("======================Encoding table===================="); for (int i = 0; i < ENCODING_TABLE_SIZE; i++) { if (freqArray[i] != 0) { System.out.print((char)i + " "); System.out.println(encodingArray[i]); } } System.out.println("========================================================"); } //----------------------------------------------------- String getOriginalString() { return myString; } } 

वह वर्ग जिसमें एनकोड / डीकोड है:

 public class HuffmanOperator { private final byte ENCODING_TABLE_SIZE = 127;//  private HuffmanTree mainHuffmanTree;//  (   ) private String myString;//  private int[] freqArray;//  private String[] encodingArray;//  private double ratio;//  public HuffmanOperator(HuffmanTree MainHuffmanTree) {//for compress this.mainHuffmanTree = MainHuffmanTree; myString = mainHuffmanTree.getOriginalString(); encodingArray = mainHuffmanTree.getEncodingArray(); freqArray = mainHuffmanTree.getFrequenceArray(); } public HuffmanOperator() {}//for extract; //---------------------------------------compression----------------------------------------------------------- private String getCompressedString() { String compressed = ""; String intermidiate = "";// (  ) //System.out.println("=============================Compression======================="); //displayEncodingArray(); for (int i = 0; i < myString.length(); i++) { intermidiate += encodingArray[myString.charAt(i)]; } //      .       8=> //    ( 1,  ) byte counter = 0;//     (   : 0<=counter<8<127) for (int length = intermidiate.length(), delta = 8 - length % 8; counter < delta ; counter++) {//delta -    intermidiate += "0"; } // -         compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate; //  setCompressionRatio(); //System.out.println("==============================================================="); return compressed; } private void setCompressionRatio() {//   double sumA = 0, sumB = 0;//A-the original sum for (int i = 0; i < ENCODING_TABLE_SIZE; i++) { if (freqArray[i] != 0) { sumA += 8 * freqArray[i]; sumB += encodingArray[i].length() * freqArray[i]; } } ratio = sumA / sumB; } public byte[] getBytedMsg() {//final compression StringBuilder compressedString = new StringBuilder(getCompressedString()); byte[] compressedBytes = new byte[compressedString.length() / 8]; for (int i = 0; i < compressedBytes.length; i++) { compressedBytes[i] = (byte) Integer.parseInt(compressedString.substring(i * 8, (i + 1) * 8), 2); } return compressedBytes; } //---------------------------------------end of compression---------------------------------------------------------------- //------------------------------------------------------------extract----------------------------------------------------- public String extract(String compressed, String[] newEncodingArray) { String decompressed = ""; String current = ""; String delta = ""; encodingArray = newEncodingArray; //displayEncodingArray(); // -   for (int i = 0; i < 8; i++) delta += compressed.charAt(i); int ADDED_ZEROES = Integer.parseInt(delta, 2); for (int i = 8, l = compressed.length() - ADDED_ZEROES; i < l; i++) { //i = 8, ..      -   current += compressed.charAt(i); for (int j = 0; j < ENCODING_TABLE_SIZE; j++) { if (current.equals(encodingArray[j])) {//  decompressed += (char)j;//   current = "";//    } } } return decompressed; } public String getEncodingTable() { String enc = ""; for (int i = 0; i < encodingArray.length; i++) { if (freqArray[i] != 0) enc += (char)i + encodingArray[i] + '\n'; } return enc; } public double getCompressionRatio() { return ratio; } public void displayEncodingArray() {//  System.out.println("======================Encoding table===================="); for (int i = 0; i < ENCODING_TABLE_SIZE; i++) { //if (freqArray[i] != 0) { System.out.print((char)i + " "); System.out.println(encodingArray[i]); //} } System.out.println("========================================================"); } } 

वह वर्ग जो फ़ाइल में लिखने की सुविधा देता है:

 import java.io.File; import java.io.PrintWriter; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.Closeable; public class FileOutputHelper implements Closeable { private File outputFile; private FileOutputStream fileOutputStream; public FileOutputHelper(File file) throws FileNotFoundException { outputFile = file; fileOutputStream = new FileOutputStream(outputFile); } public void writeByte(byte msg) throws IOException { fileOutputStream.write(msg); } public void writeBytes(byte[] msg) throws IOException { fileOutputStream.write(msg); } public void writeString(String msg) { try (PrintWriter pw = new PrintWriter(outputFile)) { pw.write(msg); } catch (FileNotFoundException e) { System.out.println(" ,     !"); } } @Override public void close() throws IOException { fileOutputStream.close(); } public void finalize() throws IOException { close(); } } 

एक फ़ाइल से पढ़ने की सुविधा देने वाला वर्ग:

 import java.io.FileInputStream; import java.io.EOFException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.Closeable; import java.io.File; import java.io.IOException; public class FileInputHelper implements Closeable { private FileInputStream fileInputStream; private BufferedReader fileBufferedReader; public FileInputHelper(File file) throws IOException { fileInputStream = new FileInputStream(file); fileBufferedReader = new BufferedReader(new InputStreamReader(fileInputStream)); } public byte readByte() throws IOException { int cur = fileInputStream.read(); if (cur == -1)//   throw new EOFException(); return (byte)cur; } public String readLine() throws IOException { return fileBufferedReader.readLine(); } @Override public void close() throws IOException{ fileInputStream.close(); } } 

खैर, और मुख्य वर्ग:

 import java.io.File; import java.nio.charset.MalformedInputException; import java.io.FileNotFoundException; import java.io.IOException; import java.nio.file.Files; import java.nio.file.NoSuchFileException; import java.nio.file.Paths; import java.util.List; import java.io.EOFException; public class Main { private static final byte ENCODING_TABLE_SIZE = 127; public static void main(String[] args) throws IOException { try {//       if (args[0].equals("--compress") || args[0].equals("-c")) compress(args[1]); else if ((args[0].equals("--extract") || args[0].equals("-x")) && (args[2].equals("--table") || args[2].equals("-t"))) { extract(args[1], args[3]); } else throw new IllegalArgumentException(); } catch (ArrayIndexOutOfBoundsException | IllegalArgumentException e) { System.out.println("    "); System.out.println(" Readme.txt"); e.printStackTrace(); } } public static void compress(String stringPath) throws IOException { List<String> stringList; File inputFile = new File(stringPath); String s = ""; File compressedFile, table; try { stringList = Files.readAllLines(Paths.get(inputFile.getAbsolutePath())); } catch (NoSuchFileException e) { System.out.println(" ,     !"); return; } catch (MalformedInputException e) { System.out.println("    "); return; } for (String item : stringList) { s += item; s += '\n'; } HuffmanOperator operator = new HuffmanOperator(new HuffmanTree(s)); compressedFile = new File(inputFile.getAbsolutePath() + ".cpr"); compressedFile.createNewFile(); try (FileOutputHelper fo = new FileOutputHelper(compressedFile)) { fo.writeBytes(operator.getBytedMsg()); } //create file with encoding table: table = new File(inputFile.getAbsolutePath() + ".table.txt"); table.createNewFile(); try (FileOutputHelper fo = new FileOutputHelper(table)) { fo.writeString(operator.getEncodingTable()); } System.out.println("   : " + compressedFile.getAbsolutePath()); System.out.println("    " + table.getAbsolutePath()); System.out.println("     !"); double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100;//  double realRatio = Math.round((double) inputFile.length() / ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100;//  System.out.println("    " + idealRatio); System.out.println("      " + realRatio); } public static void extract(String filePath, String tablePath) throws FileNotFoundException, IOException { HuffmanOperator operator = new HuffmanOperator(); File compressedFile = new File(filePath), tableFile = new File(tablePath), extractedFile = new File(filePath + ".xtr"); String compressed = ""; String[] encodingArray = new String[ENCODING_TABLE_SIZE]; //read compressed file //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!check here: try (FileInputHelper fi = new FileInputHelper(compressedFile)) { byte b; while (true) { b = fi.readByte();//method returns EOFException compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0"); } } catch (EOFException e) { } //-------------------- //read encoding table: try (FileInputHelper fi = new FileInputHelper(tableFile)) { fi.readLine();//skip first empty string encodingArray[(byte)'\n'] = fi.readLine();//read code for '\n' while (true) { String s = fi.readLine(); if (s == null) throw new EOFException(); encodingArray[(byte)s.charAt(0)] = s.substring(1, s.length()); } } catch (EOFException ignore) {} extractedFile.createNewFile(); //extract: try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) { fo.writeString(operator.extract(compressed, encodingArray)); } System.out.println("    " + extractedFile.getAbsolutePath()); } } 

Readme.txt निर्देश फ़ाइल अपने आप को लिखने के लिए है :-)

निष्कर्ष

शायद यही सब मैं कहना चाहता था। यदि आपके पास कोड में सुधार की मेरी अक्षमता , एल्गोरिथ्म और सामान्य रूप से किसी भी अनुकूलन के बारे में कुछ कहना है, तो बेझिझक लिखें। अगर मुझे कुछ गलत लगा, तो भी लिखिए। मुझे आपकी टिप्पणियों में सुनने में खुशी होगी!

पुनश्च

हां, हां, मैं अभी भी यहां हूं, क्योंकि मैं गुणांक के बारे में नहीं भूलता था। स्ट्रिंग s1 के लिए, एन्कोडिंग तालिका का वजन 48 बाइट्स होता है - मूल फ़ाइल की तुलना में बहुत अधिक, और वे अतिरिक्त शून्य के बारे में नहीं भूलते थे (जोड़ा शून्य की संख्या 7 है) => संपीड़न अनुपात एक से कम होगा: 176 / (65 + 48 * 8 + 7) = 0.38। अगर आपने भी इस पर गौर किया है, तो सिर्फ उस चेहरे पर नहीं, जिस पर आप काम कर रहे हैं। हां, यह कार्यान्वयन छोटी फाइलों के लिए बेहद अक्षम होगा। लेकिन बड़ी फ़ाइलों का क्या होता है? फ़ाइल का आकार एन्कोडिंग तालिका के आकार से अधिक है। यहाँ एल्गोरिथ्म काम करता है जैसा कि इसे करना चाहिए! उदाहरण के लिए, फॉस्ट मोनोलॉग के लिए, अभिलेखागार 1.46 के बराबर एक वास्तविक (आदर्श नहीं) गुणांक देता है - लगभग डेढ़ गुना! और हाँ, फ़ाइल अंग्रेजी में होनी चाहिए थी।