RLE-кодирование

← →
Mr. D (2007-08-07 21:31) [0]

Помогите, пожалуйста, найти грамотную реализацию алгоритма кодирования RLE на Delphi. Что-то вроде функции, которой передаешь последовательность двоичных данных, на выходе получаем закодированные данные.

Чтобы работала быстро и безглючно, учитывала ве нюансы (навроде того, что нельзя указывать число повторений более $80 и прочее)...

← →
Mr. D (2007-08-07 21:33) [1]

То, что я гуглю - или простецкое описание, или какие-то работы курсовые, за которые хотят $5 :-)

← →
Efir © (2007-08-07 21:37) [2]

А самому реализовать? Там вроде ничего сложного то и нет.

← →
Efir © (2007-08-07 21:38) [3]

А если нужна инфа по кодированию, то ент на http://compression.ru/

← →
homm © (2007-08-07 21:39) [4]

> грамотную реализацию алгоритма кодирования RLE на Delphi

Нпсколько я знаю RLE — группа алгоритмов.

← →
ferr © (2007-08-07 21:42) [5]

> То, что я гуглю - или простецкое описание, или какие-то
> работы курсовые, за которые хотят $5 :-)

Это действительно самый "простецкий" метод.

http://en.wikipedia.org/wiki/Run-length_encoding

← →
Mr. D (2007-08-07 22:16) [6]

Я знаю, что алгоритм простой.

Я читал википедию, там очень поверхностное описание, как раз нет нюансов.

У меня просто нет времени (да и желания если честно) писать свою реализацию и потом тестировать ее. Наверняка велосипед уже написан грамотно и четко.

← →
Anatoly Podgoretsky © (2007-08-07 22:34) [7]

> Mr. D (07.08.2007 21:31:00) [0]

Их же много этих RLE
Алгоритм простой, хорошо описан в стандартах и статьях.
Например для RLE 8
11xxxxxx специальный код, где 11 признак, а xxxxxx количество повторов, вслед за 11xxxxxx следует символ, который надо повторить xxxxxx раз.
Это весь алгоритм.

← →
Mr. D (2007-08-08 15:38) [8]

Anatoly Podgoretsky, ну вот и неправда. Это не может быть всем алгоритмом. А если в файле попадается как раз 11? Как его записывать, чтобы при распаковке не подумали, что 11 это признак? Наверняка экранирование или еще что.

Я слышал, что число неповторов не может более $80 - иначе все остальное уже воспринимается как символы... Вроде бы...

В общем, я как раз и хочу избежать всех этих нюансов, которых не знаю

О том, что бывает разный RLE - я слышу первый раз! Нигде не встречал упоминание о различий, типа RLE 8 :(

← →
Styx_ (2007-08-08 15:54) [9]

Дык а что экранировать - просто в этом случае надо поставить один повтор, типа 11000001 11xxxxxx

← →
@!!ex © (2007-08-08 16:06) [10]

За 5 баксов напишу вам реализацию RLE быструю, годную для сжатия TGA BMP и других подобных изображений, годную для сжатия файлов.

← →
@!!ex © (2007-08-08 16:21) [11]

Лан. Бесплатно объясняю. Тут авторы немного не то написали.
Ситуация такая, что весь RLE слой состоит из последовательностей двух типов:
1) повторяющиейся 7D7D7D7D7D7D
2) не повторяющиеся 7DF1A07D0F1A

n - количество байт в последовательности

Кодируется очень просто:
1)
первый байт последовательности представляет собой
число m=-n+1
отрицательность говорит о том, что это повторяющяяся последовательность
соответственно чтобы получить из этого числа количество повторов делаем -m+1
второй байт - байт который нужно повтороить n раз.
2)
первый байт последовательности представляет собой
число равное m=n-1
положительность говорит о том, что это не повторяющяяся последовательность
соответственно чтобы получить из этого числа количество повторов делаем n=m+1
Далее идет n байт не повторяющейся последовательности.

Собственно все. Элементарно.

← →
@!!ex © (2007-08-08 16:24) [12]

