搜索引擎的倒排索引技术的详细介绍

搜索引擎的倒排索引技术的详细介绍

写一个桌面搜索引擎还不简单?只要了解一下倒排索引的概念,每个有兴趣的程序员,花点时间,都能写出来一个自己的桌面搜索引擎。

为什么搜索引擎的查询速度这么快? 说明白了很简单,核心技术就是 “倒排索引”。

“倒排索引”这个名词很唬人,其实原理很简单。

假设有3篇文章,file1,file2,file3,文件内容如下:

file1 (单词1,单词2,单词3,单词4....)

file2 (单词a,单词b,单词c,单词d....)

file3 (单词1,单词a,单词3,单词d....)

建立的倒排索引就是这个样子:

单词1 (file1,file3)

单词2 (file1)

单词3 (file1,file3)

单词a (file2, file3)

....

这就是倒排索引,很简单吧。

比如一个文件要建立索引,就先把它抽成纯文本的格式,然后把一个一个的单词切割出来,每个单词在数据库里是一条记录,单词作为关键字,后面跟着文件的标识ID,位置。

我写的桌面搜索引擎 ftfind, 内部也采用了倒排索引技术。http://www.18ie.com

倒排索引技术,点破了很简单,我想每个有兴趣的程序员,花点时间,都能写出来一个自己的桌面搜索引擎。

还用google desktop search 干什么?看着它右边不时冒出来的广告窗口,心里就不爽。

为什么不自己写一个呢,随心所欲,自由自在。

下面收集一些需要进一步了解的知识。

在使用索引进行查找时,首先对需要索引的文档进行预处理,建立关于这些文档的索引结构。索引的技术主要有以下3种:倒排索引,后缀数组和签名文件。其中,倒排索引技术在当前大多数的信息检索系统中得到了广泛的应用,它对于关键词的搜索非常有效,在Lucene中也是使用的这种技术。后缀数组技术在短语查询中具有很快的速度,但是这样的数据结构在构造和维护时都比较复杂一些。签名文档技术在20世纪80年代时期比较流行,但是后来倒排索引技术逐渐超越了它。