智能搜索技术解决方案

智能搜索项目 技术解决方案

目录

1. 2.

系统概述 ................................................................................................................................... 2 项目目标 ................................................................................................................................... 3 2.1 输入需求 ....................................................................................................................... 3 2.2 输出结果 ....................................................................................................................... 3 2.3 目标 ............................................................................................................................... 4 2.4 运行环境 ....................................................................................................................... 4 2.5 测试环境 ....................................................................................................................... 5 2.6 可靠性分析 ................................................................................................................... 5 总体设计 ................................................................................................................................... 6 3.1 智能纠错: ...................................................................................................................... 6 3.2 同义词扩展 ................................................................................................................... 7 接口设计 ................................................................................................................................... 9 4.1 外部接口 ....................................................................................................................... 9

3.

4.

智能搜索项目技术解决方案

5.

4.2 内部接口 ..................................................................................................................... 11 数据结构 ................................................................................................................................. 11 5.1 同义词词林数据结构 ................................................................................................. 11 5.2 智能纠错 ..................................................................................................................... 12

1. 系统概述

本项目完成为搜索引擎中的两个模块，功能分别为“同义词扩展”与“智能纠错”，并与卓望现有搜索引擎产品深度集成，为卓望搜索引擎提供更加友好的用户接口，提高搜索质量和用户满意度。性能上要求增加了相关“同义词扩展”和“智能纠错”模块之后，回答用户一个查询的时间小于100ms，具体功能描述如下：

(1) 智能纠错：搜索引擎自动地纠正用户搜索输入，推测用户真正想搜索的输

智能搜索项目技术解决方案

入。搜索的结果既包含用户的原始输入搜索结果，也包含纠正后的搜索结果，并在搜索结果中提示用户是否是想搜索纠正后的词。例如用户输入“宏楼梦”，系统提示是否用户希望搜索的关键词是“红楼梦”，并返回“宏楼梦”和“红楼梦”的搜索结果。所开发的产品必须与卓望数码已开发的搜索引擎深度集成。

(2) 同义词推荐：搜索引擎自动加上搜索关键词的同义词一起搜索，如搜“红

楼梦”，自动加上其另外的书名“石头记”进行搜索。所开发的产品必须与卓望数码已开发的搜索引擎深度集成。

2. 项目目标

本项目的主要任务就是用户输入的可能是错误的查询词，我们需要推荐用户可能打算输入的词，以及给定一个词，我们推荐其同义词。

2.1 输入需求

卓望公司提供查询日志，用于日志分析，统计词频，从而做高效的查询纠错和同义词扩展。

2.2 输出结果

图1给出了了本项目需要完成的功能。其工作流程如下：  首先用户输入一个查询词  给出查询词纠正后的词  给出其同义词扩展

智能搜索项目技术解决方案

搜索引擎智能纠错同义词扩展Hadoop平台查询日志

图1 主要功能

2.3 目标

在500MB的数据上，为了支持模糊检索，索引大小为350MB左右；单台机器（Intel 2.4G CPU，2RAM内存）回答一个查询的时间在100ms以内。在20GB的数据上，通过在两台机器（每台机器8核，Intel 2.4G CPU）进行多核并行处理，回答一个查询的时间在100ms以内。

2.4 运行环境

日志分析需要8各节点的Hadoop服务器，每台机器配置如下：  Intel x86兼容处理器，双核，主频2.0GHz以上  内存4GB以上

 硬盘200GB以上，7200转  节点之间采用千兆以太网连接。 运行环境的软件要求为：

 建议使用Ubuntu 10.04 LTS 32-bit或者 64-bit Server Edition

智能搜索项目技术解决方案

 Java 6的开发和运行环境

2.5 测试环境

测试环境 服务器两台，配置如下： CPU：IIntel® Xeon®CPU E5520 @ 2.4GHz 8核 内存：8G 硬盘配置：intel x25m g2 160G SSD硬盘4块客户端主机10台，普通PC Server配置； 全部主机在同一网段内，千兆以太网交换机。 测试数据 案例描述 测试步骤 测试指标要求 查询响应速度 在500MB的数据上，为了支持模糊检索，索引大小为350MB左右；单台机器（Intel 2.4G CPU，2RAM内存）回答一个查询的时间在100ms以内。在20GB的数据上，通过在两台机器（每台机器8核，Intel 2.4G CPU）进行多核并行处理，回答一个查询的时间在100ms以内。

2.6 可靠性分析

