学位论文 > 优秀研究生学位论文题录展示

基于后缀数组聚类的元搜索引擎的设计与实现

作　者: 胡国东
导　师: 左万利
学　校: 吉林大学
专　业: 计算机软件与理论
关键词: 后缀数组聚类元搜索引擎
分类号: TP391.3
类　型: 硕士论文
年　份: 2010年
下　载: 94次
引　用: 1次
阅　读: 论文下载

内容摘要

随着信息技术的发展,特别是Internet应用的普及,人们已经从信息匮乏的时代过渡到了信息极为丰富的时代。因而搜索引擎诞生了,传统的搜索引擎根据用户输入关键字,为用户提供检索结果。但目前的搜索引擎产生的搜索结果过于庞大和杂乱,用户难以从大量的结果集中快速找到自己感兴趣的信息。由于各个搜索引擎的数据库、检索技术各不相同,返回的结果也不同,用户往往通过浏览不同的搜索引擎排在最前面的几条结果来寻找信息。所以便产生了元搜索引擎,来综合多个独立搜索引擎的结果,返回给用户。由于搜索引擎返回的结果文档较多,一种聪明的作法是对这些文档进行分类,这样就能更方便用户查找和浏览相关信息。利用文档聚类算法将搜索结果自动聚类,形成了一个类似文件夹的层次结构是一种好的方法。现在出现了越来越多的采用聚类技术的元搜索引擎。比如已经付诸商业的Vivisimo,开源的Carrot2聚类引擎等都表现出了良好的效果。更多的元搜索引擎不断的涌现出来,聚类引擎技术快速发展。但目前的聚类引擎在聚类标签的准确性,多语言的支持(比如中文)等方面存在很多的问题,仍有待于进一步研究。本文设计的基于后缀数组聚类(Suffix Tree Clustering,后面简称SAC)的元搜索引擎系统,成功的将后缀数组技术应用到了聚类引擎当中。后缀树和后缀数组都是字符串处理中非常优秀的数据结构,后缀数组占用的空间比后缀树要小,后缀树在某些情况下相对后缀数组有速度上的优势,但是并不明显。而在我们设计的后缀数组聚类引擎系统中,通过利用较少的空间开销建立了两张映射表,使得筛选簇的过程节省了很大的时间开销。因此我们设计的基于后缀数组聚类引擎系统较基于后缀树的聚类引擎系统的在速度上并没有弱势。本文实现的基于SAC元搜索引擎系统中,首先对所有文档进行了分词和去停用词,然后构建后缀数组。对于已经构造好的后缀数组而言,如何筛选并形成聚类结果簇集的才是最为重要的问题。在簇的筛选时,我们将它分为了两个步骤:基本筛选,基于Grouper规则过滤。在基本筛选时,我们引入了一个限制阈值,用它来初步的筛选出符合条件的标签并形成初始簇集。然后对于这个初始的簇集再进行Grouper规则的过滤,进而得到最终的结果簇集。这时处理还没有结束,我们对于最终的结果簇集,引入了标签的语义处理,即对有同义关系标签的簇进行合并。最后,我们将这些经过层层处理而得到的结果返回给用户。另外,我们也采用了交互聚类的设计思想,我们将聚类的结果返回给用户以后,当用户对某一个类别感兴趣时,用户可点击这个类别标签,我们就会对属于这个标签类别的所有文档进行再次聚类,并将二次聚类得到的结果放在这个标签的下一级,作为这个类的下属子类。通过这样的交互聚类设计,可以仅对用户感兴趣的文档进行二次聚类,极大的缩小了聚类文档的规模,可以有效的提高系统的效率。通过统计的一些实验数据表明,基于SAC元搜索引擎可以快速高效的完成聚类。但是分类的合理性,类标签的可读性等仍有待于进一步的提高。下面是一些基于SAC元搜索引擎需要改进的方向:1.目前的SAC元搜索引擎虽然已经引入了语义,但仅仅是合并了同义标签簇。一个方向是引入基于语义的层次化结果簇集,为用户提供了更好的结果,更好的分类形式,层次更加清晰,方便用户快速定位到感兴趣信息。另外则是如何进一步利用上下位、反义等重要语义关系进一步改善聚类结果,都有待于继续深入研究。2.引入中文词典,加入对中文语义的处理。现在仅通过引入Wordnet可以对英文的同义标签进行合并处理,因此引入中文词典,加入对中文语义的处理,合并中文同义标签,也是需要考虑的。3.引入领域词典,不论是分词阶段,还是最后的成簇及筛选阶段。一个领域词典对于专业领域文档的聚类是有莫大帮助的。4.考虑通过引入权值方式,对来自多个成员引擎的文档在结果集中的排序。目前只能选择一个成员引擎(Google或Yahoo),还不支持将两个搜索引擎的结果综合处理。5.提供更个性化的服务,比如可以在用户接口界面增加一些选项如成员引擎的选择、文档的数目、聚成类别的数目等等,由用户来设置这些选项。伴随着传统搜索引擎技术的逐渐趋于成熟,为元搜索引擎的发展提供了更加强大的支持。所以相信未来基于聚类算法的元搜索引擎将会受到越来越多的关注,会有更大的发展。

全文目录

摘要  4-6
Abstract  6-10
第1章绪论  10-14
  1.1 研究背景  10-11
  1.2 当前研究概况  11-12
  1.3 本文的主要工作  12-13
  1.4 本文的结构安排  13-14
第2章搜索引擎及聚类相关知识  14-28
  2.1 基于Robot传统搜索引擎  14-18
    2.1.1 概述  14
    2.1.2 基于Robot传统搜索引擎基本结构  14-17
    2.1.3 基于Robot传统搜索引擎优势及发展方向  17-18
  2.2 目录式搜索引擎  18-20
    2.2.1 概述  18-19
    2.2.2 优势及发展趋势  19-20
  2.3 元搜索引擎  20-24
    2.3.1 概述  20
    2.3.2 元搜索引擎的基本结构  20-22
    2.3.3 元搜索引擎的分类  22-23
    2.3.4 元搜索引擎的优点  23-24
    2.3.5 元搜索引擎的未来研究方向  24
  2.4 聚类相关知识  24-27
    2.4.1 基于划分方法  24-25
    2.4.2 基于层次方法  25-26
    2.4.3 其他方法  26-27
  2.5 本章小结  27-28
第3章基于后缀数组聚类的元搜索引擎的设计与实现  28-45
  3.1 系统的总体设计  28-29
  3.2 用户接口模块  29-30
  3.3 检索接口代理模块  30
  3.4 预处理模块  30-31
  3.5 聚类模块  31-34
    3.5.1 相关概念及算法  31-32
    3.5.2 后缀数组构建的实现  32-33
    3.5.3 构建LCP  33-34
  3.6 聚类结果簇的筛选  34-40
    3.6.1 基本筛选  34-36
    3.6.2 基于Grouper规则过滤  36-40
  3.7 结果处理模块  40-44
    3.7.1 相关概念  41
    3.7.2 基于语义的层次化处理设计与实现  41-44
  3.8 本章小结  44-45
第4章基于SAC元搜索引擎的评测与改进构想  45-50
  4.1 SAC引擎评测  45-48
  4.2 SAC元搜索引擎引擎的改进构想  48-50
第5章结论  50-51
参考文献  51-54
作者简介及科研成果  54-55
致谢  55

基于后缀数组聚类的元搜索引擎的设计与实现

内容摘要

全文目录

相似论文