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

Library/src/main/java/org/example/BookStackCompressor.java
205 строк5 KB
Dixix404
Change BookStack
16 дек 2025, 01:29
16 дек 2025, 01:29a013a3e
package org.example;

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

public class BookStackCompressor implements Compressor {

    private static final int BLOCK_SIZE = 100000;
    private static final byte[] MAGIC = {'B','S','T','K'};

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

    @Override
    public void compress(InputStream in, OutputStream out) throws IOException {
        DataOutputStream dos = new DataOutputStream(out);
        dos.write(MAGIC);
        dos.writeInt(BLOCK_SIZE);

        byte[] buffer = new byte[BLOCK_SIZE];
        int bytesRead;

        while ((bytesRead = in.read(buffer)) > 0) {
            byte[] block = Arrays.copyOf(buffer, bytesRead);

            BWTResult bwt = fastBWT(block);
            byte[] mtf = fastMTF(bwt.data);
            byte[] rle = simpleRLE(mtf);

            dos.writeInt(bwt.index);
            dos.writeInt(rle.length);
            dos.write(rle);
        }
        dos.flush();
    }

    @Override
    public void decompress(InputStream in, OutputStream out) throws IOException {
        DataInputStream dis = new DataInputStream(in);

        byte[] magic = new byte[4];
        dis.readFully(magic);
        if (!Arrays.equals(magic, MAGIC)) {
            throw new IOException("Not a BSTK file");
        }

        int blockSize = dis.readInt();

        try {
            while (true) {
                int index = dis.readInt();
                int len = dis.readInt();
                byte[] rle = new byte[len];
                dis.readFully(rle);

                byte[] mtf = decodeRLE(rle);
                byte[] bwt = decodeMTF(mtf);
                byte[] orig = reverseBWT(bwt, index);

                out.write(orig);
            }
        } catch (EOFException e) {
            // EOF
        }
        out.flush();
    }
    private BWTResult fastBWT(byte[] data) {
        int n = data.length;
        Integer[] sa = new Integer[n];
        for (int i = 0; i < n; i++) sa[i] = i;

        Arrays.sort(sa, (a, b) -> {
            for (int i = 0; i < n; i++) {
                int ca = data[(a + i) % n] & 0xFF;
                int cb = data[(b + i) % n] & 0xFF;
                if (ca != cb) return ca - cb;
            }
            return 0;
        });

        byte[] L = new byte[n];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            L[i] = data[(sa[i] + n - 1) % n];
            if (sa[i] == 0) idx = i;
        }

        return new BWTResult(L, idx);
    }

    private byte[] reverseBWT(byte[] L, int idx) {
        int n = L.length;
        int[] count = new int[257];
        for (byte b : L) count[(b & 0xFF) + 1]++;
        for (int i = 0; i < 256; i++) count[i + 1] += count[i];

        int[] next = new int[n];
        for (int i = 0; i < n; i++) {
            int c = L[i] & 0xFF;
            next[count[c]++] = i;
        }

        byte[] orig = new byte[n];
        int pos = idx;
        for (int i = 0; i < n; i++) {
            orig[i] = L[pos];
            pos = next[pos];
        }
        return orig;
    }

    private byte[] fastMTF(byte[] data) {
        byte[] result = new byte[data.length];
        byte[] list = new byte[256];
        for (int i = 0; i < 256; i++) list[i] = (byte) i;

        for (int i = 0; i < data.length; i++) {
            byte sym = data[i];

            int idx = 0;
            while (list[idx] != sym) idx++;
            result[i] = (byte) idx;

            if (idx > 0) {
                System.arraycopy(list, 0, list, 1, idx);
                list[0] = sym;
            }
        }
        return result;
    }

    private byte[] decodeMTF(byte[] data) {
        byte[] result = new byte[data.length];
        byte[] list = new byte[256];
        for (int i = 0; i < 256; i++) list[i] = (byte) i;

        for (int i = 0; i < data.length; i++) {
            int idx = data[i] & 0xFF;
            byte sym = list[idx];
            result[i] = sym;

            if (idx > 0) {
                System.arraycopy(list, 0, list, 1, idx);
                list[0] = sym;
            }
        }
        return result;
    }

    private byte[] simpleRLE(byte[] data) {
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int i = 0;

        while (i < data.length) {
            byte val = data[i];
            int count = 1;
            while (i + count < data.length && data[i + count] == val && count < 255) {
                count++;
            }

            if (count > 3 || val == 0) {
                out.write(0);
                out.write(count);
                out.write(val & 0xFF);
            } else {
                for (int j = 0; j < count; j++) {
                    out.write(val & 0xFF);
                }
            }
            i += count;
        }
        return out.toByteArray();
    }

    private byte[] decodeRLE(byte[] data) {
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int i = 0;

        while (i < data.length) {
            if (data[i] == 0 && i + 2 < data.length) {
                int count = data[i + 1] & 0xFF;
                byte val = data[i + 2];
                for (int j = 0; j < count; j++) {
                    out.write(val & 0xFF);
                }
                i += 3;
            } else {
                out.write(data[i] & 0xFF);
                i++;
            }
        }
        return out.toByteArray();
    }

    private static class BWTResult {
        byte[] data;
        int index;
        BWTResult(byte[] data, int index) {
            this.data = data;
            this.index = index;
        }
    }
}