智能搜索项目技术解决方案目录1. 系统概述 (2)2. 项目目标 (3)2.1 输入需求 (3)2.2 输出结果 (3)2.3 目标 (4)2.4 运行环境 (4)2.5 测试环境 (5)2.6 可靠性分析 (5)3. 总体设计 (6)3.1 智能纠错: (6)3.2 同义词扩展 (7)4. 接口设计 (9)4.1 外部接口 (9)4.2 内部接口 (11)5. 数据结构 (11)5.1 同义词词林数据结构 (11)5.2 智能纠错 (12)1.系统概述本项目完成为搜索引擎中的两个模块，功能分别为“同义词扩展”与“智能纠错”，并与卓望现有搜索引擎产品深度集成，为卓望搜索引擎提供更加友好的用户接口，提高搜索质量和用户满意度。
性能上要求增加了相关“同义词扩展”和“智能纠错”模块之后，回答用户一个查询的时间小于100ms，具体功能描述如下：(1)智能纠错：搜索引擎自动地纠正用户搜索输入，推测用户真正想搜索的输入。
搜索的结果既包含用户的原始输入搜索结果，也包含纠正后的搜索结果，并在搜索结果中提示用户是否是想搜索纠正后的词。
例如用户输入“宏楼梦”，系统提示是否用户希望搜索的关键词是“红楼梦”，并返回“宏楼梦”和“红楼梦”的搜索结果。
所开发的产品必须与卓望数码已开发的搜索引擎深度集成。
(2)同义词推荐：搜索引擎自动加上搜索关键词的同义词一起搜索，如搜“红楼梦”，自动加上其另外的书名“石头记”进行搜索。
所开发的产品必须与卓望数码已开发的搜索引擎深度集成。
2.项目目标本项目的主要任务就是用户输入的可能是错误的查询词，我们需要推荐用户可能打算输入的词，以及给定一个词，我们推荐其同义词。
2.1输入需求卓望公司提供查询日志，用于日志分析，统计词频，从而做高效的查询纠错和同义词扩展。
2.2输出结果图1给出了了本项目需要完成的功能。
其工作流程如下：●首先用户输入一个查询词●给出查询词纠正后的词●给出其同义词扩展图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 EditionJava 6的开发和运行环境2.5测试环境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 给出了智能纠错的框架图。
服务器端客户端图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给出了同义词扩展的结构图。
图 3 同义词扩展流程图4.接口设计4.1外部接口(1)查询纠错接口：public String FindSimilarWords(String query)输入参数：查询词返回值：纠错后的词功能：找到和查询词最接近的词(2)同义词扩展接口：public vector<String> FindSynonym(String query)输入参数：查询词返回值：和查询词相似的所有词功能：找到查询词的扩展后的同义词(3)调用query log接口：public boolean callQueryLog(String filename)输入参数：查询日志的路径返回值：log文件路径是否正确功能：统计和分析用户日志(4)日志挖掘，统计频率：public void computeWordOccurrence(string filename, map<string, int> keyword2occurrence)输入参数：filename –查询日志的路径map<string, int> keyword2occurrence –关键词和对应的频率返回值：无功能：统计日志中每个词出现的频度和词对的频率(5)计算词之间的相似度public double computeSimilarity (string keyword1, string keyword2)输入参数：keyword1 –关键词1keyword2 –关键词2返回值：相似性功能：求解两个词之间的相似性(6)查询纠错索引生成：public void createIndex(map<string, int> keywords, SimlarWordIndex index) 输入参数：map<string, int> keywords–关键词和对应的频率SimlarWordIndex index –创建后的索引返回值：无功能：创建索引(7)调用查询纠错索引：public string findsimilarwords (String keyword，SimlarWordIndex index)输入参数：Keyword - 查询词SimlarWordIndex index –索引功能：找到和查询词最接近的词(8)同义词索引生成：public void createIndex(map<string, int> keywords,SynonymIndex index)输入参数：map<string, int> keywords–关键词和对应的频率Synonym index –创建后的索引返回值：无功能：创建索引(9)调用同义词索引：public string findsimilarwords (String keyword，SynonymIndex index)输入参数：Keyword - 查询词SynonymIndex index –同义词索引功能：找到查询词的扩展词(10)统计同义词相似度：public double getSynonymSimilarity (string keyword1, string keyword2)输入参数：keyword1 –关键词1keyword2 –关键词2返回值：相似性功能：求解两个词之间的同义词分数4.2内部接口内部接口主要设计索引的维护和算法的实现。