Library/src/main/java/org/example/AdaptiveHuffmanCompressor.java - master - Dixix404/String_compression

Library/src/main/java/org/example/AdaptiveHuffmanCompressor.java
325 строк10 KB
Dixix404
AdaptiveHuffman Algorithm + changing the key structure
15 дек 2025, 17:31
15 дек 2025, 17:316c27aa7
package org.example;

import java.io.*;
import java.util.*;

public class AdaptiveHuffmanCompressor implements Compressor {

    private static final int ALPHABET_SIZE = 256;
    private static final int NYT_SYMBOL = -1; // Специальный символ для NYT узла

    @Override
    public String getName() {
        return "adaptivehuffman";
    }

    /**
     * Сжимает входной поток используя адаптивный алгоритм Хаффмана.
     *
     * @param in входной поток данных
     * @param out выходной поток для сжатых данных
     * @throws IOException при ошибках ввода-вывода
     */
    @Override
    public void compress(InputStream in, OutputStream out) throws IOException {
        // Читаем все данные
        ByteArrayOutputStream buffer = new ByteArrayOutputStream();
        byte[] tempBuffer = new byte[8192];
        int bytesRead;
        while ((bytesRead = in.read(tempBuffer)) != -1) {
            buffer.write(tempBuffer, 0, bytesRead);
        }
        byte[] data = buffer.toByteArray();

        DataOutputStream dos = new DataOutputStream(out);
        dos.writeLong(data.length);

        if (data.length == 0) {
            dos.flush();
            return;
        }

        // Инициализация дерева и кодирование
        AdaptiveHuffmanTree tree = new AdaptiveHuffmanTree();
        BitOutputStream bitOut = new BitOutputStream(dos);

        for (byte b : data) {
            int symbol = b & 0xFF; // Преобразуем в беззнаковое значение 0-255

            // Кодируем символ
            List<Integer> code = tree.encode(symbol);
            for (int bit : code) {
                bitOut.writeBit(bit);
            }

            // Обновляем дерево
            tree.update(symbol);
        }

        bitOut.flush();
        dos.flush();
    }

    /**
     * Распаковывает данные, сжатые адаптивным алгоритмом Хаффмана.
     *
     * @param in входной поток сжатых данных
     * @param out выходной поток для распакованных данных
     * @throws IOException при ошибках ввода-вывода
     */
    @Override
    public void decompress(InputStream in, OutputStream out) throws IOException {
        DataInputStream dis = new DataInputStream(in);
        long totalSymbols = dis.readLong();

        if (totalSymbols == 0) {
            return;
        }

        // Инициализация дерева и декодирование
        AdaptiveHuffmanTree tree = new AdaptiveHuffmanTree();
        BitInputStream bitIn = new BitInputStream(dis);

        for (long i = 0; i < totalSymbols; i++) {
            // Декодируем символ
            int symbol = tree.decode(bitIn);
            out.write(symbol);

            // Обновляем дерево
            tree.update(symbol);
        }

        out.flush();
    }

    private static class AdaptiveHuffmanTree {
        private Node root;
        private Node nytNode; // Not Yet Transmitted узел
        private Map<Integer, Node> leafNodes; // Карта: символ → узел листа
        private int nextNodeNumber;

        AdaptiveHuffmanTree() {
            // Начинаем с одного NYT узла
            root = new Node(NYT_SYMBOL, 0, 512);
            nytNode = root;
            leafNodes = new HashMap<>();
            nextNodeNumber = 511;
        }

        List<Integer> encode(int symbol) {
            List<Integer> code = new ArrayList<>();

            if (leafNodes.containsKey(symbol)) {
                // Символ уже в дереве - получаем путь к нему
                Node node = leafNodes.get(symbol);
                getPathToRoot(node, code);
                Collections.reverse(code);
            } else {
                // Новый символ - отправляем код NYT + сам символ (8 бит)
                getPathToRoot(nytNode, code);
                Collections.reverse(code);

                // Добавляем 8 бит самого символа
                for (int i = 7; i >= 0; i--) {
                    code.add((symbol >> i) & 1);
                }
            }

            return code;
        }

        int decode(BitInputStream bitIn) throws IOException {
            Node current = root;

            // Идем по дереву, пока не достигнем листа
            while (!current.isLeaf()) {
                int bit = bitIn.readBit();
                current = (bit == 0) ? current.left : current.right;
            }

            if (current == nytNode) {
                // Это NYT - читаем следующие 8 бит как новый символ
                int symbol = 0;
                for (int i = 0; i < 8; i++) {
                    symbol = (symbol << 1) | bitIn.readBit();
                }
                return symbol;
            } else {
                // Это известный символ
                return current.symbol;
            }
        }

