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

Library/src/main/java/org/example/Lz78Compressor.java
151 строка5 KB
Dixix404
Lz78 Algorithm + changing keys structure + Проверка работы Алгоритмов на большом текстовом файле
15 дек 2025, 21:10
15 дек 2025, 21:109a96cad
package org.example;

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

public class Lz78Compressor implements Compressor {

    private static final int MAX_DICTIONARY_SIZE = 65536; // Максимум фраз в словаре

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

    /**
     * @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.writeInt(-1);
            dos.writeByte(-1);
            dos.flush();
            return;
        }

        // Инициализация словаря (trie)
        TrieNode root = new TrieNode();
        int nextDictionaryIndex = 1; // 0 зарезервирован для пустой фразы

        int pos = 0;

        while (pos < data.length) {
            // Ищем самую длинную фразу в словаре
            TrieNode current = root;
            int phraseIndex = 0; // Индекс пустой фразы
            int matchLength = 0;

            while (pos + matchLength < data.length) {
                byte symbol = data[pos + matchLength];

                if (current.children.containsKey(symbol)) {
                    current = current.children.get(symbol);
                    phraseIndex = current.index;
                    matchLength++;
                } else {
                    break;
                }
            }

            // Определяем следующий символ
            byte nextSymbol = (pos + matchLength < data.length) ? data[pos + matchLength] : -1;

            // Выводим пару (индекс фразы, следующий символ)
            dos.writeInt(phraseIndex);
            dos.writeByte(nextSymbol);

            // Добавляем новую фразу в словарь (если есть следующий символ и место в словаре)
            if (nextSymbol != -1 && nextDictionaryIndex < MAX_DICTIONARY_SIZE) {
                TrieNode newNode = new TrieNode();
                newNode.index = nextDictionaryIndex++;
                current.children.put(nextSymbol, newNode);
            }

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

        // Маркер конца потока
        dos.writeInt(-1);
        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);

        // Словарь фраз: индекс → фраза
        Map<Integer, byte[]> dictionary = new HashMap<>();
        dictionary.put(0, new byte[0]); // Пустая фраза с индексом 0

        int nextDictionaryIndex = 1;

        while (true) {
            // Читаем пару
            int phraseIndex = dis.readInt();
            int nextSymbol = dis.readByte();

            // Проверяем маркер конца
            if (phraseIndex == -1 && nextSymbol == -1) {
                break;
            }

            // Восстанавливаем фразу
            byte[] phrase = dictionary.get(phraseIndex);

            if (phrase == null) {
                throw new IOException("Неверный индекс фразы в словаре: " + phraseIndex);
            }

            // Записываем фразу
            out.write(phrase);

            // Записываем следующий символ (если не конец)
            if (nextSymbol != -1) {
                out.write(nextSymbol);

                // Добавляем новую фразу в словарь
                if (nextDictionaryIndex < MAX_DICTIONARY_SIZE) {
                    byte[] newPhrase = new byte[phrase.length + 1];
                    System.arraycopy(phrase, 0, newPhrase, 0, phrase.length);
                    newPhrase[phrase.length] = (byte) nextSymbol;
                    dictionary.put(nextDictionaryIndex++, newPhrase);
                }
            }
        }

        out.flush();
    }

    private static class TrieNode {
        int index;                              // Индекс фразы, заканчивающейся в этом узле
        Map<Byte, TrieNode> children;          // Дети: символ → узел

        TrieNode() {
            this.index = 0;
            this.children = new HashMap<>();
        }
    }
}