简单的搜索引擎搭建

本文简述一下搜索引擎的搭建过程，具体描述的搜索是文本类型的搜索，而非网页搜索。对于网页搜索的排序，需要有很多考虑，例如pagerank算法，会优先考虑web站点的重要性。文本搜索一般为关键词检索，再根据文本的相似性对搜索得到的文本进行重排序。搜索的方法有很多，排序的方法也有很多，本文介绍最简单的搜索引擎搭建。

搜索引擎在互联网信息爆炸的时代起到了重要的作用，帮助我们进行信息过滤、信息抽取等。本文使用百度知道数据进行实验，用户输入Query请求，系统返回最为相近的百度知道问题。数据预先通过web爬虫获取。下面先直观看一下，本系统的展示效果图：

搜索算法

搜索是基于关键词进行的，一般为线性速度。预先获取与用户Query相关的候选，然后再同滚rank model得到用户最想得到的Answer。这里简单地介绍一下倒排算法。例如给定一句话“姚明NBA季后赛”，通过关键词抽取，得到“姚明”、“NBA”、“季后赛”关键词。通过上述三个词语找到预先定义好链表如下：

1. 姚明 -> 文本a -> 文本b ->...文本e
2. NBA -> 文本f -> 文本d ->...->文本e
3. 季后赛 -> 文本e ->文本k...

通过对上述链表1、2、3取并集得到所有相关的候选文本，再通过两两取交集得到文本的重要程度，可以得到预先的排序。例如上述文本e再三条候选链表都有，则文本e的重要性高。这种交集和并集的计算复杂度很低，很快就能得到搜索结果。

排序算法

为进一步提高文本与用户搜索Query的相关程度，需要对搜索得到的候选集合进行重排序。下面介绍BM25算法。 BM25算法是用来计算文本之间的相似度的，是TFIDF得到文本Bag-of-Words的改进。

一般计算公式：

其中Q表示用户输入的请求Query，d表示候选的document，Score(Q,d)表示Q和d的相似度得分，vi表示Q中的单词，d表示文档。R(vi,d)表示单词vi与d之间的相关性。 对于权重wi的计算可以用反文本词频表示。N表示总文本数量，n(vi)表示包含vi的文本数量。

词语与文本的相关性计算：

其中：

BM25算法实现的主要代码如下：

def BM25(W,R): n = len(W) score = 0 for i in range(n): score += W[i]*R[i] return scoredef IDF(nqi,N): return np.log((N-nqi+0.5)/(nqi+0.5))def getR(avgdl,d,fi): k1 = 2 b = 0.75 dl = len(d) K = k1*(1-b+b*(dl/float(avgdl))) cfi = d.count(fi) return cfi*(k1+1)/(cfi+K)def get_nqi(Doc,word): nqi = 0 for d in Doc: if word in d: nqi += 1 return nqidef BM25_Score(D,fword): W = [] R = [] N = len(D) L = 0.0 for d in D: L += len(d) avgdl = float(L)/N for word in fword: nqi = get_nqi(D,word) W.append(IDF(nqi,N)) Ri = [] for d in D: Ri.append(getR(avgdl,d,word)) R.append(Ri) Score = [] R = np.transpose(R) for i in range(N): RR = R[i] Score.append(BM25(W,RR)) return Score

由于机器学习的快速发展，现在的rank model得到了很大突破，learning-to-rank已在机器学习领域成为很重要的研究方向。有兴趣的同学，可以调研一下相应的rank model，本公众号之前有描述过如何计算文本相似度计算的深度学习模型。