Как я создал архиватор из задачки с техсобеса: сжатие файлов с помощью RLE

Привет, меня зовут Рома. Я работаю в KTS на позиции Python backend-разработчика. 

Однажды мне взбрело в голову написать собственную имплементацию алгоритма сжатия RLE. В этой статье рассказываю подробнее про RLE: что это за зверь такой, где используется, чем плох, чем хорош, и какие неожиданные сложности могут возникнуть при попытке имплементации.

Оглавление

• Немного про bzip2

• Что такое RLE

  • Данные «из жизни»

  • Предобработанные данные «из жизни»

• Варианты имплементации

  • Попытка №1. Наивный алгоритм

  • Попытка №2. Флаг счётчика

    • Попытка №2.1 Сжатие потока флагов

  • Попытка №3. Удвоение символов

  • Попытка №4. PackBits

• Итого по имплементации

  • Сжатие потока флагов

  • Удвоение символов

  • PackBits

• Заключение

Дело было поздней осенью, я сидел без работы, в голову лезли тревожные мысли о скором начале третьей мировой войны и неизбежном крахе человеческой цивилизации. Я решил написать алгоритм сжатия bzip2 в режиме «постапокалипсиса», когда все библиотеки вымерли и пришлось писать свою с нуля. В рамках челленджа запретил себе использовать сторонние библиотеки, за исключением инструментов отладки и тестирования. И так уж вышло, что RLE является частью bzip2. Затем я взял кусок своего (условно) готового проекта bzip2 и попытался превратить его во что-то человеко-читаемое, транслирующее пережитый опыт — так получилась эта статья. 

Пару слов обо мне. Я работаю программистом уже около семи лет, но по образованию я инженер-математик (как морская свинка, которая и не морская, и не свинка). Мне всегда нравилось возиться со всякими алгоритмическими задачками типа расстановки ферзей или решателей судоку – там, где программирование сильнее соприкасается с математикой. Я постоянно участвую в каких-то олимпиадных программистских контестах, решил половину литкода (сертифицированная LeetCode-обезьяна!), периодически прохожу всякие около-бесплатные курсы около-алгоритмической тематики. Не сказать, чтобы у меня был особый талант (как в программировании, так и в математике), но в усидчивости мне не откажешь. В общем, для меня это нормально – закодить какой-то алгоритм по фану в свободное время.

Мой основной язык программирования – Python, и весь код моего домашнего проекта написан на нём. Естественно, всё, что я пишу, будет проигрывать в скорости коду на C (на котором написан оригинальный bzip2). Мой RLE-велосипед был сделан just-for-fun, и ни один кусок его кода не попадёт в продакшен. В своё оправдание могу сказать, что мой челлендж состоял не в максимизации производительности, а в обретении более глубокого понимания процессов, происходящих в архиваторах. Кроме того, правильно написанный алгоритм будет одинаково хорошо сжимать файлы вне зависимости от языка программирования.

Немного про bzip2

Это алгоритм сжатия и одноимённая программа-архиватор. Далее в статье речь пойдёт только об алгоритме. Одной строкой его можно описать вот так:

Здесь каждая аббревиатура – это некая обратимая трансформация данных, все вместе они составляют конвейер, где блоки данных движутся слева-направо, а при деархивации – справа-налево. В совокупности эти трансформации делают так, что блоки на выходе обычно получаются меньше по размеру, чем на входе.

Из всех четырёх, RLE и HFC отвечают за сжатие, а BWT и MTF – вспомогательные инструменты-катализаторы, которые не меняют размер блоков, но переставляют в них байты таким образом, что их становится легче сжимать.

Как видите, загадочная аббревиатура RLE играет в этом процессе настолько важную роль, что встречается там целых два раза. Про RLE будет подробно рассказано чуть ниже. Что касается остальных акронимов:

• BWT – преобразование Барроуза-Уилера – самая заумная заумь из всех четырёх

• MTF – move-to-front-преобразование – самое простое из всех четырёх (проще, чем RLE)

• HFC – кодирование Хаффмана – по сложности где-то между RLE и BWT 

Что такое RLE

