Method compress

src/main/java/com/thealgorithms/compression/LZ77.java:54–124

Compresses the input text using the LZ77 algorithm. @param text The input string to compress. Must not be null. @param windowSize The size of the sliding window (search buffer). Must be positive. @param lookaheadBufferSize The size of the lookahead buffer. Must be positive. @return A list of {@link

(String text, int windowSize, int lookaheadBufferSize)

     * @throws IllegalArgumentException if windowSize or lookaheadBufferSize are not positive.
     */
    public static List<Token> compress(String text, int windowSize, int lookaheadBufferSize) {
        if (text == null) {
            return new ArrayList<>();
        }
        if (windowSize <= 0 || lookaheadBufferSize <= 0) {
            throw new IllegalArgumentException("Window size and lookahead buffer size must be positive.");
        }

        List<Token> compressedOutput = new ArrayList<>();
        int currentPosition = 0;

        while (currentPosition < text.length()) {
            int bestMatchDistance = 0;
            int bestMatchLength = 0;

            // Define the start of the search window
            int searchBufferStart = Math.max(0, currentPosition - windowSize);
            // Define the end of the lookahead buffer (don't go past text length)
            int lookaheadEnd = Math.min(currentPosition + lookaheadBufferSize, text.length());

            // Search for the longest match in the window
            for (int i = searchBufferStart; i < currentPosition; i++) {
                int currentMatchLength = 0;

                // Check how far the match extends into the lookahead buffer
                // This allows for overlapping matches (e.g., "aaa" can match with offset 1)
                while (currentPosition + currentMatchLength < lookaheadEnd) {
                    int sourceIndex = i + currentMatchLength;

                    // Handle overlapping matches (run-length encoding within LZ77)
                    // When we've matched beyond our starting position, wrap around using modulo
                    if (sourceIndex >= currentPosition) {
                        int offset = currentPosition - i;
                        sourceIndex = i + (currentMatchLength % offset);
                    }

                    if (text.charAt(sourceIndex) == text.charAt(currentPosition + currentMatchLength)) {
                        currentMatchLength++;
                    } else {
                        break;
                    }
                }

                // If this match is longer than the best found so far
                if (currentMatchLength > bestMatchLength) {
                    bestMatchLength = currentMatchLength;
                    bestMatchDistance = currentPosition - i; // Calculate offset from current position
                }
            }

            char nextChar;
            if (currentPosition + bestMatchLength < text.length()) {
                nextChar = text.charAt(currentPosition + bestMatchLength);
            } else {
                nextChar = END_OF_STREAM;
            }

            // Add the token to the output