双排序互关联后继树模型的若干应用研究

论文摘要

随着互联网的飞速发展,信息量的指数增长,人们很难在海量的信息中快速找到符合自己需求的信息。全文数据库的出现,大大改善了这一现状。目前比较常见和流行的全文检索模型有以下几种模型:署名文件(Signature Files)、位图(Bit Map)、倒排表(Inverted List)、∑~2矩阵Pat树和Pat数组等等,它们均有各自的局限性。互关联后继树模型是从中文语言特点出发提出的一种新颖的全文检索模型,它具有创建速度快,查询速度快,空间效率高等特点,并且可以通过索引生成原文。从提出至今,在复旦大学老师和几届学生的努力下,互关联后继树模型已经有了很大的发展。从最初的基本模型,到三元模型,再到后继有序模型,其创建、查询效率都已经有了不小的提高。作为一个优秀的全文检索模型,它被广泛应用于频繁项集挖掘、关联规则挖掘、文本过滤、概念格、时间序列特征模式挖掘等领域。互关联后继树模型的最新研究成果是双排序互关联后继树,具有高效的创建和查询算法。本文正是以双排序互关联后继树为基础,进一步研究其在最长公共子串查找和频繁项集挖掘等领域的应用。本文研究内容和创新工作主要包括以下两个方面:1)基于双排序互关联后继树的最长公共子串查找。目前常见的最长公共子串查找方法有:基于动态规划的LCS查找算法、基于广义后缀树的LCS查找算法和基于广义后缀数组的LCS查找算法。本文基于双排序互关联后继树,利用其优良特性,提出了一种全新的LCS查找算法,进一步扩展了互关联后继树模型的应用领域。相比于基于广义后缀树的LCS查找算法,该算法具有创建速度快,空间效率高,查询效率高等特点。2)基于双排序互关联后继树的频繁项集挖掘。互关联后继树模型应用于频繁项集挖掘的研究早已开始。本文在双排序互关联后继树的基础上,结合原文,提出了一种新的基于全文和双排序互关联后继树的获取直接项集算法,然后根据直接项集发现间接项集,合并后根据最小支持度得到频繁项集。随后改进了获取间接项集算法,是双排序IRST在频繁项集挖掘中的一种尝试。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 论文的组织
• 第二章 双排序互关联后继树模型研究
• 2.1 双排序互关联后继树模型简介
• 2.1.1 互关联后继树模型
• 2.1.2 双排序互关联后继树模型
• 2.2 双排序互关联后继树的创建算法
• 2.3 双排序互关联后继树后继区间二分搜索算法
• 2.3.1 正向和逆向搜索算法
• 2.3.2 时间复杂度比较
• 第三章 最长公共子串研究
• 3.1 引言
• 3.2 基于动态规划的LCS查找算法
• 3.3 基于后缀链的广义后缀树的LCS查找算法
• 3.3.1 广义后缀树及基于后缀链的Ukkonen算法
• 3.3.2 基于后缀链广义后缀树的最长公共子串查找算法
• 3.4 基于广义后缀数组的LCS查找算法
• 3.4.1 广义后缀数组
• 3.4.4 计算所有最长公共子串
• 3.5 基于双排序互关联后继树的LCS查找算法
• 3.5.1 创建双排序IRST树
• 3.5.2 LCS查找算法
• 3.5.3 实验
• 第四章 频繁项集挖掘的研究
• 4.1 引言
• 4.2 典型频繁项集挖掘算法
• 4.2.1 关联规则基本概念
• 4.2.2 频繁项集挖掘算法分类
• 4.3 基于双排序IRST和全文的频繁项集挖掘算法
• 4.3.1 创建双排序IRST树
• 4.3.2 频繁项集挖掘算法
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 硕士学位期间参与的科研项目及主要成果
• 致谢