模糊树自动机的构造及最小化算法的分析分析.docx

华
东
交
通
大
学
届硕士学位论文
模
糊
树
自
动
机
的
构造
及最小化算法的研究
软
件
学
院
孙
丹
丹
2014
书脊
独创性声明
本人郑重声明:所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表和撰写的研究成果,也不包含为获得华东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。
本人签名___ 日期
关于论文使用授权的说明
本人完全了解华东交通大学有关保留、使用学位论文的规定,即:学校有权保留送交论文的复印件,允许论文被查阅和借阅。学校可以公布论文的全部或部分内容,可以采用影印、缩印或其他复制手段保存论文。
保密的论文在解密后遵守此规定,无保密内容。
本人签名___ 导师签名_ _日期_ _
模糊树自动机的构造及最小化算法的研究
摘要
如今,随着人们经济条件的提高和科学技术水平的发展,Web 信息也越来越庞大和复杂。如何从网页的海量信息中抽取出用户所需要的信息,成为研究的热点之一。而网页信息数据间的语义交叉和语义模糊,使得传统的信息抽取技术不能满足用户的需要。为了解决这一问题,本论文研究了如何使用模糊树自动机技术来实现 Web 信息抽取, 并提出了模糊树自动机的构造方法、树自动机和模糊树自动机的最小化算法。
本论文主要工作及采用的主要技术如下:
(1)构造无秩树自动机模型。依据网站中网页信息的树状结构, 将页面中的 HTML/XML 通过 DOM 解析器,生成无秩 DOM 树集,为了解决无秩树节点数目不确定性,本文依据 DOM 树集构造(k,l) - contextual 树,得到可控制高度和宽度的树,利用双向转移函数,构造无秩树自动机。
(2)采用 Rough 集技术处理信息模糊性及构造模糊树自动机模型。依据 Rough 集理论构造符合处理网页信息模糊性的容错关系模型,再结合容错关系模型与 Rough 集理论中的上近似关系,实现了“核信息”词语的扩展,较好地解决了信息间的模糊性,增加抽取信息的准确性;并在此基础上提出了构造模糊树自动机的过程,通过实验,验证了该模糊树自动机模型在抽取信息中的有效性。
(3)树自动机及模糊树自动机的最小化。树自动机最小化的难点在于对树状态进行分类时,可能产生新的字符串状态分类。本文提出了通过定义三个操作符,追踪标记树状态和字符串状态的方式来解决这个难点;利用状态集的模糊等价,构造模糊等价类; 利用互模拟技术的前向互模拟,得到最大前向互模拟,由此构造出最小的模糊树自动机, 提出了模糊树自动机的前向互模拟算法;通过实例验证,该算法可以得到比原模糊树自动机状态少的等价模糊树自动机。
关键词:树自动机,模糊树自动机,自动机最小化,Rough 集,信息抽取
I
RESEARCH ON CONSTRUCTION AND MINIMIZATION ALGORITHM OF FUZZY TREE AUTOMATA
ABSTRACT
Now, as people's economic condition is improving and the development of science and technology, Web information is also more and more large plex. How to extract the required information from massive information in Web page, e one of the research hotspots. However, Webpage information data exist semantic overlapping and semantic fuzziness, which makes the traditional information extraction technology can not meet the needs of users. In order to solve this problem, this paper studies how to construct fuzzy tree automata for Web information extraction, and propose a constructor of fuzzy tree automata and minimization algorithm of tree and fuzzy tree automata.