RLE – это аббревиатура от “run-length encoding”. По-русски обычно переводят как «кодирование длин серий». Одна из таких вещей, с которыми люди обычно сталкиваются на лабах по программированию в универе, или готовясь к алгоритмическим секциям собеседований – например, вот эта задачка на LeetCode.

В одном предложении: это когда мы кодируем строку «АААБВВВВ» как «А3БВ4». 

Проблема RLE в том, что в реальной жизни редко встретишь данные вида «АААБВВВВ». Эффективность сжатия зависит от распределения частот повторяющихся последовательностей разных длин. Очевидно, если в файле есть много повторов, то он будет сжиматься лучше.

На практике же, на данных «из жизни» RLE работает… прямо скажем, так себе. Чтобы не быть голословным, средний показатель сжатия текстов (книги в формате txt) составляет (с моей имплементацией, на моей подборке файлов) 100.8%. Т.е. после «сжатия» размер файлов увеличился на 0.8%.

Данные «из жизни»

Далее в статье я буду иногда ссылаться на данные «из жизни», тестируя разные варианты алгоритма, или противопоставлять их искусственным примерам из студенческих лаб.

Алгоритмы сжатия обычно применяются к типам файлов, которые хорошо сжимаются. Некоторые форматы типа docx, epub или png даже имеют встроенное сжатие – сжимать их повторно не имеет смысла. Сколь хорош ни был бы алгоритм, на этих файлах он даст плохой результат. 

Текстовые же файлы, напротив, обычно хорошо поддаются сжатию. В основном их я и использовал для тестов и анализа. Разные утверждения по поводу эффективности имплементации, если не оговорено иное, будут относиться именно к текстовым файлам форматов txt и fb2 (в основном, художественная проза).

Далее в статье я часто буду ссылаться на то, что RLE на реальных данных работает посредственно. Под спойлером я аргументировал этот тезис на примере романа «Война и Мир». Коротко: никакая сколь угодно хорошая имплементация RLE не сможет сжать текст книги «Война и Мир» больше, чем на 0.1%.

Но даже для исключений, показатель N>2 не превысил 5.1% (значение было достигнуто на 2 мегабайтном fb2-файле за счёт повторяющихся пробелов в начале почти каждой строки, которые использовались для отступов в xml-блоках).

Предобработанные данные «из жизни»

Эффективность в 0.1% как-то не очень впечатляет. Но тут к нам на помощь спешат наши друзья, а точнее, пока ещё незнакомцы: BWT и MTF. Расшифровываются они как Burrows–Wheeler transformation и move-to-front. Данные «из жизни», прошедшие через конвейер BWT * MTF я буду далее называть «предобработанными». 

Надеюсь как-нибудь собраться с силами и написать статью о BWT, так как на русском материалов по этой теме мало, но пока что он, как и MTF остаётся для нас чёрным ящиком. Впрочем, у меня уже есть имплементации обоих этих алгоритмов (они являются частью моего проекта по переизобретению bzip2), и по этому можно прогнать файлы через них, посчитать байты и сравнить цифры.

Кстати, особенность связки BWT * MTF – это повторы из нулей (нулевых байт). Если файл, который прогнали через них, открыть в hex-редакторе, то в начале файла будут сгруппированы нули, перемежающиеся редкими вкраплениями ненулевых байт:

Выглядит так, будто кто-то решил нас разыграть и затёр часть файла нулями. Тем удивительнее, что обратная трансформация даёт исходный файл. 

Такое обилие повторов уже вселяет оптимизм. На файле «Война и Мир» количество потенциально сжимаемых данных (после применения трансформации BWT * MTF) выросло с 0.1% до 43.2%. В среднем по больнице показатель потенциала сжатия вырос с 0.1% до 39-40%, что, согласитесь, внушает сдержанный оптимизм. 

Следует подчеркнуть, что для эффективности сжатия это лишь оценка сверху. Если 40% файла могут быть эффективно сжаты с помощью RLE, то он сожмёт их не в 0, а тоже на какой-то процент, зависящий от природы данных и конкретной имплементации алгоритма. На таких предобработанных данных мы впоследствии будем сравнивать разные имплементации между собой. 

