Реализация кодирования длин серий

Question

Я написал программу для выполнения кодирования длин серий. В типичном сценарии, если текст

AAAAAABBCDEEEEGGHJ

кодирование длины пробега сделает его

A6B2C1D1E4G2H1J1

но добавлялось 1 для каждого неповторяющегося символа. Поскольку я сжимаю BMP-файлы с ним, у меня возникла идея поместить маркер «$» для обозначения появления повторяющегося символа (при условии, что файлы изображений содержат огромное количество повторяющегося текста).

Так бы это выглядело

$A6$B2CD$E4$G2HJ

Для текущего примера его длина такая же, но есть заметная разница для файлов BMP. Теперь моя проблема в декодировании. Бывает так, что некоторые BMP-файлы имеют шаблон $<char><num>, т.е. $I9 в исходном файле, поэтому в сжатом файле я бы также содержал тот же текст. $I9, однако после декодирования он будет воспринимать его как повторяющееся Я, которое повторяется 9 раз! Так что это дает неправильный вывод. Я хочу знать, какой символ я могу использовать, чтобы отметить начало повторяющегося символа (прогона), чтобы он не конфликтовал с исходным источником.

Answer 1

Почему бы вам не кодировать каждый $ в исходном файле как $$ в сжатом файле?

И / или использовать какой-то другой символ вместо $ - тот, который редко используется в файлах bmp.

Также обратите внимание, что формат BMP имеет встроенное сжатие RLE - смотрите здесь , внизу страницы - в разделе «Данные изображения и сжатие».

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

Answer 2

AAAAAABBCDEEEEGGHJ $ IIIIIIIII ==> $ A6 $ B2CD $ E4 $ G2HJ $$ I9

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

$ A6 $ B2CD $ E4 $ G2HJ $$ I9 ==> AAAAAABBCDEEEEGGHJ $ IIIIIIIII

Answer 3

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

AAAABBCCCCDDEEEEEEEFFG

Вы можете выбрать «G» в качестве escape-значения (или даже «H», если оно является частью вашего набора символов) и принять соглашение, согласно которому первый символ кодированного потока является escape-значением. Таким образом, приведенная выше строка может кодироваться как:

GGA4BBGC4DDGE7FFGG

или даже лучше:

HHA4BBHC4DDHE7FFG

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

Надеюсь, это поможет!

Answer 4

То, что большинство программ делают для обозначения того, что некоторые символы должны обрабатываться буквально, заключается в том, что они имеют определенную escape-последовательность.

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

^[].*+{}()$

Да, там находится ваш забавный символ знака доллара, и обычно это означает конец строки .

Итак, что программист, использующий регулярные выражения, должен буквально интерпретировать эти символы, так это то, что они должны выражать эти символы как escape-последовательность. Например, чтобы интерпретировать $ как $ , а не конец строки , программист использует \ $ , что является escape-последовательностью . (1)

В вашем случае вы можете хранить буквенные знаки доллара в сжатом файле как \ $ . (2)

1. Примечание: grep инвертирует эту логику.

2. Приведенные выше решения по сохранению $ как $$ приводят в замешательство, если в файле BMP выполняется $ .

Answer 5

Я, честно говоря, не уверен, что побудило бы кого-либо использовать текстовую RLE, если он хочет сжать с ней двоичные данные. BMP - это не текст.

Прямо сейчас, поскольку после $ читается только один байт, и это интерпретируется как число ascii от 0 до 9, этот процесс имеет диапазон длин серий от 0 до 9, что означает, что вы можете только сжать значения до до 9 повторений до того, как нужно будет написать новый флаг длины пробега. В конце концов, вы не можете сделать разницу между $I34 для длины прогона 34 и $I3 + 4 для литерала 4 за повторением 3.

Если этот же байт вместо этого интерпретируется как двоичное значение, он может содержать значения от 0 до 255 , что дает массивную разницу в эффективности.

Что касается экранирования $ самих знаков, я бы посоветовал либо всегда рассматривать его как повторение по крайней мере 1 ($$1), либо, что еще лучше, кодировать все это по-другому, с порядком значения длины выполнения и данные меняются местами, поэтому код становится $<length><data>; тогда вы можете использовать $0 в качестве специального символа, означающего «просто $». Когда вы распаковываете и сталкиваетесь с 0 после $, просто не читайте третий байт. Длина прогона, равная 0, никогда не должна появляться в сжатых данных в любом случае, поэтому ей можно придать особое значение, но это бесполезно, если байт данных ставится первым, поскольку тогда он все равно будет такой же длины, что и обычный повтор.

Answer 6

Если я правильно понимаю, проблема в том, что $ является символом для пометки повторения, а также может быть значением 'BMP'?

Если это так, то вы можете пометить двойной символ $ ('$$'), чтобы обозначить, что символ '$' должен рассматриваться не как повтор, а как один $. Это, конечно, будет означать, что код $ стоит дорого (принимает два символа вместо 1), но решит вашу проблему.

Если вы хотите получить символ «$», вам необходимо закодировать его следующим образом: $$$ 5 - означает «$», запуск «$$» = $, «5» - 5 раз.