今天我给大家讲讲倒排索引。
索引是构成搜索引擎的核心技术之一,它在日常生活中是非常常见的,比如我看一本书的时候,我首先会看书的目录,通过目录可以快速定位到具体章节的页码,加快对内容的查询速度。
文档通常保存在各种数据库管理系统之中,比如mysql, oracle等,但是搜索引擎的数据不能保存在数据库,主要原因有两点:一是搜索引擎的数据量非常庞大,大型搜索引擎需要处理数以亿计的网页数据,面对海量数据数据库很难管理。二是搜索引擎对数据的操作比较简单,一般的增删改查就够用了,而数据库支持的数据库操作是比较复杂的,牺牲了速度和空间,而搜索引擎要求响应快,信息检索效率高,在搜索引擎中主要使用倒排索引存储网页数据。
倒排索引也叫反向索引,是一种索引方法,用来存储在在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射,它是文档检索系统中最常用的数据结构。
下面以通俗的例子解释一下倒排索引,该例子取自于书中内容:有两个文档doc1和doc2,医生包含中国,美国,韩国,doc2中包含4个关键词:中国,美国,德国,英国,文档和词语的关系如下:
文档 词语 doc1 中国,美国,韩国 doc2 英国,中国,美国,德国词语所属的文档关系如下:
词语 文档 中国 doc1, doc2 美国 doc1, doc2 韩国 doc1 英国 doc2 德国 doc2
参考下表,我们深入理解一下倒排索引,我们给每个文档设置文档ID
文档ID 文档内容 1 人工智能成为互联网大会焦点 2 谷歌推出开源人工智能系统工具 3. 互联网的未来在人工智能 4 谷歌开源机器学习工具
对于文档内容,先要经过词条化处理。和英文不同的是,英语通过空格分隔单词,中文的词与词之间没有明确的分隔符号,经过分词系统进行中文分词以后把矩阵切分成一个个词条,文档4被分成“谷歌”“开源”“机器”“学习”“工具”5个词项。谷歌这个词在文档2和文档4中各出现一次,文档频率为2,倒排记录表记作2→4,文档频率也是倒排记录表的长度。依次统计各个词项的文档频率和倒排记录表,构建倒排索引过程如下:
词项文档频率倒排记录表
文档ID 文档频率 倒排记录表 人工 3. 2→3 智能 3. 2→3 成为 1 1 互联网 2 1→3
