专栏首页JavaEdge聊聊字典编码1 导论2 LZ77算法3 LZ78算法

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

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

特此来考察字典编码

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算法。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/qq_33589510复制
如有侵权,请联系 yunjia_community@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 他发明了通用数据压缩算法:Jacob Ziv获2021 IEEE荣誉勋章

    近日,90 岁的 IEEE 终身 Fellow、以色列科学家 Jacob Ziv 因其「对信息论和数据压缩技术的重要贡献和杰出研究领导地位」获得本年度的 IEE...

    机器之心
  • 90 岁程序员,他的压缩算法改变了世界!

    点击关注公众号,Java干货及时送达 近日,国际电气与电子工程学会(Institute of Electrical and Electronics Engin...

    Java技术栈
  • 90 岁程序员:他的压缩算法改变了世界!

    近日,国际电气与电子工程学会(Institute of Electrical and Electronics Engineers,简称 IEEE)宣布,授予 I...

    GitHubDaily
  • 【多媒体】PNG简介

    (本文改自多媒体导论我课上做的演讲)转眼就暑假了,这一篇我在4月份准备写结果写了一半就坑到了现在,也是很真实。

    ZifengHuang
  • 如果产品中需要压缩功能,我们应该如何选择压缩算法?

    看过很多压缩相关的技术文章,大家都在讲各种压缩算法的技术实现原理及各压缩算法之间的压缩率的对比,哪个压缩算法好等等。这些技术文章非常好,可以指引我们在技术上不...

    深度学习与Python
  • ZIP压缩算法详细分析及解压实例解释(上)

    来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往) 最近自己实...

    智能算法
  • 深度学习助力数据压缩,一文读懂相关理论

    本文对数据压缩的「前世今生」进行简要的回顾,重点分析基于深度学习的有损压缩、无损压缩方法,对基于深度学习的数据压缩进行了探讨和展望。

    机器之心
  • 十款性能最佳的压缩算法

    数据压缩是保留相同或绝大部分数据前提下减小文件大小的过程。它的原理是消除不必要的数据或以更高效的格式重新组织数据。在进行数据压缩时,你可以选择使用有损方法或无损...

    Spark学习技巧
  • Linux 命令(118)—— bzip2 命令

    bzip2 用来压缩和解压缩文件,是在 Linux 系统中经常使用的一个对文件进行压缩和解压缩的命令,采用 Burrow-Wheeler 块排序文本压缩算法和 ...

    Dabelv
  • gzip压缩算法

    gzip,zlib,以及图形格式png,使用的是同一个压缩算法deflate。我们通过对gzip源码的分析来对deflate压缩算法做一个详细的说明:

    黄规速
  • 从节省Redis内存空间说开去

    上周部门会议上讨论的一个议题是如何节省Redis内存空间,其中有个小伙伴提到可以从压缩字符串入手,我觉得这是一个可以尝试的思路。因为有时候我们存在Redis中的...

    Bug开发工程师
  • Linux普通文件压缩工具gzip、Bzip2、xz

    .zip,.gz,.bz2,.xz, .tar.gz,.tar.bz2,.tar.xz

    阿dai学长
  • 《看聊天记录都学不会Python到游戏实战?太菜了吧》(3)都说123是字符不是数字

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • 19个Linux备份压缩命令

    ? 文 | 云豆 来源 | 菜鸟教程 ? 云豆贴心提醒,本文阅读时间5分钟,文末有秘密! Linux ar命令 Linux ar命令用于建立或修改备存...

    小小科
  • 面经分享|中科院老哥的算法&开发岗面经总结

    往昔的回忆使我们激动,我们重新踏上旧日的路,一切过去日子的感情,又逐渐活在我们的心里;使我们再次心紧的是,曾经熟悉的震颤;为了回忆中的忧伤,真想吐出一声长叹……

    石晓文
  • ZIP压缩算法详细分析及解压实例解释(下)

    来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往) 7、ZIP...

    智能算法
  • 计算机圣经

    哈喽小伙伴们,我是你们的老朋友 cxuan,今天这篇文章不聊技术,我们来谈一个特别的话题。在聊这个话题前,我想先确认个事儿,在座的大部分大学所选的专业应该都是计...

    cxuan
  • 人工智能导论 (六) - 智能计算及其应用1 简介2 基本遗传算法3 编码4 适应度函数

    受自然界和生物界规律的启迪,人们根据其原理模 仿设计了许多求解问题的算法,包括人工神经网络、 模糊逻辑、遗传算法、DNA计算、模拟退火算法、 禁忌搜索算法、免疫...

    JavaEdge

扫码关注云+社区

领取腾讯云代金券