一、检索模型
搜索引擎一般流程如下：
从检索后面都属于检索模型的范畴。
搜索结果排序是搜索引擎最核心的部分，很大程度度上决定了搜索引擎的质量好坏及用户满意度。实际搜索结果排序的因子有很多，但最主要的两个因素是用户查询和网页内容的相关度，以及网页链接情况。这里主要介绍网页内容和用户查询相关的内容。判断网页内容是否与用户査询相关，这依赖于搜索引擎所来用的检索模型。检索模型是搜索引擎的理论基础，为量化相关性提供了一种数学模型，是对查询词和文档之间进行相似度计算的框架和方法。其本质就是相关度建模。
二、信息检索特点
检索有文件检索、数据库检索、信息检索等，常用的是数据库检索和信息检索。
| 数据库检索 | 信息检索 | |
| 匹配程度 | 精确 | 模糊 |
| 查询语言 | SQL | 自然语言 |
| 查询描述 | 完善 | 不完善 |
| 数据规模 | TB | PB |
| 评价标准 | 客观（二元） | 主观（多元） |
| 检索模型 | 决定性 | 可能性 |
信息检索任务是对索引结果进行相关性排序。
影响结果排序的因素有相似度、网页质量、用户偏好等等。
三、检索模型分类
检索模型一般有布尔模型、向量空间模型、概率模型、知识模型。
信息检索模型四元组[D, Q, F, R(qi, dj)]
- D: 文档集的机内表示
- Q: 用户需求的机内表示
- F: 文档表示、查询表示和它们之间的关系的模型框架(Frame)
- R(qi, dj): 给query qi 和document dj评分
四、BM25算法
BM25算法，通常用来作搜索相关性平分。对Query进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。
BM25算法的一般性公式如下：
其中，Q表示Query，qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）；d表示一个搜索结果文档；Wi表示语素qi的权重；R(qi，d)表示语素qi与文档d的相关性得分。
下面我们来看如何定义Wi。判断一个词与一个文档的相关性的权重，方法有多种，较常用的是IDF。这里以IDF为例，公式如下：
其中，N为索引中的全部文档数，n(qi)为包含了qi的文档数。
根据IDF的定义可以看出，对于给定的文档集合，包含了qi的文档数越多，qi的权重则越低。也就是说，当很多文档都包含了qi时，qi的区分度就不高，因此使用qi来判断相关性时的重要度就较低。
我们再来看语素qi与文档d的相关性得分R（qi，d）。首先来看BM25中相关性得分的一般形式：
其中，k1，k2，b为调节因子，通常根据经验设置，一般k1=2，b=0.75；fi为qi在d中的出现频率，qfi为qi在Query中的出现频率。dl为文档d的长度，avgdl为所有文档的平均长度。由于绝大部分情况下，qi在Query中只会出现一次，即qfi=1，因此公式可以简化为：
从K的定义中可以看到，参数b的作用是调整文档长度对相关性影响的大小。b越大，文档长度的对相关性得分的影响越大，反之越小。而文档的相对长度越长，K值将越大，则相关性得分会越小。这可以理解为，当文档较长时，包含qi的机会越大，因此，同等fi的情况下，长文档与qi的相关性应该比短文档与qi的相关性弱。
综上，BM25算法的相关性得分公式可总结为：
从BM25的公式可以看到，通过使用不同的语素分析方法、语素权重判定方法，以及语素与文档的相关性判定方法，我们可以衍生出不同的搜索相关性得分计算方法，这就为我们设计算法提供了较大的灵活性。
五、BM25算法实现
bm25.py
#!/usr/bin/env python # -*- coding:utf-8 -*- ''' 作者:chl 时间:2017/11/23 用图:bm25算法 ''' import math class BM25(object): def __init__(self, docs): self.D = len(docs) self.avgdl = sum([len(doc)+0.0 for doc in docs]) / self.D self.docs = docs self.f = [] # 列表的每一个元素是一个dict，dict存储着一个文档中每个词的出现次数 self.df = {} # 存储每个词及出现了该词的文档数量 self.idf = {} # 存储每个词的idf值 self.k1 = 1.5 self.b = 0.75 self.init() def init(self): for doc in self.docs: tmp = {} for word in doc: tmp[word] = tmp.get(word, 0) + 1 # 存储每个文档中每个词的出现次数 self.f.append(tmp) for k in tmp.keys(): self.df[k] = self.df.get(k, 0) + 1 for k, v in self.df.items(): self.idf[k] = math.log(self.D-v+0.5)-math.log(v+0.5) def sim(self, doc, index): score = 0 for word in doc: if word not in self.f[index]: continue d = len(self.docs[index]) score += (self.idf[word]*self.f[index][word]*(self.k1+1) / (self.f[index][word]+self.k1*(1-self.b+self.b*d / self.avgdl))) return score # 总共有N篇文档，传来的doc为查询文档，计算doc与所有文档匹配 # 后的得分score，总共有多少篇文档，scores列表就有多少项， # 每一项为doc与这篇文档的得分，所以分清楚里面装的是文档得分， # 不是词语得分。 def simall(self, doc): scores = [] for index in range(self.D): score = self.sim(doc, index) scores.append(score) return scores
六、应用示例
（1）python脚本
sortnovel.py
#!/usr/bin/env python # -*- coding:utf-8 -*- ''' 作者:chl 时间:2017/11/24 用图:小说排序 ''' #调用到Django的model块 import os, django os.environ.setdefault("DJANGO_SETTINGS_MODULE", "novel0.settings")# novel0 项目名称 django.setup() import jieba from search import utils from search.bm25 import BM25 from novel.models import Novel class Sortnovel(object): def __init__(self, docs): self.novels = Novel.objects.filter().order_by() self.sents = [] #所有原文档 self.docs = [] #所有文档列表,词表示 for novel in self.novels: sent = novel.novelname + ":" + novel.description self.sents.append(sent) docs.append(self.dealwords(sent)) #分词处理 self.bm25 = BM25(docs) def top(self, query): print(self.dealwords(query)) self.top = list(enumerate(self.bm25.simall(self.dealwords(query)))) self.sorttop = sorted(self.top, key=lambda x: x[1], reverse=True) #排序,匿名函数 i = 0 self.list = list(map(lambda x: x[0], self.sorttop)) print(self.list) #输出序号 searchtotal = object for index in self.list: #输出id，书名，得分 print(self.novels[index].novelid, self.novels[index].novelname, self.sorttop[i][1]) i += 1 return self.list def top1(self, query, limit = 10): print(self.dealwords(query)) self.top = list(enumerate(self.bm25.simall(self.dealwords(query)))) self.sorttop = sorted(self.top, key=lambda x: x[1], reverse=True) #排序,匿名函数 i = 0 self.list = list(map(lambda x: x[0], self.sorttop))[:limit] print(self.list) for index in self.list[:limit]: print(self.novels[index].novelid, self.novels[index].novelname, self.sorttop[i][1]) i += 1 return self.list def dealwords(self, sent): words = list(jieba.cut(sent)) #分词 words = utils.filter_stop(words) #过滤没意义的词 return words if __name__ == "__main__": docs = [] s = Sortnovel(docs) print(s.sents) print(docs) print("f词频： ", s.bm25.f) #谋篇文章中的词频 print("df词频： ", s.bm25.df) #所有文章的词频 print("idf权重： ", s.bm25.idf) #词的权重 query = "一个理科男穿越到唐末，在这个英雄辈出的时代逍遥地生存下去。" # qwords = s.dealwords(query) #查询语句 print() s.top1(query, 5) print(s.top) print(s.sorttop)
结果：
注意：本脚本主要服务于我的Django程序，里面调用了Django的model块，本地数据库配置等等，不能直接copy，仅供参考学习。
这里提供一个过滤不重要词语的脚本utils.py。
utils.py
#!/usr/bin/env python # -*- coding:utf-8 -*- ''' 作者:chl 时间:2017/11/23 用图:过滤垃圾词 ''' import os import re import codecs stop_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'stopwords.txt') stop = set() fr = codecs.open(stop_path, 'r', 'utf-8') for word in fr: stop.add(word.strip()) fr.close() re_zh = re.compile('([\u4E00-\u9FA5]+)') def filter_stop(words): return list(filter(lambda x: x not in stop, words)) def get_sentences(doc): line_break = re.compile('[\r\n]') delimiter = re.compile('[，。？！；]') sentences = [] for line in line_break.split(doc): line = line.strip() if not line: continue for sent in delimiter.split(line): sent = sent.strip() if not sent: continue sentences.append(sent) return sentences
滤词文件：stopwords.txt
分词工具：https://pypi.python.org/pypi/jieba/
（2）Django运用
views.py部分代码
#响应搜索页面 def search(request): global user request.encoding='utf-8' message = "" try: message = request.GET['kw'] except Exception as e: print(e) finally: page = 1 if request.GET.get("page"): page = int(request.GET.get("page")) if request.GET.get("kw1"): message = request.GET.get("kw1") if message[:4] == "BM25" or message[:4] == "bm25": # searchtotal = # print(docs) print("这是BM25算法----------------------------------------") print("查询语句 ", message[4:]) stoplist = sortnovel.top(message[4:]) searchtotal = [] searchtotal1 = Novel.objects.filter().order_by() for inovel in stoplist: searchtotal.append(searchtotal1[inovel]) del sortnovel.top #这里必须要销毁这个list对象，否则第二次查询会出现'list' object is not callable错误，即list()情况。 else: searchtotal = Novel.objects.filter(novelname__contains=message).order_by("novelid") novels = searchtotal[:10] … …
结果：
搜索结果：
后台显示：
七、体会与总结
搜索引擎非常重要，BM25算法只是其中的一个分支，机器语言和算法才是核心，加油吧！
八、参考
【1】[转]搜索引擎的文档相关性计算和检索模型（BM25/TF-IDF） - CSDN博客
http://blog.csdn.net/heiyeshuwu/article/details/43429447
【2】文本相似度-bm25算法原理及实现 - 简书
http://www.jianshu.com/p/1e498888f505
【3】BM25相关度打分公式 - 白帆mvp - 博客园
https://www.cnblogs.com/hdflzh/p/4034602.htm
