65.9K
CodeProject 正在变化。 阅读更多。
Home

RLE: 人类友好的压缩

Patrice T
starIconstarIconstarIconstarIconstarIcon

5.00/5 (13投票s)

2021 年 9 月 7 日

CPOL

5分钟阅读

viewsIcon

27778

downloadIcon

493

RLE（行程长度编码）：人类友好的压缩

背景

每当人们想节省数据存储空间时，压缩就是答案。RLE 是一种非常简单的压缩算法。

xPrompt 下载和 prg 文件

xPrompt.zip 包含 xHarbour 脚本引擎的 Windows 可执行文件。这是运行 prg 代码所需的应用程序。

用法

  • 将 prg 文件复制到 xPrompt 的同一目录中
  • 启动 xPrompt
  • 键入 "do FileName.prg" 来运行代码

xHarbour 是免费软件，可在 xHarbour.org 下载 [^]。

xHarbour 是 xBase 系列语言的一部分：xBase - Wikipedia [^]。

目录

  1. 引言
  2. RLE 算法
    1. 示例
    2. RLE 翻译表
    3. 编码
    4. 解码
  3. 康威生命游戏
    1. 示例
    2. RLE 翻译表
    3. 编码
    4. 解码
  4. 俄罗斯方块：一个实际案例
    1. 示例
    2. RLE 翻译表
    3. 编码
    4. 解码
  5. 关注点
  6. 链接
  7. 历史

1. 引言

RLE 的意思是“游程长度编码”，这种压缩方法侧重于相同值的重复（游程）以实现压缩。这也意味着它仅在适合的数据集上有效。由于它非常简单，因此可以手动进行编码和解码。

2. RLE 算法

RLE 是一种应用于文本的无损数据压缩算法。其原理是用计数值和数据值的一次出现来替换相同数据的游程。当游程重复 3 次或更多次时，该操作很有意义。由于我们在编码游程时使用数字，因此当输入包含数字时，必须进行转换以避免数据和计数之间的冲突。

当数据中出现大量具有相同数据的长游程的大型位图时，RLE 就显得很有意义。

  • 传真：RLE 在全球范围内广泛用于传真，因为传真是由仅黑或白的点组成的图，并且具有大量相同颜色的游程。
  • 游戏关卡：像俄罗斯方块这样的具有 2D 地图关卡的游戏是很好的候选者，因为在游戏的任何时候，只需要以未压缩的形式呈现当前关卡。
  • 大型数据集：康威生命游戏就是一个很好的例子，它包含只有两个值的大型数据集，并且以死细胞为主。

示例

在此示例中，位图是输入，右侧是每行的 RLE 编码。下方是完整的 RLE。最后是输入大小和 RLE 大小。输出未经优化。

Bitmap Letter A
Bitmap                 RLE
...................... 22.$
...................... 22.$
.......xxxxxxx........ 7.7x8.$
.....xxxxxxxxxxx...... 5.11x6.$
....xxxxxxxxxxxxx..... 4.13x5.$
....xxxx......xxxx.... 4.4x6.4x4.$
...xxxx........xxx.... 3.4x8.3x4.$
...xxx.........xxx.... 3.3x9.3x4.$
...............xxx.... 15.3x4.$
..............xxxx.... 14.4x4.$
......xxxxxxxxxxxx.... 6.12x4.$
....xxxxxxxxxxxxxx.... 4.14x4.$
...xxxxxxxxx...xxx.... 3.9x3.3x4.$
..xxxxx........xxx.... 2.5x8.3x4.$
..xxx..........xxx.... 2.3x10.3x4.$
..xxx.........xxxx.... 2.3x9.4x4.$
..xxx.........xxxx.... 2.3x9.4x4.$
..xxxx......xxxxxx.... 2.4x6.6x4.$
...xxxxxxxxxxx.xxxxx.. 3.11x.5x2.$
....xxxxxxxxx...xxxx.. 4.9x3.4x2.$
.....xxxxxx.....xxxx.. 5.6x5.4x2.$
...................... 22.$
...................... 22.!
22.$22.$7.7x8.$5.11x6.$4.13x5.$4.4x6.4x4.$3.4x8.3x4.$3.3x9.3x4.$15.3x4.$14.4x
4.$6.12x4.$4.14x4.$3.9x3.3x4.$2.5x8.3x4.$2.3x10.3x4.$2.3x9.4x4.$2.3x9.4x4.$2.4x
6.6x4.$3.11x.5x2.$4.9x3.4x2.$5.6x5.4x2.$22.$22.!
Bitmap size= 506 RLE size= 204

