CTW无损压缩算法的原理与应用摘要：在有限的传输带宽下传输数据时，传输率受到限制，如何高效地压缩传输数据，以便减少存储空间和传输时间，已经成为迫切需要解决的问题。本文在一种无损数据压缩算法CTw（contexttreeweight）的基础上，提出了改进的CTW算法。该算法采用了新的更低穴余度的概率估算法，并继承了CTW算法所具有的速度快和抗差错能力强等特点，与通用压缩软件inzip相比能够获得更好的压缩率，从而保证了实时处理的可行性。本文基于对实际数据的实验，针对此算法的工作原理进行了综述，并提出了扩展和进一步研究的建议。关键词：无损压缩；CTW：上下文加权树Theprincipleand application ofCTWlossless compressionalgorithmAbstract:It is restricted to transmit data on limited bandwidth, so it is importantto resolve the problem of how tocompress the data in high effect so that the storage space and transmission time would be reduced. This paperproposes an ameliorated CTW algorithm based on CTW alorithm which is a sort of lossless data compressionalgorithm.This alorithm uses new probability estimation algorithm to reduce the redundancy, and inherits itscharacters offast processing speed and strong capacity.Comparedto popular compression software,which is Winzipthe Ameliorated CTW Algorithm can acquire better compression rate,and guarantee the feasibility on real?timeoperation. Basing on the operation on actual data, this paper describes the task principle, and indicates somesuggestions for development and further research.Keywords: lossless compression; CTW algorithm, context tree weight0引言近年来，随着可视电话、图文电视等各种数字图像通信技术的迅速发展，大量数据的存储成了多媒体技术最大的难题之一，这就需要有效的数据压缩算法；但是压缩也会对实时处理、存取和检索产生一定的影响，即带来一定的处理延迟。众多的数据压缩技术按压缩的失真度可以分成2个主要类型：有损压缩和无损压缩。有损压缩是指使用压缩后的数据进行重构后，得到的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解，无损压缩也称余压缩，是指使用压缩后的数据进行重构后，得到的数据与原来的数据完全相同。常见的无损编码方法有预测编码、变换编码、矢量量化、算术编码。本文研究的CTW系列算法就是无损压缩算法中的一种。CTW无损压缩算法采用了低穴余度的概率估算法，能够获得极高的压缩率，特别适用于文本数据的无损压缩[2]。1CTW算法基本原理CTW译码解码器核心包括2个部分：CTW模型预算估计器和算术译码器。其基本的工作过程如下：预算估计器接受未压缩的数据并对下一个符号进行概率估计，然后将评估的结果，即估计概率传给算术译码器，算术译码器利用得到的结果和目前的资源对原始数据进行译码，最终得到压缩后的数据。已压缩数未压缩数据算法译码器据模型预测估计器图1一CTW译码器CTW算法的一个非常重要的特性就是基于上下文树，它是在译码解码过程中动态建立的。上下文被定义为位于正在被译码的符号前面的所有符号。上下文树中出现的每个上下文都会作为一种路径被存储起来。上下文树中的每个节点包含两种类型的数据：管理树的结构所必需的4位数据以及概率估计和加权所必需的4位数据，其中第2种类型的数据最终会用于算术译/解码。用此编码器对某一位进行编码时需要依次完成下面3步：
CTW 无损压缩算法的原理与应用 摘要：在有限的传输带宽下传输数据时, 传输率受到限制, 如何高效地压缩传输数据, 以便减少存储空间和 传输时间, 已经成为迫切需要解决的问题。本文在一种无损数据压缩算法 CTW(context tree weight) 的基 础上, 提出了改进的 CT W 算法。该算法采用了新的更低冗余度的概率估算法, 并继承了 CT W 算法所具有 的速度快和抗差错能力强等特点, 与通用压缩软件 Winzip 相比能够获得更好的压缩率, 从而保证了实时处 理的可行性。本文基于对实际数据的实验, 针对此算法的工作原理进行了综述, 并提出了扩展和进一步研究 的建议。 关键词：无损压缩；CTW；上下文加权树 The principle and application of CTW lossless compression algorithm Abstract: It is restricted to transmit data on limited bandwidth, so it is important to resolve the problem of how to compress the data in high effect so that the storage space and transmission time would be reduced. This paper proposes an ameliorated CTW algorithm based on CTW alorithm which is a sort of lossless data compression algorithm. This alorithm uses new probability estimation algorithm to reduce the redundancy, and inherits its characters of fast processing speed and strong capacity. Compared to popular compression software, which is Winzip, the Ameliorated CTW Algorithm can acquire better compression rate, and guarantee the feasibility on real?time operation. Basing on the operation on actual data, this paper describes the task principle, and indicates some suggestions for development and further research. Keywords: lossless compression; CTW algorithm; context tree weight 0 引言 近年来,随着可视电话、图文电视等各种数字图像通信技术的迅速发展,大量数据的存储成了多媒 体技术最大的难题之一, 这就需要有效的数据压缩算法; 但是压缩也会对实时处理、存取和检索产生 一定的影响, 即带来一定的处理延迟。众多的数据压缩技术按压缩的失真度可以分成 2 个主要类型: 有损压缩和无损压缩[1] 。有损压缩是指使用压缩后的数据进行重构后, 得到的数据与原来的数据有所 不同, 但不会让人对原始资料表达的信息造成误解, 无损压缩也称冗余压缩, 是指使用压缩后的数 据进行重构后, 得到的数据与原来的数据完全相同。常见的无损编码方法有预测编码、变换编码、 矢量量化、算术编码。本文研究的 CTW 系列算法就是无损压缩算法中的一种。CTW 无损压缩算法 采用了低冗余度的概率估算法，能够获得极高的压缩率，特别适用于文本数据的无损压缩[2]。 1 CTW 算法基本原理 CTW 译码解码器核心包括 2 个部分：CTW 模型预算估计器和算术译码器。其基本的工作过程 如下：预算估计器接受未压缩的数据并对下一个符号进行概率估计，然后将评估的结果，即估计概 率传给算术译码器，算术译码器利用得到的结果和目前的资源对原始数据进行译码，最终得到压缩 后的数据。 模型预测估计器 未压缩数据 算法译码器 已压缩数 据 图 1—CTW 译码器 CTW 算法的一个非常重要的特性就是基于上下文树，它是在译码解码过程中动态建立的。上下 文被定义为位于正在被译码的符号前面的所有符号。上下文树中出现的每个上下文都会作为一种路 径被存储起来。上下文树中的每个节点包含两种类型的数据：管理树的结构所必需的 4 位数据以及 概率估计和加权所必需的 4 位数据，其中第 2 种类型的数据最终会用于算术译/解码。用此编码器对 某一位进行编码时需要依次完成下面 3 步：
（1）寻找与当前的上下文相适合的路径，这就意味着上下文中的各个符号可以用来决定从每一节点出发的路径的方向：（2）对于路径上的每一个节点而言，利用存储于节点内部的数据可以首先计算出下一个符号的估计概率Pe，利用所有Pe的值，通过一种加权功能计算出加权的概率Pw（3）最后，将计算出的加权概率Pw送给算术译码器，由算术译码器对符号加以译码，而上下文树更新后用于新的数据。CTW算法的核心就在于估计概率Pe和加权概率PW的计算。概率估计1.1对于上下文树中路径上的每个节点，对相邻符号的概率估计是基于此结点中0和1的个数来计算的。这种概率估计法实际上是无记忆信息源（即参数e未知）产生符号Xt作为相邻的符号。在CTW算法中，包含两种概率估算法，即KT估算法和ZR估算法。1.1.1KT估算法对于带有未知参数θE[0,1]的无记忆信息源，可以使用KT估算法进行概率估计。此方法定义条件概率如下：b+1/2Pe(Xe = 1|xf-1) = 1 - Pe(Xt = 0lxf-1) = (1)a+b+1式中：a和b分别代表符号xt-1队列中0和1的个数，而xt-1是此前由无记忆信息源产生的。参数穴余度限定为(1-)agb1(2)p(xD)≤log=≥10og(a + b) +11(a)"(b2Va+b(a+b)la+b1.1.2ZR估算法为了降低信息源只产生0或0时的参数几余度，ZR估计器被定义为[3(a.b)(a 0)1(P(a, 0)+(a> 0,b = 0)(3)P (a,b) = N2(P(0, b) +4(a = 0. b > 0)((a = 0,b= 0)在信息源只产生0和1时，参数穴余度可以由式限定：(1-)bp(x) = log-≤log4=2(4)pe(a,b)对一般文件来说，在通常情况下信息源只产生0或1，此ZR估算法通常会有比KT估算法更好的结果。1.2加权计算Pe(a,b)+Il,PwsP%(xf-1,Xt = 0)Ix - D) =(5)2式中：s代表包括上下文，xi-1代表包括上下文s在内的所有符号的全部信源符号序列的后继符号队列，Xt代表当前的符号，xi一D代表最初的上下文，其深度为D（即全部信源符号序列的前D个符号），而Pps代表其上下文Φs（Φ为0或0）的子节点的加权概率。本文所述的CTW算法在执行过程中，所有的概率是由以2为底的对数表示的。采用对数表示法的好处是将乘除法操作简化为加减运算，从而降低运算的复杂度
（1）寻找与当前的上下文相适合的路径，这就意味着上下文中的各个符号可以用来决定从每一 节点出发的路径的方向； （2）对于路径上的每一个节点而言，利用存储于节点内部的数据可以首先计算出下一个符号的 估计概率 Pe，利用所有 Pe 的值，通过一种加权功能计算出加权的概率 Pw； （3）最后，将计算出的加权概率 Pw 送给算术译码器，由算术译码器对符号加以译码，而上下 文树更新后用于新的数据。 CTW 算法的核心就在于估计概率 Pe 和加权概率 Pw 的计算。 1.1 概率估计 对于上下文树中路径上的每个节点，对相邻符号的概率估计是基于此结点中 0 和 1 的个数来计 算的。这种概率估计法实际上是无记忆信息源（即参数 θ 未知）产生符号 Xt 作为相邻的符号。在 CTW 算法中，包含两种概率估算法，即 KT 估算法和 ZR 估算法。 1.1.1 KT 估算法 对于带有未知参数 θ∈[0,1]的无记忆信息源，可以使用 KT 估算法进行概率估计。此方法定义条 件概率如下: 𝑃𝑒(𝑋𝑡 = 1|𝑥1 𝑡−1) = 1 − 𝑃𝑒(𝑋𝑡 = 0|𝑥1 𝑡−1) = 𝑏+1/2 𝑎+𝑏+1 （1） 式中：a 和 b 分别代表符号𝑥1 𝑡−1 队列中 0 和 1 的个数，而𝑥1 𝑡−1是此前由无记忆信息源产生的。 参数冗余度限定为 ρ(𝑥1 𝑇) ≤ log (1 − 𝜃)𝑎𝜃𝑏 1 2 1 √𝑎 + 𝑏 � 𝑎 𝑎 + 𝑏� 𝑎 � 𝑏 𝑎 + 𝑏� 𝑏 ≤ 1 2 log(𝑎 + 𝑏) + 1 （2 ） 1.1.2 ZR 估算法 为了降低信息源只产生 0 或 0 时的参数冗余度，ZR 估计器被定义为 𝑃𝑒 𝑧𝑧(𝑎, 𝑏) = ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 1 2 �𝑃𝑒(𝑎, 𝑏)� (𝑎 0) 1 2 �𝑃𝑒(𝑎, 0)� + 1 4 (𝑎 > 0, 𝑏 = 0) 1 2 �𝑃𝑒(0, 𝑏)� + 1 4 (𝑎 = 0. 𝑏 > 0) 1 (𝑎 = 0, 𝑏 = 0) (3) 在信息源只产生 0 和 1 时，参数冗余度可以由式限定： ρ(𝑥1 𝑇) = log (1 − 𝜃)𝑎𝜃𝑏 𝑃𝑒 𝑧𝑧(𝑎, 𝑏) ≤ log 4 = 2 (4) 对一般文件来说，在通常情况下信息源只产生 0 或 1，此 ZR 估算法通常会有比 KT 估算法更好的结 果。 1.2 加权计算 𝐏𝒘 𝒔 (𝑥1 𝑡−1, 𝑋𝑡 = 0)|𝑥1 0 − D) = 𝑃𝑒(𝑎, 𝑏) + ∏ 𝑃𝑤 𝜌𝜌 𝜌 2 (5) 式中：s 代表包括上下文，𝑥1 𝑡−1 代表包括上下文 s 在内的所有符号的全部信源符号序列的后继 符号队列，𝑋𝑡代表当前的符号，𝑥1 0 − D代表最初的上下文，其深度为 D（即全部信源符号序列的前 D 个符号），而𝑃𝑤 𝜌𝜌代表其上下文ϕs（ϕ为 0 或 0）的子节点的加权概率。本文所述的 CTW 算法在执 行过程中，所有的概率是由以 2 为底的对数表示的。采用对数表示法的好处是将乘除法操作简化为 加减运算，从而降低运算的复杂度
1.3树的组织结构CTW算法是一种二进制算法，它把每个字节分解为单独的8位，符号的每一位都有自己独立的上下文树，而且每个二进制符号的上下文包含了所有先前的二进制符号。依据当前位节点的状态从8组树中挑选1组，而其所在字节的前几位就在已选出的组中选择一棵树，于是当前面的符号也作为上下文树时，实际上就一共有255个不同的上下文树，其中第1个字节对应1棵树，第2个字节对应2棵树，第3个字节对应3棵树，以此类推。如图1所示为某一字节的第3位的上下文树。需要注意的是上下文树的结构并不是二元树，而是上述的255位树，其原因在于加权只可能在字节边界上发生。假设这255棵树都是二元树，由于存储空间有限，树的大小也是有限的，则每棵树的最大深度值是确定的，因此每棵树不仅仅在字节边界上有叶节点，而且在字节内部也存在叶节点，这就意味着前面的符号中只有一部分可以用来作为当前位的上下文树，如此操作将无法实现高效率的压缩进程，而且在字节内部进行加权是否有效值得商椎。因此加权只在字节边界发生，对于每个节点，树将分裂为256条不同的路径，使用此加权方法后，树中的节点数量减少了，压缩进程的执行时间也会缩短，压缩穴余度也相应降低，2实验综述在VC++6.0编程环境下编制改进的CTW压缩算法软件，对文本文件、图像文件和声音文件及其他类型文件进行压缩。并与常用压缩软件Winzip所压制的压缩文件进行压缩率的横向对比。设置译码器的参数如表1所示。图像2.bmp实验过程：File: 1Compressedfilesize:21132bytesUncompressedfilesize:49258bytesCTW settingsusedfor encodingTree depth: 6Sizeoftreearray:4194304nodes(33554432bytes)Max.number of tries in tree array:32Filebuffersize:49258bytes (max.4194304)Strict pruning:enabledRoot weighting: disabledMax.log beta:1024Estimator:Zero-Redundancy表一CTW算法参数设置参数值6Tree DepthSize of Tree Array33554432B32Max.Number of TriesMax. File Buffer Size4194304BEnabledStrict PruningDisabledRoot Weighting1024Max. Log BetaEstimatorZero redundancy表二实验结果比较CTWWinzip文件类型文件名称文件大小压缩后大小/B压缩率(%)压缩后大小/B压缩率(%)93.06文本文件1.txt8388646181492.6358.234
1.3 树的组织结构 CTW 算法是一种二进制算法，它把每个字节分解为单独的 8 位，符号的每一位都有自己独立的 上下文树，而且每个二进制符号的上下文包含了所有先前的二进制符号。依据当前位节点的状态从 8 组树中挑选１组，而其所在字节的前几位就在已选出的组中选择一棵树，于是当前面的符号也作 为上下文树时，实际上就一共有 255 个不同的上下文树，其中第１个字节对应 1 棵树，第 2 个字节 对应 2 棵树，第 3 个字节对应 3 棵树，以此类推。如图１所示为某一字节的第 3 位的上下文树。需 要注意的是上下文树的结构并不是二元树，而是上述的 255 位树，其原因在于加权只可能在字节边 界上发生。假设这 255 棵树都是二元树，由于存储空间有限，树的大小也是有限的，则每棵树的最 大深度值是确定的，因此每棵树不仅仅在字节边界上有叶节点，而且在字节内部也存在叶节点，这 就意味着前面的符号中只有一部分可以用来作为当前位的上下文树，如此操作将无法实现高效率的 压缩进程，而且在字节内部进行加权是否有效值得商榷。因此加权只在字节边界发生，对于每个节 点，树将分裂为 256 条不同的路径，使用此加权方法后，树中的节点数量减少了，压缩进程的执行 时间也会缩短，压缩冗余度也相应降低。 2 实验综述 在 VC+ + 6. 0 编程环境下编制改进的 CTW 压缩算法软件, 对文本文件、图像文件和声音文件 及其他类型文件进行压缩。并与常用压缩软件 Winzip 所压制的压缩文件进行压缩率的横向对比。 设置译码器的参数如表 1 所示。 图像 2.bmp 实验过程： File: 1 Compressed filesize: 21132 bytes Uncompressed filesize: 49258 bytes CTW settings used for encoding: Tree depth: 6 Size of tree array: 4194304 nodes (33554432 bytes) Max. number of tries in tree array: 32 File buffer size: 49258 bytes (max. 4194304) Strict pruning: enabled Root weighting: disabled Max. log beta: 1024 Estimator: Zero-Redundancy 表一 CTW 算法参数设置 参数 值 Tree Depth Size of Tree Array 6 33554432B Max. Number of Tries Max. File Buffer Size Strict Pruning Root Weighting Max. Log Beta Estimator 32 4194304B Enabled Disabled 1024 Zero redundancy 表二实验结果比较 文件类型 文件名称 文件大小 Winzip 压缩后大小/B 压缩率(%) CTW 压缩后大小/B 压缩率(%) 文本文件 1. txt 838864 61814 92.63 58.234 93.06
图像文件2.bmp492582528449.962113258.10音频文件3..wav41.3143.733522388206744419822114.htlm4733797402784.366239886.82其他文件由实验结果可以看出，CTW算法平均压缩率要高于Winzip压缩软件5%左右，从而具有较高的工作效率，在需要实时处理的压缩领域有很好的应用前景。进一步完善CTW算法实时对大型文件的压缩将是今后研究的一个方向。3CTW无损压缩算法的应用3.1在管道检测中的应用超声和漏磁无损检测方法是目前输油管道常用的安全检测方法，然而其检测数据庞大，必须对数据进行压缩。CTW的无损压缩算法采用了新的更低穴余度的概率估算法，具有速度快和抗差错能力强等特点，将该算法应用于输油管道超声和漏磁方法无损检测实验数据的无损压缩，得到了较高的压缩率，与LZW无损压缩算法相比获得了更高的压缩率[3-4]。表三CTW算法参数设置6Tree Depth33554432BSize of Tree Array32Max. Number of TriesMax. File Buffer Size4294304BStrict PruningEnabledDisabledRoot Weighting1024Max. Log BetaEstimatorZero redundancy数据压缩前后比较见表4。从表4可知，漏磁数据的压缩率为88.45%，超声数据的压缩率88.95%：CTW算法的压缩率比LZW算法的压缩率提高了10%以上。表四CTW与LZW比较CTWLZW文件大小/Kb压缩后大小/Kb压缩率（%）压缩后大小/Kb压缩率（%）漏磁2402390.425079.17超声222.2281.503.8567.92从实验结果可以看到，与经典的LZW无损压缩算法相比，CTW拥有更高压缩率，这主要由于CTW是一种二进制算法，采用了低穴余度的概率估算法，能够大大提高压缩效率。同时改变CTW的参数设置，能够得到不同的压缩结果，这样在对管道进行在线检测和对检测数据进行实时压缩时，可以根据实际情况合理选择参数，从而能够使CTW无损压缩在管道检测时能够更高效的进行数据的压缩。3.2将CTW算法用于语言的二次压缩语音信号经过自适应增量调制量化后形成的是二进制序列，序列的符号之间有很大的相关性，序列的下一个符号的出现概率往往只依赖于有限数量下最近的符号，即具有高阶马氏链的概率特性。如果用自适应算术编码对此序列进行二次压缩，必然会使得序列高效无失真地压缩。但是，长期以来自适应算术编码这种无失真的高效编码之所以没有广泛应用于语音编码技术，一个重要原因就是信源高阶马氏链的概率难于统计。CTW算法能够有效实时地统计信源的概率，从而为自适应算术编码应用于语音压缩开辟了广阔的前景。图2是将CTW算法应用于语音压缩而提出的编解码的框图
图像文件 音频文件 其他文件 2. bmp 3. .wav 4. htlm 49258 3522388 473379 25284 2067444 74027 49.96 41.31 84.36 21132 1982211 62398 58.10 43.73 86.82 由实验结果可以看出，CTW 算法平均压缩率要高于 Winzip 压缩软件 5% 左右, 从而具有较高 的工作效率,在需要实时处理的压缩领域有很好的应用前景。进一步完善 CTW 算法实时对大型文件 的压缩将是今后研究的一个方向。 3 CTW 无损压缩算法的应用 3.1 在管道检测中的应用 超声和漏磁无损检测方法是目前输油管道常用的安全检测方法，然而其检测数据庞大，必须对 数据进行压缩。CTW 的无损压缩算法采用了新的更低冗余度的概率估算法，具有速度快和抗差错能 力强等特点，将该算法应用于输油管道超声和漏磁方法无损检测实验数据的无损压缩，得到了较高 的压缩率，与 LZW 无损压缩算法相比获得了更高的压缩率[3-4]。 表三 CTW 算法参数设置 Tree Depth 6 Size of Tree Array 33554432B Max. Number of Tries Max. File Buffer Size Strict Pruning Root Weighting Max. Log Beta Estimator 32 4294304B Enabled Disabled 1024 Zero redundancy 数据压缩前后比较见表 4。从表 4 可知，漏磁数据的压缩率为 88.45%，超声数据的压缩率 88.95%； CTW 算法的压缩率比 LZW 算法的压缩率提高了 10%以上。 表四 CTW 与 LZW 比较 文件大小/Kb CTW 压缩后大小/Kb 压缩率（%） LZW 压缩后大小/Kb 压缩率（%） 漏磁 超声 240 22 23 2.22 90.42 81.50 50 3.85 79.17 67.92 从实验结果可以看到，与经典的 LZW 无损压缩算法相比，CTW 拥有更高压缩率，这主要由于 CTW 是一种二进制算法，采用了低冗余度的概率估算法，能够大大提高压缩效率。同时改变 CTW 的 参数设置，能够得到不同的压缩结果，这样在对管道进行在线检测和对检测数据进行实时压缩时， 可以根据实际情况合理选择参数，从而能够使 CTW 无损压缩在管道检测时能够更高效的进行数据 的压缩。 3.2 将 CTW 算法用于语言的二次压缩 语音信号经过自适应增量调制量化后形成的是二进制序列，序列的符号之间有很大的相关性， 序列的下一个符号的出现概率往往只依赖于有限数量下最近的符号，即具有高阶马氏链的概率特性。 如果用 自适应算术编码对此序列进行二次压缩 ，必然会使得序列高效无失真地压缩。但是，长期 以来 自适应算术编码这种无失真的高效编码之所以没有广泛应用于语音编码技术，一个重要原因就 是信源高阶马氏链的概率难于统计。CTW 算法能够有效实时地统计信源的概率，从而为自适应算 术编码应用于语音压缩开辟了广阔的前景。图 2 是将 CTW 算法应用于语音压缩而提出的编解码的 框图
CTW压缩语言连续可变斜率增自适应算术编码后的L信号量调制(AMC)码镜图2-CTW应用语言压缩的编码过程CTW压缩自适应算术编码连续可变斜率增语言后的信号(AMC)量调制码镜图3一CTW应用与语言压缩的解码过程可以发现对于未知概率特性的二进制树形信源，CTW算法是可以构造一种简单可行的自适应算术编码的方案，能够基本解决信源的概率统计问题，并且将其用于高质量的语音二次压缩中，从而为自适应算术编码的在语音中实际应用提供了一种切实可行的思路。4结语本文将一种改进的无损压缩CTW算法为研究对象，该算法较好地改善了通用压缩算法中普遍存在的占用内存较多和压缩比有限等问题。在介绍CTW算法原理后，做了一系列实验，与流行的Winzip压缩和LZW算法压缩，均有很好的优势。目前此算法在其他领域也有应用[5-6]。在无损视频压缩中，CTW算法可以更好估计补偿误差的概率分布配合优化后的运动估计与补偿算法从而进一步提高无损视频压缩算法的性能。CTW算法还可与LZ算法结合，应用在DNA序列数据压缩中，此算法中每个输入的符号都会计算当其使用LZ算法和使用CTW算法时分别的压缩率，然后选用能够提升整体序列压缩比的算法对当前符号进行压缩，从而CTW+LZ算法的压缩率比仅使用LZ算法的BioCompress系列算法和GenCompress算法有一定的提升，但同时压缩时间大幅度增加。总体而言，DNA序列中的长片段倾向于使用CTW算法进行编码，而短序列则更常用LZ算法进行压缩。对于序列中的互补回文和近似序列，CTW+LZ算法使用动态规划的方法配合哈希表进行针对性的压缩编码.除DNA序列数据外，CTW+LZ算法也被应用于蛋白质序列数据的压缩中。参考文献[袁枚，袁文．数据压缩技术及其应用[M]：北京：电子工业出版社，1995.[2】孙文杰，李剑，李洪波，无损压缩CTW算法的改进及性能分析[J]．电子测量技术，2007，30(7)：7-10[3】陈勇强，陈亮，成伟。LZW无损压缩算法在管道漏磁检测中的应用[J]。电子测量技术，2013，30(2)：44-47[4】陈亮，孟庆愿，成伟。CTW无损压缩算法在管道无损检测中的应用[J]。实验技术与管理，2012，29(6)：42-44[5】纪震，周家锐，姜来。DNA序列数据压缩技术综述[J]．电子学报，2010，38(5)：1114-1221[6】夏杰，侯朝焕。一种新型的无损视频压缩算法[J].电子与信息学报，2006，28（3)：386-389
连续可变斜率增 量调制 CTW 自适应算术编码 （AMC） 语言 信号 压缩 后的 码镜 图 2-CTW 应用语言压缩的编码过程 连续可变斜率增 量调制 CTW 自适应算术编码 （AMC） 语言 信号 压缩 后的 码镜 图 3—CTW 应用与语言压缩的解码过程 可以发现对于未知概率特性的二进制树形信源 ，CTW 算法是可以构造一种简单可行的自适应 算术编码的方案，能够基本解决信源的概率统计问题 ，并且将其用于高质量的语音二次压缩中，从 而为 自适应算术编码的在语音中实际应用提供了一种切实可行的思路。 4 结语 本文将一种改进的无损压缩 CTW 算法为研究对象，该算法较好地改善了通用压缩算法中普遍 存在的占用内存较多和压缩比有限等问题。在介绍 CTW 算法原理后，做了一系列实验，与流行的 Winzip 压缩和 LZW 算法压缩，均有很好的优势。 目前此算法在其他领域也有应用[5-6]。在无损视频压缩中，CTW 算法可以更好估计补偿误差的 概率分布配合优化后的运动估计与补偿算法从而进一步提高无损视频压缩算法的性能。CTW 算法还 可与 LZ 算法结合，应用在 DNA 序列数据压缩中，此算法中每个输入的符号都会计算当其使用 LZ 算法和使用 CTW 算法时分别的压缩率，然后选用能够提升整体序列压缩比的算法对当前符号进行 压缩，从而 CTW+LZ 算法的压缩率比仅使用 LZ 算法的 BioCompress 系列算法和 GenCompress 算 法有一定的提升，但同时压缩时间大幅度增加。总体而言，DNA 序列中的长片段倾向于使用 CTW 算法进行编码，而短序列则更常用 LZ 算法进行压缩。对于序列中的互补回文和近似序列，CTW +LZ 算法使用动态规划的方法配合哈希表进行针对性的压缩编码.除 DNA 序列数据外，CTW+LZ 算法也 被应用于蛋白质序列数据的压缩中。 参考文献 [1] 袁枚, 袁文. 数据压缩技术及其应用[M] . 北京: 电子工业出版社, 1995. [2] 孙文杰, 李剑, 李洪波. 无损压缩 CTW 算法的改进及性能分析[J]. 电子测量技术, 2007, 30(7): 7-10 [3] 陈勇强,陈亮,成伟. LZW 无损压缩算法在管道漏磁检测中的应用[J]. 电子测量技术, 2013, 30(2): 44-47 [4] 陈亮, 孟庆愿,成伟. CTW 无损压缩算法在管道无损检测中的应用[J]. 实验技术与管理, 2012, 29(6): 42-44 [5] 纪震,周家锐,姜来. DNA 序列数据压缩技术综述[J]. 电子学报, 2010, 38(5): 1114-1221 [6] 夏杰，侯朝焕.一种新型的无损视频压缩算法[J].电子与信息学报, 2006, 28(3):386-389