Варианты имплементации

Попытка №1. Наивный алгоритм

Давайте попробуем изобрести RLE с нуля.

Если супер-кратко, то RLE (run-length encoding / кодирование длин серий) – это такая штука, когда мы превращаем строку "gooooooooogle" в "go9gle".

Если чуть более подробно, то мы выявляем в последовательности символов повторы: "g (ooooooooo) gle". Затем каждый такой повтор мы сокращаем до единственного символа и добавляем счетчик – исходное количество символов в повторе: "g (o,9) gle" => "go9gle". Декодируя строку, мы восстанавливаем все повторы, опираясь на значения их счётчиков:

// encoding
"gooooooooogle" => "go9gle"
// decoding
"go9gle" => "g" + "o"*9 + "gle" => "gooooooooogle"

В таком виде задача RLE предстаёт нам на собеседованиях и в университетах.

Хорошее и понятное объяснение. Одна с ним беда – оно не работает. По крайней мере, для общего случая. Чтобы всё сломалось, достаточно включить числа в список допустимых символов входной строки, и с декодированием возникнут проблемы.

Пусть, к примеру, у нас есть вот такая закодированная строка: "h32". Вот несколько вариантов её декодировки:

• "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh" ("h"*32)

• "h33" ("h"*1 + "3"*2)

• "hhh2" ("h"3 + "2"1)

• "h32" ("h32"*1)

Неопределенность мешает восстановлению данных. Похоже, наивный алгоритм, никуда не годится. В реальности всё ещё хуже, потому что в общем случае мы должны уметь работать с произвольными последовательностями байт. Т.е. строка "h33" на самом деле выглядит как [0x68, 0x33, 0x33]. 

Для простоты примем, что мы решаем задачу RLE над алфавитом из всех возможных символов длиной 1 байт, т.е. от 0x00 до 0xff. (В общем случае алфавит может быть произвольным, содержать больше одного байта в символе, и даже символы с неодинаковой длиной в байтах.)

Основной вопрос: как отличать символы (исходные байты последовательности) от счётчиков (служебные байты, хранящие длины повторов)?

Попытка №2. Флаг счётчика

Информация о том, что конкретный байт принадлежит одной из двух категорий, кодируется в один бит. Пусть 0 соответствует категории «символ», а 1 – категории «счётчик».

Эти флаговые биты могут записываться прямо в поток кодируемых данных. Можно: 

• вставлять флаговый бит перед каждым байтом (сомнительный подход, т.к. портит выравнивание данных, ведь теперь у нас в байте 9 бит)

• группировать флаговые биты по восемь штук и вставлять в поток с промежутками по восемь байт

• не заморачиваться и писать все флаговые биты в отдельный поток данных; потом эти два потока можно склеить в один файл

Впрочем, в использовании флагов есть один фатальный недостаток: накладные расходы на память. Один дополнительный бит на каждый байт – это +12.5% (одна восьмая) к размеру данных: слишком серьёзный гандикап.

Есть ли какие-то возможности для оптимизации? Да вроде бы нет. Мы уже максимально экономно храним флаги: по одному на бит. Меньше – нельзя просто по законам физики! Или всё-таки можно?

Давайте представим, как будет выглядеть поток сигнальных бит:

0000000000001000000000000000000000000000000000010000000000000000

Ранее мы видели, что в данных «из жизни» повторы встречаются нечасто. Повторяющаяся последовательность – редкое событие. Символы будут встречаться гораздо чаще, чем счётчики. 

С точки зрения теории информации, утверждение «такой-то байт является символом» даёт нам меньше 1 бита информации (имеется в виду собственная информация по Шеннону).

Расчёт для частоты встречаемости счётчиков 1/20:

Расчёт для частоты встречаемости счётчиков 1/100:

То есть, как это ни парадоксально, хранить флаг принадлежности символу в одном бите – это уже расточительство.

Напротив, утверждение «такой-то байт является счётчиком» несёт больше 1 бита информации (4.32 бита, если счётчики составляют 5% данных, 6.64 бит – если 1%).

