倒排索引

倒排索引基本概念

文档(Document)： 一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖更多种形式，比如Word，PDF，html，XML等不同格式的文件都可以称之为文档。再比如一封邮件，一条短信，一条微博也可以称之为文档。在本书后续内容，很多情况下会使用文档来表征文本信息。
文档集合(Document Collection)： 由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。
文档编号(Document ID)： 在搜索引擎内部，会将文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理，每个文档的内部编号即称之为“文档编号”，后文有时会用DocID来便捷地代表文档编号。
单词编号(Word ID)： 与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。
倒排索引(Inverted Index)： 倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。
单词词典(Lexicon)： 搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
倒排列表(PostingList)： 倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。
倒排文件(Inverted File)： 所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。

doc1 = "The cat sit on the mat"
doc2 = "The cat catches a mice"
doc3 = "Here is a little cat"

# 不区分大小写
doc1 = doc1.lower()
doc2 = doc2.lower()
doc3 = doc3.lower()

documentCollection = [doc1, doc2, doc3]  # 文档集合


# invertedIndex函数，建立倒排列表[单词ID，单词，文档频率，倒排列表(DocID;TF;<POS>)]
def invertedIndex(doc):
    lexicon = []  # 初始化一个空列表，记录所有单词
    invertedFile = []  # 倒排文件

    for i in range(len(doc)):
        doc[i] = doc[i].split(" ")  # 提取每个文档中的单词
        # print(doc[i])
        lexicon += doc[i]  # 合并

    for index in range(len(lexicon) - 1, -1, -1):  # 倒着遍历整个单词表去重
        if lexicon.count(lexicon[index]) > 1:
            lexicon.pop(index)

    for i in range(len(lexicon)):  # 遍历整个单词表
        word = lexicon[i]
        count = 0  # 初始化文档频率为0
        postingList = []  # 倒排列表
        for j in range(len(doc)):  # 将单词与每一篇文档比对
            DocID = 0  # 文档编号初始化为0
            TF = 0  # 单词频率初始化为0
            POS = []  # 一个空列表用来记录索引（可能有多个）
            if word in doc[j]:  # 如果在第j+1篇文档中有这个单词
                count += 1  # 文档频率+1
                DocID = j+1  # 记录文档编号
                for index in range(len(doc[j])):  # 遍历第j+1篇文档中的每一个单词，进行比对
                    if doc[j][index] == word:  # doc[j]中索引为index的单词为所要找到的单词时
                        TF += 1  # 单词频率+1
                        POS.append(index+1)  # 记录单词位置
            if TF != 0:  # 如果单词在第j+1篇文档中出现，即文档频率不为0，则记录其倒排列表
                postingList.append((DocID, TF, POS))
        invertedFile.append([i+1, word, count, postingList])

    return invertedFile


print(invertedIndex(documentCollection))

代码运行结果：

[
[1, 'the', 2, [(1, 2, [1, 5]), (2, 1, [1])]], 
[2, 'cat', 3, [(1, 1, [2]), (2, 1, [2]), (3, 1, [5])]], 
[3, 'sit', 1, [(1, 1, [3])]], 
[4, 'on', 1, [(1, 1, [4])]], 
[5, 'mat', 1, [(1, 1, [6])]], 
[6, 'catches', 1, [(2, 1, [3])]], 
[7, 'a', 2, [(2, 1, [4]), (3, 1, [3])]], 
[8, 'mice', 1, [(2, 1, [5])]], 
[9, 'here', 1, [(3, 1, [1])]], 
[10, 'is', 1, [(3, 1, [2])]], 
[11, 'little', 1, [(3, 1, [4])]]
]