电商搜索引擎-算法选型

我们日常使用的搜索引擎源自现代信息检索系统学术界对现代信息检索的定义一般是： 从大规模非结构化数据的集合中找出满足用户信息、需求的资料的过程。

这里的“非结构化”其实是针对经典的数据库而言的数据库里的记录都有严格的字段定义（Scheme），是“结构化”数据的典型代表例如每道菜都有名字，想要吃鱼时，查询“水煮鱼”就非常高效。

相反，“非结构化”没有这种严格的定义，计算机世界存储的大量文本就是一个典型的代表一篇文章如果没有进行特殊处理，对于其描述的菜叫什么名字、需要准备哪些食材等信息，我们是一无所知的自然，我们也就无法将其中的内容和已经定义好的数据库字段进行匹配，这也是数据库在处理非结构化数据时非常乏力的原因之一。

此时，信息检索的技术可以极大地帮助我们非结构化数据的特性是没有严格的数据格式定义，这点决定了信息检索的如下两个核心要素：

• 相关性：用户查询和返回结果之间是否有足够的相关性缺乏了严格的定义，自然语言所表达的含义是相当丰富的，如何让计算机更好地‘理解”人类的信息需求是关键。
• 及时性：用户输入查询后多久能够获得返回的结果要解决相关性，就要设计合理的模型，那么模型的复杂度可能会提升，相应的计算量也会变大，因此需要高效率的系统实现。

二、相关性

2.1 布尔模型（ Boolean Model)

假设我非常喜欢吃川菜中的水煮鱼，其香辣的味道令人难忘那么，如果我想看一篇介绍川菜文化的文章，最简单的方法莫过于看看其中是否提到关键词“水煮鱼”了。如果有（返回值为真），那么我认为就是相关的；如果没有（返回值假），那么我就认为其不相关。

就是最基本的布尔模型如果将本次查询转换为布尔表达式也很简单，就一个条件：

水煮鱼

当然，你会觉得，中华饮食源远流长，川菜经典怎么会只有水煮鱼呢？没错，我还非常喜爱粉蒸排骨，它是小时候逢年过节的必备菜肴 那么，将条件修改一下

水煮鱼 OR 粉蒸排骨

哈哈，这下，不仅仅是水煮鱼，谈到“粉蒸排骨”的文 也会认定为其与川菜文化相关 如果想看看在上海哪家店可以吃到这些美食呢？再修改下：

（水煮鱼 OR 粉蒸排骨） AND 上海

这里，“上海”是必要条件，而水煮鱼或粉蒸排骨，有一样就可以啦。最后，我们可以看看哪些文章提到了上海的餐馆经营川菜，而且至少提供水煮鱼和粉蒸排骨两味佳肴中的一道只要理解了布尔表达式，就能理解信息检索中的布尔模型 近些年，除了基本的 AND、OR NOT 操作，布尔模型还有所扩展。

其中，最常见的是邻近操作符（Proximity），用于确保关键词出现在一定的范围之内。其假设就是不同的搜索关键词，如果它们出现的位置越近，那么命中结果的相关性就越高。

总体上来看，布尔模型的优点是简单易懂，系统实现的成本也较低。不过，它的弱点是对相关性刻画不足。相关与否是个模糊的概念，有的文章和查询条件关系密切，非常符合用户的信息需求，而有些不尽然。仅仅通过“真”和“假”2个值来表示，过于绝对，也没有办法体现其中的区别 那么，有没有更好的解决方案呢？

2.2 基于 排序 的布尔模型（ Ranked Boolean Model )

为了增强布尔模型，需要考虑如何为匹配上的文档来打分。相关性越高的文档其获得的分数就越高。第一个最直观的想法就是：每个词在不同文档里的权重是不一样的，可以通过这个来计算得分。这里介绍使用最为普遍的 tf- idf机制。

假设我们有一个文档集合（Collection）, c表示整个集合，d表示其中一篇文章，t表示一个单词。那么这里tf表示词频（Term Frequency），就是一个词t在文章中（或是文章的某个字段中）出现的次数。一般的假设是，某个词在文章中的tf越高，表示该词t对于该文而言越重要。当然，篇幅更长的文档可能拥有更高的tf值，我们会在后面Lucene的介绍中讨论如何计算可以使得tf更合理。

同时，另外一个常用的是 idf，它表示逆文档频率（Inverse Document Frequency）。首先，df表示文档频率（ Document Frequency ），即文档集合c中出现某个词t文档数量。一般的假设是，某个词t在文档集合c中，出现在越多的文档中，那么其重要性就越低，反之则越高。

刚开始可能会感觉有点困惑，但是仔细想想这并不难理解。好比“的、你、我、是”这种词经常会出现文档中，但是并不代表什么具体的含义。再举个例子，在讨论美食的文档集合中，“美食”可能会出现在上万篇文章中，但它并不能使得某篇文档变得特殊。相反，如果只有3篇文章讨论到水煮鱼，那么这3篇文章和水煮鱼的相关性就远远高于其他文章。 “水煮鱼”这个词在文档集合中就应该拥有更高的权重。对此，通常用df的反比例指标idf表示其重要性，基本公式如下：