Расчёт для частоты встречаемости счётчиков 5%:

Расчёт для частоты встречаемости счётчиков 1%:

Да и вообще, взгляните на поток сигнальных бит. Что бы вы подумали, увидев такое вне контекста? Какое неэффективное хранение информации. Её же можно… сжать. Каким-нибудь алгоритмом, который хорошо работает на последовательностях с большим количеством повторов. Хм-м-м…

Попытка №2.1 Сжатие потока флагов

Похоже, чтобы решить RLE, нужно сначала решить RLE. Знаем-знаем, проходили…

Но есть хорошая новость: сжать нужно последовательность с непомерно большим количеством повторов. Причём нули будут повторяться постоянно, а единицы – почти никогда, так как повторение единиц означает, что счётчик не влез в один разряд, т.е. его значение превышает 255.

Теория информации даёт нам подсказку, что можно кодировать флаги счётчиков (единицы) четырьмя, или даже шестью битами, и мы всё равно выйдем в плюс.

Что, если мы будем считать длины повторов нулей? Мы ожидаем (согласно статистике данных «из жизни»), что единицы будут встречаться нечасто. Скажем, примерно 1 раз на 100 нулей. Значит, длина обычно будет влезать в 7 бит (от 1 до 127, а 0 используется как флаг счётчика). 

Для предобработанных данных частота встречаемости счётчиков должна быть ещё выше. Экспериментально установленное оптимальное значение: 4 бита (т.е. на 15 нулей почти всегда будет попадаться одна единица).

// исходный поток флаговых бит:
   0000000000001000000000000000000000000000000000010000000000000000
// [  12 нулей]1[       31 ноль  +  ещё 3 нуля   ]1[      16 нулей]
//    ^        ^        ^               ^         ^       ^
      0b0110   0b0000   0b1111          0b0011    0b0000  0b1000
// сжатый поток:
   0110 0000 1111 0011 0000 1000

Нулевой код (0b0000) используется как флаг счётчика. Любой другой отличный от нуля код интерпретируется как повтор из нулей указанной длины. Исходная последовательность содержала 8 байт (64 бита) флагов. Сжатая содержит 3 байта.

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

Итого: 12.5% накладных расходов превращается в что-то около 1.5-2.0% (в теории). Уже терпимо.

from itertools import groupby

...

class RleStreams:
    def encode(self, block: bytes) -> bytes:
        unc_flag_stream: list[int] = []  # несжатый массив флагов
        symbol_stream: bytearray = bytearray()  # массив символов


        for byte, group in groupby(block):  # разбиваем на повторяющиеся группы
            count = len(list(group))
            if count > 1:  # есть повтор
                unc_flag_stream.append(0)  # 0 - значит "не счётчик"
                symbol_stream.append(byte)


                counter_bytes: bytes = _get_counter_bytes(count)  #
                # _get_counter_bytes(int) -> bytes
                # example: 12345 => [0x30, 0x39]
                # в общем случае счётчик может не влезть в один байт


                for b in counter_bytes:
                    unc_flag_stream.append(1)  # 1 - значит "счётчик"
                    symbol_stream.append(b)
            else:  # нет повтора
                for _ in range(count):
                    unc_flag_stream.append(0)
                    symbol_stream.append(byte)
        flag_stream: bytearray = _compress_flag_stream(
            unc_flag_stream
        )  # <= очень много кода, 50% всей сложности алгоритма
        # _compress_flag_stream - делает всю работу по сжатию битовых флагов


        encoded: bytearray = _join_streams(flag_stream, symbol_stream)
        # _join_streams - приклеивает len(flag_stream).to_bytes(...) + flag_stream
        #  в начало symbol_stream
        return bytes(encoded)


    def decode(self, block: bytes) -> bytes:
        flag_stream, symbol_stream = _slplit_streams(block)
        unc_flag_stream = _uncompress_flag_stream(
            flag_stream
        )  # <= много кода, 20% всей сложности алгоритма
        assert len(symbol_stream) == len(unc_flag_stream)
        decoded = bytearray()
        for flag, group in groupby(
            zip(unc_flag_stream, symbol_stream), key=lambda t: t[0]
        ):  # разбиваем на группы по значению флагов
            g_bytes = [b for _, b in group]
            if flag == 0:  # не повторы
                decoded.extend(g_bytes)
            else:  # повторы
                counter = int.from_bytes(
                    g_bytes, signed=False, byteorder="big"
                )
                decoded.extend([decoded[-1]] * (counter - 1))
        return bytes(decoded)

