新闻动态
单词词典及哈希加链表
https://www.sytm.net 发布日期:2013/9/8 5:54:32

单词词典是倒排索引中非常重要的组成部分,它用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索引擎是,根据用户的查询词,去单词词典里查询,就能够获得响应的倒排列表,并以此作为后续排序的基础。

对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构和树形词典结构。

上图是这种词典结构示意图。这种词典结构主要是由两个部分构成,主题部分是哈希表,每个哈希表项保存一个指针,指针指向冲突链表,在突然链表里,相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词获得相同的哈希值,如果是这样,在哈希表方法里被才称作是一次冲突,可以相同哈希值的单词存储在链表里,以供后续查询。

对于某个在文档中出现的单词T,首先利用哈希 函数获得其哈希值,之后根据哈希值对应的哈希表项读取其中保存的指针,就找到了对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,响应的词典结构也就建立起来了。

在响应用户查询 请求时,其过程与建立词典类似,不同点在于即使词典里没有出现过某个单词,也不会添加到词典内,以下图为例,假设用户输入的查询请求为单词3,对这个单词进行哈希,定位到哈希表内的2号槽,从其保留的指针可以获得冲突链表,依次将单词3和冲突链表内的单词比较,发现单词3在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的到排列表来进行后续工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

更多阅读
返回列表
© 2010 TianMei Technology All rights reserved. ICP:辽B2-20150138辽公网安备 21010202000010号  目录概览