Python简易搜索引擎原理及实现（一）建立倒排索引

一、什么是倒排索引

在搜索引擎每个文件都对应一个文件ID，文件内容被表示为一系列关键词的集合（实际上在搜索引擎索引库中，关键词也已经转换为关键词ID），例如【文档1】经过分词，提取了20个关键词，每个关键词都会记录他在文档中的出现次数和出现位置。

得到正向索引的结构如下：

“文档1”的ID > 单词1：出现次数，出现位置列表；单词2：出现次数，出现位置列表；…… “文档2”的ID > 此文档出现的关键词列表。

……

一般是通过key找value

倒排索引概念

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

二、实现步骤

1）选定数据源，如某类网站、某类期刊、某类会议。 2）（手工/自动）获取数据源中的文本信息，如将每个网页作为一篇文献，存为.txt 文档。 3）分词算法：中文文档，选用中文分词工具来实现。 4）排序算法：对提取的所有 items(信息项)进行排序。 5）词频算法：统计在每个文档中出现的每个 item 的词频 tf。 6）去重算法：计算出现每个 item 的文档个数 df，将重复出现的 item 进行去重处理。 7）创建索引结构：建立字典结构和 PostingList 结构，存储 items 和 df、DocIDs 和 tf

三、代码实现

1.数据爬取（豆瓣Top250）

import requests
from bs4 import BeautifulSoup
import time
import os
import sys

def request_douban(url): # 请求并获取豆瓣的源码
    # headers = {''}
    # cookies = {''}
    # cyheaders = {''}
    # cycookies = {''}
    try:
        #response = requests.get(url, headers=cyheaders, cookies=cycookies)
        response = requests.get(url) #
        if response.status_code == 200:
            return response.text
    except requests.RequestException:
        return None

n = 226


def saveToEveryFile(soup, *parm):
    if soup.find(class_= 'all hidden') is not None:
        intro = soup.find(class_='all hidden').get_text().replace(u' ','')
    else:
        intro = soup.find(property='v:summary').get_text().replace(u' ','')
    item_director = soup.find(text='导演').parent.parent.find(class_='attrs').get_text().strip()
    itemkind = ''
    for i in soup.find_all(property='v:genre'):
        itemkind = itemkind + ' ' + i.get_text().strip()
    myPath = os.path.join(os.getcwd(), "exp" + os.sep + "data" + os.sep + "movie" + str(n) + ".txt")  # windows下去掉exp + os.sep +
    myfile = open(myPath, "w", encoding='utf-8')
    for item in parm:
        myfile.write(item)
    myfile.write("导演:" + item_director + "\n")
    myfile.write('类型:' + itemkind + '\n')
    myfile.write(intro+"\n")


def saveToFile(soup):
    myfile = open("douban.txt", "a+", encoding='utf-8')
    list = soup.find(class_='grid_view').find_all('li')
    for item in list:
        item_url = item.find('a').get('href')
        item_name = item.find(class_='title').string
        item_img = item.find('a').find('img').get('src')
        item_index = item.find(class_='').string
        item_score = item.find(class_='rating_num').string
        item_author = item.find('p').text
        if (item.find(class_='inq') != None):
            item_intr = item.find(class_='inq').string

        # print('爬取电影：' + item_index + ' | ' + item_name +' | ' + item_img +' | ' + item_score +' | ' + item_author +' | ' + item_intr )
#        print('爬取电影：' + item_index + ' | ' + item_name + ' | ' + item_score + ' | ' + item_intr)

        global n

        pageHtml = request_douban(item_url)
        pageSoup = BeautifulSoup(pageHtml, 'lxml')
        # print(pageSoup)
        saveToEveryFile(pageSoup, "影片名称:" + item_name.strip(), "影片序号:" + item_index.strip(),"豆瓣分数:" + item_score.strip())
        myfile.write(item_url + " | " + item_name + ":" + item_intr + "\n")
        n = n + 1
        time.sleep(5)

def main(page):
    url = 'https://movie.douban.com/top250?start=' + str(page * 25) + '&filter='
    html = request_douban(url)
    soup = BeautifulSoup(html, 'lxml')
    saveToFile(soup)

if __name__ == '__main__':
    for i in range(9, 10):
        main(i)

2. 单词分词

中文分词，使用jieba分词工具进行单词分词。下面简单介绍一下jieba

jieba

jieba库是一款优秀的 Python 第三方中文分词库，jieba库中用于分词的方法有三个：jieba.cut jieba.cut_for_search jieba.lacut

🌲jieba.cut：给定中文字符串，分解后返回一个迭代器，需要for循环访问，有四个参数：

需要分词的字符串
cut_all ：控制是否采用全模式
HMM：是否使用HMM模型（默认True）
use_paddle：参数用来控制是否使用paddle模式下的分词模式，paddle模式采用延迟加载方式，通过enable_paddle接口安装paddlepaddle-tiny，并且import相关代码

🌲jieba.cut_for_search：该方法和cut一样，分解后返回一个迭代器，需要用for循环访问。不过它是搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。

🌲jieba.lcut：和jieba.cut使用方法一样，不过返回的是列表list。

jieba 支持三种分词模式：精确模式、全模式和搜索引擎模式，下面是三种模式的特点。

精确模式：试图将语句最精确的切分，不存在冗余数据，适合做文本分析
全模式：将语句中所有可能是词的词语都切分出来，速度很快，但是存在冗余数据
搜索引擎模式：在精确模式的基础上，对长词再次进行切分

3. 建立倒排索引

将爬取的数据进行分词计算tf, df，建立字典结构和PostingList存储词条名df以及df个docID和tf.

1️⃣ 我们需要创建如图所示的结构：

2⃣️对提取的item（信息项进行排序）

3⃣️ 统计在每个文档中出现的每个 item 的词频 tf

4⃣️ 计算出现每个 item 的文档个数 df，将重复出现的 item 进行去重处理

5⃣️ 倒排索引建立完成，输出字典结构和Posting List结构到文件

最终形成的倒排索引结构如图：

4. 具体代码

def segmentations(ID):
    moviePath = NAME + str(ID) + '.txt'
    singleFile = open(os.path.join(dataPath, moviePath), 'r', encoding='utf-8')
    contents = singleFile.read()
    segmentation = jieba.cut_for_search(contents)
    
    cnt = 0
    itemdict = dict()
    for items in segmentation:
        if items not in rubbish and items is not None:
            # sortedList.append(items)
            cnt = cnt + 1
            if itemdict.get(items) is None:
                itemdict.update({items: 0})
            itemdict[items] = itemdict[items] + 1 # 记录每个item出现的次数
    for item, count in itemdict.items():
        tfdict[item] = 1.0 * count / cnt # 计算tf：单词频率信息
        resultdict[item].update({'df': resultdict.get(item).get('df') + 1}) # 计算df：文档频率信息
        resultdict.get(item).update({ID: tfdict[item]})

if __name__ == '__main__':
    n = 1
    while n <= 250:
        segmentations(n)
        print(n)
        n = n + 1
    resultfile = open(os.path.join(dataPath, 'result.txt'), 'w', encoding='utf-8')
    for items, val in resultdict.items():
        resultfile.write(items + ' ' + 'df:' + str(val.get('df')) + '\n')
        for innerItem, innerVal in val.items():
            if innerItem is not 'df':
                innerItem = 'DocID' + str(innerItem)
                innerVal = 'tf: ' + str(innerVal)
            else:
                continue
            resultfile.write(str(innerItem) + ' ' + str(innerVal) + '\n')

简易搜索引擎（一）