1.单词——文档矩阵
单词——文档矩阵是表达两者之间所具有的一种包含关系的概念模型。
如下:每列代表一个文档,每行代表一个单词
从上面的矩阵可以得出,
纵向维度:
每列代表的文档包含了哪些单词,比如Doc1包含了关键词Item1、Item2、Item3
横向维度:
每个单词被那些Doc所包含,比如Item2被Doc1、Doc2包含
搜索引擎的索引其实就是实现单词——文档矩阵的具体数据结构。我们可以通过不同的方式来实现上述概念模型。如倒排索引、签名文件、后缀树等方式。
2. 倒排索引的基本概念
文档(Document):
代表以文本形式存在的存储对象,一条记录,一篇文章,一个PDF等都是文档。
文档集合(Document Collection):
由若干文档构成的集合。
文档编号(Document ID):
在搜索引擎内部,会为文档集合中的每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识。即DocID
单词编号(Word ID):
与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。
倒排索引(Inverted Index):
是实现单词——文档矩阵的一种具体存储形式。通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:单词词典和倒排文件。
单词词典(Lexicon):
搜索引擎通常的搜索单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向倒排列表的指针。
倒排列表(PostingList):
倒排列表记载了出现过某个单词的所有文档列表以及单词在该文档中出现的位置信息,每个记录称为一个倒排项,根据倒排列表,可以获知哪些文档包含某个单词。
倒排文件(Inverted File):
所有单词的倒排列表往往顺序的存储在磁盘的某个文件里,这个文件就称为倒排文件,倒排文件是存储倒排索引的物理文件。