RLE 翻译表

模式 编码 含义
。（点） 。（点） 白点
x x 黑点
  数字 重复次数
  $ 行尾
  ! 模式结束

编码

在 RLE.zip 中，程序文件是 RLE_Enc_fax.prg，输入模式在文件 Fax.txt 中，结果在文件 Fax.log 中。

* RLE encoding for Simple Bitmap
clear screen

/* Data file structure
pattern Name on first line
Pattern
empty line to indicate the end of pattern
*/

mdl= {}
* Read input file
handle= fopen("Fax.txt")
tmp= freadln(handle, ,1024)
do while len(tmp) > 0
	tmp= left(tmp,len(tmp)-2) // remove carriage return
	aadd(mdl, tmp)
	tmp= freadln(handle, ,1024)
enddo
fclose(handle)

* process input file
set printer to Fax.log
set printer on
title= .T.
for scan=1 to len(mdl)
	? mdl[scan] // output pattern name
	rle= ""
	bitmap= 0

	scan++
	do while len(mdl[scan]) != 0
		? mdl[scan] // output pattern line
		rle_line= ""
		bitmap += len(mdl[scan])
		last= mdl[scan,1]
		cnt= 1
		for scanc=2 to len(mdl[scan])
			if last= mdl[scan, scanc]
				cnt++
			else
				if cnt> 1
					rle_line += str(cnt,,, .t.)
				endif
				rle_line += last

				last= mdl[scan, scanc]
				cnt= 1
			endif
		next
		* if last != "."
			if cnt> 1
				rle_line += str(cnt,,, .t.)
			endif
			rle_line += last
		* endif
		scan++
		if len(mdl[scan]) = 0
			rle_line += "!"
		else
			rle_line += "$"
		endif
		?? " "
		?? rle_line // output line encoding
		rle += rle_line

	enddo
	? rle // output full RLE
	? "Bitmap size= "+str(bitmap,,, .t.)
	?? " RLE size= "+str(len(rle),,, .t.)
	?

next
set printer off
set printer to
return

解码

在 RLE.zip 中，程序文件是 RLE_Dec_fax.prg。

* RLE decoding for simple Bitmap
clear screen

pattern= "22.$22.$7.7x8.$5.11x6.$4.13x5.$4.4x6.4x4.$3.4x8.3x4.$3.3x9.3x
4.$15.3x4.$14.4x4.$6.12x4.$4.14x4.$3.9x3.3x4.$2.5x8.3x4.$2.3x10.3x
4.$2.3x9.4x4.$2.3x9.4x4.$2.4x6.6x4.$3.11x.5x2.$4.9x3.4x2.$5.6x5.4x2.$22.$22.!"

* process RLE pattern
cnt=0
for scan=1 to len(pattern)
	char= pattern[scan]
	if isdigit(char)
		cnt= cnt*10+ val(char)
	else
		if char= "$" .or. char= "!"
			? // next line
		else
			if cnt= 0
				cnt=1
			endif
			for rep= 1 to cnt
				? char
			next
		endif
		cnt= 0
	endif
next
?

return

3. 康威生命游戏

生命游戏模式非常适合 RLE 压缩，因为数据集很大，细胞要么是死的要么是活的，并且死细胞占数据集的大部分。

