|本期目录/Table of Contents|

[1]付　敏１,２,戴祖旭,等.压缩编码的上下文树构造算法[J].武汉工程大学学报,2015,37(04):51-55.[doi:10. 3969/j. issn. 1674-2869. 2015. 0４. 012]
　,,et al.Ｃｏｎｔｅｘｔ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｍｐｒｅｓｓｉｏｎ ｅｎｃｏｄｉｎｇ[J].Journal of Wuhan Institute of Technology,2015,37(04):51-55.[doi:10. 3969/j. issn. 1674-2869. 2015. 0４. 012]
点击复制

压缩编码的上下文树构造算法(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
37
期数:
2015年04期
页码:
51-55
栏目:
机电与信息工程
出版日期:
2015-04-30

文章信息/Info

Title:
Ｃｏｎｔｅｘｔ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｍｐｒｅｓｓｉｏｎ ｅｎｃｏｄｉｎｇ
文章编号:
1674-2869(2015).0４--0056-03
作者:
付　敏１; ２; 戴祖旭1; 王道蓬２
１武汉工程大学理学院，湖北 武汉 ４３０５０２；２华中科技大学图像识别与人工智能研究所多谱图像信息处理国防重点实验室，湖北 武汉 ４３００７４
Author(s):
ＦＵ Ｍｉｎ１; ２;  ＤＡＩ Ｚｕ－ｘｕ1;  ＷＡＮＧ Ｄａｏ－ｐｅｎｇ２
1．Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ， Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ ４３０５０２， Ｃｈｉｎａ; 2．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｍｕｌｔｉ－ｓｐｅｃｔｒａｌ Ｉｍａｇｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｎａｔｉｏｎａｌ Ｄｅｆｅｎｓｅ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ
关键词:
上下文树; ｎ元树; 压缩编码
Keywords:
ｃｏｎｔｅｘｔ ｔｒｅｅ; ｎ＿ｇｒａｍ ｔｒｅｅ;  ｃｏｍｐｒｅｓｓｉｏｎ ｅｎｃｏｄｉｎｇ
分类号:
ＴＰ３０９.７
DOI:
10. 3969/j. issn. 1674-2869. 2015. 0４. 012
文献标志码:
A
摘要:
上下文树是构造无算压缩算法的一种重要基础，作为信息处理过程分析随机序列统计特性的常用数据结构，随机序列中的符号来自于某个固定的符号集合. 上下文树一般是一棵ｎ元树，其中ｎ大于１，但是树是一种占用计算机内存较多的数据结构，因此提出了基于压缩编码的上下文树构造算法，根据符号的一阶统计特性对符号做二进制的压缩编码，用二元树代替ｎ（ｎ＞２）元树，在相同内存的存储空间下，可以大大增加树的高度. 计算机数值实验表明基于压缩编码的上下树构造对子串做出了更大长度的相关性检测，并且提高了数据分析的精度.
Abstract:
Ｔｈｅ ｃｏｎｔｅｘｔ ｔｒｅｅ ａｓ ａ ｃｏｍｍｏｎｌｙ ｕｓｅｄ ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｐｌａｙｓ ａ ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｒｏｌｅ ｉｎ ａｎａｌｙｚｉｎｇ ｓｔａｔｉｓｔｉｃａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ， ａｎｄ ｔｈｅ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｏｆ ｓｙｍｂｏｌｓ ｇｅｎｅｒａｌｌｙ ｃｏｍｅｓ ｆｒｏｍ ａ ｆｉｘｅｄ ｓｙｍｂｏｌ ｓｅｔ． Ｔｈｅ ｇｅｎｅｒａｌ ｃｏｎｔｅｘｔ ｔｒｅｅ ｉｓ ａ ｎ－ｔｒｅｅ， ｉｎ ｗｈｉｃｈ ｎ ｉｓ ｍｏｒｅ ｔｈａｎ １． Ｂｅｃａｕｓｅ ｔｈｅ ｔｒｅｅ ｉｓ ａ ｋｉｎｄ ｏｆ ｃｏｍｐｕｔｅｒ ｍｅｍｏｒｙ ｗａｓｔｉｎｇ ｄａｔａ ｓｔｒｕｃｔｕｒｅ， ａ ｃｏｎｔｅｘｔ ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｍｐｒｅｓｓ ｃｏｄｉｎｇ ｗａｓ ｐｒｅｓｅｎｔｅｄ ｕｔｉｌｉｚｉｎｇ ｔｈｅ ｆｉｒｓｔ－ｏｒｄｅｒ ｓｔａｔｉｓｔｉｃａｌ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｂｉｎａｒｙ ｓｙｍｂｏｌｓ． Ｉｎ ｔｈｅ ｎｕｍｅｒｉｃａｌ ｅｘｐｅｒｉｍｅｎｔ ｕｎｄｅｒ ｔｈｅ ｓａｍｅ ｍｅｍｏｒｙ ｓｔｏｒａｇｅ ｓｐａｃｅ ｃｏｎｄｉｔｉｏｎ， ｔｈｅ ｔｒｅｅ’ｓ ｈｅｉｇｈｔ ｈａｓ ｂｅｅｎ ｇｒｅａｔｌｙ ｉｎｃｒｅａｓｅｄ， ａｎｄ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｄａｔａ ａｎａｌｙｓｉｓ ａｌｓｏ ｉｍｐｒｏｖｅｄ．

参考文献/References:

［１］　洪汉玉，章秀华，程莉．道路病害形态特征的图像分析［Ｊ］．武汉工程大学学报，２０１４，３６（４）：７０－７６．ＨＯＮＧ Ｈａｎ－ｙｕ，ＺＨＡＮＧ Ｘｉｕ－ｈｕａ，ＣＨＥＮＧ Ｌｉ． Ｉｍａｇｅ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ ｆｏｒ ｒｏａｄ ｄｉｓｅａｓｅ ｍｏｒｐｈｏｌｏｇｙ ｃｈａｒａｃｔｅｒｉｓｔｉｃ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ２０１４，３６（４）：７０－７６．（ｉｎ Ｃｈｉｎｅｓｅ）［２］　孙玉昕， 章瑾．利用堆排序优化路径搜索效率的分析［Ｊ］．武汉工程大学学报，２０１３，３５（１０）：５０－５５． ＳＵＮ Ｙｕ－ｘｉｎ， ＺＨＡＮＧ Ｊｉｎ．Ｐｒａｃｔｉｃａｌ ａｎａｌｙｓｉｓ ｏｆ ｉｍｐｒｏｖｉｎｇ ｐａｔｈ ｓｅａｒｃｈｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｂｙ ｈｅａｐ ｓｏｒｔ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ２０１３，３５（１０）：５０－５５．（ｉｎ Ｃｈｉｎｅｓｅ）［３］　王学华，刘莉君，马凡杰，等．数控激光加工路径链表快速搜索优化［Ｊ］．武汉工程大学学报 ，２０１４，３６（１０）：５２－５７．ＷＡＮＧ Ｘｕｅ－ｈｕａ，ＬＩＵ Ｌｉ－ｊｕｎ，ＭＡ Ｆａｎ－ｊｉｅ ｅｔ ａｌ． Ｒａｐｉｄ ｒｏｕｔｉｎｅ ｓｅａｒｃｈｉｎｇ ｏｆ ｎｕｍｅｒｉｃａｌ ｃｏｎｔｒｏｌ ｌａｓｅｒ ｐｒｏｃｅｓｓｉｎｇ ｂａｓｅｄ ｏｎ ｌｉｎｋｅｄ ｌｉｓｔ ｓｔｒｕｃｔｕｒｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２０１４，３６（１０）：５２－５７．（ｉｎ Ｃｈｉｎｅｓｅ）［４］　徐超，周一民，沈磊．一种面向隐含主题的上下文树核［Ｊ］．电子与信息学报，２０１０， ３２（１１）：２６９５－２700．ＸＵ Ｃｈａｏ，ＺＨＯＵ Ｙｉ－ｍｉｎ， ＳＨＥＮ Ｌｅｉ．Ａ ｃｏｎｔｅｘｔ ｔｒｅｅ ｋｅｒｎｅｌ ｂａｓｅｄ ｏｎ ｌａｔｅｎｔ ｓｅｍａｎｔｉｃ ｔｏｐｉｃ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ＆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，２０１０，３２（１１）：２６９５－２６０６．（ｉｎ Ｃｈｉｎｅｓｅ）［５］　ＲＩＳＳＡＮＥＮ Ｊ． Ａ ｕｎｉｖｅｒｓａｌ ｄａｔａ ｃｏｍｐｒｅｓｓｉｏｎ ｓｙｓｔｅｍ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｙ， １９８３， ２９（５）： ６５６－６６４．［６］　陈亮，孟庆愿， 董彦磊，等．ＣＴＷ无损压缩算法在管道无损检测中的应用［Ｊ］．实验技术与管理， ２０１２，２９（６）：４２－４７．ＣＨＥＮ Ｌｉａｎｇ，ＭＥＮＧ Ｑｉｎｇｙｕａｎ，ＤＯＮＧ Ｙａｎｌｅｉ，ｅｔ ａｌ．Ｕｓｉｎｇ ＣＴＷ ｌｏｓｓｌｅｓｓ ｃｏｍｐｒｅｓｓｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｐｉｐｅｌｉｎｅｓ ｎｏｎｄｅｓｔｒｕｃｔｉｖｅ ｔｅｓｔｉｎｇ［Ｊ］． Ｅｘｐｅｒｉｍｅｎｔａｌ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｍａｎａｇｅｍｅｎｔ，２０１２，２９（６）：４２－４７．（ｉｎ Ｃｈｉｎｅｓｅ）［７］　ＤＵＭＯＮＴ Ｔｈｉｅｒｒｙ．Ｃｏｎｔｅｘｔ ｔｒｅｅ ｅｓｔｉｍａｔｉｏｎ ｉｎ ｖａｒｉａｂｌｅ ｌｅｎｇｔｈ ｈｉｄｄｅｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｙ， ２０１４， ６０（６）： ３１９６－３２０８．［８］　ＧＷＡＤＥＲＡ Ｒ， ＧＩＯＮＩＳ Ａ， ＭＡＮＮＩＬＡ Ｈ． Ｏｐｔｉｍａｌ ｓｅｇｍｅｎｔａｔｉｏｎ ｕｓｉｎｇ ｔｒｅｅ ｍｏｄｅｌｓ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２００８， １５（３）： ２５９－２８３．［９］　Ｍａｒｔｉｎｓ Ｄ Ａ， Ｎｅｖｅｓ Ａ Ｊ Ｒ， Ｐｉｎｈｏ Ａ Ｊ． Ｖａｒｉａｂｌｅ Ｏｒｄｅｒ Ｆｉｎｉｔｅ－Ｃｏｎｔｅｘｔ Ｍｏｄｅｌｓ ｉｎ ＤＮＡ Ｓｅｑｕｅｎｃｅ Ｃｏｄｉｎｇ［C］//Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ Ｉｍａｇｅ Ａｎａｌｙｓｉｓ． Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ， ２００９： ４５７－４６４．［１０］　Ｂ?譈ＨＬＭＡＮＮ Ｐ． Ｍｏｄｅｌ ｓｅｌｅｃｔｉｏｎ ｆｏｒ ｖａｒｉａｂｌｅ ｌｅｎｇｔｈ Ｍａｒｋｏｖ ｃｈａｉｎｓ ａｎｄ ｔｕｎｉｎｇ ｔｈｅ ｃｏｎｔｅｘｔ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ａｎｎａｌｓ ｏｆ ｔｈｅ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｔｉｓｔｉｃａｌ Ｍａｔｈｅｍａｔｉｃｓ， ２０００， ５２（２）： ２８７－３１５．［１１］　Ｃ?魪ＮＡＣ Ｐ， ＣＨＡＵＶＩＮ Ｂ， ＰＡＣＣＡＵＴ Ｆ， ｅｔ ａｌ． Ｃｏｎｔｅｘｔ ｔｒｅｅｓ， ｖａｒｉａｂｌｅ ｌｅｎｇｔｈ Ｍａｒｋｏｖ ｃｈａｉｎｓ ａｎｄ ｄｙｎａｍｉｃａｌ ｓｏｕｒｃｅｓ［C］//Ｓéｍｉｎａｉｒｅ ｄｅ Ｐｒｏｂａｂｉｌｉｔéｓ ＸＬＩＶ． Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ， ２０１２： １－３９．

相似文献/References:

备注/Memo

备注/Memo:
收稿日期:2015-01-12基金项目:湖北省自然科学基金重点项目(2010CDA009),湖北省自然科学基金一般项目(2009CDB367),国家自然科学基金面上项目(61175013),武汉工程大学校级教研项目(X2013021).作者简介:付敏(1979-),女,湖北襄阳人,讲师,博士研究生.研究方向:信息处理袁计算机视觉.
更新日期/Last Update: 2015-05-25