单词词典
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
胡满超 阅读(517)
评论(0) 编辑 收藏 引用 所属分类:
搜索引擎