Кодирование длин серий

В этой статье мы рассмотрим, как работает алгоритм кодирования длин серий, для чего он используется и как реализовать его функции кодирования и декодирования в Python.

Кодирование длин серий (RLE) - это очень простая форма сжатия данных, в которой поток данных предоставляется в качестве входных данных (например, «AAABBCCCC»), а выходными данными является последовательность отсчетов последовательных значений данных в строке (например, « 3A2B4C "). Этот тип сжатия данных осуществляется без потерь, что означает, что при распаковке все исходные данные будут восстановлены при декодировании. Его простота как в кодировании (сжатии), так и в декодировании (распаковке) - одна из самых привлекательных особенностей алгоритма.

Здесь вы можете увидеть простой пример потока («прогона») данных в исходном и закодированном виде:

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

 AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

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

 6A1F2D7C1A17E

В этом примере мы смогли сжать данные с 34 символов до 13.

Как вы могли заметить, чем больше последовательных значений в строке, тем больше места мы экономим в результате сжатия. С другой стороны, если у вас есть последовательность данных, которая часто меняется между значениями (например, «BEFEFADED»), то мы вообще не сэкономим много места. Фактически, мы могли бы даже увеличить размер наших данных, поскольку один экземпляр символа дает 2 символа (т.е. «A» становится «1A») на выходе кодирования.

По этой причине RLE подходит только для определенных типов данных и приложений. Например, камера Pixy , которая представляет собой роботизированную камеру, которая помогает легко отслеживать объекты, использует RLE для сжатия помеченных видеоданных перед их передачей со встроенной камеры во внешнее приложение. Каждому пикселю дается метка «нет объекта», «объект 1», «объект 2» и т. Д. Это идеальная кодировка для этого приложения из-за ее простоты, скорости и способности сжимать данные меток с низкой энтропией.

Кодирование

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

Ниже вы найдете простую реализацию на Python:

 # rle-encode.py 
 
 def rle_encode(data): 
 encoding = '' 
 prev_char = '' 
 count = 1 
 
 if not data: return '' 
 
 for char in data: 
 # If the prev and current characters 
 # don't match... 
 if char != prev_char: 
 # ...then add the count and character 
 # to our encoding 
 if prev_char: 
 encoding += str(count) + prev_char 
 count = 1 
 prev_char = char 
 else: 
 # Or increment our counter 
 # if the characters do match 
 count += 1 
 else: 
 # Finish off the encoding 
 encoding += str(count) + prev_char 
 return encoding

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

Продолжая работу с тем же файлом, что и выше, вот пример выполняемого кода:

 encoded_val = rle_encode('AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE') 
 print(encoded_val)

И вывод:

 $ python rle-encode.py 
 6A1F2D7C1A17E

Расшифровка

Декодирование потока данных в кодировке RLE на самом деле даже проще, чем его кодирование. Как и раньше, вы просматриваете поток данных по одному символу за раз. Если вы видите числовой символ, вы добавляете его к своему count , а если вы видите нечисловой символ, вы добавляете count этих символов к своему декодированию, которое возвращается вызывающей стороне после итерации по всем входным data .

Вот алгоритм, реализованный на Python:

 # rle-decode.py 
 
 def rle_decode(data): 
 decode = '' 
 count = '' 
 for char in data: 
 # If the character is numerical... 
 if char.isdigit(): 
 # ...append it to our count 
 count += char 
 else: 
 # Otherwise we've seen a non-numerical 
 # character and need to expand it for 
 # the decoding 
 decode += char * int(count) 
 count = '' 
 return decode

Мы можем запустить этот код на том же выходе, который мы получили от нашей кодировки:

 decoded_val = rle_decode('6A1F2D7C1A17E') 
 print(decoded_val)

И вывод такой же, как и наш исходный ввод для функции кодирования:

 $ python rle-decode.py 
 AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

Обратите внимание, что эта реализация не выполняет никакой проверки ошибок, чтобы убедиться, что у нас есть допустимый поток данных RLE. Если какие-либо входные данные отформатированы неправильно, вы, вероятно, столкнетесь с ошибкой.

Кодирование

Расшифровка

Содержание