Рубрики
Без рубрики

Кодирование длины пробега

Автор оригинала: Scott Robinson.

Кодирование длины пробега

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

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

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

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

AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

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

6A1F2D7C1A17E

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

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

Из-за этого ПРАВИЛО подходит только для определенных типов данных и приложений. Например, камера Pixy camera , которая является робототехнической камерой, которая помогает вам легко отслеживать объекты, использует 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 этих символов в свое декодирование, которое возвращается вызывающему абоненту после того, как вы повторяете все входные данные .

Вот алгоритм, реализованный в 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. Если какие-либо входные данные не отформатированы должным образом, то вы, скорее всего, столкнетесь с ошибкой.