倒排索引的构建与查询

倒排索引是信息检索的重要技术，本文将基于中文短信数据（数据集可在本文所附资源处下载或点击此处链接下载），编程构建倒排索引并实现布尔查询。

1. 功能设计

用户输入查询，按下回车键，如果该查询作为单独的查询词命中，程序返回一个列表作为查询结果，列表中包含全部的命中文档。列表中的每一项的格式为：“文档ID:查询词在该文档中的词频”。例如：用户输入的查询为“蓝猫”，返回的查询结果为[‘34:1’, ‘246914:1’, ‘294413:1’, ‘404281:1’, ‘444679:1’, ‘452678:1’, ‘519311:1’, ‘660405:1’]，表示“蓝猫”一词在文档ID为34、246914、294413、404281、444679、452678、519311、660405的8个文档中均出现过一次。
如果步骤1中的查询未命中，则对该查询进行分词，对分词后得到的查询词列表执行AND布尔查询。如果执行AND查询命中，程序返回同时包含全部查询词的文档ID列表。例如：用户输入的查询为“文化墙”，返回的查询结果为[‘472358’, ‘727722’, ‘560771’, ‘102998’, ‘14’]，表示“文化”、“墙”两词同时出现在文档ID为472358、727722、560771、102998、14的8个文档中。
如果步骤2中的AND布尔查询未命中，则对分词后的查询词列表执行OR布尔查询。如果OR布尔查询命中，则程序返回文档ID列表。否则，程序返回“没找到”。

2. 实现思路

实现思路主要分为三个步骤：第一步，对中文文本进行分词并去除停用词；第二步，构建倒排索引；第三步，根据倒排索引完成查询。

在第一步中，中文文本分词使用结巴分词工具，停用词列表共1893个停用词，主要去除了标点符号、特殊字符、数字序号、无意义的停顿词、虚词等。

在第二步中，倒排索引的构建采用MapReduce的思想。主要分为Map、Combine、Reduce三阶段，示例如下图所示。

MapReduce流程示例

在Map阶段，对每个文档进行分词，以键值对的形式将分词结果存储在字典中输出，其中键为“文档ID:词”，值为一个元素均为1的列表，列表的长度为该词在相应文档中出现的次数。

在Combine阶段，对Map的输出结果进行一次合并归约，即对于Map阶段输出的字典中的每个键值对，将原先的元素均为1的值列表做求和操作，转换为词频。

在Reduce阶段，继续对Combine阶段的输出结果进行合并。最终输出结果字典中，每个键值对为<词, 文档ID:词频>的形式。

在第三步中，根据倒排索引进行的查询主要分为三次判断：首先判断用户输入的查询是否可以作为单独的查询词命中。若可以命中，则返回结果；否则，对查询进行分词，对分词列表做AND布尔查询。然后判断AND布尔查询是否可以命中，若可以命中，则返回结果；否则，对分词列表做OR布尔查询。然后判断OR布尔查询是否可以命中，若可以命中，则返回结果；否则，返回“没找到”。在AND布尔查询中，将每个词的文档ID列表取交集；在OR布尔查询中，将每个词的文档ID列表取并集。示例如下图所示。

根据倒排索引进行查询的判断逻辑示例

3. 代码

最终整体代码inverted_index.py完成如下所示。除主函数之外，代码中的函数主要有：stopwordslist(filepath)、mapper(docId, list)、combiner(dic)、reducer(dic)、get_inverted_index(filepath, stopwords)五个。可以看到，以下代码中并未涉及到shuffle环节，这是因为实验中选用的文档ID为短信所在行的行号，每个文档是顺序处理的且在处理后存储到有序字典中，因此省略了按文档ID排序的环节。

# -*- coding;utf-8 -*-

import os
import jieba
import re
import json
import collections
from functools import reduce
import io
#import sys
#sys.stdout = io.TextIOWrapper(sys.stdout.buffer, encoding='utf-8')

#读取停用词列表
def stopwordslist(filepath):  
    stopwords = [line.strip() for line in open(filepath, 'r', encoding='utf-8').readlines()]  
    return stopwords  