其中N是整个文档集合中文章的数量，log 是为了确保 idf 分值不要远远高于tf而埋没tf的贡献，默认取10为底。所以单词t的df越低，其idf就越高，t的重要性就越高。那么综合起来， tf-idf的基本公式表示如下：

也就是说，一个单词t，如果它在文档中的词频tf越高，且在整个集合中的idf也很高，那么t对于d而言就越重要。

2.3 向量空间模型（ Vector Space Model )

排序布尔模型是一种基于加权求和的打分机制，下面将介绍一个比排序布尔模型稍微复杂一点的向量空间模型。此模型的重点，就是将某个文档转换为一个向量 还是以上面的文章为例。

统计其中的单词，假设去重后一共有50个不同（Unique）的词，那么该文梢的向量就是50个纬度，其中每个纬度是其对应单词的tf-idf值，看上去就像这样:

（四川 = 1.84 ，水煮鱼 = 6.30 ，专辑 = 6.80 ,…… )

当然，在系统实现的时候，不会直接用单词来代来表纬度，而是用单词的ID。如此一来，一个文档集合就会转换为 一组向量，每个向量代表一篇文档。这种表示忽略了单词在文章中出现的顺序，可以大大简化很多模型中的计算复杂度 ，同时又保证了相当的准确性，我们通常也称这种处理方式为词包（Bag Of Word），这点在第一篇的文本分类和聚类中已经有所提及。

同理，用户输入的查询也能转换为一组向量，只是和文档向量相比较，查询向量的维度会非常低。最后，相关性问题就转化为计算查询向量和文档向量之间的相似度了。在实际处理中，最常用的相似性度量方式是余弦距离。因为它正好是一个介于0和1之间的数，如果向盘一致就是1，如果正交就是0，这也符合相似度百分比的特性，具体的计算公式如下：

其图形化解释如图所示：

相对于标准的布尔数学模型，向量空间模型具有如下优点：

• 基于线性代数的简单模型，非常容易理解

• 词组的权重可以不是二元的，例如采用 tf-idf 这种机制

• 允许文档和索引之间连续相似程度的计算，以及基于此的排序，不限于布尔模型的 “真”“假”两值

• 允许关键词的部分匹配

当然，基本的向量空间模型也有很多不足之处：

例如对于很长的文档，相似度得分不会很理想；没有考虑到单词所代表的语义，还是限于精准匹配；没有考虑词在文档中出现的顺序等。

三、及时性

经过前面的探讨，我们发现：要解决相关性，就要根据需求设计合理的模型，越是精细模型，其计算的复杂度往往也就越高。同时，我们又要保证非常高的查询效率。互联网时代，用户就是普通的冲浪者，“爽快”的体验至关重要。因此 搜索引擎的结果处理必须是秒级的，通常不能超过3秒。坐在电脑前等待几分钟只是为了知道明天广州的天气情况是无法想象的，也是无法接受的。相关性计算的复杂度和速度，看上去就成了一对无法调和的矛盾体，该如何解决呢？

这里必须要提到检索引擎最经典的数据结构设计一一倒排索引（或者称逆向索引）。先让我们假想一下，你是一个热爱读书的人，当你进入图书馆或书店的时候，会怎样快速发现自己喜爱的图书呢？没错，就是看书架上的标签。如果看到 个架子上标着“烹饪 ·地美食”，那么恭喜你，离介绍川菜的书就不远了。倒排索引做的就是贴标签的事情。看看下 面的例子，这是没有经过倒排索引处理的原始数据，当然实际中的文章不会如此之短。

对于每篇文章的内容，我们先进行中文分词，然后将分好的词作为该篇的标签。例如对ID为1的文章“最上瘾的绝味川菜”进行分词，可分为如下5个词：

最，上瘾，的，绝味，川菜

那么文章1就会有5个关键词标签

再分析ID为2的文章“大厨必读系列：经典川菜”，它可以分为如下5个词：

大厨，必读，系列，经典，川菜

如果和第1次的标签结果合并起来

请注意ID为5的关键词“川菜”，它在文章1和2中都出现过，所以我们会将其对应的文档ID写上“1，2”

如此逐个分析完所有5篇文章之后，我们会得到表如下 ，这就是倒排索引的原型。

这里一共出现了18个不重复的单词，我们将这个集合称为文档集合的词典或词汇（Vocabulary）。从上面这个结构可以看出，建立倒排索引的时候，是将文档一关键词的关系转变为关键词一文档集合的关系，同时逐步建立词典。有了这种数据结构，你会发现关键词的查询就像在图书馆里根据标签找书一样方便快捷，效率得到大大提升。例如，我们查找：

川菜 AND 舌尖

通过查找“川菜”系统会返回文章ID：l、2、3；通过查找“舌尖”系统会返回文章ID：3、4,再取交集，我们就能找到文章3并进行返回。取交集的归并操作在计算机领域已经非常成熟，速度快得惊人。

考虑到布尔模型的邻近（Proximity）操作，或者其他的计算模型，我们还可以在数据结构中加上词的位置，以及tf－idf等信息，这里不再深入展开 此处最重要的结论是：我们可以通过倒排索引保持超高的效率。