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

Library/src/main/java/org/example/HuffmanCompressor.java
279 строк10 KB
Dixix404
Fano Algorithm + changing the key structure
15 дек 2025, 15:00
15 дек 2025, 15:001bfaa0a
package org.example;

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

public class HuffmanCompressor implements Compressor {

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

    /**
     * Сжимает входной поток используя алгоритм Хаффмана.
     *
     * @param in входной поток данных
     * @param out выходной поток для сжатых данных
     * @throws IOException при ошибках ввода-вывода
     */
    @Override
    public void compress(InputStream in, OutputStream out) throws IOException {
        // Шаг 1: Читаем все байты и подсчитываем частоты
        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();

        if (data.length == 0) {
            // Пустой файл - просто записываем 0
            DataOutputStream dos = new DataOutputStream(out);
            dos.writeInt(0);
            dos.flush();
            return;
        }

        // Подсчет частот
        Map<Byte, Long> frequencies = buildFrequencyTable(data);

        // Шаг 2: Строим дерево Хаффмана
        HuffmanNode root = buildHuffmanTree(frequencies);

        // Шаг 3: Генерируем коды для каждого байта
        Map<Byte, String> huffmanCodes = new HashMap<>();
        generateCodes(root, "", huffmanCodes);

        // Шаг 4: Записываем заголовок (таблицу частот)
        DataOutputStream dos = new DataOutputStream(out);
        writeHeader(dos, frequencies, data.length);

        // Шаг 5: Кодируем и записываем данные
        encodeData(dos, data, huffmanCodes);

        dos.flush();
    }

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

        // Читаем заголовок
        int uniqueBytes = dis.readInt();

        if (uniqueBytes == 0) {
            // Пустой файл
            return;
        }

        // Восстанавливаем таблицу частот
        Map<Byte, Long> frequencies = new HashMap<>();
        for (int i = 0; i < uniqueBytes; i++) {
            byte value = dis.readByte();
            long freq = dis.readLong();
            frequencies.put(value, freq);
        }

        long totalBytes = dis.readLong();

        // Восстанавливаем дерево Хаффмана
        HuffmanNode root = buildHuffmanTree(frequencies);

        // Декодируем данные
        decodeData(dis, out, root, totalBytes);

