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

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

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

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

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

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

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

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

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

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

^[].*+{}()$

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

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

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

1. NB: grep инвертирует эту логику.

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

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

AAAABBCCCCDDEEEEEEEFFG

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

GGA4BBGC4DDGE7FFGG

или еще лучше:

HHA4BBHC4DDHE7FFG

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

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

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

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

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

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

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

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

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