Алгоритм RLE

Что такое архивация?

Архивация (или сжатие) - это процесс уменьшения размера файла путем особого способа его записи. Представьте, что у вас есть текст:

AAAAAABBCCCCCC

Вместо того чтобы хранить каждую букву отдельно, мы можем записать его как:

6A2B6C

Где цифра означает, сколько раз повторяется следующая буква. Таким образом, мы сократили 14 символов до 6!

Что такое RLE?

RLE (Run-Length Encoding) - это один из самых простых алгоритмов сжатия данных. Он особенно эффективен для файлов, где есть много повторяющихся последовательностей.

Как работает RLE?

Давайте разберем на простом примере:

Исходные данные: WWWWWWWWWWYYYZXX

1. Находим повторения:
   WWWWWWWWWW (10 W подряд)
   YYY (3 Y подряд)
   Z (1 Z)
   XX (2 X подряд)

2. Кодируем:
   10W3Y1Z2X

Добавим немного теории про байты

Что такое бит?

Бит - это наименьшая единица измерения информации, которая может быть представлена в компьютере. Он может быть либо 0, либо 1.

Что такое байт?

Байт - это единица измерения информации, которая состоит из 8 бит. Каждый бит может быть либо 0, либо 1. Таким образом, один байт может хранить числа от 0 до 255 (всего 256 различных значений).

Двоичная система и биты

Давайте разберем, как устроен байт:

1 байт = 8 бит
Биты нумеруются справа налево от 0 до 7:

Бит №:    7  6  5  4  3  2  1  0
Значение: 0  0  0  0  0  0  0  0

Каждый бит представляет степень двойки:

Бит №:    7    6    5    4    3    2    1    0
Степень:  2⁷   2⁶   2⁵   2⁴   2³   2²   2¹   2⁰
Значение: 128  64   32   16   8    4    2    1

128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

Двоичная запись числа

Чтобы понять, как записываются числа в двоичной системе, давайте разберем это на простом примере.

В обычной (десятичной) системе мы используем цифры от 0 до 9. А в двоичной системе используются только цифры 0 и 1.

Например, возьмем число 13:

Десятичная запись:  13
Двоичная запись:    1101

Как это работает? Давайте разберем по шагам:

1101 в двоичной системе означает:
- 1 в позиции 3 = 1 × 2³ = 1 × 8 = 8
- 1 в позиции 2 = 1 × 2² = 1 × 4 = 4
- 0 в позиции 1 = 0 × 2¹ = 0 × 2 = 0
- 1 в позиции 0 = 1 × 2⁰ = 1 × 1 = 1
Складываем все значения: 8 + 4 + 0 + 1 = 13

Это как считать по разрядам в обычных числах, только вместо степеней 10 используются степени 2!

Простой способ перевести число в двоичную систему - делить его на 2 и записывать остатки справа налево:

13 ÷ 2 = 6 (остаток 1)
6 ÷ 2 = 3  (остаток 0)
3 ÷ 2 = 1  (остаток 1)
1 ÷ 2 = 0  (остаток 1)

Результат (читаем остатки снизу вверх): 1101

Шестнадцатеричная запись числа

Шестнадцатеричная система (или hexadecimal) используется для удобного представления двоичных чисел. Вместо того, чтобы писать длинные последовательности 0 и 1, мы используем цифры от 0 до 9 и буквы от A до F.

В шестнадцатеричной системе каждый символ представляет число от 0 до 15:

0  = 0     4  = 4     8  = 8      C = 12
1  = 1     5  = 5     9  = 9      D = 13
2  = 2     6  = 6     A = 10      E = 14
3  = 3     7  = 7     B = 11      F = 15

Давайте разберем на примере, как число 173 (десятичное) записывается в шестнадцатеричной системе:

Делим число на 16 и записываем остатки справа налево:
```
173 ÷ 16 = 10 (остаток 13)
10 ÷ 16 = 0   (остаток 10)
```
Заменяем остатки на шестнадцатеричные символы:
- 13 = D
- 10 = A
Читаем справа налево: AD