def mapper(docId, list):
    #初始化结果字典为空
    dic = {} 
    dic = collections.OrderedDict()
    #对于分词后序列中的每一个词term
    for term in list: 
        #将文档ID与词拼接起来，作为关键字
        key = ''.join([str(docId), ':', term]) 
        #如果该关键字已经存在于结果字典中
        if key in dic: 
            valuelist = dic.get(key)
            #则在值列表中新增1，标志词term在文档中再次出现
            valuelist.append(1) 
            dic[key] = valuelist
        else:
            #否则表明词term首次出现在文档中
            dic[key] = [1] 
    return dic


def combiner(dic):
    keys = dic.keys()
    result = {}
    result = collections.OrderedDict()
    for key in keys:
        valuelist = dic.get(key)
        count = 0
        #计算每个词在文档中出现的次数（词频）
        for i in valuelist:
            count += i
        result[key] = count
    return result

def reducer(dic):
    keys = dic.keys()
    #初始化结果字典为空
    result = {}
    result = collections.OrderedDict()
    for key in keys:
        #将输入字典中的关键字拆分为文档ID与词term
        docId, term = key.split(":")
        #将文档ID与词term的词频拼接起来作为value
        value = ''.join([docId, ':', str(dic.get(key))])
        #如果词term存在于结果字典中
        if term in result:
            valuelist = result[term]
            #则将该value加入值列表中
            valuelist.append(value)
            result[term] = valuelist
        else:
            result[term] = [value]
    return result

def get_inverted_index(filepath, stopwords):
    file = open(filepath, 'r', encoding='utf-8')
    lineNum = 0
    temp = {}
    temp = collections.OrderedDict()
    while True:
        lineNum += 1
        line = file.readline()
        if line != '':
            line = line.strip('\n').split('\t')[1]
            print (lineNum, ' ', line,)
        else:
            break
        termlist = []
        for w in list(jieba.cut(line)):
            if w not in stopwords:
                termlist.append(w)
        mdic = mapper(lineNum, termlist)
        cdic = combiner(mdic)
        print(cdic)
        temp.update(cdic)
    rdic = reducer(temp)
    return rdic


if __name__ == '__main__':
    stopwords = stopwordslist('stopwords.txt')
    try:
        #若倒排索引文件已经生成，则直接从文件中读取
        file = open('index.txt', 'r', encoding='utf-8')
        js = file.read()
        dic = json.loads(js)
        file.close()
    except:
        #否则生成倒排索引文件
        dic = get_inverted_index('data.txt', stopwords)
        js = json.dumps(dic)
        file = open('index.txt', 'w', encoding='utf-8')
        file.write(js)
        file.close()
    while(1):
        query = input('请输入你想查找的内容(输入q退出):')
        if query == 'q' or query == 'Q':
            break
        else:
            if query in dic:
                print(dic.get(query))
            else:
                termlist = []
                for w in list(jieba.cut(query)):
                    termlist.append(w)
                results = []       
                for i in range(0,len(termlist)):
                    if termlist[i] in dic:
                        temp = []
                        for item in dic.get(termlist[i]):
                            docId, freq = item.split(":")
                            temp.append(docId)
                        results.append(temp)
                if results == []:
                    print('没找到')
                else:
                    #AND查询
                    fm = lambda x,y: list(set(x).intersection(set(y))) if isinstance(x, list) and isinstance(y, list) else 'error'
                    fn = lambda x: x[0] if len(x) == 1 else [] if  len(x) == 0 else reduce(fm,tuple(y for y in x))
                    temp = results
                    final_results = fn(temp)
                    if final_results != []:
                        print(final_results)
                    else:
                        #OR查询
                        fm = lambda x,y: list(set(x).union(set(y))) if isinstance(x, list) and isinstance(y, list) else 'error'
                        fn = lambda x: x[0] if len(x) == 1 else [] if  len(x) == 0 else reduce(fm,tuple(y for y in x))
                        temp = results
                        final_results = fn(temp)
                        print(final_results)

4. 运行结果

首次运行inverted_index.py，将生成倒排索引文件index.txt。之后再次运行inverted_index.py，将从倒排索引文件中加载倒排索引为字典格式。倒排索引加载完毕，程序提示：“请输入你想查找的内容(输入q退出)”，用户输入查询，按下回车即可进行循环查询，输入q字符跳出循环。测试用例如下：