Попытка №3. Удвоение символов

Ещё один хитроумный способ пометки счётчика основан на том, что RLE-кодированные последовательности не содержат повторов среди своих символьных байт.

В исходных данных каждый повтор заменяем двумя его первыми байтами и сразу за ними располагаем счётчик.

// исходные данные: 
      0x61 0x62 0x62 0x62 0x62 0x62 0x62 0x62 0x62 0x63 0x64
//       a    b    b    b    b    b    b    b    b    c    d

// кодированные данные:
      0x61 0x62 0x62 0x08 0x63 0x64
//         ^^^^^^^^^ – повтор: следующий байт будет счётчиком
//       a         b    8    c    d

У этого подхода есть две важных особенности:

Во-первых, теперь все счётчики ограничены по размеру одним байтом (точнее, мы должны назначить им постоянную длину). В примере с флаговыми битами счётчики могли иметь произвольную длину: хоть два байта, хоть двадцать (эпический повтор из 10**36 ТБ подряд идущих нулей, ужатый до 21 байта). А теперь, если в последовательности больше 255 повторов, то мы должны разбить её на несколько частей. Впрочем, не велика потеря. На эффективности алгоритма это почти никак не отразится ввиду редкости больших значений счётчиков.

Во-вторых, мы обязаны сжимать все встреченные повторы. С флагами мы вольны были сами выбирать, какие повторы сжимать (могли просто пометить повтор нулевыми флагами, будто это неповторяющаяся последовательность). В удвоении символов же мы отталкиваемся от предположения, что закодированная последовательность не может содержать повторов. 

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

// исходные данные: 
   0x61 0x61 0x62 0x62 0x63 0x63
//    a    a    b    b    c    c 

// кодированные данные:
   0x61 0x61 0x02 0x62 0x62 0x02 0x63 0x63 0x02
// ^^^^^^^^^      ^^^^^^^^^      ^^^^^^^^^ 
//         a    2         b    2         c    2

Сжатые данные составляют 133% от несжатых.

Это проблема потому, что как в данных из «жизни», так и в предобработанных данных повторы по два попадаются чаще, чем любые другие повторы, и если на каждой такой паре мы будем получать лишний байт, то выигрыш от оставшихся повторов может не окупить наши издержки.

Из плюсов этого подхода: он очень лёгок в имплементации. Код на питоне (с красивым форматированием) занимает 45 строк, и там нет ничего заумного.

Эксперименты на обработанных (через BWT и MTF) данных показывают, что накладные расходы на пары (повторы по два) в целом не приводят к большому проигрышу (подробности: в конце статьи). Т.е. если вам нужно на коленке закодить RLE, удвоение символов – хороший вариант. 

from itertools import groupby




class RlePairs:
    def encode(self, block: bytes) -> bytes:
        encoded: bytearray = bytearray()
        for byte, group in groupby(block):  # разбиваем на повторяющиеся группы
            count = len(list(group))
            if count > 1:
                while count > 1:
                    encoded.append(byte)  # два одинаковых символа
                    encoded.append(byte)  # значит сразу за ними будет счётчик
                    cur_count = min(
                        count, 255
                    )  # если > 255, кодируем по частям
                    counter_byte = cur_count.to_bytes(
                        1, signed=False, byteorder="big"
                    )[0]
                    encoded.append(counter_byte)
                    count -= cur_count
                if count == 1:
                    encoded.append(byte)
            else:
                encoded.append(byte)
        return bytes(encoded)


    def decode(self, block: bytes) -> bytes:
        decoded = bytearray()
        prev_byte: int | None = None
        next_will_be_counter = False
        for byte in block:
            if byte == prev_byte:
                prev_byte = None
                next_will_be_counter = True
            elif next_will_be_counter:
                next_will_be_counter = False
                counter = int.from_bytes([byte], signed=False, byteorder="big")
                decoded.extend([decoded[-1]] * (counter - 1))
            else:
                prev_byte = byte
                decoded.append(byte)
        return bytes(decoded)

