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

Library/src/main/java/org/example/FanoCompressor.java
309 строк11 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 FanoCompressor implements Compressor {

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

    /**
     * Сжимает входной поток используя алгоритм Фано.
     *
     * @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 = generateFanoCodes(frequencies);

        // Шаг 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 = generateFanoCodes(frequencies);

        // Создаем обратную таблицу: код → байт
        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 карта частот
     * @return карта: байт → код
     */
    private Map<Byte, String> generateFanoCodes(Map<Byte, Long> frequencies) {
        // Создаем список символов, отсортированный по убыванию частоты
        List<FanoSymbol> symbols = new ArrayList<>();
        for (Map.Entry<Byte, Long> entry : frequencies.entrySet()) {
            symbols.add(new FanoSymbol(entry.getKey(), entry.getValue()));
        }

        // Сортируем по убыванию частоты (важно для алгоритма Фано)
        symbols.sort((a, b) -> {
            int freqCompare = Long.compare(b.frequency, a.frequency);
            if (freqCompare != 0) return freqCompare;
            // При равной частоте - по значению байта для стабильности
            return Byte.compare(a.value, b.value);
        });

        // Генерируем коды рекурсивно
        Map<Byte, String> codes = new HashMap<>();
        if (symbols.size() == 1) {
            // Единственный символ - код "0"
            codes.put(symbols.get(0).value, "0");
        } else {
            assignFanoCodes(symbols, "", codes);
        }

        return codes;
    }

    /**
     * Рекурсивно присваивает коды символам методом Фано.
     * Делит список на две части с примерно равной суммой частот.
     *
     * @param symbols список символов (отсортирован по убыванию частоты)
     * @param prefix текущий префикс кода
     * @param codes карта для сохранения кодов
     */
    private void assignFanoCodes(List<FanoSymbol> symbols, String prefix, Map<Byte, String> codes) {
        if (symbols.isEmpty()) {
            return;
        }

        // Базовый случай: один символ
        if (symbols.size() == 1) {
            codes.put(symbols.get(0).value, prefix.isEmpty() ? "0" : prefix);
            return;
        }

        // Находим точку разбиения для максимально равного деления по частотам
        int splitPoint = findOptimalSplitPoint(symbols);

        // Левая часть (более частые символы) - код '0'
        List<FanoSymbol> left = symbols.subList(0, splitPoint);
        assignFanoCodes(left, prefix + "0", codes);

        // Правая часть (менее частые символы) - код '1'
        List<FanoSymbol> right = symbols.subList(splitPoint, symbols.size());
        assignFanoCodes(right, prefix + "1", codes);
    }

    /**
     * Находит оптимальную точку разбиения списка на две части
     * с минимальной разницей суммарных частот.
     *
     * @param symbols список символов
     * @return индекс разбиения
     */
    private int findOptimalSplitPoint(List<FanoSymbol> symbols) {
        if (symbols.size() <= 1) {
            return 1;
        }

        // Вычисляем общую сумму частот
        long totalFrequency = 0;
        for (FanoSymbol s : symbols) {
            totalFrequency += s.frequency;
        }

        // Ищем точку разбиения, минимизирующую |leftSum - rightSum|
        long leftSum = 0;
        int bestSplit = 1;
        long minDifference = Long.MAX_VALUE;

        for (int i = 0; i < symbols.size() - 1; i++) {
            leftSum += symbols.get(i).frequency;
            long rightSum = totalFrequency - leftSum;
            long difference = Math.abs(leftSum - rightSum);

            if (difference < minDifference) {
                minDifference = difference;
                bestSplit = i + 1;
            }
        }

        return bestSplit;
    }

    /**
     * Записывает заголовок файла с таблицей частот.
     *
     * @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 FanoSymbol {
        byte value;
        long frequency;

        FanoSymbol(byte value, long frequency) {
            this.value = value;
            this.frequency = frequency;
        }
    }
}