장님 앞에서는 애꾸가 복된 자 이다. - 프레데리크 대왕

Billboarding Tutorial
expat/reference
lua 5.0 beta�� ȣȯ��ҵ�
win32api/���ϱ�4

RLE ��

* 구글에서 우연히 찾은 화일안의 내용 중 RLE 부분만 번역한 것입니다.

원본화일 : CODECS.ZIP

1 개요
2 첫번째 RLE 구조(scheme)
3 Second RLE scheme

[edit]

1 개요 #

RLE은 Run Length Encoding의 약어이다. 다른 약어를 들자면 RLC (Run Length Coding)라고도 한다. (둘은 같은 뜻이다.) 이 방식의 아이디어는 데이타를 반복되는 프레임에 기준하여 재코딩하는 것이다. 프레임은 한번 이상 반복되는 하나 이상의 바이트들이 될 수 있다.

There are several means to encode occurrences. 따라서, 몇가지 코덱(복호기)를 가지게 될 것이다. 예를 들자면, 다음과 같은 배열을 가지고 있다고 하자:

0,0,0,0,0,0,255,255,255,2,3,4,2,3,4,5,8,11

몇몇 코덱은 단지 0과 255 전체의 반복만을 다룰 것이고, 몇몇 코덱은 0의 반복과 255의 반복을 별도로 다룰 것이다.

이 예제에 기초한 중요한 점들을 명심하도록. 코덱은 압축하려고 하는 모든 데이타에 동작하지는 않는다. 그래서, 반복되는 요소가 없는 경우, RLE방식의 코덱은 압축할 수 없다고 할 필요는 없다. 실제로, 반복되지 않은 데이타를 압축하려고 시도할 것이다. (이것은 데이타를 그대로 복사하는 것과 같다.) 물론, 입력 데이타의 복사본은 각 복사 블럭의 앞에 "헤더"가 붙어있다. 이것은 전체데이타를 압축한다기 보다는 도리어 크기를 증가시킬 수 있다. 그러나 압축되는 전체 데이타의 입장에서 보면, 반복되는 프레임 부분의 압축은 비압축부분보다 훨씬 적은 공간을 차지할 것이다.

RLE라는 이름을 가진 모든 알고리즘은 다음과 같은 3~4개의 수치를 가지고 있다:

Value saying if there's a repetition
Value saying how many repetitions (or non repetition)
Value of the length of the frame (useless if you just encode frame with one byte as maximum length)
Value of the frame to repeat (or not)

언급한 것을 설명하기위해 4가지의 알고리즘을 제시하도록 하겠다.

[edit]

2 첫번째 RLE 구조(scheme) #

첫번째 구조는 내가 알고 있는 한 가장 간단한 구조이다. MAC 어드레스 시스템(MacPackBit)에서 사용된 것과 Targa, PCX, TIFF등등의 화일포멧에서 사용된 방식과 비슷하게 보일 수도 있다.

여기, 모든 압축된 블럭은 헤더(header)라고 이름지어진 1 바이트로 시작된다. 이것은 아래 그림과 같다:

Bits	7	6	5	4	3	2	1	0
Header	X	X	X	X	X	X	X	X

비트 7 : 압축 상황 (1 = 압축이 적용됨)
0 ~ 6 : 다루어야할 바이트의 수

따라서, 만약 비트 7이 0으로 설정되었다면, 0 ~ 6비트 부분은 뒤따라오는 바이트 수를 나타낸다. (minus 1, to gain more over compress) So, if the bit 7 is set up to 0, the 0 to 6 bits give the number of bytes that follow (minus 1, to gain more over compress) and that were not compressed (native bytes). 만약 비트 7이 1로 설정되어있으면, If the bit 7 is set up to 1, the same 0 to 6 bits give the number of repetition (minus 2) of the following byte.

보다시피, 이 방법은 단지 1 바이트로 프레임을 제어할 뿐이다.

추가사항 : 여러분은 압축하기 위해서는 적어도 1개의 바이드를 가져야 하므로 비압축 프레임에 대해.. You have 'minus 1' for non-repeated frames because you must have at least one byte to compress and 'minus 2' for repeated frames because the repetition must be 2, at least.

Compression scheme:

	      First byte=Next
		    /\
		   /  \
Count the byte         Count the occurrence of NON identical
occurrences            bytes (maximum 128 times)
(maximum 129 times)    and store them in an array
	|                        |
	|                        |
  1 bit '1'                 1 bit '0'
+ 7 bits giving           + 7 bits giving
  the number (-2)           the number (-1)
  of repetitions            of non repetition
+ repeated byte           + n non repeated bytes
	|                        |
 1xxxxxxx,yyyyyyyy        0xxxxxxx,n bytes
[-----------------]      [----------------]

Example:

Sequence of bytes to encode	Coded values	Differences with compression (unit: byte)
255,15,	1,255,15,	-1
255,255,	128,255,	0
15,15,	128,15,	0
255,255,255,	129,255,	+1
15,15,15,	129,15,	+1
255,255,255,255,	130,255,	+2
15,15,15,15	130,15	+2

See codecs source codes: codrle1.c and dcodrle1.c

[edit]

3 Second RLE scheme #

In the second scheme of RLE compression you look for the less frequent byte in the source to compress and use it as an header for all compressed block.

In the best cases, the occurrence of this byte is zero in the data to compress.

Two possible schemes, firstly with handling frames with only one byte, secondly with handling frames with one byte *and* more. The first case is the subject of this current compression scheme, the second is the subject of next compression scheme.