Попытка №4. PackBits

Этот алгоритм был придуман программистами из Apple. Проще всего будет объяснить его на примере.

Пусть имеем какие-то сырые данные (для удобства будем обращаться с ними как со строками):

"inqktqigfffffhmkvosynozpgggggggggpcrelizif"

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

"inqktqig", 5*"f", "hmkvvosynozp", 9*"g", "pcrelizzif"

Теперь настал черёд кодирования:

(8,"inqktqig"), [5,"f"], (12,"hmkvvosynozp"), [9,"g"],(10, "pcrelizzif")

Здесь круглыми скобками обозначены последовательности несжатых байт, квадратными – сжатые повторяющиеся байты. Каждая порция байт всегда начинается со счётчика, который для несжатых данных обозначает длину последовательности, а для сжатых – количество повторов.

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

Создатели PackBits предлагают для этих целей использовать знак счётчика. Отрицательные числа используются как счётчики повторов в сжатых данных, положительные – как счётчики длины несжатых данных:

8 "inqktqig" -5 "f" 12 "hmkvvosynozp" -9 "g" 10 "pcrelizzif"

Таким образом, максимальный размер счётчика будет 127 (т.к. один бит ушел на знак). Можно считать от нуля и дотянуть до 128, но тогда код станет несколько менее нагляден.

Последовательность всегда начинается со счётчика. Если он положительный и равен n, то следующий счётчик будет через n+1 байт. Если он отрицателен, то следующий счётчик будет через 2 байта.

from collections import namedtuple
from itertools import groupby




Repeat = namedtuple("Repeat", ["times", "byte"])


class RlePackBits:
    def encode(self, block: bytes) -> bytes:
        chunks: list[Repeat | list[int]] = []
        for byte, group in groupby(block):  # разбиваем на повторяющиеся группы
            count = len(list(group))
            if count > 1:
                chunks.append(Repeat(count, byte))  # нашли повтор длиной count
            else:  # не повтор
                if not chunks or isinstance(chunks[-1], Repeat):
                    chunks.append([])
                chunks[-1].extend([byte] * count)  # type: ignore[union-attr]
                # добавили байт в крайний чанк не повторяющихся байт


        encoded = bytearray()
        for chunk in chunks:
            if isinstance(chunk, Repeat):  # чанк с повторами
                times, byte = chunk
                while times > 0:
                    counter = min(128, times)
                    times -= counter
                    # отрицательное число - признак повтора (от -128 до -1)
                    counter_byte = (-counter).to_bytes(
                        1, signed=True, byteorder="big"
                    )[0]
                    encoded.append(counter_byte)  # записываем счётчик
                    encoded.append(byte)  # записываем символ
            elif isinstance(chunk, list):  # чанк с не-повторами
                total_length = len(chunk)
                for i, byte in enumerate(chunk):
                    if i % 127 == 0:
                        length = min(127, total_length - i)
                        # положительное число - признак не-повтора (от 1 до 127)
                        length_byte = length.to_bytes(
                            1, signed=True, byteorder="big"
                        )[0]
                        encoded.append(length_byte)  # записываем счётчик
                    encoded.append(byte)  # записываем символ
        return bytes(encoded)


    def decode(self, block: bytes) -> bytes:
        decoded = bytearray()
        next_counter_byte = 0  # сколько осталось до следующего счётчика
        repeat = 0 # длина текущего повтора (0 если не повтор)
        for byte in block:
            if next_counter_byte == 0:
                counter_int = int.from_bytes(
                    [byte], signed=True, byteorder="big"
                )
                if counter_int > 0:  # не повтор
                    next_counter_byte = counter_int
                else:  # повтор
                    next_counter_byte = 1
                    repeat = -counter_int
            else:
                next_counter_byte -= 1
                if repeat:
                    decoded.extend([byte] * repeat)
                    repeat = 0
                else:
                    decoded.append(byte)
        return decoded

