首页 > 知识点讲解
       算法
知识路径: > 多媒体数据压缩编码技术基础 > 统计编码 > 字典编码 > 字典编码 > 
被考次数:1次     被考频率:低频率     总体答错率:46%     知识难度系数:     
相关知识点:2个      
        隐式字典的典型压缩算法有LZ77和LZSS。显式字典的典型压缩算法有LZ78和LZW。下面介绍LZ77算法和LZSS算法。
               LZ77算法
               为了更好地说明LZ77算法的原理,首先介绍该算法中的几个术语。
               . 输入流:要被压缩的字符序列。
               . 字符:输入流中的基本数据单元。
               . 编码位置:输入流中当前要编码的字符位置,指前向缓冲存储器中的开始字符。
               . 前向缓存:存放从编码位置到输入流结束的字符序列。
               . 窗口:包含W个字符的窗口,字符是从编码位置开始往后数的,也就是最后处理的字符数。
               . 指针:指向窗口中的匹配串并包含长度的指针。
               LZ77算法的核心是查找从前向缓冲存储器开始的最长的匹配串。该算法的具体执行步骤如下。
               步骤1:把编码位置设置到输入流的开始位置。
               步骤2:查找窗口中最长的匹配串。
               步骤3:以(Pointer, Length)Characters的格式输出。其中Pointer是指向窗口中匹配串的指针,Length表示匹配字符的长度,Characters是前向缓存中不匹配的第1个字符。
               步骤4:如果前向缓冲存储器不是空的,则把编码位置和窗口向前移(Length+1)个字符,然后返回步骤2。
               LZSS算法
               LZSS算法通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这种解决方案包含冗余信息,冗余信息表现在两个方面:一是编码器的输出可能包含空指针;二是编码器可能输出额外字符,即可能包含下一个匹配串中的字符。LZSS算法以比较有效的方法解决了这个问题,它的思想是如果匹配串的长度比指针本身的长度长,就输出指针,否则就输出真实字符。由于输出数据流中包含指针和字符本身,因此为了区分它们就需要有额外的标志位,即ID位。
               LZSS算法的具体执行步骤如下。
               步骤1:把编码位置置于输入流的开始位置。
               步骤2:在前向缓冲存储器中查找窗口中最长的匹配串。
               ①Pointe:匹配串指针。
               ②Length:匹配串长度。
               步骤3:判断匹配串长度Length是否大于或等于最小匹配串长度(Length≥MIN_ LENGTH)。
               是:输出指针,然后把编码位置向前移动Length个字符。
               否:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动1个字符。
               步骤4:如果前向缓冲存储器不是空的,则返回步骤2。
               在相同的计算环境下,LZSS算法比LZ77可获得更高的压缩比,而译码同样简单。这也就是为什么这种算法成为开发新算法的基础,许多后来开发的文档压缩程序都使用了LZSS的思想,如PKZip、ARJ、LHArc和ZOO等,其差别仅仅是指针的长短和窗口的大小有所不同。
               LZSS同样可以和熵编码联合使用,如ARJ就与霍夫曼编码联用,而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码。
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2016年上半年
   多媒体应用设计..
   上午试卷 综合知识
第43题
选择题
下列数据压缩编码方法中(43)编码属于词典编码。

46%
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有