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

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. NB: grep инвертирует эту логику.

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

Answer 5

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

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

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

Answer 6

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

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

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

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