前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >聊聊字典编码1 导论2 LZ77算法3 LZ78算法

聊聊字典编码1 导论2 LZ77算法3 LZ78算法

作者头像
JavaEdge
发布2019-01-02 13:06:34
3.4K0
发布2019-01-02 13:06:34
举报
文章被收录于专栏:JavaEdgeJavaEdge

最近由于课程设计需要做解压缩算法

特此来考察字典编码

1 导论

许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。因此,人们提出了许许多多的数据压缩方法,企图用来对这些数据进行压缩编码,在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。 字典编码(dictionary encoding)技术(以下简称DE)就是属于这一类,这种技术属于无损压缩技术。

  • DE根据的是数据本身包含有重复代码这个特性 例如文本文件和光栅图像就具有这种特性

1.1 分类

种类很多,归纳起来大致有两类

1.1.1 查找正在压缩的字符序列是否在历史输入数据中出现过

用已经出现过的字符串替代重复部分,输出仅仅是指向之前出现过的字符串的“指针”

  • 这里的“字典”指 用以前处理过的数据来表示编码过程中遇到的重复部分 这类编码的所有算法都是以abraham lempeljakob ziv在1977年研究发表的称为lz77算法为基础

1.1.2 从输入的数据中创建一个“短语字典(dictionary of the phrases)”

这种短语不一定是像“好好学习天天向上”和“你个糟老头子坏得很我信你个鬼”这类具有具体含义的短语,它可以是任意字符的组合 编码数据过程中当遇到已经在字典中出现的“短语”时,编码器就输出这个字典中的短语的“索引号”,而不是短语本身。 j.ziva.lempel在1978年首次发表了这种编码方法的文章 在他们的研究基础上,terry a.weltch在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为LZW(lempel-ziv walch)压缩编码,首先在高速硬盘控制器上应用了这种算法

2 LZ77算法

2.1 常见术语

  • 输入数据流(input stream) 要被压缩的字符序列
  • 字符(character) 输入数据流中的基本单元。
  • 编码位置(coding position) 输入数据流中当前要编码的字符位置,指前向缓冲存储器中的开始字符
  • 前向缓冲存储器(Lookahead buffer) 存放从编码位置到输入数据流结束的字符序列的存储器。
  • 窗口(window) 包含W个字符的窗口,字符是从编码位置开始向后数也就是最后处理的字符数
  • 指针(pointer) 指向窗口中的匹配串且含长度的指针

核心是查找从前向缓冲存储器开始的最长的匹配串

2.2 执行步骤

1.把编码位置设置到输入数据流的起始位 2.查找窗口中最长的匹配串 3.以“(Pointer, Length) Characters”的格式输出 其中Pointer是指向窗口中匹配串的指针,Length表示匹配字符的长度,Characters是前向缓冲存储器中的不匹配的第1个字符。 4.如果前向缓冲存储器不是空的,则把编码位置和窗口向前移(Length+1)个字符,然后返回到步骤2

[例]

待编码的数据流

编码过程

  • “步骤” 编码步骤
  • “位置” 编码位置,输入数据流中的第1个字符为编码位置1
  • “匹配串” 窗口中找到的最长的匹配串
  • “字符” 匹配后在前向缓冲存储器中的第1个字符
  • “输出” 以“(Back_chars, Chars_length) Explicit_character”格式输出
    • (Back_chars, Chars_length) 指向匹配串的指针 告诉译码器在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出
    • Explicit_character 真实字符 例如,表编码过程的输出(5,2) C告诉译码器回退5个字符,然后拷贝2个字符“AB”

但wikipedia认为,粗体字理解成 从编码位置开始往回数Back_chars个字符,从该字符开始数起的字符串与接下来的Chars_length个字符完全相同

原文

3 LZ78算法

