具有间隙约束的搜索引擎原型系统的研究与实现

摘要

搜索引擎是为人们能够快速、准确地在浩瀚的互联网资源中查找自己所需要的信息而诞生的，是Internet和时代飞速发展的产物。尽管现有的搜索引擎已经具备成熟、完善的检索机制，但其还是在检索结果中存在各种各样的不足，即各种搜索引擎都不支持具有间隙约束的搜索，因此对具有间隙约束的搜索进行研究是非常有实际应用意义的。
　　模式匹配问题也称作串匹配问题，它是计算机科学领域的基本问题的其中之一，它在众多领域都有重要的应用。而具有间隙约束的模式匹配是模式匹配的一个重要的研究内容。多年来研究者们致力于研究多个间隙约束的模式匹配问题，一般可描述为P=p0[min0,max0]p1...[minj-1,maxj-1]pj...[minm-1,maxm-1]pm，这里，minj-1和maxj-1分别指在pj-1和pj之间可以通配的最小和最大间隙，具有多个间隙约束的模式匹配问题在诸多领域具有重要应用。据此，由于前面所述搜索引擎存在的不足，本文结合倒排索引和跨度查询(SpanQuery)来对此缺陷进行改进，即 ABSQ(the inverted index Algorithm based SpanQuery span query)算法。由于SpanQuery跨度查询匹配的条数有所限制，所以本文据此还针对数组和键值对两种不同存储方式设计了匹配条数更多的两个算法。分别为ABAS(the inverted index Algorithm Based on Array Storage)以及ABKS算法(the inverted index Algorithm Based on Key-value Storage)，此外，还实现了不用索引的算法RRSA(Recently the Right Scan Algorithm)来和ABSQ进行对比。
　　实验结果表明，RRSA和ABSQ比较，在索引文件少文件内容少的情况下，RRSA在运行时间上优于ABSQ，而随着索引文件和文件内容的不断增大，ABSQ在运行时间上明显要优于RRSA。而ABAS和ABKS两算法与ABSQ比较，时间上没有太大的差异，但在匹配结果上要优于ABSQ。ABAS和ABKS做比较，运行时间和结果都没有明显的区别。实验表明ABKS算法是相对较好的算法。最后，将此算法用于具有间隙约束的搜索引擎系统中，取得了较好的成果，证明该算法的客观性和可行性，同时也证明了该系统的合理性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 课题的研究背景和意义

1.2 课题的研究现状和存在的问题

1.3 论文的主要研究内容

1.4 论文的内容安排

第二章 搜索引擎的概述

2.1 搜索引擎的发展历程

2.2 搜索引擎的工作原理

2.3 搜索引擎的体系结构

2.4 本章小结

第三章 Lucene的核心技术分析

3.1 搜索引擎Lucene

3.2 中文分词

3.3 本章小结

第四章 系统的设计、实现与结果分析

4.1 系统实现目标

4.2 系统的具体设计方案

4.3 实验结果及分析

4.4 系统页面设计

4.5 本章小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