Сжатие строки (Run-Length Encoding)

Сжатие строки методом Run-Length Encoding (RLE)

Run-Length Encoding — это простой, но эффективный алгоритм сжатия данных, который замещает последовательные одинаковые символы на сам символ и количество его повторений.

Алгоритм

1. Проверить, будет ли сжатая строка меньше оригинала
2. Пройти по строке и считать последовательные одинаковые символы
3. Добавить в результат символ и его количество
4. Если итоговая длина >= оригинальной, вернуть оригинал

Основное решение

public class RunLengthEncoding {
    
    /**
     * Сжимает строку методом Run-Length Encoding
     * 
     * @param str исходная строка
     * @return сжатая строка или оригинал, если сжатие неэффективно
     */
    public static String compress(String str) {
        // Шаг 1: Null и empty check
        if (str == null || str.isEmpty()) {
            return str;
        }
        
        // Шаг 2: Вычислить размер сжатой строки
        int compressedLength = getCompressedLength(str);
        
        // Если сжатая строка не короче, вернуть оригинал
        if (compressedLength >= str.length()) {
            return str;
        }
        
        // Шаг 3: Выполнить сжатие
        StringBuilder compressed = new StringBuilder(compressedLength);
        int count = 1;
        
        for (int i = 0; i < str.length(); i++) {
            // Если следующий символ отличается, добавляем текущий
            if (i + 1 >= str.length() || 
                str.charAt(i) != str.charAt(i + 1)) {
                
                compressed.append(str.charAt(i));
                compressed.append(count);
                count = 1;
            } else {
                count++;
            }
        }
        
        return compressed.toString();
    }
    
    /**
     * Вычисляет размер сжатой строки БЕЗ фактического сжатия
     * Оптимизация: если размер >= оригинального, останавливаемся
     */
    private static int getCompressedLength(String str) {
        int compressedLength = 0;
        int count = 1;
        
        for (int i = 0; i < str.length(); i++) {
            // Если следующий символ отличается
            if (i + 1 >= str.length() || 
                str.charAt(i) != str.charAt(i + 1)) {
                
                // Добавляем символ + количество (количество может быть 1-5 цифр)
                compressedLength += 1 + String.valueOf(count).length();
                count = 1;
            } else {
                count++;
            }
            
            // Оптимизация: если уже больше или равно оригиналу, можем вернуть
            if (compressedLength >= str.length()) {
                return str.length();  // Не имеет смысла сжимать
            }
        }
        
        return compressedLength;
    }
}

Тестирование

public class Main {
    public static void main(String[] args) {
        // Примеры, где сжатие эффективно
        testCompress("aabcccccaaa", "a2b1c5a3");
        testCompress("aaa", "a3");
        testCompress("aaaa", "a4");
        testCompress("aaaaaaaaaaaaabbbbccd", "a12b4c2d1");
        
        // Примеры, где сжатие неэффективно (возвращаем оригинал)
        testCompress("abcd", "abcd");
        testCompress("abcdef", "abcdef");
        testCompress("aabbcc", "aabbcc");  // a2b2c2 = 6 символов, оригинал = 6
        
        // Edge cases
        testCompress("", "");
        testCompress("a", "a");
        testCompress("aa", "aa");  // a2 = 2 символа, оригинал = 2 символа
    }
    
    private static void testCompress(String input, String expected) {
        String result = RunLengthEncoding.compress(input);
        String status = result.equals(expected) ? "✓" : "✗";
        System.out.println(status + " Input: \"" + input + "\" → \"" + 
                         result + "\" (expected: \"" + expected + "\")");
    }
}

Декомпрессия

Часто нужно уметь распаковывать сжатую строку:

public class RunLengthDecoding {
    
    /**
     * Распаковывает строку из RLE формата
     * 
     * @param compressed сжатая строка в формате RLE
     * @return распакованная строка
     */
    public static String decompress(String compressed) {
        if (compressed == null || compressed.isEmpty()) {
            return compressed;
        }
        
        StringBuilder decompressed = new StringBuilder();
        int i = 0;
        
        while (i < compressed.length()) {
            char character = compressed.charAt(i);
            i++;
            
            // Читаем число
            StringBuilder countStr = new StringBuilder();
            while (i < compressed.length() && 
                   Character.isDigit(compressed.charAt(i))) {
                countStr.append(compressed.charAt(i));
                i++;
            }
            
            // Если нет числа, это ошибка
            if (countStr.length() == 0) {
                throw new IllegalArgumentException(
                    "Invalid RLE format at position " + (i - 1)
                );
            }
            
            int count = Integer.parseInt(countStr.toString());
            
            // Добавляем символ count раз
            for (int j = 0; j < count; j++) {
                decompressed.append(character);
            }
        }
        
        return decompressed.toString();
    }
}

// Тестирование декомпрессии
public class DecompressionTest {
    public static void main(String[] args) {
        testDecompress("a2b1c5a3", "aabcccccaaa");
        testDecompress("a3", "aaa");
        testDecompress("a12b4c2d1", "aaaaaaaaaaaaabbbbccd");
    }
    
    private static void testDecompress(String compressed, String expected) {
        String result = RunLengthDecoding.decompress(compressed);
        String status = result.equals(expected) ? "✓" : "✗";
        System.out.println(status + " \"" + compressed + "\" → \"" + 
                         result + "\"");
    }
}

Анализ сложности

// Временная сложность: O(n)
// - Один проход по строке для вычисления размера: O(n)
// - Один проход по строке для сжатия: O(n)
// - Всего: O(n) + O(n) = O(n)

// Пространственная сложность: O(n)
// - StringBuilder хранит сжатую строку
// - В худшем случае (нет повторений) размер = оригинальному: O(n)

Оптимизированное решение

Можно оптимизировать, чтобы не вычислять размер дважды:

public class RunLengthEncodingOptimized {
    
    public static String compress(String str) {
        if (str == null || str.isEmpty()) {
            return str;
        }
        
        // Проверяем и одновременно сжимаем
        StringBuilder compressed = new StringBuilder();
        int count = 1;
        
        for (int i = 0; i < str.length(); i++) {
            // Если следующий символ отличается, добавляем
            if (i + 1 >= str.length() || 
                str.charAt(i) != str.charAt(i + 1)) {
                
                compressed.append(str.charAt(i));
                compressed.append(count);
                
                // Оптимизация: проверяем на лету
                if (compressed.length() >= str.length()) {
                    return str;  // Сжатие неэффективно
                }
                
                count = 1;
            } else {
                count++;
            }
        }
        
        return compressed.toString();
    }
}

Практические применения RLE

1. Факс и черно-белые изображения — очень эффективно
2. Текстовые файлы — часто неэффективно
3. Последовательности ДНК — может быть эффективно
4. Логотипы и графика — зависит от содержимого
5. Телеметрия — если данные имеют паттерны

Сравнение с другими алгоритмами

• RLE — простой, быстрый, но не всегда эффективный
• Huffman Coding — лучше для текста, сложнее в реализации
• LZW — универсальный, используется в GIF/TIFF
• DEFLATE — основа ZIP, отличные соотношения (RLE + Huffman)

Ключевые моменты при реализации

1. StringBuilder вместо String конкатенации — критично для производительности
2. Проверка размера сжатой строки — не всегда сжатие полезно
3. Правильная обработка чисел больше 9 — "a12" не "a1" + "2"
4. Edge cases — пустая строка, один символ, четные последовательности
5. Временная сложность O(n) — один или два прохода, не больше

Это классический алгоритм, часто появляющийся на интервью для проверки понимания циклов, строк и оптимизации памяти.