1、中华人民共和国国家标准信息技术信息交换用数据压缩具有嵌入字典的自适应编码算法发布实施国家技术监督局发布前言本标准等同采用国际标准信息技术信息交换用数据压缩具有嵌入字典的自适应编码算法为适应信息交换本标准规定了无损的压缩算法以减少用编码形式表示的数据的位数本标准无论在技术内容上还是在编排格式上均与国际标准保持一致附录附录和附录均是提示的附录本标准由中华人民共和国电子工业部提出本标准由电子工业部标准化研究所归口本标准起草单位电子工业部标准化研究所本标准主要起草人王宝艾杨霖郑洪仁前言国际标准化组织和国际电工委员会是世界性的标准化专门机构国家成员体它们都是或的成员国通过国际组织建立的各个技术委员会参与
2、制定针对特定技术范围的国际标准和的各技术委员会在共同感兴趣的领域内进行合作与和有联系的其他官方和非官方国际组织也可参与国际标准的制定工作对于信息技术和建立了一个联合技术委员会即由联合技术委员会提出的国际标准草案需分发给国家成员体进行表决发布一项国际标准至少需要的参与表决的国家成员体投标赞成国际标准是由欧洲计算机制造商协会标准编制的在特定的快速跟踪程序下被所采纳同时被和国际组织通过附录附录和附录仅供参考引言在过去的十年里颁布了许多有关磁带盒式磁带和卡式磁带以及盒式光盘的国际标准最近开发的这些媒体具有高的物理记录密度为了最佳利用最终的数据容量设计了多种压缩算法以减少用编码形式表示的用户数据的位数将
3、来这些压缩算法将由建立的国际登记机构登记登记将对每一个已登记的算法分配一数字的标识符对于记录媒体该标识符应包含在记录格式中以指明所使用的是哪种哪些压缩算法该国际标准是第一个有关压缩算法的国际标准中华人民共和国国家标准信息技术信息交换用数据压缩具有嵌入字典的自适应编码算法国家技术监督局批准实施范围本标准规定了无损的压缩算法以减小用位字节编码表达信息所要求的位数此算法称为根据和的数据压缩本标准既不规定重置字典的策略也不规定冻结字典的策略因为它们是依赖于实现的当信息必须记录在可互换的媒体上时此算法特别有用它的使用并不局限于这种应用一致性如果一个压缩算法的输出数据流满足第章的要求则认为与本标准一致引用
4、标准下列标准所包含的条文通过在本标准中引用而构成为本标准的条文本标准出版时所示版本均为有效所有标准都会被修订使用本标准的各方应探讨使用下列标准最新版本的可能性信息技术无损的数据压缩算法的登记规程定义代码值一个从到变化的整数它由压缩算法产生代码字在以二进制表达代码值的输出流中或个连续位的集合压缩比压缩算法的输入流中的位数除以压缩算法的输出流中的位数字典由项组成的一个表它用于保留输入流中选择的字节串每一项由大于的唯一代码值标识空状态字典中无数据的状态冻结状态不再有数据加入字典的状态记法和同义词本标准中的数用十进制表示记录结束算法标识符本算法在国际登记组织登记的数字标识符是压缩算法概述压缩算法应以位
5、数据字节流的形式接受信息输入并以新组织成位字节的位流形式输出代码字本算法应识别输入流中字节串的重复并应从输出流中排除这样的冗余随着由电子信息处理系统和设备产生发送或记录的信息类型的多样化数据重复度足够高以允许输出流比输入流有效地包含更少的位数但是在变态环境下输出流可能比输入流包含更多的位数实际上达到的压缩比依赖于具体的输入数据流的特征本算法的压缩是无损的即它可能使用互补的解压缩算法完全恢复数据的原始表达本算法包含一些特征这些特征帮助算法实现数据存储和检索设备在顺序方式下处理可变长度的数据记录运算原则运算的基本原则是对出现在输入流中的字节串的一个字典进行编译使用该字典检测重复串并为每个重复串产生
6、一个代码字这个代码字表达一个代码值它是对应重复串而被引用的字典项字典的编译本算法开始运算之前字典应设置成空状态见本算法应检测输入流并应查找第一个出现的唯一对或唯一串唯一对是一个还没有被分配字典项的字节串个字节的唯一串是一个还没有被分配字典项的字节串但是前面的个字节应已被分配字典项字典项能分配给串的最大长度是个字节当遇到唯一对时本算法应输出一个代码字以表达该对的第一个字节的代码值当遇到字节的唯一串时本算法应输出一个代码字以表达该串前面个字节的代码值然后如果字典未被冻结见且不超过则它应把唯一对或唯一串输进字典并分配下一个未使用的代码值给该项从当前唯一对的第二个字节或从当前唯一串的最后一个字节开始则
7、本算法应继续检测输入流并查找下一个唯一对或唯一串冻结字典当出现下列情况时应认为字典处在冻结状态所有有用的代码值都已被分配本算法的执行程序已决定不把唯一对或唯一串输入字典例如因为在字典中查找未占用空间所耗费的时间太多改掉字典冻结状态的唯一方法是重置空状态见重置字典为空状态如果已输入算法的所有字节已由代码字表达本算法允许在任何时候重置字典为空状态例如如果因为当前字典项没有充分反映输入流当前的重复特征而使当前压缩程度不够算法可以选择重置字典边界在输入流中自然边界可以存在于字节集之间例如输入流可以由记录的序列组成每个记录包含一个或多个字节这种情况下自然边界存在于记录之间本算法应提供在输出流中识别这种边
8、界的方法以致于它们可以被解压缩算法认识和重组这种标识应由代码字输出完成见后跟表达单个字节字节对或字节串的代码值的代码字这些代码字是为检测输入流的唯一对或唯一串的目的而暂时保存的然后输入流的检测应从下一记录的第一个字节继续开始这个结果是输入流中边界之间的数据由输出流中相应边界之间的代码字完全表达输出流中这样的边界被认为是定位于跟在紧随代码字后的代码字的填充位的末端字典的重建字典本身不作为特征项包含在输出流中任何适用的解压缩算法都将重建字典并存储来自压缩算法输出流数据的原始表达式代码值代码值到分配给控制代码见代码值到分配给编码字节见代码值到分配给字典代码见控制代码定义个控制代码如下所述的代码值到的
9、值不用字典冻结该控制代码的代码值应为它指示字典已经冻结不强制算法输出该代码值只要输入至算法的所有字节已由代码字表达就可以在算法决定冻结字典之后的任何时候输出它字典重置该控制代码的代码值应为它应是字典重置为空状态后由本算法输出的第一个代码值在其他任何时候都不应当输出它必要时在此输出流中包含此代码值的代码字应由足够数量的用来填充下一个位字节的且被置成的比特跟随着增加代码字大小该控制代码的代码值应为它应该表示所有随后代码字若有的话直到下一个增加代码字大小的控制代码为止的位数目比包含此代码值的代码字的位数目多记录结束该控制代码的代码值应为它应该指示在输入流中一个记录边界存在于用下一个代码字表达的代码值
10、表示的字节对或串之后必要时在此输出流中包含该代码值的代码字应由足够数量的用来填充下一个位字节的且被置成的比特跟随着此输出流中的下一个代码字应由足够数量的用来填充下一个位字节的且被置成的比特跟随着后者要求是为确保表示输入流中的一个记录的一组代码字从位字节开始在连续的位字节结束编码字节一个已编码字节表示输入流中的单个字节一个已编码字节的完整集合表示单个字节的可能值的完整集合即到一个已编码字节应这样计算将此字节值加来进行编码字典代码一个字典代码识别一个字节对或一个字节串的字典项代码字当字典是空状态时代码字的大小是位如有必要增加代码字大小使之能够表达因太大而不能被当前代码字大小表达的代码值见本算法也可
11、以在其他任何时候增加代码字大小如果当前代码字的大小大于表达要求的代码值所必须的大小冗余位应比需要位在更高的位置并置为减少代码字大小的规则应是本算法置字典为空状态应输出表达字典重置控制代码的代码字该代码字的大小应是如果存在的最后一个增加代码字大小控制代码所要求的大小如果有必要应将填充位置成直到下一个字节下一个代码字应是位的代码字输出时代码字应从最低有效位开始顺序输入代码字的位从而构造成位字节从最右位开始从右至左外理构造成位字节的连续位当字节中所有位置都被使用应输出此字节随后代码字的位进入输出流的下一字节附录提示的附录通常的算法示例下面描述了通常的压缩算法表述使用结构化的英语也称为伪代码该语言使用
12、普通英语的词汇语法和语义加上特殊的单词和格式约定它表述指令或者是无条件执行或者是按存在的特殊条件或者多个条件的组合执行它也表述这样的条件另外它还提供注释其目的是有助于读者理解本算法按照有条件执行或重复执行将指令组成集合以文本缩排分层来表示一个指令集合有相同等级的或不同等级的缩排除非要在哪里重复执行或有条件执行已被表明外指令应从页上方向下顺序执行注释被括在花括号内它并不执行算法的具体实现可互不相同例如决定冻结字典或重置字典为空状态的实现策略算法包括两部分第一部分处理输入流并产生代码值第二部分处理代码值并产生代码字在输入流中如果记录边界跟有在第一部分产生的特殊代码值表示的串的最后字节则给该代码值添
13、加一个指示符标志出现这样一个标志就命令第二部分产生包含代码值的代码字代码值产生器本算法的运算如表所示术语意为输出一个代码值术语意为输出一个带添加指示符标志的代码值被输出的此代码值括在圆括号内本算法的一个基本成分是串称为它用于匹配输入流与相应的字典项它可以为空如果非空它包含的字节数应少于个字典项是长度在到字节之间的串因而在字典中查找一个字节的串将会失败对待输入流中的最后字节就如同它后面跟有记录边界一样以下是对表所示算法的基本特征的总体描述外部层初始化字典为空状态并输出字典重置控制代码重复执行的指令每重复一次便处理一个记录直到整个输入流字节被处理完为止处理一个记录从输入流取得记录的第一个字节如果该
14、记录仅包含这个字节则输出该字节的编码字节并确保代码字产生器产生代码字和适当的填充位否则重复执行中的指令直到此记录的所有字节被处理完为止处理一个字节对从输入流取得下一个字节从而形成对如果在字典中有这个对那么执行中的指令否则如果可能把这个对加到字典中或者如果不可能则冻结字典输出对的第一个字节的编码字节并抛弃第一个字节如果剩余的字节是此记录的最后字节那么输出该字节的编码字节并确保代码字产生器产生代码字和适当的填充位处理一个字节串重复执行中的指令把此对扩充到增加长度的串中直到到达记录末尾或在字典中不存在该串在前一种情况下输出该串的字典代码并确保代码字产生器产生代码字和适当的填充位在后一种情况下如果可能
15、把这个串加到字典中或者如果不可能则冻结字典输出此串的所有字节除了最后字节外的字典代码抛弃这些字节如果剩余的字节是此记录的最后字节那么输出该字节的编码字节并确保代码字产生器产生代码字和适当的填充位扩充对或串除非此对或串的当前最后字节是此记录的最后字节从输入流取得下一字节把它添加到当前对或串并为新形成的串查找字典表代码值产生器表完代码字产生器本算法的本部分从代码值产生代码字同时按需要在输出流中填充字节边界本算法的运算如表所示要输出的代码字的内容括在圆括号内表代码字产生器附录提示的附录对给定的输入流输出代码值的示例下例中自上而下运行表输入流输入字节字典代码字典项代码值输出代码值含义字典重置的编码字节的编码字节的编码字节的编码字节表完输入流输入字节字典代码字典项代码值输出代码值含义的字典代码的字典代码的字典代码的字典代码的字典代码的字典代码的字典代码的字典代码的编码字节的编码字节的编码字节在这个例子中用于表示数据的位数目从减小到这是的压缩比对更长的输入流压缩比更大这是因为在输入流中重复的串的事例将更多而将做出更多的字典项压缩比的典型值是从到的范围附录提示的附录参考文献等盘式磁带驱动器数据压缩惠普月刊第卷年月第页
