Library/src/main/java/org/example/LZWCompressor.java - master - Dixix404/Image_Compression

Library/src/main/java/org/example/LZWCompressor.java
269 строк10 KB
Dixix404
Algorithm LZW
16 дек 2025, 00:10
16 дек 2025, 00:107dedccb
package org.example;

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

public class LZWCompressor implements Compressor {

    private static final byte[] SIGNATURE = {'L', 'Z', 'W', 0};
    private static final int INITIAL_DICT_SIZE = 256;  // Одиночные байты
    private static final int MAX_DICT_SIZE = 65536;    // Максимум словаря (2^16)

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

    /**
     * @param inputBmpPath путь к входному BMP файлу
     * @param outputPath путь к выходному сжатому файлу
     * @throws IOException при ошибках чтения/записи
     */
    @Override
    public void compress(String inputBmpPath, String outputPath) throws IOException {
        // Читаем BMP
        BMPImage image = new BMPImage();
        image.read(inputBmpPath);

        // Получаем пиксельные данные
        byte[][] pixels = image.getPixels();
        int height = image.getHeight();
        int width = image.getWidth();

        // Преобразуем 2D массив в 1D для LZW кодирования
        byte[] flatPixels = flattenPixels(pixels);

        // Применяем LZW кодирование
        List<Integer> compressed = compressLZW(flatPixels);

        // Записываем сжатый файл
        try (DataOutputStream dos = new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(outputPath)))) {

            // Записываем сигнатуру
            dos.write(SIGNATURE);

            // Записываем BMP заголовки
            dos.write(image.getFileHeader());
            dos.write(image.getInfoHeader());

            // Записываем размеры
            dos.writeInt(width);
            dos.writeInt(height);
            dos.writeInt(flatPixels.length);  // Размер несжатых данных

            // Записываем сжатые данные (индексы словаря)
            for (int code : compressed) {
                dos.writeInt(code);
            }
        }
    }

    /**
     * @param inputPath путь к сжатому файлу
     * @param outputBmpPath путь к выходному BMP файлу
     * @throws IOException при ошибках чтения/записи
     */
    @Override
    public void decompress(String inputPath, String outputBmpPath) throws IOException {
        try (DataInputStream dis = new DataInputStream(
                new BufferedInputStream(new FileInputStream(inputPath)))) {

            // Читаем и проверяем сигнатуру
            byte[] signature = new byte[4];
            dis.readFully(signature);

            if (!Arrays.equals(signature, SIGNATURE)) {
                throw new IOException("Неверная сигнатура файла (не LZW формат)");
            }

            // Читаем BMP заголовки
            byte[] fileHeader = new byte[14];
            byte[] infoHeader = new byte[40];
            dis.readFully(fileHeader);
            dis.readFully(infoHeader);

            // Читаем размеры
            int width = dis.readInt();
            int height = dis.readInt();
            int uncompressedSize = dis.readInt();

            // Читаем сжатые данные
            List<Integer> compressed = new ArrayList<>();
            try {
                while (true) {
                    compressed.add(dis.readInt());
                }
            } catch (EOFException e) {
                // Конец файла - это нормально
            }

            // Декодируем LZW данные
            byte[] decodedPixels = decompressLZW(compressed, uncompressedSize);

            // Преобразуем обратно в 2D массив
            byte[][] pixels = unflattenPixels(decodedPixels, height, width);

            // Создаём и записываем BMP
            BMPImage image = new BMPImage();
            image.setHeaders(fileHeader, infoHeader, width, height);
            image.setPixels(pixels);
            image.write(outputBmpPath);
        }
    }

    /**
     * @param data исходные данные
     * @return список индексов словаря
     */
    private List<Integer> compressLZW(byte[] data) {
        List<Integer> result = new ArrayList<>();

        // Инициализируем словарь одиночными байтами
        Map<List<Byte>, Integer> dictionary = new HashMap<>();
        for (int i = 0; i < INITIAL_DICT_SIZE; i++) {
            List<Byte> entry = new ArrayList<>();
            entry.add((byte) i);
            dictionary.put(entry, i);
        }
        int nextCode = INITIAL_DICT_SIZE;

        // Текущая последовательность
        List<Byte> current = new ArrayList<>();

        for (byte b : data) {
            List<Byte> next = new ArrayList<>(current);
            next.add(b);

            if (dictionary.containsKey(next)) {
                // Последовательность в словаре - продолжаем
                current = next;
            } else {
                // Выводим код текущей последовательности
                result.add(dictionary.get(current));

                // Добавляем новую последовательность в словарь
                if (nextCode < MAX_DICT_SIZE) {
                    dictionary.put(next, nextCode++);
                }

                // Начинаем новую последовательность
                current = new ArrayList<>();
                current.add(b);
            }
        }

        // Выводим последнюю последовательность
        if (!current.isEmpty()) {
            result.add(dictionary.get(current));
        }

        return result;
    }

    /**
     * @param compressed список индексов словаря
     * @param expectedSize ожидаемый размер несжатых данных
     * @return распакованные данные
     * @throws IOException при ошибках декодирования
     */
    private byte[] decompressLZW(List<Integer> compressed, int expectedSize) throws IOException {
        ByteArrayOutputStream output = new ByteArrayOutputStream(expectedSize);

        // Инициализируем словарь одиночными байтами
        Map<Integer, List<Byte>> dictionary = new HashMap<>();
        for (int i = 0; i < INITIAL_DICT_SIZE; i++) {
            List<Byte> entry = new ArrayList<>();
            entry.add((byte) i);
            dictionary.put(i, entry);
        }
        int nextCode = INITIAL_DICT_SIZE;

        if (compressed.isEmpty()) {
            return output.toByteArray();
        }

        // Читаем первый код
        int oldCode = compressed.get(0);
        List<Byte> sequence = dictionary.get(oldCode);
        if (sequence == null) {
            throw new IOException("Неверный код в сжатых данных: " + oldCode);
        }

        for (byte b : sequence) {
            output.write(b);
        }

        // Обрабатываем остальные коды
        for (int i = 1; i < compressed.size(); i++) {
            int code = compressed.get(i);
            List<Byte> entry;

            if (dictionary.containsKey(code)) {
                // Код в словаре
                entry = dictionary.get(code);
            } else if (code == nextCode) {
                // Специальный случай: код ещё не в словаре
                entry = new ArrayList<>(sequence);
                entry.add(sequence.get(0));
            } else {
                throw new IOException("Неверный код LZW: " + code);
            }

            // Выводим последовательность
            for (byte b : entry) {
                output.write(b);
            }

            // Добавляем новую последовательность в словарь
            if (nextCode < MAX_DICT_SIZE) {
                List<Byte> newEntry = new ArrayList<>(sequence);
                newEntry.add(entry.get(0));
                dictionary.put(nextCode++, newEntry);
            }

            sequence = entry;
        }

        return output.toByteArray();
    }

    /**
     * @param pixels массив [height][width * 3]
     * @return плоский массив байтов
     */
    private byte[] flattenPixels(byte[][] pixels) {
        int totalBytes = 0;
        for (byte[] row : pixels) {
            totalBytes += row.length;
        }

        byte[] flat = new byte[totalBytes];
        int offset = 0;

        for (byte[] row : pixels) {
            System.arraycopy(row, 0, flat, offset, row.length);
            offset += row.length;
        }

        return flat;
    }

    /**
     * @param flat плоский массив байтов
     * @param height высота изображения
     * @param width ширина изображения
     * @return массив [height][width * 3]
     */
    private byte[][] unflattenPixels(byte[] flat, int height, int width) {
        byte[][] pixels = new byte[height][width * 3];
        int offset = 0;

        for (int y = 0; y < height; y++) {
            System.arraycopy(flat, offset, pixels[y], 0, width * 3);
            offset += width * 3;
        }

        return pixels;
    }
}