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

Library/src/main/java/org/example/ShannonCompressor.java
286 строк11 KB
Dixix404
Shannon Algorithm + changing the key structure
15 дек 2025, 16:22
15 дек 2025, 16:227280951
package org.example;

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

public class ShannonCompressor implements Compressor {

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

    /**
     * Сжимает входной поток используя алгоритм кодирования Шеннона.
     *
     * @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) {
            DataOutputStream dos = new DataOutputStream(out);
            dos.writeInt(0);
            dos.flush();
            return;
        }

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

        // Шаг 2: Генерируем коды Шеннона
        Map<Byte, String> codes = generateShannonCodes(frequencies, data.length);

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

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

        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();

        // Восстанавливаем коды Шеннона
        Map<Byte, String> codes = generateShannonCodes(frequencies, (int) totalBytes);

        // Создаем обратную таблицу: код → байт
        Map<String, Byte> reverseMap = new HashMap<>();
        for (Map.Entry<Byte, String> entry : codes.entrySet()) {
            reverseMap.put(entry.getValue(), entry.getKey());
        }

        // Декодируем данные
        decodeData(dis, out, reverseMap, 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 карта частот
     * @param totalCount общее количество символов
     * @return карта: байт → код
     */
    private Map<Byte, String> generateShannonCodes(Map<Byte, Long> frequencies, int totalCount) {
        // Создаем список символов с вероятностями
        List<ShannonSymbol> symbols = new ArrayList<>();
        for (Map.Entry<Byte, Long> entry : frequencies.entrySet()) {
            double probability = (double) entry.getValue() / totalCount;
            symbols.add(new ShannonSymbol(entry.getKey(), entry.getValue(), probability));
        }

        // Сортируем по убыванию вероятности
        symbols.sort((a, b) -> Double.compare(b.probability, a.probability));

        // Вычисляем длины кодов по формуле Шеннона: l = ⌈-log₂(p)⌉
        for (ShannonSymbol symbol : symbols) {
            if (symbol.probability > 0) {
                symbol.codeLength = (int) Math.ceil(-Math.log(symbol.probability) / Math.log(2));
            } else {
                symbol.codeLength = 1;
            }
        }

        // Вычисляем кумулятивные вероятности
        double cumulativeProbability = 0.0;
        for (ShannonSymbol symbol : symbols) {
            symbol.cumulativeProbability = cumulativeProbability;
            cumulativeProbability += symbol.probability;
        }

        // Генерируем коды на основе кумулятивных вероятностей
        Map<Byte, String> codes = new HashMap<>();

        for (ShannonSymbol symbol : symbols) {
            // Преобразуем кумулятивную вероятность в двоичную дробь
            String code = generateCodeFromProbability(symbol.cumulativeProbability, symbol.codeLength);
            codes.put(symbol.value, code);
        }

        // Обработка случая единственного символа
        if (codes.size() == 1) {
            codes.replaceAll((k, v) -> "0");
        }

        return codes;
    }

    /**
     * Генерирует двоичный код из кумулятивной вероятности.
     *
     * @param probability кумулятивная вероятность
     * @param length требуемая длина кода
     * @return двоичный код
     */
    private String generateCodeFromProbability(double probability, int length) {
        StringBuilder code = new StringBuilder();

        for (int i = 0; i < length; i++) {
            probability *= 2;
            if (probability >= 1.0) {
                code.append('1');
                probability -= 1.0;
            } else {
                code.append('0');
            }
        }

        return code.toString();
    }

    /**
     * Записывает заголовок файла с таблицей частот.
     *
     * @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 reverseMap обратная карта: код → байт
     * @param totalBytes ожидаемое количество байтов
     * @throws IOException при ошибках чтения/записи
     */
    private void decodeData(DataInputStream dis, OutputStream out,
                            Map<String, Byte> reverseMap, long totalBytes) throws IOException {
        long bytesDecoded = 0;
        StringBuilder currentCode = new StringBuilder();

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

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

                // Проверяем, есть ли такой код в таблице
                if (reverseMap.containsKey(currentCode.toString())) {
                    out.write(reverseMap.get(currentCode.toString()));
                    bytesDecoded++;
                    currentCode.setLength(0); // очищаем код
                }
            }
        }
    }

    private static class ShannonSymbol {
        byte value;
        long frequency;
        double probability;
        double cumulativeProbability;
        int codeLength;

        ShannonSymbol(byte value, long frequency, double probability) {
            this.value = value;
            this.frequency = frequency;
            this.probability = probability;
        }
    }
}