3.1 术语和符号

  • 字符流(Charstream) 要被编码的数据序列
  • 字符(Character) 字符流中的基本数据单元
  • 前缀(Prefix) 在一个字符之前的字符序列 -缀-符串(String) 前缀+字符
  • 码字(Code word) 码字流中的基本数据单元,代表字典中的一串字符
  • 码字流(Codestream) 码字和字符组成的序列,编码器的输出
  • 字典(Dictionary) 缀-符串表。按照字典中的索引号对每条缀-符串(String)指定一个码字(Code word)
  • 当前前缀(Current prefix) 在编码算法中使用,指当前正在处理的前缀,用符号P表示。
  • 当前字符(Current character) 在编码算法中使用,指当前前缀之后的字符,用符号C表示。
  • 当前码字(Current code word) 在译码算法中使用,指当前处理的码字,用W表示当前码字,String.W表示当前码字的缀-符串

3.2 编码算法

不断从字符流中提取新的缀-符串(String),通俗地理解为新“词条”,然后用“代号”也就是码字(Code word)表示这个“词条” 这样一来,对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream),生成码字流(Codestream),从而达到压缩数据的目的

在编码开始时字典是空的,不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C,并把这个字符C添加到字典中作为一个由一个字符组成的缀-符串(string)。在编码过程中,如果出现类似的情况,也照此办理。在字典中已经包含某些缀-符串(String)之后,如果“当前前缀P +当前字符C”已经在字典中,就用字符C来扩展这个前缀,这样的扩展操作一直重复到获得一个在字典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C,并把P+C添加到字典中作为前缀(Prefix),然后开始处理字符流(Charstream)中的下一个前缀。

LZ78编码器的输出是码字-字符(W,C)对,每次输出一对到码字流中,与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String),然后添加到字典中

3.3 具体算法

步骤1

在开始时,字典和当前前缀P都是空的

步骤2

当前字符C:=字符流中的下一个字符

步骤3

P+C 是否在字典中 (1) “是” 用C扩展P,让P := P+C (2) “否”     ① 输出与当前前缀P相对应的码字和当前字符C     ② 把字符串P+C 添加到字典中     ③ 令P:=空值 (3) 字符流中是否还有字符需要编码     ① “是” 返回到步骤2     ② “否” 若当前前缀P非空,输出相应于当前前缀P的码字,然后结束编码

3.4 译码算法

在译码开始时译码字典是空的,它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时,码字就参考已经在字典中的缀-符串,然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream),而把当前缀-符串(string.W+C)添加到字典中。在译码结束之后,重构的字典与编码时生成的字典完全相同。LZ78译码的具体算法如下:   步骤1: 在开始时字典是空的。   步骤2: 当前码字W :=码字流中的下一个码字。   步骤3: 当前字符C := 紧随码字之后的字符。   步骤4: 把当前码字的缀-符串(string.W)输出到字符流(Charstream),然后输出字符C。   步骤5: 把string.W+C添加到字典中。   步骤6: 判断码字流中是否还有码字要译    (1) 如果“是”,就返回到步骤2。    (2) 如果“否”,则结束。

[例4.6] 编码字符串如表4-13所示,编码过程如表4-14所示。现说明如下:   ●“步骤”栏表示编码步骤。   ●“位置”栏表示在输入数据中的当前位置。   ●“字典”栏表示添加到字典中的缀-符串,缀-符串的索引等于“步骤”序号。   ●“输出”栏以(当前码字W, 当前字符C)简化为(W, C)的形式输出。 表4-13 编码字符串

位置

1

2

3

4

5

6

7

8

9

字符

A

B

B

C

B

C

A

B

A

表4-14 编码过程

步骤

位置

字典

输出

1

1

A

(0,A)

2

2

B

(0,B)

3

3

B C

(2,C)

4

5

B C A

(3,A)

5

8

B A

(2,A)

与LZ77相比,LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目,而压缩率与LZ77类似。

LZW算法

