模糊树自动机的构造及最小化算法的研究

摘要

如今，随着人们经济条件的提高和科学技术水平的发展，Web信息也越来越庞大和复杂。如何从网页的海量信息中抽取出用户所需要的信息，成为研究的热点之一。而网页信息数据间的语义交叉和语义模糊，使得传统的信息抽取技术不能满足用户的需要。为了解决这一问题，本论文研究了如何使用模糊树自动机技术来实现 Web信息抽取，并提出了模糊树自动机的构造方法、树自动机和模糊树自动机的最小化算法。
　　本论文主要工作及采用的主要技术如下：
　　（1）构造无秩树自动机模型。依据网站中网页信息的树状结构，将页面中的HTML/XML通过DOM解析器，生成无秩DOM树集，为了解决无秩树节点数目不确定性，本文依据DOM树集构造(k,l)contextual树，得到可控制高度和宽度的树，利用双向转移函数，构造无秩树自动机。
　　（2）采用Rough集技术处理信息模糊性及构造模糊树自动机模型。依据Rough集理论构造符合处理网页信息模糊性的容错关系模型，再结合容错关系模型与Rough集理论中的上近似关系，实现了“核信息”词语的扩展，较好地解决了信息间的模糊性，增加抽取信息的准确性；并在此基础上提出了构造模糊树自动机的过程，通过实验，验证了该模糊树自动机模型在抽取信息中的有效性。
　　（3）树自动机及模糊树自动机的最小化。树自动机最小化的难点在于对树状态进行分类时，可能产生新的字符串状态分类。本文提出了通过定义三个操作符，追踪标记树状态和字符串状态的方式来解决这个难点；利用状态集的模糊等价，构造模糊等价类；利用互模拟技术的前向互模拟，得到最大前向互模拟，由此构造出最小的模糊树自动机，提出了模糊树自动机的前向互模拟算法；通过实例验证，该算法可以得到比原模糊树自动机状态少的等价模糊树自动机。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1 .1 问题的提出

1 .2 研究的意义

1 .3 国内外研究现状

1 .4 课题主要研究内容

1 .5 本文创新点

1 .6 各章节安排

第二章 自动机相关技术

2 .1 字符串自动机

2 .2 树自动机

2 .3 树自动机状态转移的表示

2 .4 树自动机的一般构造算法

2 .5 本章小结

第三章 Rough集相关技术

3 .1 Rough集基本概念

3 .2 Rough集关系

3 .3 Rough集理论

3 .4 本章小结

第四章 模糊树自动机模型构造

4 .1 标记文档结构树

4 .2 Rough集处理信息标记节点中信息的不确定性

4 .3 模糊树自动机构造过程

4 .4 实验

4 .5 本章小结

第五章 模糊树自动机最小化

5 .1 最小化树自动机的存在性

5 .2 树自动机最小化

5 .3 模糊树自动机最小化

5 .4 本章小结

第六章 总结

6 .1 主要工作回顾

6 .2 本课题今后需进一步研究的地方

参考文献

个人简历在读期间发表的学术论文

致谢