游程长度编码 - LifeWiki [^]

在 Category:Patterns - LifeWiki [^] 中可以找到数百个 RLE 压缩的模式。

示例

2-engine Cordership
...................OO.................... 19b2O$
...................OOOO.................. 19b4O$
...................O.OO.................. 19bOb2O$
......................................... $
....................O.................... 20bO$
...................OO.................... 19b2O$
...................OOO................... 19b3O$
.....................O................... 21bO$
.................................OO...... 33b2O$
.................................OO...... 33b2O$
......................................... $
......................................... $
......................................... $
......................................... $
......................................... $
......................................... $
....................................O.... 36bO$
...................................OO.... 35b2O$
..................................O...O.. 34bO3bO$
...................................OO..O. 35b2O2bO$
........................................O 40bO$
.....................................O.O. 37bObO$
......................................O.. 38bO$
......................................O.. 38bO$
......................................OO. 38b2O$
......................................OO. 38b2O$
......................................... $
......................................... $
.............O..........O................ 13bO10bO$
............OOOOO.....O.OO...........O... 12b5O5bOb2O11bO$
...........O..........O...O.........O.... 11bO10bO3bO9bO$
............OO........OOO.O.........OO... 12b2O8b3ObO9b2O$
.............OO.........OO............O.. 13b2O9b2O12bO$
OO.............O.....................OOO. 2O13bO21b3O$
OO...................................OOO. 2O35b3O$
......................................... $
......................................... $
......................................... $
......................................... $
......................................... $
......................................... $
........OO............................... 8b2O$
........OO...........OO.................. 8b2O11b2O$
...................OO..O................. 19b2O2bO$
........................O...O............ 24bO3bO$
..................O.....O...O............ 18bO5bO3bO$
...................O..OO...O.O........... 19bO2b2O3bObO$
....................OOO.....O............ 20b3O5bO$
............................O............ 28bO!
19b2O$19b4O$19bOb2O$$20bO$19b2O$19b3O$21bO$33b2O$33b2O$$$$$$$36bO$35b2O$3
4bO3bO$35b2O2bO$40bO$37bObO$38bO$38bO$38b2O$38b2O$$$13bO10bO$12b5O5bOb2O1
1bO$11bO10bO3bO9bO$12b2O8b3ObO9b2O$13b2O9b2O12bO$2O13bO21b3O$2O35b3O$$$$$
$$8b2O$8b2O11b2O$19b2O2bO$24bO3bO$18bO5bO3bO$19bO2b2O3bObO$20b3O5bO$28bO!
Bitmap size= 2009 RLE size= 292

未进行行尾优化的结果。请注意 RLE 大小的差异。

19b2O20b$19b4O18b$19bOb2O18b$41b$20bO20b$19b2O20b$19b3O19b$21bO19b$33b2O6b$
33b2O6b$41b$41b$41b$41b$41b$41b$36bO4b$35b2O4b$34bO3bO2b$35b2O2bOb$40bO$37b
ObOb$38bO2b$38bO2b$38b2Ob$38b2Ob$41b$41b$13bO10bO16b$12b5O5bOb2O11bO3b$11bO
10bO3bO9bO4b$12b2O8b3ObO9b2O3b$13b2O9b2O12bO2b$2O13bO21b3Ob$2O35b3Ob$41b$41
b$41b$41b$41b$41b$8b2O31b$8b2O11b2O18b$19b2O2bO17b$24bO3bO12b$18bO5bO3bO12b
$19bO2b2O3bObO11b$20b3O5bO12b$28bO12b!
Bitmap size= 2009 RLE size= 413

RLE 翻译表

模式 编码 含义
。（点） b 死细胞
O o 活细胞
  数字 重复次数
  $ 行尾
  ! 模式结束

由于游戏区域默认设置为死细胞，因此可以移除行尾的死细胞。

编码

