搜索引擎-一种提示词推荐算法

    　　搜索引擎可以说目前所有互联网应用里技术含量最高的一种。尽管应用形式比较简单：用户输入查询词，搜索引擎返回搜索结果。但是，搜索引擎需要达到的目标：更全、更快、更准。如何让搜索结果更准确始终是搜索引擎的一大难题。

　　公司最近在开发某行业的垂直搜索引擎，我作为该项目组的核心成员主要是负责核心算法的研究工作。我也是刚开始接触这个行业，目前还处于摸索阶段，还有很长的路要走。

言归正传，先谈一下这个项目的背景。这个项目是一个行业性质的垂直搜索引擎。用户分为两大类：普通用户、专业用户。整个项目分为：爬虫技术组，引擎组，大数据分析组和算法组。引擎的爬虫、词库的建立和引擎的选型都不是本文的重点，就一笔带过，重点在于推荐算法的设计。

一、网络爬虫

　　系统的数据，需要从几个专业网站进行抓取。尝试了几个爬虫，最后选取heritrix最为我们的爬虫框架，选取它的原因主要是感觉配置项虽然多，但是比较灵活，特别适合我们的要求。当然，爬从技术组也自己尝试实现了一个爬虫，主要是爬取地址比较固定几种数据。

二、词库的建立

　　词库初步分为专业主题词、行业普通词库、一般通用词库、废词库、还有用于感情分析的词库。

专业词库的实现前期是采取人工的方式来处理的，并制作了若干的辅助工具，供专业人员来挑选、合并、删除主题词的操作。

后面几种词库的实现，是先选用了搜狗等几种输入法的词库库为基础，在这些词库的基础上对爬虫爬出来的文档进行向量化。

三、引擎的搭建

　　通过对采集的数据进行去噪、分段、特征提取，然后把相应的数据导入到solr里。

四、推荐算法

　　当用户输入关键词查询的时候，如何让用户查询更准确呢？我们设想，针对用户的输入，我们如果能给出若干个和用户输入的关键词相似度很近的词，以这些作为查询条件，如果我们的算法足够好，搜索出来的结果会大大增加检索的准确度。下面给出具体的算法思路：

从向量化的角度来看，每一篇文档都对应一个向量，其中表示特征项i.

是一个向量由词、词的位置、TF等义项来确定的。对于版本1，我们只取了词、词的位置。我们先用分类规则，把文档分成若干类，基于每一类进行如下计算：

表示两个特征项的相似度。

我们定义一下距离公式

 

我们对于每个文档的特征项，两两求出特征项的相似度。通过这个距离公式

我们可以得出，对于每一个分类，以这些特征项为顶点，以相似度距离为边，就构

成了如下的无向图。

     （lawnet）

　　类比于wordnet和知网的hownet，我们称这个无向图，为lawnet。

　　那我们的设想问题就转化为：选取任意一个顶点，找出若干个（譬如10个）由这些顶点组成的最小生成树或者边权之和最小的最小子图。这是一个局部最优的随机问题。也就是说，我们只需要满足用户认可的体验程度即可，如果概率为90%，也就是说，当用户输入10000次，我们能成功给出9000次的提示词就行了。

目前的解法我尝试了两种：

　　一种PRIM算法。

　　第二种算法：先通过floyd算法，算出任意两点的最短距离，作为一个边；这些边就组合成一个集合。然后给任意的顶点，从这个边集合里找出包含这个顶点的前N个最小边。