მონაცემთა შეკუმშვა ჰაფმანის ალგორითმით

Entry

ამ სტატიაში ვისაუბრებ ჰაფმანის ცნობილ ალგორითმზე, ასევე მის გამოყენებაზე მონაცემთა შეკუმშვისას.

შედეგად, ჩვენ დავწერთ მარტივ არქივს. ეს უკვე იყო სტატია ჰაბრეზე, მაგრამ პრაქტიკული განხორციელების გარეშე. მიმდინარე პოსტის თეორიული მასალა აღებულია სკოლის კომპიუტერული მეცნიერების გაკვეთილებიდან და რობერტ ლაფორეტის წიგნიდან „მონაცემთა სტრუქტურები და ალგორითმები ჯავაში“. ასე რომ, ყველაფერი მოჭრილია!

პატარა ანარეკლი

ჩვეულებრივ ტექსტურ ფაილში ერთი სიმბოლო დაშიფრულია 8 ბიტით (ASCII კოდირება) ან 16 (Unicode კოდირება). შემდეგი, განვიხილავთ ASCII კოდირებას. მაგალითად, აიღეთ სტრიქონი s1 = "SUSIE SAYS IT IS EASYn". საერთო ჯამში, სტრიქონში 22 სიმბოლოა, რა თქმა უნდა, ინტერვალის და ახალი ხაზის სიმბოლოს ჩათვლით - 'n'. ამ ხაზის შემცველი ფაილი იწონის 22*8 = 176 ბიტს. მაშინვე ჩნდება კითხვა: არის თუ არა რაციონალური 8 ბიტის გამოყენება 1 სიმბოლოს დაშიფვრისთვის? ჩვენ არ ვიყენებთ ყველა ASCII სიმბოლოს. მაშინაც კი, თუ ისინი ყოფილიყვნენ, უფრო რაციონალური იქნებოდა, მიეცეთ ყველაზე ხშირი ასო - S - ყველაზე მოკლე კოდი, ხოლო უიშვიათესი ასოსთვის - T (ან U, ან 'n') - უფრო ავთენტური კოდი. ეს არის ჰაფმანის ალგორითმი: თქვენ უნდა იპოვოთ საუკეთესო კოდირების ვარიანტი, რომელშიც ფაილი იქნება მინიმალური წონის. სავსებით ნორმალურია, რომ სხვადასხვა სიმბოლოს ექნება სხვადასხვა კოდის სიგრძე - ეს არის ალგორითმის საფუძველი.

კოდირება

რატომ არ მივცეთ სიმბოლოს '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. შექმენით Node ობიექტი შეტყობინებებიდან თითოეული სიმბოლოსთვის (სტრიქონი s1). ჩვენს შემთხვევაში, იქნება 9 კვანძი (Node ობიექტები). თითოეული კვანძი შედგება ორი მონაცემთა ველისაგან: სიმბოლო და სიხშირე
2. შექმენით ხის ობიექტი (BinaryTree) თითოეული კვანძის კვანძისთვის. კვანძი ხდება ხის ფესვი.
3. ჩადეთ ეს ხეები პრიორიტეტულ რიგში. რაც უფრო დაბალია სიხშირე, მით უფრო მაღალია პრიორიტეტი. ამრიგად, მოპოვებისას ყოველთვის შეირჩევა ყველაზე დაბალი სიხშირის ხე.

შემდეგი, თქვენ უნდა გააკეთოთ ციკლურად შემდეგი:

1. ამოიღეთ ორი ხე პრიორიტეტული რიგიდან და გახადეთ ისინი ახალი კვანძის შვილებად (ახლად შექმნილი კვანძი ასოს გარეშე). ახალი კვანძის სიხშირე უდრის ორი შთამომავალი ხის სიხშირეების ჯამს.
2. ამ კვანძისთვის შექმენით ამ კვანძზე დაფუძნებული ხე. ჩადეთ ეს ხე ისევ პრიორიტეტულ რიგში. (რადგან ხეს ახალი სიხშირე აქვს, ის სავარაუდოდ ახალ ადგილზე მოხვდება რიგში)
3. გააგრძელეთ 1 და 2 ნაბიჯები, სანამ რიგში არ დარჩება ერთი ხე - ჰაფმანის ხე

განვიხილოთ ეს ალგორითმი სტრიქონზე s1:

აქ სიმბოლო "lf" (linefeed) აღნიშნავს ახალ ხაზს, "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-ჯერ! მაგრამ ეს უტოპიაა. ასეთი თანაფარდობა ნაკლებად სავარაუდოა. რატომ? ამაზე ცოტა მოგვიანებით იქნება განხილული.

დეკოდირება