在LZW算法中使用的术语与LZ78使用的相同,仅增加了一个术语—前缀根(Root),它是由单个字符串组成的缀-符串(String)。在编码原理上,LZW与LZ78相比有如下差别:①LZW只输出代表字典中的缀-符串(String)的码字(code word)。这就意味在开始时字典不能是空的,它必须包含可能在字符流出现中的所有单个字符,即前缀根(Root)。②由于所有可能出现的单个字符都事先包含在字典中,每个编码步骤开始时都使用一字符前缀(one-character prefix),因此在字典中搜索的第1个缀-符串有两个字符。   现将LZW编码算法和译码算法介绍如下。

1. 编码算法   LZW编码是围绕称为字典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列,并且为每个表项分配一个码字(Code word),或者叫做序号,如表4-15所示。这张转换表实际上是把8位ASCII字符集进行扩充,增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位,12位可以有4096个不同的12位代码,这就是说,转换表有4096个表项,其中256个表项用来存放已定义的字符,剩下3840个表项用来存放前缀(Prefix)。 表4-15 字典

码字(Code word)

前缀(Prefix)

1

193

A

194

B

255

1305

abcdefxyF01234

LZW编码器(软件编码器或硬件编码器)就是通过管理这个字典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream),字符流可以是用8位ASCII字符组成的字符串,而输出是用n位(例如12位)表示的码字流(Codestream),码字代表单个字符或多个字符组成的字符串。   LZW编码器使用了一种很实用的分析(parsing)算法,称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中,每一次分析都要串行地检查来自字符流(Charstream)的字符串,从中分解出已经识别的最长的字符串,也就是已经在字典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符,形成新的扩展字符串——缀-符串(String):Prefix.C。这个新的缀-符串(String)是否要加到字典中,还要看字典中是否存有和它相同的缀-符串String。如果有,那么这个缀-符串(String)就变成前缀(Prefix),继续输入新的字符,否则就把这个缀-符串(String)写到字典中生成一个新的前缀(Prefix),并给一个代码。   LZW编码算法的具体执行步骤如下:   步骤1: 开始时的字典包含所有可能的根(Root),而当前前缀P是空的;   步骤2: 当前字符(C) :=字符流中的下一个字符;   步骤3: 判断缀-符串P+C是否在字典中    (1) 如果“是”:P := P+C // (用C扩展P);    (2) 如果“否”     ① 把代表当前前缀P的码字输出到码字流;     ② 把缀-符串P+C添加到字典;     ③ 令P := C //(现在的P仅包含一个字符C);   步骤4: 判断码字流中是否还有码字要译    (1) 如果“是”,就返回到步骤2;    (2) 如果“否”     ① 把代表当前前缀P的码字输出到码字流;     ② 结束。   LZW编码算法可用伪码表示。开始时假设编码字典包含若干个已经定义的单个码字。例如,256个字符的码字,用伪码可以表示成:

Dictionary[j] ← all n single-character, j=1, 2, …,n   j ← n+1   Prefix ← read first Character in Charstream   while((C ← next Character)!=NULL)   Begin    If Prefix.C is in Dictionary     Prefix ← Prefix.C    else     Codestream ← cW for Prefix    Dictionary[j] ← Prefix.C    j ← n+1    Prefix ← C   end   Codestream ← cW for Prefix