Итого по имплементации

Два основных параметра для сравнения: накладные расходы (оверхед) и эффективность сжатия.

Накладные расходы считались как процент сжатия на подборке данных «из жизни», которые (как было сказано выше в статье) практически не поддаются сжатию RLE. Например: накладные расходы в 12.3-23.4% означают, что в худшем случае размер файла увеличился на 23.4%, а в лучшем – на 12.3%.

Эффективность сжатия считалась как процент сжатия по всем файлам выборки после трансформации BWT*MTF. Например: эффективность сжатия в 12.3-23.4% означает, что в худшем случае размер файла уменьшился на 12.3%, а в лучшем – на 23.4%.

Сжатие потока флагов

• плюсы:

  • счётчики переменной длины

  • мы не обязаны кодировать повторы (можем пропускать пары)

• минусы:

  • сложно имплементировать с нуля

    • нужно использовать в тандеме с алгоритмом упаковки (склеить поток флагов и поток данных в один файл)

    • нужно уметь обрабатывать файлы побитово 

  • худший из трёх по всем параметрам

• ссылка на мою имплементацию

Моё итоговое впечатление: много работы ради сомнительной выгоды – никому не рекомендую. Суммарно по времени оно заняло больше, чем два других способа вместе. А код получился довольно замороченный и муторный в отладке. Вдвойне обидно, что при этом сжатие потока флагов показывает худшие результаты.

Особенно сложно было написать и отладить побитовое сжатие: когда длину кодирующего символа в битах можно задавать произвольно (не кратной восьми). Ведь по правилам челленджа я не могу пользоваться сторонними пакетами, а в Python «из-коробки» нет удобных инструментов для работы с битами.

Экспериментально установленная оптимальная длина кодирующего символа: 4 бита. На такой длине достигается минимум накладных расходов.

Удвоение символов

• плюсы:

  • очень легко имплементировать

• минусы:

  • счётчики фиксированной длины

  • плохо работает с повторами по два

  • мы обязаны кодировать все встреченные повторы

• ссылка на мою имплементацию

Не требует никаких заморочек с битами или чего-то такого. Логика работы очень простая. Минимум тонких моментов, где можно допустить ошибку.

Изначально скептически относился к этому подходу, и для меня стало сюрпризом, что он обогнал поток флагов. Опасения по поводу плохой эффективности обработки пар – оказались напрасными. 

Пожалуй, это лучший вариант для собеседования, если интервьюер попросит написать «честный» RLE.

PackBits

• плюсы:

  • умеренно легко имплементируется

  • лучшие результаты по сжатию и оверхеду

• минусы:

  • счётчики фиксированной длины

• ссылка на мою имплементацию

Немного сложнее в реализации, чем удвоение символов (больше мест, где можно допустить ошибку), но гораздо-гораздо легче, чем поток флагов.

Прекрасные показатели сжатия и низкие накладные расходы.

Лучшая версия RLE из представленных по итогам моего небольшого исследования.

Заключение

Вот такую работу я проделал, постигая тайны RLE.

Многое осталось «за кадром». Некоторые другие части алгоритма bzip2 заслуживают отдельных статей — уж слишком они объёмные.

Алгоритм упаковки блоков тоже не вошел в статью. Этот «велосипед» было интересно изобретать, но в итоге всё сводится к вариациям «закодируй длину блока в заголовке фиксированного размера, а затем размести сам блок».

В тексте я пытался передать эмоции, которые испытывал во время своего мини-исследования: удивление, любопытство, азарт. Но в то же время хотел, чтобы материал оставался фактологически точным и нёс полезные знания.

А насколько мне удалось – судить уже вам. Спасибо, что дочитали до конца! 

Читайте наши другие статьи про Python:

Визуализация 5 алгоритмов сортировки на Python

Фоновые асинхронные задачи в FastAPI и их мониторинг

Разбираемся в асинхронности: где полезно, а где — нет?

Как мы сделали и оптимизировали механизм правил для персонализации UI

Websocket-сервер для геолокации на asyncio