ისე, ალბათ ყველაზე მარტივი რამ არის გაშიფვრა. ვფიქრობ, ბევრმა თქვენგანმა გამოიცანით, რომ შეკუმშული ფაილის შექმნა შეუძლებელია, ყოველგვარი მინიშნებების გარეშე, თუ როგორ იყო კოდირებული - ჩვენ ვერ შევძლებთ მის გაშიფვრას! დიახ, დიახ, გამიჭირდა ამის გაცნობიერება, მაგრამ მე უნდა შევქმნა ტექსტური ფაილის table.txt შეკუმშვის ცხრილით:

01110
 00
A010
E1111
I110
S10
T0110
U01111
Y1110

ცხრილის ჩანაწერი სახით „სიმბოლო“ „სიმბოლო კოდი“. რატომ არის 01110 სიმბოლოს გარეშე? სინამდვილეში, ეს არის სიმბოლოთი, მხოლოდ java ინსტრუმენტებით, რომლებსაც ვიყენებ ფაილში გამოტანისას, ახალი ხაზის სიმბოლო - 'n' - გარდაიქმნება ახალ ხაზად (რაც არ უნდა სულელურად ჟღერდეს). აქედან გამომდინარე, ცარიელი ხაზი ზემოთ არის სიმბოლო 01110 კოდისთვის. 00 კოდისთვის სიმბოლო არის სივრცე სტრიქონის დასაწყისში. დაუყოვნებლივ უნდა ვთქვა, რომ ცხრილის შენახვის ეს მეთოდი შეიძლება იყოს ყველაზე ირაციონალური ჩვენი ხანის კოეფიციენტისთვის. მაგრამ ადვილი გასაგები და განხორციელებაა. მოხარული ვიქნები მოვისმინო თქვენი რეკომენდაციები კომენტარებში ოპტიმიზაციის შესახებ.

ამ ცხრილით მისი გაშიფვრა ძალიან ადვილია. გავიხსენოთ რა წესით ვიხელმძღვანელეთ კოდირების შექმნისას:

არცერთი კოდი არ უნდა იყოს სხვა პრეფიქსი

აქ ის თამაშობს ხელშემწყობ როლს. ჩვენ ვკითხულობთ ბიტ-ბიტი თანმიმდევრობით და როგორც კი მიღებული სტრიქონი, რომელიც შედგება წაკითხული ბიტებისაგან, ემთხვევა სიმბოლოს სიმბოლოს შესაბამის დაშიფვრას, მაშინვე ვიცით, რომ სიმბოლოს სიმბოლო (და მხოლოდ ის!) იყო კოდირებული. შემდეგი, ჩვენ ვწერთ სიმბოლოს დეკოდირების სტრიქონზე (სტრიქონი, რომელიც შეიცავს დეკოდირებულ შეტყობინებას), გადავაყენებთ d სტრიქონს და ვკითხულობთ დაშიფრულ ფაილს შემდგომში.

Реализация

დროა დავამცირო ჩემი კოდი არქივის დაწერით. დავარქვათ კომპრესორი.

Თავიდან დაწყება. უპირველეს ყოვლისა, ჩვენ ვწერთ 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;
    }
}

ახლა ხე:

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 ინსტრუქციებით 🙂

დასკვნა

მგონი სულ ეს იყო რისი თქმაც მინდოდა. თუ რაიმე გაქვთ სათქმელი კოდის, ალგორითმის, ზოგადად, რაიმე ოპტიმიზაციის გაუმჯობესების ჩემს არაკომპეტენტურობაზე, მაშინ თავისუფლად დაწერეთ. თუ რამე არ ავხსენი დაწერე. სიამოვნებით მოვისმენდი თქვენგან კომენტარებში!

PS

დიახ, დიახ, მე ისევ აქ ვარ, რადგან კოეფიციენტი არ დამავიწყდა. სტრიქონისთვის s1, კოდირების ცხრილი იწონის 48 ბაიტს - ბევრად აღემატება თავდაპირველ ფაილს და არ დაივიწყეს დამატებითი ნულები (დამატებული ნულების რაოდენობა არის 7) => შეკუმშვის კოეფიციენტი იქნება ერთზე ნაკლები: 176 /(65 + 48*8 + 7) = 0.38. თუ თქვენც შეამჩნიეთ ეს, მაშინ უბრალოდ სახეზე არ ხართ დასრულებული. დიახ, ეს განხორციელება უკიდურესად არაეფექტური იქნება მცირე ზომის ფაილებისთვის. მაგრამ რა ხდება დიდ ფაილებთან? ფაილის ზომა ბევრად აღემატება კოდირების ცხრილის ზომას. ეს არის სადაც ალგორითმი მუშაობს ისე, როგორც უნდა! მაგალითად, ამისთვის ფაუსტის მონოლოგი არქივატორი იძლევა რეალურ (არა იდეალიზებულ) კოეფიციენტს, რომელიც უდრის 1.46-ს - თითქმის ერთნახევარჯერ! დიახ, ფაილი ინგლისურ ენაზე უნდა ყოფილიყო.

წყარო: www.habr.com