2. 译码算法   LZW译码算法中还用到另外两个术语:①当前码字(Current code word):指当前正在处理的码字,用cW表示,用string.cW表示当前缀-符串;②先前码字(Previous code word):指先于当前码字的码字,用pW表示,用string.pW表示先前缀-符串。   LZW译码算法开始时,译码字典与编码字典相同,它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW),从码字流中读当前码字(cW)之后输出当前缀-符串string.cW,然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到字典中。   LZW译码算法的具体执行步骤如下:   步骤1:在开始译码时字典包含所有可能的前缀根(Root)。   步骤2:cW :=码字流中的第一个码字。   步骤3:输出当前缀-符串string.cW到码字流。   步骤4: 先前码字pW := 当前码字cW。   步骤5: 当前码字cW := 码字流中的下一个码字。   步骤6: 判断先前缀-符串string.pW是否在字典中    (1) 如果“是”,则:     ① 把先前缀-符串string.pW输出到字符流。     ② 当前前缀P :=先前缀-符串string.pW。     ③ 当前字符C :=当前前缀-符串string.cW的第一个字符。     ④ 把缀-符串P+C添加到字典。    (2) 如果“否”,则:     ① 当前前缀P :=先前缀-符串string.pW。     ② 当前字符C :=当前缀-符串string.cW的第一个字符。     ③ 输出缀-符串P+C到字符流,然后把它添加到字典中。   步骤7: 判断码字流中是否还有码字要译    (1) 如果“是”,就返回到步骤4。    (2) 如果“否”, 结束。   LZW译码算法可用伪码表示如下:

Dictionary[j] ← all n single-character, j=1, 2, …,n   j ← n+1   cW ← first code from Codestream   Charstream ← Dictionary[cW]   pW ← cW   While((cW ← next Code word)!=NULL)   Begin    If cW is in Dictionary     Charstream ← Dictionary[cW]     Prefix ← Dictionary[pW]     cW ← first Character of Dictionary[cW]     Dictionary[j] ← Prefix.cW     j ← n+1     pW ← cW    else     Prefix ← Dictionary[pW]     cW ← first Character of Prefix     Charstream ← Prefix.cW    Dictionary[j] ← Prefix.C    pW ← cW    j ← n+1   end   [例4.7] 编码字符串如表4-16所示,编码过程如表4-17所示。现说明如下:   ●“步骤”栏表示编码步骤;   ●“位置”栏表示在输入数据中的当前位置;   ●“字典”栏表示添加到字典中的缀-符串,它的索引在括号中;   ●“输出”栏表示码字输出。

表4-16 被编码的字符串

位置

1

2

3

4

5

6

7

8

9

字符

A

B

B

A

B

A

B

A

C

表4-17 LZW的编码过程

步骤

位置

字典

输出

(1)

A

(2)

B

(3)

C

1

1

(4)

A B

(1)

2

2

(5)

B B

(2)

3

3

(6)

B A

(2)

4

4

(7)

A B A

(4)

5

6

(8)

A B A C

(7)

6

--

--

--

(3)

表4-18解释了译码过程。每个译码步骤译码器读一个码字,输出相应的缀-符串,并把它添加到字典中。例如,在步骤4中,先前码字(2)存储在先前码字(pW)中,当前码字(cW)是(4),当前缀-符串string.cW是输出(“A B”),先前缀-符串string.pW ("B")是用当前缀-符串string.cW ("A")的第一个字符,其结果("B A") 添加到字典中,它的索引号是(6)

表4-18 LZW的译码过程

步骤

代码

字典

输出

(1)

A

(2)

B

(3)

C

1

(1)

--

--

A

2

(2)

(4)

A B

B

3

(2)

(5)

B B

B

4

(4)

(6)

B A

A B

5

(7)

(7)

A B A

A B A

6

(3)

(8)

A B A C

C

LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度,以及在字典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。   LZW算法取得了专利,专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司),除了商业软件生产公司之外,可以免费使用LZW算法。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.12.27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1 导论
    • 1.1 分类
      • 1.1.1 查找正在压缩的字符序列是否在历史输入数据中出现过
      • 1.1.2 从输入的数据中创建一个“短语字典(dictionary of the phrases)”
  • 2 LZ77算法
    • 2.1 常见术语
      • 2.2 执行步骤
        • [例]
    • 3 LZ78算法
      • 3.1 术语和符号
        • 3.2 编码算法
          • 3.3 具体算法
            • 步骤1
            • 步骤2
            • 步骤3
          • 3.4 译码算法
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档