        out.flush();
    }

    /**
     * Подсчитывает частоты встречаемости каждого байта.
     *
     * @param data массив байтов для анализа
     * @return карта: байт → частота
     */
    private Map<Byte, Long> buildFrequencyTable(byte[] data) {
        Map<Byte, Long> frequencies = new HashMap<>();
        for (byte b : data) {
            frequencies.put(b, frequencies.getOrDefault(b, 0L) + 1);
        }
        return frequencies;
    }

    /**
     * Строит дерево Хаффмана на основе таблицы частот.
     *
     * @param frequencies карта частот
     * @return корень дерева Хаффмана
     */
    private HuffmanNode buildHuffmanTree(Map<Byte, Long> frequencies) {
        // Используем приоритетную очередь для выбора узлов с минимальной частотой
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();

        // Создаем листовые узлы для каждого байта
        for (Map.Entry<Byte, Long> entry : frequencies.entrySet()) {
            queue.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // Строим дерево снизу вверх
        while (queue.size() > 1) {
            HuffmanNode left = queue.poll();
            HuffmanNode right = queue.poll();

            // Создаем внутренний узел с суммарной частотой
            HuffmanNode parent = new HuffmanNode(null, left.frequency + right.frequency);
            parent.left = left;
            parent.right = right;

            queue.offer(parent);
        }

        return queue.poll();
    }

    /**
     * Генерирует коды Хаффмана для каждого байта.
     *
     * @param node текущий узел дерева
     * @param code текущий код (строка из '0' и '1')
     * @param codes карта для сохранения кодов
     */
    private void generateCodes(HuffmanNode node, String code, Map<Byte, String> codes) {
        if (node == null) {
            return;
        }

        // Листовой узел - сохраняем код
        if (node.data != null) {
            codes.put(node.data, code.isEmpty() ? "0" : code);
            return;
        }

        // Рекурсивно обходим дерево
        generateCodes(node.left, code + "0", codes);
        generateCodes(node.right, code + "1", codes);
    }

    /**
     * Записывает заголовок файла с таблицей частот.
     *
     * @param dos поток вывода
     * @param frequencies таблица частот
     * @param totalBytes общее количество байтов
     * @throws IOException при ошибках записи
     */
    private void writeHeader(DataOutputStream dos, Map<Byte, Long> frequencies, long totalBytes) throws IOException {
        dos.writeInt(frequencies.size());

        for (Map.Entry<Byte, Long> entry : frequencies.entrySet()) {
            dos.writeByte(entry.getKey());
            dos.writeLong(entry.getValue());
        }

        dos.writeLong(totalBytes);
    }

    /**
     * Кодирует данные и записывает их побитово.
     *
     * @param dos поток вывода
     * @param data исходные данные
     * @param codes таблица кодов Хаффмана
     * @throws IOException при ошибках записи
     */
    private void encodeData(DataOutputStream dos, byte[] data, Map<Byte, String> codes) throws IOException {
        StringBuilder bits = new StringBuilder();

        // Кодируем каждый байт
        for (byte b : data) {
            bits.append(codes.get(b));
        }

        // Записываем биты побайтово
        int i = 0;
        while (i + 8 <= bits.length()) {
            String byteString = bits.substring(i, i + 8);
            int byteValue = Integer.parseInt(byteString, 2);
            dos.writeByte(byteValue);
            i += 8;
        }

        // Если остались биты, дописываем нулями и записываем последний байт
        if (i < bits.length()) {
            String lastBits = bits.substring(i);
            while (lastBits.length() < 8) {
                lastBits += "0";
            }
            int byteValue = Integer.parseInt(lastBits, 2);
            dos.writeByte(byteValue);
        }
    }

    /**
     * Декодирует данные используя дерево Хаффмана.
     *
     * @param dis входной поток
     * @param out выходной поток
     * @param root корень дерева Хаффмана
     * @param totalBytes ожидаемое количество байтов
     * @throws IOException при ошибках чтения/записи
     */
    private void decodeData(DataInputStream dis, OutputStream out, HuffmanNode root, long totalBytes) throws IOException {
        long bytesDecoded = 0;
        HuffmanNode current = root;

        // Читаем данные побайтово
        while (bytesDecoded < totalBytes) {
            int byteValue = dis.readUnsignedByte();

            // Обрабатываем каждый бит в байте
            for (int i = 7; i >= 0 && bytesDecoded < totalBytes; i--) {
                int bit = (byteValue >> i) & 1;

                // Идем по дереву: 0 - влево, 1 - вправо
                current = (bit == 0) ? current.left : current.right;

                // Достигли листа - записываем байт
                if (current.data != null) {
                    out.write(current.data);
                    bytesDecoded++;
                    current = root;
                }
            }
        }
    }

    /**
     * Узел дерева Хаффмана.
     */
    private static class HuffmanNode implements Comparable<HuffmanNode> {
        Byte data;           // Значение байта (null для внутренних узлов)
        long frequency;      // Частота встречаемости
        HuffmanNode left;    // Левый потомок (бит 0)
        HuffmanNode right;   // Правый потомок (бит 1)

        /**
         * Создает узел дерева.
         *
         * @param data значение байта (null для внутренних узлов)
         * @param frequency частота встречаемости
         */
        HuffmanNode(Byte data, long frequency) {
            this.data = data;
            this.frequency = frequency;
        }

        @Override
        public int compareTo(HuffmanNode other) {
            return Long.compare(this.frequency, other.frequency);
        }
    }
}