Итак:

Десятичное число:      173
Шестнадцатеричное:     AD
Двоичное число:        10101101

Почему это удобно? Потому что каждая шестнадцатеричная цифра точно представляет 4 бита:

A    = 1010 (в двоичной)
D    = 1101 (в двоичной)
AD   = 1010 1101 (в двоичной)

Поэтому программисты часто используют шестнадцатеричную систему - она позволяет компактно записывать двоичные числа. Например, вместо того чтобы писать 11111111, можно просто написать FF!

Схема работы нашего улучшенного RLE алгоритма:

Исходные данные: WWWWWBBAAAAACCCC

1. Анализируем последовательности:
   - WWWWW (5 повторений) → Сжимаем как [0x85, W]  (0x85 = 128 + 5)
   - BB (2 повторения) → Не сжимаем, записываем как [0x02, B, B]
   - AAAAA (5 повторений) → Сжимаем как [0x85, A]
   - CCCC (4 повторения) → Сжимаем как [0x84, C]

В нашей реализации:

Если байт повторяется ≥4 раз, используем сжатие
Если повторений <4, записываем как есть
Первый байт каждой последовательности содержит информацию о типе последовательности:
- Если старший бит = 1 (0x80), это сжатая последовательность
- Если старший бит = 0, это несжатая последовательность

А почему 4 повторения?

Это связано с эффективностью сжатия. Давайте разберем почему:

При сжатии последовательности мы используем 2 байта:
- 1 байт для управляющего символа (счётчик + флаг)
- 1 байт для самого повторяющегося символа
При записи без сжатия мы используем:
- 1 байт для счётчика
- N байт для самих символов

Давайте сравним размеры:

Для 3 повторений:
Без сжатия:   [0x03, A, A, A]        = 4 байта
Со сжатием:   [0x83, A]              = 2 байта
Экономия: 2 байта

Для 4 повторений:
Без сжатия:   [0x04, A, A, A, A]     = 5 байт
Со сжатием:   [0x84, A]              = 2 байта
Экономия: 3 байта

Таким образом, реальная экономия места начинается именно с 4 повторений. При 3 повторениях и меньше выгоднее записывать символы как есть, без сжатия, так как накладные расходы на управляющие байты не окупаются.

Запись 0x85

Префикс 0x означает, что число записано в шестнадцатеричной системе счисления
85 - это само шестнадцатеричное число
В двоичной системе 0x85 выглядит так:

0x85 в двоичном виде:
1    0    0    0    0    1    0    1
2⁷   2⁶   2⁵   2⁴   2³   2²   2¹   2⁰
128  64   32   16   8    4    2    1

1*128 + 0*64 + 0*32 + 0*16 + 0*8 + 1*4 + 0*2 + 1*1 = 133

Почему 128 + число?

В нашем алгоритме мы используем старший бит (самый левый, бит №7) как флаг:

Если он равен 1 (128), это означает сжатую последовательность
Если он равен 0, это несжатая последовательность

Пример:

Хотим закодировать 5 повторений:
1. Устанавливаем старший бит (добавляем 128)
2. Добавляем количество повторений (5)
128 + 5 = 133 (или 0x85 в шестнадцатеричной системе)

В двоичном виде:
1    0    0    0    0    1    0    1
↑    |         5 в двоичном        |
флаг

Практический пример

Допустим, у нас есть последовательность "AAAAA":

1. Это 5 повторений, значит используем сжатие
2. Формируем управляющий байт:
   - 128 (флаг сжатия) + 5 (количество) = 133 (0x85)
3. Записываем в файл:
   - Первый байт: 0x85 (управляющий)
   - Второй байт: 'A' (сам символ)

При чтении:

1. Читаем первый байт (0x85)
2. Проверяем старший бит:
   0x85 & 0x80 = 128 (true) → это сжатая последовательность
3. Получаем количество:
   0x85 & 0x7F = 5 (убираем старший бит)
4. Читаем символ 'A'
5. Повторяем его 5 раз

Что значит эта запись 0x85 & 0x80?

