随笔 - 89  文章 - 118  trackbacks - 0
<2013年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

单词词典
1、哈希加链表
2、树形结构:B树或者B+树
倒排列表:
单词+文档号,词频,出现的位置
文档号一般采用差值存储,以节省空间
建立索引
1、两遍文档遍历法
第一遍,收集全局统计信息,文档数N,每个文档包含不同单词数M,每个单词在多少个文档中出现过的信息DF,通过这些信息可以计算出最终索引的大小
第二遍,在建立好的内存中建立索引,从磁盘读取文档并解析文档是最消耗时间的步骤
2、排序法
始终在内存中分配固定大小的空间,用来存放词典信息和索引中间结果,当分配空间消耗光的时候,把中间结果写入磁盘,清空内存数据进行下一轮索引
中间结果排序,排序前,文档ID,单词ID,单词频率
排序后,单词ID(主键),文档ID(次键)
合并中间结果,把中间结果文件进行合并,按单词ID写入最终结果文件
3、归并法
在中间结果排序完成以后,把字典信息也写入文档中,这样全额使用内存
在建立中间索引中,实际单词,文档编号,词频
合并时,针对每个单词的倒排列表进行合并,形成最终的词典信息
动态索引
倒排索引:词典在内存里,倒排列表存储在磁盘文件中
临时索引:词典和倒排列表都在内存中,当有新文档加入时,放到临时索引中
删除文档列表:当文档内容被更改时,系统认为旧文档被删除,增加一篇新文档
当用户输入查询时,先从找倒排索引+临时索引,去掉删除文档列表中的文档结果
索引更新策略
1、完全重建策略:当新增文档达到一定数量后,新老索引合并重建,适合小文档集合,主流商业搜索引擎一般也采用此方式来维护
2、再合并策略:当新增文档达到一定数量后,新老索引合并重建,此时老索引还在被使用,由于老索引有序,所以合并策略执行较快,但是读老索引,建新索引,也需要较多IO时间,比较耗时
3、原地更新策略:在建立老索引时,在老索引倒排列表中留有一定的余地,新加入索引直接追加到预留空间,实验数据表明,更新效率比再合并策略低
4、混合策略:将单词根据不同性质进行分类,对其索引采取不同的索引更新策略,长倒排列表单词采取原地更新策略(读写开销大),短倒排列表采取再合并策略(读写开销不算太大

查询处理
1、一次一文档,找到包含关键字的所有文档集合,一次计算一个文档的得分,依次计算所有文档,计算后一般采用优先队列对分数进行排序
2、一次一单词,一次计算一个单词的得分,并把结果以文档编写为关键值,以hash表存储得分,计算所有文档得分后,对hash表进行排序
跳跃指针
在存储倒排索引文档编号时,通常使用跳跃指针节省空间,跳跃指针分块使用根号L为长度效果较好
多字段索引:对网页的不同区域进行字段划分,进行索引
1、多索引方式,对每个不同的字段分别建立索引
2、倒排列表方式,把字段信息存储到倒排列表项中
3、扩展列表方式,把每个字段出现的位置记录到一张列表里,倒排索引找到单词后,判断单词的位置是否在某字段范围中
短语查询:本质上是如何在索引中维护单词顺序关系或位置信息
1、位置信息索引,通过位置信息判断两个词是否为短语关系,适合常规短语
2、双词索引,首词+下词,只对计算代价高的短语建立双词索引,一般短语通过常规手段达到目的
3、短语索引,缺点无法将所有短语都建好索引,从用户查询日志或网页本身挖掘短语,适合热门短语
4、混合方法,用户查询->短语索引->双词索引->常规索引
分布式索引:多台机器协作完成索引
1、按文档划分,每台机器负责对某个文档子集建立索引
2、按单词划分,将单词分别传送给服务器1,计算结果后,再传送给服务器2,一次一单词的查询处理方式
posted on 2013-09-16 14:01 胡满超 阅读(502) 评论(0)  编辑 收藏 引用 所属分类: 搜索引擎

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理