在 RLE.zip 中，程序文件是 RLE_Enc_gol.prg，输入模式在文件 Gol.txt 中，结果在文件 Gol.log 中。

* RLE encoding for Conway's Game of Life
clear screen

/* Data file structure
GoL pattern Name on first line
Pattern
empty line to indicate the end of pattern
*/

mdl= {}
* Read input file
handle= fopen("gol.txt")
tmp= freadln(handle, ,1024)
do while len(tmp) > 0
	tmp= left(tmp,len(tmp)-2) // remove carriage return
	aadd(mdl, tmp)
	tmp= freadln(handle, ,1024)
enddo
fclose(handle)

* process input file
set printer to GoL.log
set printer on
title= .T.
for scan=1 to len(mdl)
	? mdl[scan] // pattern name
	rle= ""
	bitmap= 0

	scan++
	do while len(mdl[scan]) != 0
		? mdl[scan] // output pattern line
		rle_line= ""
		bitmap += len(mdl[scan])
		last= mdl[scan,1]
		cnt= 1
		for scanc=2 to len(mdl[scan])
			if last= mdl[scan, scanc]
				cnt++
			else
				if cnt> 1
					rle_line += str(cnt,,, .t.)
				endif
				if last= "."
					rle_line += "b" // translation
				else
					rle_line += last
				endif

				last= mdl[scan, scanc]
				cnt= 1
			endif
		next
		if last != "."  // EOL optimization
			if cnt> 1
				rle_line += str(cnt,,, .t.)
			endif
			if last= "."
				rle_line += "b" // translation
			else
				rle_line += last
			endif
		endif
		scan++
		if len(mdl[scan]) = 0
			rle_line += "!"
		else
			rle_line += "$"
		endif
		?? " "
		?? rle_line // output line encoding
		rle += rle_line

	enddo
	? rle // output full RLE
	? "Bitmap size= "+str(bitmap,,, .t.)
	?? " RLE size= "+str(len(rle),,, .t.)
	?

next
set printer off
set printer to
return

解码

在 RLE.zip 中，程序文件是 RLE_Dec_Gol.prg 和 Gol.cpp。

* RLE decoding for simple Bitmap
clear screen

pattern= "19b2O$19b4O$19bOb2O$$20bO$19b2O$19b3O$21bO$33b2O$33b2O$$$$$$$36bO
$35b2O$34bO3bO$35b2O2bO$40bO$37bObO$38bO$38bO$38b2O$38b2O$$$13bO10bO$12b5O5
bOb2O11bO$11bO10bO3bO9bO$12b2O8b3ObO9b2O$13b2O9b2O12bO$2O13bO21b3O$2O35b3O$
$$$$$$8b2O$8b2O11b2O$19b2O2bO$24bO3bO$18bO5bO3bO$19bO2b2O3bObO$20b3O5bO$28bO!"

* process RLE pattern
cnt= 0
for scan=1 to len(pattern)
	char= pattern[scan]
	if isdigit(char)
		cnt= cnt*10+ val(char)
	else
		if char= "$" .or. char= "!"
			? // next line
		else
			if cnt= 0
				cnt=1
			endif
			if char= "b"
				char= "."
			endif
			for rep= 1 to cnt
				?? char
			next
		endif
		cnt= 0
	endif
next
?