整个系统都应采用高可用性架构，无单点故障。系统整体可靠性达到99.999%。在部分节点发生故障后，能够根据日志恢复故障节点丢失的数据，保证数据不丢失、不错乱，保证数据一致性和正确性。

智能搜索项目技术解决方案

3. 总体设计

3.1 智能纠错:

为了衡量两个不同输入词的相似性，我们需要衡量词与词之间的相似性。例如衡量“宏楼梦”和“红楼梦”的相似性。传统的方法可以用编辑距离来衡量词之间的相似性，即从一个词转换为另外一个词所需要的最少原子操作次数（包括删除一个字，插入一个字，替换一个字）。例如“宏楼梦”和“红楼梦”的编辑距离是1。然而这种方法存在着两个问题：（1）由于汉字通常较短，这种相似性函数并不适合于汉字；（2）这种方法只考虑了汉字，而没考虑拼音。例如尽管“宏楼梦”和“宏梦”的编辑距离也是1， 但是显然“红楼梦”和“宏楼梦”更相似。因此我们不仅要考虑字形之间的相似性程度，还要考虑读音、声调等因素来衡量汉字之间的相似性，进而对查询结果进行打分排序。例如“红楼梦”和“宏楼梦”的拼音相同，因此他们的相似性更大。因此我们通过衡量两个词的读音相似程度，汉字相似程度，声调相似程度，字型相似程度等多重因素来考虑汉字之间的相似性。此外，我们还要考虑少数民资的发音，例如卷舌音等来进一步提高我们相似性函数的准确性。

给定一个查询词和多个历史查询（通过用户的查询日志获得），我们就可以根据这个相似性函数找到和查询词相似的所有相近词作为该查询词的纠错。一种简单的方法就是计算查询词和每个历史查询的相似度，然后返回给用户一个最相近的查询词。然而历史查询可能非常多，例如上亿，因此这种算法的效率很低。为了解决这种问题，我们提出高效的索引和算法来解决这一问题。假设我们只推荐拼音编辑距离不大于的所有查询，我们通过以下步骤来完成：

(1) 首先对于一组历史查询，我们把他们转换为拼音。

(2) 对于每个转换后的拼音，假设其长度为l，我们把其分为+1段，前段

长度为l/(+1) ，最后一段为l-* l/(+1) 。并且为每一段字串建一个倒排列表，记录包含该子段的所有查询（ID）。

(3) 给定一个查询q，我们按照下面的方法产生q的所有子序列，假设q的

长度为|q|：

智能搜索项目技术解决方案

a) 对于q的任意长度为i的字串，|q|  i |q|-，按照上面的方法生成

q的字串；

b) 在q末端添加j个字母，1j|q|-，，按照上面的方法生成q的字串； (4) 对于q的每个字串，查找倒排列表，倒排列表中的每个历史查询就是q

的一个候选集；

(5) 验证候选集，得到所有结果；

(6) 对结果进行打分排序，返回最终top-k个结果。

该方法不用遍历所有的历史查询，通过字串共享和字串倒排列表就可以进行有效地过滤，从而提高查询效率。图2 给出了智能纠错的框架图。

客户端 用户输入结果服务器端智能纠错结果排序 DHTMLEventsModificationsJavaScriptDOM客户端缓存Internet 请求服务器端缓存索引监听更新客户端 - 浏览器索引模块数据 图2 智能纠错

3.2 同义词扩展

为了支持同义词扩展，我们需要建立同义词表来支持同义词查询，提出快速的算法来实现高效的同义词推荐。

(1) 同义词字典：英文单词有WordNet来衡量英文单词的相近程度，中文也

智能搜索项目技术解决方案

有同义词词林来衡量词组的相似性。WordNet和同义词词林反映了常用词的相似程度，可以用于同义词扩展，例如Apple和苹果。但是这些方法存在两个问题：i) 对中文来说，没有免费的大规模高质量的同义词词林，因此我们要研究如何生成同义词词林；ii）当前的同义词词林不能很好的统计新的同义词，例如小强 = 蟑螂，xjdm = 兄弟姐妹。为了解决这一问题，我们需要研究新的算法来动态生成同义词词林。 我们按照下面的步骤生成同义词词林：

（a） 大规模数据统计：用Hadoop分布式计算平台，统计用户的查询

日志，计算词与词之间的贡献程度。我们利用map-reduce来进行词组的统计。

（b） 产生相关度比较高的词对，并利用搜索引擎验证两个词是否是同

义词，即分析搜索引擎的返回结果，看两个词之间出现的位置关系和频率关系。