        void update(int symbol) {
            Node node;

            if (leafNodes.containsKey(symbol)) {
                // Символ уже есть - обновляем его вес
                node = leafNodes.get(symbol);
            } else {
                // Новый символ - создаем узлы
                Node newNyt = new Node(NYT_SYMBOL, 0, nextNodeNumber--);
                Node newLeaf = new Node(symbol, 0, nextNodeNumber--);

                newLeaf.parent = nytNode;
                newNyt.parent = nytNode;

                nytNode.left = newNyt;
                nytNode.right = newLeaf;
                nytNode.symbol = -2; // Больше не NYT

                leafNodes.put(symbol, newLeaf);
                nytNode = newNyt;
                node = newLeaf.parent;
            }

            // Обновляем веса до корня
            while (node != null) {
                node.weight++;

                // Проверяем sibling property и при необходимости меняем узлы местами
                Node maxNode = findMaxNodeInBlock(node);
                if (maxNode != node && maxNode != node.parent) {
                    swapNodes(node, maxNode);
                    node = maxNode;
                }

                node = node.parent;
            }
        }

        private Node findMaxNodeInBlock(Node node) {
            List<Node> allNodes = new ArrayList<>();
            collectNodes(root, allNodes);

            Node maxNode = node;
            for (Node n : allNodes) {
                if (n.weight == node.weight && n.number > maxNode.number && n != node.parent) {
                    maxNode = n;
                }
            }

            return maxNode;
        }

        private void collectNodes(Node node, List<Node> nodes) {
            if (node != null) {
                nodes.add(node);
                collectNodes(node.left, nodes);
                collectNodes(node.right, nodes);
            }
        }

        private void swapNodes(Node a, Node b) {
            Node tempParent = a.parent;
            boolean aIsLeft = (tempParent != null && tempParent.left == a);

            Node bParent = b.parent;
            boolean bIsLeft = (bParent != null && bParent.left == b);

            // Меняем родителей
            a.parent = bParent;
            b.parent = tempParent;

            // Обновляем ссылки у родителей
            if (tempParent != null) {
                if (aIsLeft) tempParent.left = b;
                else tempParent.right = b;
            }

            if (bParent != null) {
                if (bIsLeft) bParent.left = a;
                else bParent.right = a;
            }

            // Меняем номера
            int tempNumber = a.number;
            a.number = b.number;
            b.number = tempNumber;
        }

        private void getPathToRoot(Node node, List<Integer> path) {
            Node current = node;
            while (current.parent != null) {
                Node parent = current.parent;
                if (parent.left == current) {
                    path.add(0);
                } else {
                    path.add(1);
                }
                current = parent;
            }
        }
    }

    private static class Node {
        int symbol;      // Символ (для листьев) или -1 для NYT, -2 для внутренних узлов
        int weight;      // Вес (частота)
        int number;      // Номер узла (для sibling property)
        Node left;
        Node right;
        Node parent;

        Node(int symbol, int weight, int number) {
            this.symbol = symbol;
            this.weight = weight;
            this.number = number;
        }

        boolean isLeaf() {
            return left == null && right == null;
        }
    }

    private static class BitOutputStream {
        private DataOutputStream out;
        private int currentByte;
        private int numBitsInByte;

        BitOutputStream(DataOutputStream out) {
            this.out = out;
            this.currentByte = 0;
            this.numBitsInByte = 0;
        }

        void writeBit(int bit) throws IOException {
            currentByte = (currentByte << 1) | (bit & 1);
            numBitsInByte++;

            if (numBitsInByte == 8) {
                out.writeByte(currentByte);
                currentByte = 0;
                numBitsInByte = 0;
            }
        }

        void flush() throws IOException {
            if (numBitsInByte > 0) {
                currentByte <<= (8 - numBitsInByte);
                out.writeByte(currentByte);
            }
        }
    }

    private static class BitInputStream {
        private DataInputStream in;
        private int currentByte;
        private int numBitsRemaining;

        BitInputStream(DataInputStream in) {
            this.in = in;
            this.currentByte = 0;
            this.numBitsRemaining = 0;
        }

        int readBit() throws IOException {
            if (numBitsRemaining == 0) {
                currentByte = in.readUnsignedByte();
                numBitsRemaining = 8;
            }

            numBitsRemaining--;
            return (currentByte >> numBitsRemaining) & 1;
        }
    }
}