P.S.
Как вы понимаете, т.к. один бит мы заняли, то максимальная длина, которую мы можем закодировать не может превышать 2^(8-1)=128=$80

← →
@!!ex © (2007-08-08 16:32) [13]

Есть своя специфика при сжатии изображения(BMP TGA), но она напрямую RLE не касаеться.

← →
Mr. D (2007-08-08 16:49) [14]

Непонятны чисто логически эти операции с прибавлением и вычитанием единицы... Зачем? Пусть бы это было просто ShortInt число.

Если оно отрицательно - значит по модулю столько символов идет повторение. Если положительно - значит, столько неповторов идет.

← →
Mr. D (2007-08-08 16:50) [15]

> Есть своя специфика при сжатии изображения(BMP TGA), но
> она напрямую RLE не касаеться

это ты про палитру?

← →
@!!ex © (2007-08-08 16:54) [16]

> [14] Mr. D (08.08.07 16:49)

тогда 127. 0 повторений не бывает. поэтому и эти изврещения с 1.

> это ты про палитру?

Пофиг на палитру.
Я про слои.

← →
Mr. D (2007-08-08 18:02) [17]

Ты говоришь: "отрицательность говорит о том", отрицательность кого? Числа m или числа n?

Видимо, числа "n".

Итак, число "n" будет отрицательным, если:

-128 <= m <= -1

А положительным число "n" будет, если:

0 <= m <= 127

В итоге:

Получается, бывает максимум 129 повторов или 128 неповторов (в отличии, от 128 повторов и 127 неповторов в случае без извращений с 1).

Все верно?

← →
@!!ex © (2007-08-08 19:03) [18]

Все не верно.
1) Отрицательность числа M.
Это та самая
1ххххххх
n - это как раз число находящееся в xxxxxxx
А 1 или 0 указывают знак числа.
2)129+128 = 257.. А у нас всего 256 в байт вмещаеться.....

← →
Mr. D (2007-08-08 19:41) [19]

> Отрицательность числа M

ок. Тогда как я понимаю, 0 считается положительныи числом и идет как n=1 неповтор?

Тогда может быть максимум:

1) 129 повторов, при этом n=129:

m = -n+1 = - 129 + 1 = -128 (максимальное отрицательное однобайтовое число)

2) и 128 неповторов, при этом n = 128

m = n-1 = 128 - 1 = 127 (максимальное положительное однобайтовое число)

> 2)129+128 = 257.. А у нас всего 256 в байт вмещаеться...
> ..

ну вот, даже ты здесь лоханулся. Кодируется максимально 129 повторов и 128 неповторов. Но при операциях с этой единицей, задействуется 0 и отменяется значение 1 повтор, потому что 1 повтор это тоже самое, что 1 неповтор, закодировать с помощью RLE вариант "1 повтор" нельзя.

Поэтому различных вариантов 128+128 = 256
Вот как оказывается, алгоритм то простенький, а сколько нюансов!!!

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

← →
@!!ex © (2007-08-08 20:01) [20]

> ну вот, даже ты здесь лоханулся. Кодируется максимально
> 129 повторов и 128 неповторов. Но при операциях с этой единицей,
> задействуется 0 и отменяется значение 1 повтор, потому
> что 1 повтор это тоже самое, что 1 неповтор, закодировать
> с помощью RLE вариант "1 повтор" нельзя.

Блин. Уже бошка не варит.
Действительно так и есть. 1 повтора не бывает.
Это видно из формул с 1, которые я выше писал.
Ньюансы возникли скорее из-за несовсем точно выраденных мной мыслей.
А так, в 11 весь алгоритм приведен, ну кроме диапазона N точного.

> Я об этом и говорил, что хотел проверенный код. Но сейчас
> уж видимо сам напишу готовый вариант, за 2 дня успел вроде
> полностью понять что к чему.

Полезнее, чем готовый код юзать.
Незабудь код полученной функции тут выложить. ;)

← →
Lacmus © (2007-08-08 20:13) [21]

http://www.torry.net/vcl/vcltools/text/adqstrings.zip
function Q_PackRLE(Source, Dest: Pointer; SrcL: Cardinal): Cardinal; overload; function Q_PackRLE(const S: string; MaxL: Integer = -1): string; overload;