В этой записи & - это побитовый оператор "И" (AND). Давайте посмотрим, как он работает:

Сначала числа переводятся в двоичную систему:

0x85 = 1000 0101
0x80 = 1000 0000

Операция & сравнивает каждую пару битов и возвращает 1 только если оба бита равны 1:

  1000 0101  (0x85)
& 1000 0000  (0x80)
-----------
  1000 0000  (128 в десятичной)

В нашем алгоритме RLE это используется для проверки старшего бита (самого левого):

Если результат равен 128, значит старший бит был 1 → это сжатая последовательность
Если результат равен 0, значит старший бит был 0 → это несжатая последовательность

Это очень распространённый приём в программировании, когда нужно проверить конкретный бит в числе. Операция & с маской (в нашем случае 0x80) "обнуляет" все биты кроме того, который мы хотим проверить.

А это чему равно 0x85 & 0x7F?

Давайте разберем эту операцию:

Переведем числа в двоичную систему:

0x85 = 1000 0101
0x7F = 0111 1111  (это маска, которая содержит все 1, кроме старшего бита)

Выполним побитовое И (&):

  1000 0101  (0x85)
& 0111 1111  (0x7F)
-----------
  0000 0101  (5 в десятичной)

В результате получаем 5.

Это очень полезная операция в нашем RLE алгоритме - она позволяет "убрать" старший бит (который использовался как флаг сжатия) и получить само значение счетчика повторений.

То есть:

0x85 & 0x80 проверяет, является ли последовательность сжатой
0x85 & 0x7F извлекает количество повторений (в данном случае 5)

Маска 0x7F (0111 1111) часто используется именно для этой цели - она "обнуляет" старший бит, оставляя все остальные биты без изменений.

Откуда берется второе число после амперсанда &?

В операциях с битами второе число (после &) называется "маской", и оно выбирается специально в зависимости от того, какие биты мы хотим проверить или извлечь:

Для проверки старшего бита используется маска 0x80:

0x80 = 1000 0000

Эта маска оставляет только самый левый бит, все остальные обнуляются.

Для извлечения значения без старшего бита используется маска 0x7F:

0x7F = 0111 1111

Эта маска обнуляет старший бит, но сохраняет все остальные.

Эти конкретные числа (0x80 и 0x7F) не случайны:

0x80 (128) - это минимальное число с установленным старшим битом
0x7F (127) - это максимальное число, которое можно записать в 7 бит

Другие часто используемые маски:

0xFF = 1111 1111  (все биты включены)
0x0F = 0000 1111  (включены только младшие 4 бита)
0xF0 = 1111 0000  (включены только старшие 4 бита)

В нашем RLE алгоритме мы используем именно 0x80 и 0x7F, потому что:

Старший бит используется как флаг сжатия
Оставшиеся 7 бит используются для хранения длины последовательности (до 127 символов)

Почему это удобно?

Один байт может хранить и тип последовательности (сжатая/несжатая), и её длину
Мы можем кодировать последовательности длиной до 127 символов (так как 7 бит остаются для хранения длины)
Это эффективно с точки зрения использования памяти

Теперь, когда вы понимаете, как работают байты и биты в нашем алгоритме, давайте рассмотрим еще несколько примеров:

Пример 1: 6 букв 'B'
Управляющий байт: 128 + 6 = 134 (0x86)
Запись: [0x86, 'B']

Пример 2: 3 разные буквы "XYZ"
Управляющий байт: 3 (без флага сжатия)
Запись: [0x03, 'X', 'Y', 'Z']

Разбор случая с 20 повторениями

Расчёт управляющего байта

20 в двоичном виде:     0 0 0 1 0 1 0 0
Добавляем флаг (128):   1 0 0 1 0 1 0 0

Бит №:    7    6    5    4    3    2    1    0
Значение: 1    0    0    1    0    1    0    0
Вес:      128  64   32   16   8    4    2    1

Итого: 128 + 20 = 148 (или 0x94 в шестнадцатеричной системе)

Визуальное представление для 20 повторений:

