《武汉工程大学学报》 2015年04期
51-55
出版日期：2015-04-30
ISSN:1674-2869
CN:42-1779/TQ
压缩编码的上下文树构造算法
０ 引 言信息处理技术的飞速发展使得算法应用越来越为广泛，在图像处理［１］，路径搜索优化［２-３］以及工程应用等领域，数学形态学越来越重要. 作为其中的一种重要的数据结构，上下文树是信息处理过程中分析随机序列统计特性的常用工具. 利用上下文树获取序列中字符串［４-５］的频率分布，可以构造高效的数据压缩算法［６-７］，通过上下文树分析文本或生物ＤＮＡ序列中符号的相关性，可以准确实现文档或ＤＮＡ序列的自动分段［８-９］. 同时，上下文树也是研究可变长Ｍａｒｋｏｖ链的主要数学工具，用于随机序列发生器设计［１０-１１］. 随机序列中的符号来自于某个固定的符号集合，比如英文文档包括２６个字母，ＤＮＡ序列由Ａ、Ｃ、Ｇ、Ｔ组成，它们分别代表组成ＤＮＡ的四种核苷酸一腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶．因此上下文树一般是一棵ｎ元树，其中ｎ大于１. 树是一种占用计算机内存较多的数据结构，系统内存容量会直接影响树的高度，而树高决定了分析过程中序列子字符串的长度，会直接影响符号串统计特性的精度. 本文提出了基于压缩编码的上下文树构造算法，根据符号的一阶统计特性对符号做二进制的压缩编码，用二元树代替ｎ（ｎ＞２）元树，在相同内存的存储空间下，可以大大增加树的高度，对子串做更大长度的相关性检测，提高分析的精度. １ 上下文树设Ａ＝｛ａ１，ａ２，…，ａｎ｝是一个符号集合，随机序列ｘ＝ｘ－Ｎ ｘ－Ｎ＋１…ｘ－１ｘ０ｘ１…ｘＭｘｉ∈Ａ，ｉ∈Ｉ从序列ｘ中任取一点，比如ｘ０，向左回溯，找到ｘ＝ｘ－ｊｘ－ｊ＋１…ｘ－１ｘ０，其中０≤Ｊ≤Ｎ，使得条件概率为 P(x|x-J x-J+1…x-1x0)=P(x|x-J-1x-Jx-J+1…x-1x0)（１）成立，设ｘ＝ｘ－ｊ ｘ－ｊ＋１…ｘ－１ｘ０ 为 ｘ１的上下文环境. ｘ１的上下文环境说明了影响符号ｘ１的出现的历史追溯到ｘ－Ｊ即可，不必再回溯到ｘ－Ｊ－１以及更早的符号. 要验证式（１）中的ｎ个等式，需要根据序列ｘ统计出字符串ｘ－ｊ－１ｘ－ｊ…ｘ－１ｘ０ｘ和ｘ－ｊ ｘ－ｊ＋１…ｘ－１ｘ０ｘ出现的频数. 统计频数的工作由如下的上下文树算法完成. 算法１：上下文树构造算法：（１）初始化根节点，符号计数设置为０.（２）假设根据字符串ｘｔ＝ｘ１ｘ２…ｘｔ构造出树Ｔｔ，当前输入符号为ｘｔ＋１，从根节点出发，按照字符串ｘｔｘｔ－１…的指引，访问Ｔｔ的结点，直到ｘｔ的符号用完，或者到了叶子结点. 对每个访问到的结点，将该结点处的符号ｘｔ＋１的计数增加１.（３）如果最后一次访问到的结点ｘｔ＋１处的计数≥２，创建一个新结点ｘｔ…ｘｔ－ｊ＋１ ｘｔ－ｊ，新结点ｘｔ＋１处的计数置为１，其他符号的计数置为０，得到树Ｔｔ＋１.从上下文树构造算法可知，树Ｔｔ是一棵ｎ元树，其高度随着从左到右扫描序列的时刻ｔ增加而增加. ｎ元树结点个数有如下性质：命题１：高度为ｈ的ｎ元满树第ｌ层结点数为ｎｌ个，全部节点数为■个. 命题２：高度为ｈ的ｎ元满树的长度为ｌ（ｌ≤ｈ）的字符串个数为ｎｌ个. ２ 基于压缩编码的上下文树算法由于随机序列中符号出现的概率是非均匀分布的，利用熵压缩编码的原理可以对符号进行二进制变长压缩编码，二进制符号作为码元符号，随机序列中的自然语言符号可编码为变长的二进制串. 本文在构建上下文树的时候，树的结点不是自然语言符号，而是仅含０，１的二元树，每个自然语言符号都对应着二元树上的一段路径. 算法２：基于压缩编码的上下文树算法.（１）统计随机序列的符号的频率，构造Ｈｕｆｆｍａｎ 编码，形成码表，用Ｂ（ｘｉ）表示自然语言符号ｘ对应的二进制串.（２）初始化根结点，符号计数置为０，令ｔ时刻自然语言符号序列为ｘｔ＝ｘ１ｘ２…ｘｔ.（３）假设根据字符串ｘｔ＝ｘ１ｘ２…ｘｔ构造出树Ｔｔ，当前输入为ｘｔ＋１，从根结点出发，按照字符ｘｔｘｔ－１…的指引，访问Ｔｔ的结点，直到ｘｔ的符号用完，或者到了叶子结点，比如Ｂ（ｘｔ）…Ｂ（ｘｔ－ｊ＋１）. 对每个访问到的结点，将该结点处符号ｘｔ＋１的计数增加１.（４）如果最后一次访问到的结点ｘｔ＋１处的计数≥２，创建一个新结点Ｂ（ｘｔ）…Ｂ（ｘｔ－ｊ＋１）Ｂ（ｘｔ－ｊ），新结点处ｘｔ＋１的计数置为１，其他符号的计数置为０，得到树Ｔｔ＋１. 基于压缩编码的上下文树算法与上下文树算法不同点在于，将ｎ元树化为二元树，ｎ元树中的每个结点在二元树中扩展为一条路径. 该路径对应着自然语言符号的Ｈｕｆｆｍａｎ编码. 下面的结论表明，将ｎ元树化为二元树，在表达相同数量的自然语言字符串情况下占用的内存却大大减少了. 命题３：设ｎ元树的每个节点指针域占用字节数为ｄ，数据域占用字节数为ｍ，对ｎ个符号采用二进制编码，平均码长为ｌ０．则高度为ｈ的ｎ元满树所占用字节总数 （nd+m）■＞（2d+m）（2hl+1-1）（２）证明：由熵编码原理可知平均码长ｌ０≤ｌｏｇ■■，因此ｎｈ≥２■，下面证明 （nd+m）■＞（2d+m）（2hl+1-1）即（ｎｄ＋ｍ）（ｎｈ＋１－１）＞（ｎ－１）（２ｄ＋ｍ）（２ｎｈ－１）ｄｎｈ＋２＋ｍｎｈ＋１－ｎｄ－ｍ＞（２ｄ＋ｍ）（２ｎｈ＋１－２ｎｈ－ｎ＋１）展开移项得到：ｄｎｈ＋２＋（m-4d-2m）ｎｈ＋１+(4d+2m)ｎｈ-nd-m+4dn+mn-2d-m＞0ｄｎｈ＋２＋（-4d-m）ｎｈ＋１+(4d+2m)ｎｈ+（m+d）（n-2）＞0由于（ｍ＋ｄ）（ｎ－２）≥０令ｄｎｈ＋２－（４ｄ＋ｍ）ｎｈ＋１＋（４ｄ＋２ｍ）ｎｈ≥０ （３）除以ｎｈ得到： ｄｎ２－（４ｄ＋ｍ）ｎ＋（４ｄ＋２ｍ）≥０（４） Δ＝（４ｄ＋ｍ）２－４ｄ（４ｄ＋２ｍ）＝ｍ２＞０故关于ｎ的不等式（４）有解 ｎ≤2或ｎ≥２＋■也即ｎ≥２时结论成立.表1 ３个长度为62的字符串1-62阶条件概率计算结果范例Table 1 Computational results of 3 stings’ conditional probability ３ 实验结果利用基于压缩编码的上下文树构造算法对英文长篇小说《Ｆｏｒｒｅｓｔ Ｇｒａｍｐ》（Ｗｉｎｓｔｏｎ Ｇｒｏｏｍ， １９８６）开展了统计工作，程序运行环境为３２位微软ＸＰ ｓｅｒｖｉｃｅ ｐａｃｋ３ 操作系统，Ｐｅｎｔｉｕｍ Ｄｕａｌ－Ｃｏｒｅ Ｅ６７００ ＣＰＵ，主频３．２０ ＧＨｚ，内存２ ＧＢyte分析字符串长度达到６２个自然语言符号时，运行时间约３４分钟，统计出共２８１ ７０５条长度为６２的字符串，每个字符串分别计算出从１阶到６２阶条件概率以供后续分析使用. 表１给出了其中的３个计算结果.从数据统计分析可以看出，符号的一阶统计特性可以在数值实验中得到，对文本信息的符号做二进制的压缩编码，在结构处理上采用二元树代替（＞２）元树，在相同内存的存储空间下，理论上证明可以增加树的高度，实验也进一步验证结论. 基于此，可以对长度更大的子串进行相关性检测，并且提高分析的精度.