← →
Anatoly Podgoretsky © (2007-08-09 00:43) [22]

Mr. D (08.08.07 15:38) [8]
Голову применить, сделать один повтор и потом сам символ

← →
Mr. D (2007-08-09 01:14) [23]

> Голову применить, сделать один повтор и потом сам символ

я не знаю где вы выкопали RLE 8, но алгоритм вы сказали неверный. То, что понимают под RLE нормально объяснил только @!!ex

← →
ANTPro © (2007-08-09 01:31) [24]

> [23] Mr. D (09.08.07 01:14)

Тебе же сказали, что вариаций его куча... Я вот по-другому не похоже на то что описал @!!ex. Результат правда меня не обрадывал, очень плохое сжатие, хотя скорость распаковковки порадовала. Но потом я попробывал прикрутить UCL и забил RLE :) Возможно еще жив сорец, но он на KOL.

← →
Mr. D (2007-08-09 05:17) [25]

> Тебе же сказали, что вариаций его куча...

а вы не могли бы дать ссылочку, где хоть немного рассказывается о вариациях? Я везде вижу упоминание только о том, что алгоритм один. Правда, его по разному рассказывают ;-)

← →
Mr. D (2007-08-09 05:22) [26]

УЖАС! Простенький алгоритм. Я когда начал реализовывать... В общем, у меня получилось монстроидально, но это самое лучшее, что получилось (вариантов тоже куча была):

=====================================================================
uses ... , Types, ... type // для работы функции RLE PByteMaxArray = ^TByteMaxArray; TByteMaxArray = array[0..MaxInt-1] of byte; // состояния сравнения: не было сравнений, равно, не равно TRLEAction = (actRLE_None, actRLE_Equal, actRLE_NotEqual); ... function RLEcompress(Src: Pointer; const Len: integer): TByteDynArray; var PSrc: PByteMaxArray; iSrc, iResult, CountRepeat, CountDiff: integer; PrevAct: TRLEAction; FlagStop: boolean; begin PSrc := Src ; // если параметр Len указан неправильно if (Len < 1) or (Len >= MaxInt div 2 ) then SetLength(Result, 0) // если данные состоят всего из 1-го байта else if Len = 1 then begin SetLength(Result, 2); Result[0] := Len - 1; // означает, что далее идет 1 байт данных (неповтор), m=n-1 Result[1] := PSrc[0] ; // единственный байт данных end // если данные состоян из 2-ух и более байт else begin // выделяем памяти в 2 раза больше, чем исходная последовательность SetLength(Result, 2*Len); iResult := 0; iSrc := 1; CountRepeat := 0; CountDiff := 0; PrevAct := actRLE_None ; FlagStop := false; while not FlagStop do begin FlagStop := iSrc = (Len -1); if PSrc[iSrc-1] = PSrc[iSrc] then // пара байт равна begin inc(CountRepeat); if (PrevAct = actRLE_NotEqual) and (CountDiff>0) then // если до этого пары байт были не равны begin // рассматриваем ситуацию, когда 2 повторяющихся байта среди // неповторяющихся не имеет смысла формировать в повтор if Len > iSrc + 1 then if CountDiff < 126 then if PSrc[iSrc] <> PSrc[iSrc+1] then begin inc(CountDiff); inc(iSrc); dec(CountRepeat); continue; end; Result[iResult] := CountDiff - 1 ; // байт счетчика (неповторы): m = n-1 inc(iResult); CopyMemory(@Result[iResult], @(PSrc^[iSrc-CountDiff-1]), CountDiff); inc(iResult, CountDiff); CountDiff := 0; end; if (CountRepeat = 128) or (FlagStop) then // больше 128 пар повторов указывать нельзя begin // если по счетчику получается, что равны 128 пар байт, то значит // всего между собой равны 129 байтов Result[iResult] := -(CountRepeat+1) + 1 ; // байт счетчика (повторы): m = -n+1 inc(iResult); Result[iResult] := PSrc[iSrc-1]; inc(iResult); CountRepeat := 0; // начинаем анализ пар заново inc(iSrc); PrevAct := actRLE_None ; // исключительная ситуация - остался 1 байт в конце, невозможно проанализировать пару if iSrc = (Len -1) then begin FlagStop := true; Result[iResult] := $00; // значение счетчика, означает, что далее 1 байт данных Result[iResult+1] := PSrc[iSrc] ; inc(iResult, 2); end; end else PrevAct := actRLE_Equal ; end else // пара байт не равна begin inc(CountDiff); if PrevAct = actRLE_Equal then // если до этого пары байт были равны begin // при переходе от повторяющейся пары байт к неповторяющейся паре // нельзя говорить о том, что есть уникальный байт. // Возможно, это переход от одной повторяющейся последовательности к другой dec(CountDiff); // если по счетчику получается, что равны между собой CountRepeat пар // байт, то значит всего между собой равны CountRepeat + 1 байтов Result[iResult] := -(CountRepeat+1) + 1 ; // байт счетчика (повторы): m = -n+1 inc(iResult); Result[iResult] := PSrc[iSrc-1]; inc(iResult); CountRepeat := 0; end; if (CountDiff = 128) or (FlagStop) then // больше 128 неповторов указывать нельзя begin // если байты кончились - то последний байт тоже относим к неповторяющемуся if (FlagStop) and (CountDiff < 128) then begin Result[iResult] := (CountDiff+1) - 1 ; // байт счетчика (неповторы): m = n-1 inc(iResult); CopyMemory(@Result[iResult], @(PSrc^[iSrc-CountDiff]), CountDiff+1); inc(iResult, CountDiff+1); end else begin Result[iResult] := CountDiff - 1 ; // байт счетчика (неповторы): m = n-1 inc(iResult); CopyMemory(@Result[iResult], @(PSrc^[iSrc-CountDiff]), CountDiff); inc(iResult, CountDiff); end; // начинаем анализ пар заново PrevAct := actRLE_None ; // исключительная ситуация - остался 1 байт в конце, невозможно проанализировать пару // а 129 неповторов записать нельзя if (FlagStop) and (CountDiff = 128) then begin Result[iResult] := $00; // значение счетчика, означает, что далее 1 байт данных Result[iResult+1] := PSrc[iSrc] ; inc(iResult, 2); end; CountDiff := 0; end else PrevAct := actRLE_NotEqual ; end; inc(iSrc); end; SetLength(Result, iResult); end; end;

