http://blog.csdn.net/hguisu/article/details/7962350

http://blog.csdn.net/hguisu/article/details/7969757

=====================           我是分割线          =============================

 

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

倒排索引有两种不同的反向索引形式：

        一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。

        一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

        现代搜索引起的索引都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构，“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构.

单词词典常用的数据结构有   哈希加链表     树形结构  

1、简单索引构建

索引的建立相当于从正排表到倒排表的建立过程。

流程：

          分词 -> 去重 -> 单词倒排

2、合并法建立索引

归并法,即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。

 

合并流程：

1）页面分析，生成临时倒排数据索引A，B，当临时倒排数据索引A，B占满内存后，将内存索引A，B写入临时文件生成临时倒排文件，

2)  对生成的多个临时倒排文件 ,执行多路归并 ,输出得到最终的倒排文件 ( inverted file)。

索引创建过程中的页面分析 ,特别是中文分词为主要时间开销。算法的第二步相对很快。这样创建算法的优化集中在中文分词效率上。

 

3、并行与分布式建立索引