基于倒排索引和字典树的站内搜索引擎的设计与实现

发布时间：2017-11-03 12:09

  本文关键词：基于倒排索引和字典树的站内搜索引擎的设计与实现

  更多相关文章： 站内搜索 倒排索引 拼音联想 字典树Trie

【摘要】：随着互联网的不断发展,快节奏的生活,人们对更好的用户体验的追求,搜索的长时间等待变得让人无法忍受。如何获得更快的搜索、更好的搜索结果、更符合用户心理的推荐成为很多网站、手机应用的痛点。本项目意在通过建立倒排索引加快搜索,使用字典树结构快速找到联想词,二者相结合的方式提供良好的搜索体验。完成一个独立的站内搜索引擎,使得项目可以快速的移植到不同的系统中,提高开发速度,降低开发成本。本项目主要完成一个轻量级站内搜索引擎。系统主要分为两大部分:第一部分为全文索引引擎,主要负责从数据源建立倒排索引、以有效的格式保存索引、增量更新索引、索引的压缩、搜索排序等功能;第二部分主要为拼音搜索引擎,主要完成关键字检索、模糊查询、拼音联想等功能;此外完成系统对外的相关接口。主要的工作内容是:独立完成对整个站内搜索引擎需求分析、系统设计、系统实现以及测试等工作;完成了系统的8大核心功能模块,2个辅助模块以及所有对外的接口。具体包括(1)文档数据源获取,(2)倒排索引的建立与压缩,(3)倒排索引更新,(4)倒排索引的查找,(5)搜索排序,(6)拼音转化功能的实现,(7)拼音搜索Trie建立,(8)拼音联想词的查找,以及辅助功能如高亮显示、相关推荐等功能。系统进行设计时,极为关注其本身的可拓展性、可移植性和实用性。系统实现过程中使用基于磁盘排序的归并算法,可以针对内存无法装下的数据进行排序,增强系统可用性;同时使用cidx Hit算法进行压缩,使得倒排索引在不影响效率的情况下占用内存小;相关性的计算使用BM25算法,此外给出不同域权重排序方式,增强系统的灵活性;由于拼音生成联系词生成需要快速反馈给用户,所以选择了字典树作为拼音联想的核心数据结构,做到及时有效的对用户输入进行反馈,增强系统的用户体验性。最终内部搜索响应时间一般为0.02s,拼音联想响应时间约为2ms,有力保障了本系统的可用性和实用性。目前本文对应的系统应用项目成果展示为百度APIStore的官网站内搜索(http://apistore.baidu.com/)。
【关键词】：站内搜索 倒排索引 拼音联想 字典树Trie
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.52;TP391.3
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第1章 绪论9-20
• 1.1 课题背景及研究的目的和意义9-10
• 1.2 国内外相关研究现状10-17
• 1.2.1 搜索引擎的分类10-11
• 1.2.2 全文搜索引擎现状分析11-13
• 1.2.3 全文搜索引擎关键技术概述13-15
• 1.2.4 国内外开源检索框架现状分析15-17
• 1.3 本文的主要研究内容17-20
• 1.3.1 本系统的目标与挑战17-18
• 1.3.2 本文选用的相关基础框架18-19
• 1.3.3 本文的研究内容结构说明19-20
• 第2章 基于索引的站内搜索引擎需求分析20-26
• 2.1 引言20
• 2.2 站内搜索系统功能需求分析20-25
• 2.2.1 拼音搜索引擎需求分析22-23
• 2.2.2 后台检索引擎需求分析23-25
• 2.3 站内搜索系统性能需求分析25
• 2.4 本章小结25-26
• 第3章 基于索引的站内搜索引擎的设计26-46
• 3.1 引言26
• 3.2 基于倒排索引和字典树站内搜索系统的总体设计26-28
• 3.3 基于倒排索引的检索系统的详细设计28-39
• 3.3.1 文档数据源获取模块的详细设计28-32
• 3.3.2 索引建立模块的详细设计32-35
• 3.3.3 索引更新模块的详细设计35-36
• 3.3.4 搜索查询模块的详细设计36-38
• 3.3.5 搜索排序模块的详细设计38-39
• 3.4 基于字典树的拼音联想搜索的详细设计39-45
• 3.4.1 拼音转化模块的详细设计39-41
• 3.4.2 核心数据结构的详细设计41-42
• 3.4.3 字典树建立模块的详细设计42-44
• 3.4.4 拼音搜索模块的详细设计44-45
• 3.5 本章小结45-46
• 第4章 基于索引的站内搜索引擎的具体实现46-71
• 4.1 引言46
• 4.2 基于倒排索引的检索系统的具体实现46-61
• 4.2.1 文档数据源获取模块的具体实现46-48
• 4.2.2 索引建立模块的具体实现48-55
• 4.2.3 索引更新模块的具体实现55-57
• 4.2.4 搜索查询模块的具体实现57-59
• 4.2.5 搜索排序模块的具体实现59-61
• 4.3 基于字典树的拼音联想搜索的具体实现61-69
• 4.3.1 拼音转化模块的具体实现62-64
• 4.3.2 核心数据结构的具体实现64-65
• 4.3.3 字典树建立模块的具体实现65-67
• 4.3.4 拼音搜索模块的具体实现67-69
• 4.4 其他辅助模块的实现69-70
• 4.5 本章小结70-71
• 第5章 站内搜索系统实现结果以及系统测试71-81
• 5.1 系统功能测试结果展示71-76
• 5.1.1 拼音搜索交互测试效果展示71-73
• 5.1.2 后台检索结果测试效果展示73-74
• 5.1.3 系统线下测试效果展示74-76
• 5.2 系统性能测试76-80
• 5.2.1 测试环境与测试方式76
• 5.2.2 系统测试结果说明76-80
• 5.3 本章小结80-81
• 结论81-82
• 参考文献82-86
• 致谢86-87
• 个人简历87

，

本文编号：1136118