=====================================================================

Опять же, пришлось учитывать много нюансов. Один из нюансов:

Исходная последовательность, пример: $5A B7 B7 D6
Тут вроде бы налицо повтор два раза B7, но реально в обрамлении
неповторов упаковывать двухповтор смысла не имеет. получится так:
00 5A FF B7 00 D6
Что составляет 6 байт. Выгоднее такие повторы не упаковывать и
получить: 03 5A B7 B7 D6 - что составляет 5 байт.

Ну и прочее, прочее... Написал примитивную программу для тестирования алгоритма, вроде бы функцию отладил, но полностью не уверен ;(
Если кто сделает нагляднее или там быстрее - выкладывайте!

← →
Mr. D (2007-08-09 05:34) [27]

А вот функция из модуля QStrings, который посоветовал Lacmus.

Эту функцию я вообще не понимаю. Не знаю, может она быстрее моей, но алгоритм работы непонятен! Откуда там набор ExVals? Нафига проверяется вхождение, что за спец. символы?

А вот описание:

{
Если символ повторяется менее трех раз, то никаких замен не производится. Если число повторений символа от трех до восьми, то эта последовательность заменяется двумя символами, от 9 до 127 - тремя символами, от 128 до 16383 - четырьмя.......

[skip]

Каждый единичный специальный символ заменяется парой символов, последовательность из двух специальных символов (одинаковых) заменяется парой символов, последовательность от 3 до 127 специальных символов заменяется тремя символами, далее - как обычно.

Почему двумя символами заменяется только повторение от 3 до 8?! Ведь одним байтом можно указывать до 128 неповторов и 129 повторов?!

Что за спец. символы, с чего они взялись? Также там написано, что если в последовательности исходной много спец. символов - то результат может быть куда больше, чем исходник (как предел - в два раза разбухнет "архивированная" информация)
Муторно в общем как-то. Может, кто знает ответы?

type PRLECnt = ^TRLECnt; TRLECnt = array[0..5] of Byte; const RLECC3 = $16; RLECC4 = $17; RLECC5 = $18; RLECC6 = $19; RLECC7 = $1D; RLECC8 = $1E; RLECCN = $7F; ExVals: set of Byte = [RLECC3,RLECC4,RLECC5,RLECC6,RLECC7,RLECC8,RLECCN]; ... function Q_PackRLE(Source, Dest: Pointer; SrcL: Cardinal): Cardinal; overload; var P1: PByte; P2: PRLECnt; Cnt: Cardinal; B: Byte; begin P1 := Source; P2 := Dest; while SrcL <> 0 do begin Cnt := 1; B := P1^; Dec(SrcL); Inc(P1); while SrcL <> 0 do if P1^ = B then begin Inc(P1); Dec(SrcL); Inc(Cnt); end else Break; if not (B in ExVals) then begin if Cnt = 1 then begin PByte(P2)^ := B; Inc(PByte(P2)); end else if Cnt > 8 then begin P2^[0] := RLECCN; P2^[1] := B; Inc(PByte(P2),2); while Cnt > 127 do begin PByte(P2)^ := Byte(Cnt) or $80; Inc(PByte(P2)); Cnt := Cnt shr 7; end; PByte(P2)^ := Cnt; Inc(PByte(P2)); end else begin case Cnt of 2: P2^[0] := B; 3: P2^[0] := RLECC3; 4: P2^[0] := RLECC4; 5: P2^[0] := RLECC5; 6: P2^[0] := RLECC6; 7: P2^[0] := RLECC7; 8: P2^[0] := RLECC8; end; P2^[1] := B; Inc(PByte(P2),2); end; end else begin P2^[1] := B; if Cnt = 1 then begin P2^[0] := RLECC6; Inc(PByte(P2),2); end else if Cnt = 2 then begin P2^[0] := RLECC4; Inc(PByte(P2),2); end else begin P2^[0] := RLECCN; Inc(PByte(P2),2); while Cnt > 127 do begin PByte(P2)^ := Byte(Cnt) or $80; Inc(PByte(P2)); Cnt := Cnt shr 7; end; PByte(P2)^ := Cnt; Inc(PByte(P2)); end; end; end; Result := LongWord(P2); Dec(Result,LongWord(Dest)); end;

Объясни для чего тебе RLE?

← →
Mr. D (2007-08-09 14:44) [29]

> Объясни для чего тебе RLE?

для сжатия информации! Пока для сжатия последовательности RGB байт (почти BMP).

А кто-нибудь знает ответы на вопросы, озвученные в [27]? Что это за RLE такое со спец. символами?!

И есть где-нибудь описание какие хоть варианты RLE бывают?

> Пока для сжатия последовательности RGB байт (почти BMP)

Ну раз "почти", проанализируй любой файл PCX-формата - многое сразу станет понятным.

← →
Mr. D (2007-08-09 16:55) [31]

Не могу я себе позволить еще неделю убить на анализ файла PCX-формата. Может, где написано об этом?

Что за RLE в [27], что за спец. символы, зачем их выделяют?!

> А кто-нибудь знает ответы на вопросы, озвученные в [27]?
Знает - не значит ответит.

← →
Mr. D (2007-08-09 18:13) [33]

О боже... Ну ладно, переформулирую - "Может кто-нибудь ответить на мои вопросы?"

> Может кто-нибудь ответить на мои вопросы?
Может - не значит ответит. )

Насколько я понял, RLE - это замена входной последовательности байтов на пары (количество повторений, символ). Реализаций может быть много и отличаются они в кодировании количества повторений. Вполне возможно, что в [27] это оригинальная реализация RLE и специальные символы могут быть любыми, но эти меньше всего встречаются.

RLE-кодирование Найти похожие ветки