（c） 系统自动返回最可能的同义词，然后人工进行审核。

（d） 同义词相似性分析：分析同义词之间的相似度，并给出分数，主

要通过统计进行分析得到。

(2) 同义词推荐算法：首先给定一个统一词典，每一行代表一组同义词，当

用户输入一行中任意一个词的时候，我们都可以返回其他相关的词。当用户输入一个查询词时，最简单的方法是，我们在同义词词林中找到该词，并推荐同行中其他词。然而这种算法效率较慢，不能做到实时的同义词扩展。为了解决这一问题我们建立一个基于Hash的方法： （a） 首先对于每个词，我们记录该词对应行的起始位置，例如“中国”，

100

（b） 当用户输入中国时，我们就可以找到文件100对应的位置是和中

国相关的词组，我们可以读取这一行获得中国的同义词 （c） 但是上面方法可能索引较大，因此我们对词语进行hash，把所有

单词hash到一个指定的空间，这样就可以控制索引的大小。 （d） 对返回的扩展词进行打分排序，给出一个分数从大到小的一个顺

智能搜索项目技术解决方案

序。

图3给出了同义词扩展的结构图。

在线同义词扩展索引同义词词林索引更新Hadoop分析查询日志

图 3 同义词扩展流程图

4. 接口设计

4.1 外部接口

(1) 查询纠错接口：

public String FindSimilarWords(String query) 输入参数：查询词 返回值：纠错后的词

功能：找到和查询词最接近的词

(2) 同义词扩展接口：

public vector FindSynonym(String query) 输入参数：查询词

返回值：和查询词相似的所有词

功能：找到查询词的扩展后的同义词

(3) 调用query log接口：

public boolean callQueryLog(String filename)

智能搜索项目技术解决方案

输入参数：查询日志的路径 返回值：log文件路径是否正确 功能：统计和分析用户日志

(4) 日志挖掘，统计频率：

public void computeWordOccurrence(string filename, map keyword2occurrence) 输入参数：

filename – 查询日志的路径

map keyword2occurrence – 关键词和对应的频率 返回值：无

功能：统计日志中每个词出现的频度和词对的频率

(5) 计算词之间的相似度

public double computeSimilarity (string keyword1, string keyword2) 输入参数：

keyword1 – 关键词1 keyword2 – 关键词2 返回值：相似性

功能：求解两个词之间的相似性

(6) 查询纠错索引生成：

public void createIndex(map keywords, SimlarWordIndex index) 输入参数：

map keywords– 关键词和对应的频率 SimlarWordIndex index – 创建后的索引 返回值：无 功能：创建索引

(7) 调用查询纠错索引：

public string findsimilarwords (String keyword，SimlarWordIndex index) 输入参数：

Keyword - 查询词

SimlarWordIndex index –索引 功能：找到和查询词最接近的词

(8) 同义词索引生成：

public void createIndex(map keywords,SynonymIndex index) 输入参数：

map keywords– 关键词和对应的频率 Synonym index – 创建后的索引 返回值：无 功能：创建索引

智能搜索项目技术解决方案

(9) 调用同义词索引：

public string findsimilarwords (String keyword，SynonymIndex index) 输入参数：

Keyword - 查询词

SynonymIndex index – 同义词索引 功能：找到查询词的扩展词

(10) 统计同义词相似度：

public double getSynonymSimilarity (string keyword1, string keyword2) 输入参数：

keyword1 – 关键词1 keyword2 – 关键词2 返回值：相似性

功能：求解两个词之间的同义词分数

4.2 内部接口

内部接口主要设计索引的维护和算法的实现。

5. 数据结构

5.1 同义词词林数据结构

KeywordID Keyword KeywordOccurrence KeywordType HashValue KeywordID, KeywordID Relevance 查询词ID，查询词ID 两个查询词的词义相似性 查询词ID 查询词 查询词出现次数 查询词所属类型 查询词的Hash值 智能搜索项目技术解决方案

5.2 智能纠错

KeywordCN KeywordPinyin KeywordOccurrence KeywordID, KeywordID Similarity 查询词ID，查询词ID 两个查询词的相似程度 同义词索引，其结构是： Map Keyword: 关键词 Location：文件中的位置，从该位置起一行就是所有的同义词 查询纠错索引： Map IL> Substring: 字串 IL：倒排列表，包含该字串的所有查询词 查询词（中文） 查询词（拼音） 查询词出现次数 SynonymIndex SimlarWordIndex