return
' Sample program for HP Prime calculator
RLEMap (px, py, RLE)
' Game of Life RLE decoding
BEGIN
  LOCAL Row, Col, Ptr, Cnt, Cod;
  Row:= py; Col:= px+2; Cnt:= 0;
  FOR Ptr FROM 1 TO DIM(RLE) DO
    Cod:= MID(RLE, Ptr, 1);
    CASE
      IF INSTRING("0123456789", Cod) <> 0 THEN Cnt:= Cnt*10+EXPR(Cod); END;
      IF Cod == "$" THEN Row:= Row+MAX(1, Cnt); Col:= px+2; Cnt:= 0; END;
      IF INSTRING("b.", Cod) <> 0 THEN Col:= Col+MAX(1, Cnt); Cnt:= 0; END;
      IF INSTRING("oA", Cod) <> 0 THEN
        FOR Col FROM Col TO Col+MAX(1, Cnt)-1 DO
          Lignes(IP(Row/60)+1, Col):= BITOR(Lignes(IP(Row/60)+1, Col), 
          BITSL(#2,(Row MOD 60) ));
        END;
        Cnt:= 0;
      END;
    END;
  END;
  LDisp();
END;
// A RLE decoder for GoL in C.
void RLEMap(int px, int py, string RLE) {

	unsigned int Row, Col, Ptr, Cnt;
	char Cod;
	Row = py + 1;
	Col = px + 1 + 2;
	Cnt = 0;
	for (Ptr = 0; Ptr < RLE.length(); Ptr++) {
		Cod = RLE[Ptr];
		switch (Cod) {
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			Cnt = Cnt * 10 + (Cod - '0');
			break;
		case '$':
			if (Cnt == 0)
				Cnt = 1;
			Row = Row + Cnt;
			Col = px + 1 + 2;
			Cnt = 0;
			break;
		case 'b':
		case '.':
			if (Cnt == 0)
				Cnt = 1;
			Col = Col + Cnt;
			Cnt = 0;
			break;
		case 'o':
		case 'O':
			if (Cnt == 0)
				Cnt = 1;
			for (; Cnt > 0; Cnt--) {
				CellSet(Row, Col);
				Col++;
			}
			Cnt = 0;
		}
	}
}

4. 俄罗斯方块：一个实际案例

早在 2013-2014 年，我就参与了“HP Prime 图形计算器”的 beta 测试。计算器上市后不久，一位 HP 粉丝论坛的成员为该计算器发布了一个俄罗斯方块游戏。

除了添加使用键盘的可能性（原始版本仅支持触摸屏）之外，我还使用 RLE 压缩了所有 40 个关卡。

原始源代码 SokobanBeta1.03.prime 的大小为 112k (UTF16)。我的版本 SokobanBeta1.5.prime 的大小为 52k (UTF16)。大约只有一半大小。

示例

Level 1-1 as matrix                          RLE
[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]   $                   
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]   $                   
,[0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0]   2b4w4b3w$           
,[0,0,1,3,0,1,1,1,0,0,1,4,1,0,0,0,0,0,0,0]   2bwdb3w2bwsw$       
,[0,0,1,3,0,0,0,1,1,1,1,0,1,1,1,1,0,0,0,0]   2bwd3b4wb4w$        
,[0,0,1,3,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0]   2bwd5b2wbw2bw$      
,[0,0,1,1,1,0,1,0,0,0,0,0,0,0,2,1,0,0,0,0]   2b3wbw7bcw$         
,[0,0,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,0,0,0]   4bw3bwb4wb2w$       
,[0,0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0]   3b2wbwbw7bw$        
,[0,0,0,1,0,2,1,0,1,0,1,0,2,0,0,0,1,0,0,0]   3bwbcwbwbwbc3bw$    
,[0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0]   3bw10b3w$           
,[0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]   3b12w$              
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]   $                   
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]   $                   
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]  !                   
$$2b4w4b3w$2bwdb3w2bwsw$2bwd3b4wb4w$2bwd5b2wbw2bw$2b3wbw7bcw$4bw3bwb4wb2w$
3b2wbwbw7bw$3bwbcwbwbwbc3bw$3bw10b3w$3b12w$$$!
Matrix Size= 20* 15= 300  RLE Size= 120
Matrix Size in source code= 630

RLE 翻译表

模式 编码 含义
0 b 背景
1 w 墙
2 c 方块（包裹）
3 d 目的地（目标）
4 s 俄罗斯方块
  数字 重复次数
  $ 行尾
  ! 模式结束