For the frame of one byte, header byte is written in front of all repetition with at least 4 bytes. It is then followed by the repetition number minus 1 and the repeated byte. Header byte, Occurrence number-1, repeated byte

If a byte don't repeat more than tree times, the three bytes are written without changes in the destination stream (no header nor length, nor repetition in front or after theses bytes).

An exception: If the header byte appears in the source one, two, three and up times, it'll be respectively encoded as following: - Header byte, 0 - Header byte, 1 - Header byte, 2 - Header byte, Occurrence number-1, Header byte

Example, let's take the previous example. A non frequent byte is zero-ASCII because it never appears.

Sequence of bytes to encode | Coded values | Differences with compression


(unit: byte)

255,15, | 255,15, | 0 255,255, | 255,255, | 0

15,15, | 15,15, | 0

255,255,255, | 255,255,255, | 0

15,15,15, | 15,15,15, | 0

255,255,255,255, | 0,3,255, | -1

15,15,15,15 | 0,3,15 | -1

If the header would appear, we would see:

Sequence of bytes to encode | Coded values | Differences with compression


(unit: byte)

0, | 0,0, | +1

255, | 255, | 0

0,0, | 0,1, | 0 15, | 15, | 0

0,0,0, | 0,2, | -1

255, | 255, | 0

0,0,0,0 | 0,3,0 | -1

See codecs source codes: codrle2.c and dcodrle2.c

*** Third RLE scheme ***

It's the same idea as the second scheme but we can encode frames with more than one byte. So we have three cases:

- If it was the header byte, whatever is its occurrence, you encode it with: Header byte,0,number of occurrence-1 - For frames which (repetition-1)*length>3, encode it as: Header byte, Number of frame repetition-1, frame length-1,bytes of frame - If no previous cases were detected, you write them as originally (no header, nor length, nor repetition in front or after theses bytes).

Example based on the previous examples:

Sequence of bytes to encode | Coded values | Differences with compression


(unit: byte)

255,15, | 255,15, | 0 255,255, | 255,255, | 0

15,15, | 15,15, | 0

255,255,255, | 255,255,255, | 0

15,15,15, | 15,15,15, | 0

255,255,255,255, | 255,255,255,255, | 0

15,15,15,15, | 15,15,15,15, | 0

16,17,18,16,17,18, |16,17,18,16,17,18,| 0

255,255,255,255,255, | 0,4,0,255, | -1

15,15,15,15,15, | 0,4,0,15, | -1

16,17,18,16,17,18,16,17,18,| 0,2,2,16,17,18, | -3

26,27,28,29,26,27,28,29 |0,1,3,26,27,28,29 | -1

If the header (value 0) would be met, we would see:

Sequence of bytes to encode | Coded values | Differences with compression


(unit: byte)

0, | 0,0,0, | +2

255, | 255, | 0

0,0, | 0,0,1, | +1

15, | 15, | 0

0,0,0, | 0,0,2, | 0

255, | 255, | 0

0,0,0,0 | 0,0,3 | -1

See codecs source codes: codrle3.c and dcodrle3.c

*** Fourth RLE scheme ***

This last RLE algorithm better handles repetitions of any kind (one byte and more) and non repetitions, including few non repetitions, and does not read the source by twice as RLE type 3.

Compression scheme is:

First byte=Next byte?

Yes / \ No

/ \

1 bit '0' 1 bit '1'

/ \

Count the Motif of several occurrences repeated byte? of 1 repeated ( 65 bytes repeated byte (maximum 257 times maxi) 16449 times) /\

/\ / \

/ \ / \

/ \ / \ 1 bit '0' 1 bit '1' 1 bit '0' 1 bit '1'

+ 6 bits + 14 bits + 6 bits of | giving the giving the the length Number of non repetition length (-2) length (-66) of the motif (maximum 8224) of the of the + 8 bits of /\ repeated byte repeated byte the number (-2) < 33 / \ > 32 + repeated byte + repeated byte of repetition / \


+ bytes of the 1 bit '0' 1 bit '1'

| | motif + 5 bits of + 13 bits


\| the numer (-1) of the

| | | of non number (-33)


\| repetition of repetition

| | | + non + non


\| repeated repeated

| | | bytes bytes


\| \| \|

| | | | 111xxxxx,xxxxxxxx,n bytes


\| \| -------------------------

| | | |


\| 110xxxxx,n bytes

| | | ----------------


\|

| | 10xxxxxx,yyyyyyyy,n bytes


-------------------------

| | | 01xxxxxx,xxxxxxxx,1 byte | ------------------------ |

00xxxxxx,1 byte ---------------

Example, same as previously:

Sequence of bytes to encode | Coded values | Differences with compression


(unit: byte)

255,15,255,255,15,15 |11000101b,255,15,255,255,15,15 | +1

255,255,255 | 00000001b,255, | -1

15,15,15 | 00000001b,15, | -1

255,255,255,255 | 00000010b,255, | -2

15,15,15,15 | 00000010b,15, | -2

16,17,18,16,17,18 | 10000001b,0,16,17,18, | -1

255,255,255,255,255 | 00000011b,255, | -3

15,15,15,15,15 | 00000011b,15, | -3

16,17,18,16,17,18,16,17,18 | 10000001b,16,17,18, | -4

26,27,28,29,26,27,28,29 | 10000010b,26,27,28,29 | -2

번역중

ID
Password
Join

Contents

1 개요 #

2 첫번째 RLE 구조(scheme) #

3 Second RLE scheme #