RLE & BWT. Кодер и декодер

1.

2.

3.

4.

5.

6.

7.

Кодирование длин серий (англ. run-length encoding, RLE)
или кодирование повторов — алгоритм сжатия данных,
заменяющий повторяющиеся символы (серии) на один
символ и число его повторов. Серией называется
последовательность, состоящая из нескольких одинаковых
символов. При кодировании (упаковке, сжатии) строка
одинаковых символов, составляющих серию, заменяется
строкой, содержащей сам повторяющийся символ и
количество его повторов. Это преобразование не изменяет
сами символы, а изменяет только их порядок в строке, при
этом повторяющиеся подстроки после применения
перестановки собираются в плотные группы, которые
гораздо лучше сжимаются с помощью алгоритма RLE.

8.

Файл
Размер
Результат
сжатия
BWT
350 Кб
128,5 Кб
169,3 Кб
147,0 КБ
Текстовый
файл
11 Кб
63,2%
1035,7Кб
14,6 Кб
13,6 Кб
1002 Кб
Без
BWT
Степень сжатия Размер
блока
в
BWT
Без
байтах
BWT
51,6%
58,0%
512
-196,3%
33,9%
32,2 Кб
-25,26%
2048
8192
512
-195,1%
2048
6,6 Кб
39,2%
8192
1366,2 Кб
-36,5%
512
1238,5 Кб
442,1 Кб
2353,9 КБ
-23,7%
55,8%
-195%
2048
8192

9.

Результат сжатия
500
Размер после сжатия
450
400
350
300
250
200
150
100
50
0
Исходный размер
Результат сжатия
Размер блока: 8192 байта