Исходные данные:
AAAAAAAAAAAAAAAAAAAA

Сжатые данные (2 байта):
[10010100, 01000001]
   ↑         ↑
   0x94      'A'

Разбор первого байта (0x94):
1 0010100
↑ ↑
| 20 в двоичном виде
Флаг сжатия

Это показывает, насколько эффективно работает сжатие: 20 байт исходного текста превращаются всего в 2 байта в архиве!

Пример с последовательностью "AAAAAAAAAAAAAAAAAAAA" (20 букв 'A')

1. Записываем управляющий байт: 0x94 (148)
   - Старший бит 1 (флаг сжатия)
   - Остальные биты содержат число 20
2. Записываем сам символ: 'A'

Итоговая запись в архиве: [0x94, 'A']

Проверка при чтении:

1. Читаем первый байт (0x94)
2. Проверяем старший бит:
   0x94 & 0x80 = 128 (true) → это сжатая последовательность
3. Получаем количество:
   0x94 & 0x7F = 20 (убираем старший бит)
4. Читаем символ 'A'
5. Повторяем его 20 раз

Сравнение эффективности:

Исходный размер: 20 байт
Сжатый размер:   2 байта
Степень сжатия:  90%

20 байт → 2 байта
Экономия: 18 байт

Это отличный пример того, почему RLE особенно эффективен для данных с большим количеством повторений. Чем длиннее последовательность повторяющихся символов (до 127), тем лучше степень сжатия.

Визуальная схема работы алгоритма

Входные данные: AAAAAABBBCC
                ↓
┌────────────────────────────────┐
│ Проход по символам и подсчет   │
│ повторений                     │
└────────────────────────────────┘
                ↓
┌────────────────────────────────┐
│ Проверка количества повторений │
└────────────────────────────────┘
                ↓
          count >= 4?
           /     \
         да      нет
         /         \
   Сжатие       Без сжатия
[128+count,X]   [count,X,X,...]

Условия и правила

1. Сжатая последовательность:
   ┌──────────────────────────┐
   │ Условие: count >= 4      │
   │ Формат: [128+count, sym] │
   │ Пример: AAAAA → [0x85,A] │
   └──────────────────────────┘

2. Несжатая последовательность:
   ┌─────────────────────────────────┐
   │ Условие: count < 4              │
   │ Формат: [count, sym, sym, ...]  │
   │ Пример: ABC → [0x03,A,B,C]      │
   └─────────────────────────────────┘

Пример пошагового разбора

Входные данные: "AAAAABBC"

1. Начало: current = 'A', count = 1

2. Обработка 'A':
   AAAAA → count = 5
   Сжатие: [0x85, 'A']  // 0x85 = 128 + 5

3. Обработка 'B':
   BB → count = 2
   Без сжатия: [0x02, 'B', 'B']

4. Обработка 'C':
   C → count = 1
   Без сжатия: [0x01, 'C']

Итоговый результат:
[0x85, 'A', 0x02, 'B', 'B', 0x01, 'C']

Процесс распаковки в памяти:

Буфер: [0x85, 'A', 0x02, 'B', 'B']
        ↓
        i=0: Читаем 0x85
             ↓
        i=1: Читаем 'A', повторяем 5 раз
             ↓
        i=2: Читаем 0x02
             ↓
        i=3,4: Копируем 'B', 'B'

Результат: [A, A, A, A, A, B, B]

Важное замечание

В нашем алгоритме мы можем закодировать максимум 127 повторений в одном управляющем байте. Так происходит потому что:

Старший бит занят под флаг (1)
Остаётся 7 бит для числа
2⁷ - 1 = 127 (максимальное число, которое можно записать в 7 бит)

Если у нас будет больше повторений, например 130, то последовательность нужно будет разбить:

Последовательность: AAAA...AAAA (130 раз)

Будет закодирована как:
[0xFF, 'A']  // 127 повторений (127 + 128 = 255 = 0xFF)
[0x83, 'A']  // оставшиеся 3 повторения (3 + 128 = 131 = 0x83)