查询：“蓝猫”，结果：[‘34:1’, ‘246914:1’, ‘294413:1’, ‘404281:1’, ‘444679:1’, ‘452678:1’, ‘519311:1’, ‘660405:1’]（属于查询词可作为单个词命中文档的情况）
查询：“渤海”，结果：[‘24:2’, ‘5466:1’, ‘6478:1’, ‘10162:1’, ‘11618:1’, ‘24448:1’, ‘28510:1’, ‘30315:1’, ‘31080:1’, ‘32418:1’, ‘61972:1’, ‘70692:1’, ‘80132:2’, ‘113344:1’, ‘113581:1’, ‘116005:1’, ‘123980:2’, ‘168168:1’, ‘173460:1’, ‘176530:1’, ‘186451:2’, ‘187653:1’, ‘207964:1’, ‘209533:1’, ‘216139:1’, ‘220807:1’, ‘238442:1’, ‘241201:1’, ‘244691:1’, ‘259685:1’, ‘260014:2’, ‘268367:1’, ‘281240:2’, ‘285323:1’, ‘304731:1’, ‘314724:2’, ‘315673:1’, ‘361410:1’, ‘374756:1’, ‘385608:1’, ‘441109:1’, ‘477490:1’, ‘492804:1’, ‘493811:1’, ‘494802:1’, ‘499013:1’, ‘514353:1’, ‘529791:1’, ‘530882:1’, ‘532511:1’, ‘536790:1’, ‘539291:1’, ‘541265:1’, ‘555833:1’, ‘558951:1’, ‘566540:1’, ‘571613:1’, ‘588200:1’, ‘597989:1’, ‘616213:1’, ‘624738:1’, ‘631713:1’, ‘679088:1’, ‘686993:1’, ‘692306:1’, ‘717532:1’, ‘717598:1’, ‘749175:1’, ‘757471:1’, ‘796113:1’]
查询：“南京四川”，结果：[‘500318’, ‘462582’, ‘329294’, ‘368153’, ‘260541’, ‘612586’, ‘606335’, ‘781114’, ‘507296’, ‘213024’, ‘419647’, ‘765378’, ‘148594’, ‘79034’, ‘710908’, ‘357999’, ‘27’, ‘426147’, ‘571882’, ‘476409’, ‘36435’, ‘741202’]（属于AND布尔查询的情况）
查询：“文化墙”，结果：[‘560771’, ‘102998’, ‘14’, ‘472358’, ‘727722’]（属于AND布尔查询的情况）
查询：“渤海蓝猫”，结果：[‘477490’, ‘61972’, ‘624738’, ‘30315’, ‘10162’, ‘28510’, ‘11618’, ‘32418’, ‘555833’, ‘281240’, ‘514353’, ‘260014’, ‘529791’, ‘315673’, ‘187653’, ‘113581’, ‘294413’, ‘113344’, ‘616213’, ‘207964’, ‘679088’, ‘541265’, ‘209533’, ‘24’, ‘268367’, ‘588200’, ‘5466’, ‘631713’, ‘519311’, ‘757471’, ‘216139’, ‘116005’, ‘244691’, ‘31080’, ‘404281’, ‘558951’, ‘173460’, ‘749175’, ‘304731’, ‘259685’, ‘597989’, ‘493811’, ‘220807’, ‘285323’, ‘539291’, ‘238442’, ‘374756’, ‘444679’, ‘492804’, ‘660405’, ‘6478’, ‘385608’, ‘532511’, ‘80132’, ‘186451’, ‘176530’, ‘34’, ‘314724’, ‘536790’, ‘361410’, ‘24448’, ‘70692’, ‘241201’, ‘441109’, ‘686993’, ‘499013’, ‘692306’, ‘566540’, ‘246914’, ‘494802’, ‘571613’, ‘717532’, ‘452678’, ‘530882’, ‘123980’, ‘717598’, ‘168168’, ‘796113’]
（属于OR布尔查询的情况）
查询：“english”，结果：“没找到”

用编辑器打开给定的中文短信数据，使用字符串搜索功能加以验证，发现上述测试用例是可以通过的。