前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >简单的搜索引擎搭建

简单的搜索引擎搭建

作者头像
CodeInHand
发布2018-06-07 11:52:19
1.2K0
发布2018-06-07 11:52:19
举报
文章被收录于专栏:Pytorch实践

本文简述一下搜索引擎的搭建过程,具体描述的搜索是文本类型的搜索,而非网页搜索。对于网页搜索的排序,需要有很多考虑,例如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算法实现的主要代码如下:

代码语言:javascript
复制
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,本公众号之前有描述过如何计算文本相似度计算的深度学习模型。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-05-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 CodeInHand 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 搜索算法
  • 排序算法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档