C++ и RLE для последовательностей символов

У меня есть трудности с тем, как использовать RLE для последовательностей символов.

Например, я могу выполнить кодирование RLE для таких строк, как

"ASSSAAAEERRRRRRRR"

который будет преобразован в:

"A1S3A3E2R8".

Но я хотел бы выполнить RLE для таких строк, как

"XXXYYYYY(1ADEFC)(EDCADD)(1ADEFC)(1ADEFC)(1ADEFC)"

который будет преобразован в:

"X3Y5(1ADEFC)1(EDCADD)1(1ADEFC)3"

Есть ли способ добраться до него? Эта работа становится немного проще, потому что длинные строки всегда следуют в скобках. Не могли бы вы посоветовать сделать это на C++?
Если есть лучший способ хранения значений, чем использование скобок, было бы здорово, если бы вы меня порекомендовали.


c++ run-length-encoding
person ghostmansd    schedule 09.10.2011    source источник
comment
Что вы действительно пытаетесь сделать? Сжать данные?   -  person NPE    schedule 09.10.2011
comment
Да, я пытаюсь сжать текстовые файлы, содержащие цвета пикселей из изображения. Я хотел бы использовать RLE для этих файлов. После RLE я могу использовать сжатие gzip для этих файлов, чтобы добиться лучшего сжатия.   -  person ghostmansd    schedule 09.10.2011
comment
Вполне вероятно, что вы обнаружите, что gzip уже хорошо обнаруживает и сжимает повторяющиеся шаблоны, а также повторяющиеся символы. Это в основном то, что делает алгоритм LZ77, а LZ77 — это первый шаг gzip сжатия.   -  person NPE    schedule 09.10.2011
comment
Да, я уже сделал это, используя только gzip, но размер все равно великоват. Например, я создал файл, который содержит цвета белого изображения размером ~2700x4000 пикселей и имеет вес около 10,7 МБ. Если я использую только gzip, он весит около 100 КБ, но если я делаю сначала RLE, а затем RLE, он имеет вес около 0,5 КБ.   -  person ghostmansd    schedule 09.10.2011
comment
Справедливо. Молодцы, что провели тесты.   -  person NPE    schedule 09.10.2011
comment
О, ошибка. Сначала RLE, а затем сжатие gzip. :-)   -  person ghostmansd    schedule 09.10.2011

Ответы (2)


arrow_upward
4
arrow_downward

Вы должны разбить эту проблему на более мелкие части. Во-первых, у вас должна быть функция, которая токенизирует ваш поток и возвращает каждую отдельную часть. Для этого примера входного потока:

"XXXYYYYY(1ADEFC)(EDCADD)(1ADEFC)(1ADEFC)(1ADEFC)"

эта функция вернет следующие элементы, по одному на каждый вызов:

X
X
X
Y
Y
Y
Y
Y
(1ADEFC)
(EDCADD)
(1ADEFC)
(1ADEFC)
(1ADEFC)
<eof>

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

person Miguel    schedule 09.10.2011
comment
Все гениальное просто. :-) Спасибо, буду следовать этому пути! - person ghostmansd; 09.10.2011

arrow_upward
0
arrow_downward

Поскольку вы упомянули, что намерены кодировать данные RLE, чтобы позже использовать сжатие gzip и добиться лучшего сжатия, мой ответ: не утруждайте себя кодированием в первую очередь. Сжатие gzip использует DEFLATE, который представляет собой обобщение кодирования длин серий, которое может использовать преимущества последовательностей строк символов. Вы не получите лучшего сжатия, применяя один и тот же алгоритм дважды, и на самом деле вы можете даже немного потерять сжатие.

Если вы настаиваете на выполнении собственного RLE, возможно, будет лучше сохранить установленную длину вместо использования круглых скобок. То есть вместо (1ADEFC)3 используйте 61ADEFC3. Также обратите внимание, что вы намерены сжимать пиксели, которые используют полный диапазон значений байтов. Имейте это в виду, поскольку алгоритм, написанный для работы со строками, не подходит для необработанных данных со встроенными нулями и непечатаемыми символами повсюду.

person K-ballo    schedule 09.10.2011
comment
Отличие есть. После того, как я использовал алгоритм RLE и сжатие gzip, была действительно большая разница. Я сделал это на файле, который содержит только символы Y 2700x4000, но это только пример. - person ghostmansd; 09.10.2011
comment
@ghostmansd: Вы должны быть осторожны, делая выводы из таких тривиальных тестов ... алгоритмы часто игнорируют вырожденные случаи, которые никогда не встречаются в реальном использовании, в пользу лучшей производительности с более типичными данными. - person Dennis Zickefoose; 09.10.2011
comment
@Dennis Zickefoose: такие файлы всегда будут генерироваться из обычных изображений и будут иметь магические числа, поэтому ошибки будут минимальными. - person ghostmansd; 09.10.2011
comment
@ghostmansd: Но обычное изображение не будет иметь десять миллионов копий одного и того же пикселя. Вот что я пытаюсь сказать... вы получаете аналогичные результаты от входных данных, которые представляют фактическое использование, или только от таких вырожденных случаев? - person Dennis Zickefoose; 09.10.2011
comment
@dennis-zickefoose: А, я понял. Да, шанс получить полностью белые изображения невелик, но некоторые из изображений (например, двухтональные сканы книг) все же имеют большие последовательности белого цвета. Это может быть полезно, я думаю. - person ghostmansd; 09.10.2011