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

《基于倒排索引和字典树的站内搜索引擎的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于倒排索引和字典树的站内搜索引擎的设计与实现THEDESIGNANDIMPLEMENTATIONOFSITESEARCHENGINEBASEDONTHEINVERTEDINDEXANDTHETRIE孙芳媛哈尔滨工业大学2016年6月国内图书分类号：TP311学校代码：10213国际图书分类号：621.3密级：公开工程硕士学位论文基于倒排索引和字典树的站内搜索引擎的设计与实现硕士究生：孙芳媛导师：王宏志申请学位：工学硕士学科：软件工程所在单位：软件学院答辩日期：2016年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:

2、TP311U.D.C:621.3DissertationfortheMasterDegreeinEngineeringTHEDESIGNANDIMPLEMENTATIONOFSITESEARCHENGINEBASEDONTHEINVERTEDINDEXANDTHETRIECandidate：SunFangyuanSupervisor：Prof.WangHongzhiAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：SoftwareEngineeringAffiliation：School

3、SoftwareDateofDefence：June,2016Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要随着互联网的不断发展，快节奏的生活，人们对更好的用户体验的追求，搜索的长时间等待变得让人无法忍受。如何获得更快的搜索、更好的搜索结果、更符合用户心理的推荐成为很多网站、手机应用的痛点。本项目意在通过建立倒排索引加快搜索，使用字典树结构快速找到联想词，二者相结合的方式提供良好的搜索体验。完成一个独立的站内搜索引擎，使得项目可以快速的移植到不同

4、的系统中，提高开发速度，降低开发成本。本项目主要完成一个轻量级站内搜索引擎。系统主要分为两大部分：第一部分为全文索引引擎，主要负责从数据源建立倒排索引、以有效的格式保存索引、增量更新索引、索引的压缩、搜索排序等功能；第二部分主要为拼音搜索引擎，主要完成关键字检索、模糊查询、拼音联想等功能；此外完成系统对外的相关接口。主要的工作内容是：独立完成对整个站内搜索引擎需求分析、系统设计、系统实现以及测试等工作；完成了系统的8大核心功能模块，2个辅助模块以及所有对外的接口。具体包括(1)文档数据源获取，(2)倒排索引的建立与压缩，(3)倒排索引更新，(4)

5、倒排索引的查找，(5)搜索排序，(6)拼音转化功能的实现，(7)拼音搜索Trie建立，(8)拼音联想词的查找，以及辅助功能如高亮显示、相关推荐等功能。系统进行设计时，极为关注其本身的可拓展性、可移植性和实用性。系统实现过程中使用基于磁盘排序的归并算法，可以针对内存无法装下的数据进行排序，增强系统可用性；同时使用cidxHit算法进行压缩，使得倒排索引在不影响效率的情况下占用内存小；相关性的计算使用BM25算法，此外给出不同域权重排序方式，增强系统的灵活性；由于拼音生成联系词生成需要快速反馈给用户，所以选择了字典树作为拼音联想的核心数据结构，做到及

6、时有效的对用户输入进行反馈，增强系统的用户体验性。最终内部搜索响应时间一般为0.02s，拼音联想响应时间约为2ms，有力保障了本系统的可用性和实用性。目前本文对应的系统应用项目成果展示为百度APIStore的官网站内搜索(http://apistore.baidu.com/)。关键词：站内搜索；倒排索引；拼音联想；字典树Trie-I-哈尔滨工业大学工程硕士学位论文AbstractWiththecontinuousdevelopmentoftheInternetandfast-pacedlife,peoplepursueabetteruserexp

7、erience,whilelongtimewaitingforsearchbecomeintolerable.Plentyofmobileappsandwebsitesshareapainfulconcernhowtoobtainafastersearchprocess,bettersearchresultsandrecommendationsthatbettermatchusers'thoughts.Theprojectisintendedtoprovideabetteruserexperienceandabettersearchexperie

8、ncebybuildinganinvertedindextospeedupthesearchphase,andbuildingadigi