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

Library/src/main/java/org/example/Lz77Compressor.java
166 строк6 KB
Dixix404
Lz77 Algorithm + changing keys structure
15 дек 2025, 20:19
15 дек 2025, 20:19f951cb8
package org.example;

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

public class Lz77Compressor implements Compressor {

    // Размер окна поиска (search buffer)
    private static final int WINDOW_SIZE = 4096;

    // Размер буфера просмотра (look-ahead buffer)
    private static final int LOOKAHEAD_SIZE = 256;

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

    /**
     * @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);

        if (data.length == 0) {
            // Пустой файл - маркер конца
            dos.writeShort(0);
            dos.writeShort(0);
            dos.writeByte(-1);
            dos.flush();
            return;
        }

        int pos = 0;

        while (pos < data.length) {
            // Находим самое длинное совпадение в окне поиска
            Match match = findLongestMatch(data, pos);

            // Определяем следующий байт после совпадения
            int nextBytePos = pos + match.length;
            byte nextByte = (nextBytePos < data.length) ? data[nextBytePos] : -1;

            // Записываем тройку (offset, length, next_byte)
            dos.writeShort(match.offset);
            dos.writeShort(match.length);
            dos.writeByte(nextByte);

            // Сдвигаем позицию
            pos += match.length + 1;
        }

        // Маркер конца потока
        dos.writeShort(0);
        dos.writeShort(0);
        dos.writeByte(-1);

        dos.flush();
    }

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

        while (true) {
            // Читаем тройку
            int offset = dis.readShort() & 0xFFFF;  // беззнаковый short
            int length = dis.readShort() & 0xFFFF;
            int nextByte = dis.readByte();

            // Проверяем маркер конца
            if (offset == 0 && length == 0 && nextByte == -1) {
                break;
            }

            // Копируем совпадение из уже декодированных данных
            byte[] decodedData = decoded.toByteArray();
            int startPos = decodedData.length - offset;

            for (int i = 0; i < length; i++) {
                // Важно: можем ссылаться на данные, которые только что записали
                // (когда offset < length, происходит самореференция)
                byte b = decoded.toByteArray()[startPos + i];
                decoded.write(b);
            }

            // Записываем следующий байт (если не маркер конца)
            if (nextByte != -1) {
                decoded.write(nextByte);
            }
        }

        // Записываем результат
        decoded.writeTo(out);
        out.flush();
    }

    /**
     * @param data массив данных
     * @param currentPos текущая позиция кодирования
     * @return информация о найденном совпадении
     */
    private Match findLongestMatch(byte[] data, int currentPos) {
        int bestOffset = 0;
        int bestLength = 0;

        // Определяем границы окна поиска
        int windowStart = Math.max(0, currentPos - WINDOW_SIZE);
        int windowEnd = currentPos;

        // Определяем размер буфера просмотра
        int lookaheadEnd = Math.min(data.length, currentPos + LOOKAHEAD_SIZE);

        // Ищем все возможные совпадения в окне
        for (int i = windowStart; i < windowEnd; i++) {
            int matchLength = 0;

            // Считаем длину совпадения
            while (currentPos + matchLength < lookaheadEnd &&
                    data[i + matchLength] == data[currentPos + matchLength]) {
                matchLength++;

                // Не даём выйти за границы окна поиска при самореференции
                if (i + matchLength >= currentPos) {
                    break;
                }
            }

            // Обновляем лучшее совпадение
            if (matchLength > bestLength) {
                bestLength = matchLength;
                bestOffset = currentPos - i;
            }
        }

        return new Match(bestOffset, bestLength);
    }

    private static class Match {
        int offset;  // Расстояние назад до начала совпадения
        int length;  // Длина совпадения

        Match(int offset, int length) {
            this.offset = offset;
            this.length = length;
        }
    }
}