编码

此函数用于编码一个俄罗斯方块关卡。语言是 hpppc：Hewlett-Packard Prime 编程语言，一种 BASIC。

RLEEnc (Mt) // RLE encoder
BEGIN
  LOCAL Row, Col, Cod, Cnt, Tmp, Sz;
  Tmp:= ""; Sz:=SIZE(Mt);
  FOR Row FROM 1 TO Sz(1) DO
    Cnt:= 1; Cod:= Mt(Row,1);
    FOR Col FROM 2 TO Sz(2) DO
      IF Cod == Mt(Row,Col) THEN
        Cnt:= Cnt+1;
      ELSE
        IF Cnt <> 1 THEN Tmp:= Tmp+ STRING(Cnt,2,0); END;
        Tmp:= Tmp+ MID("bwcds",Cod+1,1);
        Cnt:= 1; Cod:= Mt(Row,Col);
      END;
    END;
    IF Cod <> 0 THEN
      IF Cnt <> 1 THEN Tmp:= Tmp+ STRING(Cnt,2,0); END;
      Tmp:= Tmp+ MID("bwcds",Cod+1,1);
    END;
    Tmp:= Tmp+ "$";
  END;
  RETURN Tmp;
END;

由于这是计算器编程，因此没有简单的方法可以进行终端输出进行编码。我需要一个补充函数来解决这个问题。

编码函数是内部程序（在程序外部不可见）。因此，我创建了一个可从用户计算器界面调用的导出函数。

其优点在于，用户界面中的结果可以被复制/粘贴到模拟器外部，从而方便地将结果粘贴到源代码中。

// Apply RLE compression to all levels
// remove drawscreen() before converting
EXPORT Sok_RLE()
BEGIN
  LOCAL Lst:={};
  FOR NAJ FROM 10 TO 49 DO
    loadsubnivel();
    IF TYPE(matriz) == 2 THEN
      Lst:= CONCAT(Lst, {{NAJ, matriz}});
    ELSE
      Lst:= CONCAT(Lst, {{NAJ, RLEEnc (matriz)}});
    END;
  END;
  RETURN Lst;
END;

解码

语言是 hpppc：Hewlett-Packard Prime 编程语言，一种 BASIC。

RLEDec (Rows, Cols, RLE) // RLE decoder
BEGIN
  LOCAL Row, Col, Ptr, Cnt, Cod, Tmp;
  Row:= 1; Col:= 1; Cnt:= 0;
  Tmp:= MAKEMAT(0,Rows,Cols);
  FOR Ptr FROM 1 TO DIM(RLE) DO
    CASE
      IF INSTRING("0123456789", MID(RLE, Ptr, 1)) <> 0 
      THEN Cnt:= Cnt*10+EXPR(MID(RLE, Ptr, 1)); END;
      IF MID(RLE, Ptr, 1) == "$" THEN Row:= Row+MAX(1, Cnt); Col:= 1; Cnt:= 0; END;
      DEFAULT
      Cod:= INSTRING("bwcds", MID(RLE, Ptr, 1));
      FOR Col FROM Col TO Col+MAX(1, Cnt)-1 DO Tmp(Row,Col):=Cod- 1; END; Cnt:= 0;
    END;
  END;
  RETURN Tmp;
END;

5. 值得关注的要点

  • 一种易于处理的数据压缩算法

7. 历史

  • 2021 年 3 月 21 日：初稿
  • 2021 年 9 月 6 日：第一个版本
  • 2021 年 9 月 8 日：第二个版本，增加了康威生命游戏
  • 2021 年 9 月 11 日：第三个版本，增加了俄罗斯方块示例
  • 2022 年 1 月 2 日：添加了参考 .sok 文件
  • 2022 年 1 月 30 日：修复了拼写错误
  • 2022 年 1 月 16 日：为生命游戏添加了一个 C 解码器，已更新下载
© . All rights reserved.