: 邓小平安定军山 正向最大匹配: 邓小平/安定/ 正向分词时优先。
统计结果表明:单纯使用正向最大匹配的错误率为1/169，单纯使用反 统计结果表明:单纯使用正向最大匹配的错误率为1/169，单纯使用反向 最大匹配的错误率为1/245。逆向匹配的切分精度略高于正向匹配。 最大匹配的错误率为1/245。逆向匹配的切分精度略高于正向匹配。
2.基于统计的分词方法 相邻的字同时出现的次数越多，就越有可能构成一个词。 相邻的字同时出现的次数越多，就越有可能构成一个词。 用于系统自动识别新词。 用于系统自动识别新词。 3.基于理解的分词方法 在分词的同时进行句法、语义分析， 在分词的同时进行句法、语义分析，利用句法信息和语义 信息来处理歧义现象。 信息来处理歧义现象。
二.三级Cache的设计 三级Cache的设计
精确匹配 用户查询 一级cache 一级cache (内存) 内存) 精确匹配 二级Cache 二级Cache 磁盘） （磁盘） 二分查找 二分查找 索引 磁盘） （磁盘）
分词 例：“姚明和叶莉” 姚明和叶莉” 三级Cache 三级Cache (内存) 内存)
如:在长度为11的哈希表中已填有关键字为17，60，29的记录 在长度为11的哈希表中已填有关键字为 ，60，29的记录 的哈希表中已填有关键字为17 (哈希函数 H(key)=key MOD11)
③ 处理冲突的方法 为该关键字的记录找到另一个“ 的哈希地址。 为该关键字的记录找到另一个“空”的哈希地址。 例：开放定址法 Hi=(H(key)+di) MOD m (m=空间大小) (m=空间大小 空间大小) di=1, di=1,2,…,m-1 称线性探测再散列
只要是两次提交同样的查询，第二次返回时间总是0.001秒, 只要是两次提交同样的查询，第二次返回时间总是0.001秒 证明Cache的存在 的存在。 证明Cache的存在。
2.Cache的实现－哈希(Hash)表 2.Cache的实现－哈希(Hash)表 的实现 ① 什么是哈希表 不经过任何比较，一次存取便能得到所查记录。 不经过任何比较，一次存取便能得到所查记录。 在记录的存储位置和它的关键字之间建立一个对应关系 ② 哈希函数的构造方法 例：除留余数法 H(key)=key MOD p
查询:何润东西南北( 何润东” 查询:何润东西南北(“何润东”、“东西南北”两个词) 东西南北”两个词) 正向最大匹配: 何润东/ 正向最大匹配: 何润东/西/南北
归纳: 归纳: 首先用专有词典采用最大正向匹配分词，切分出部分结果； 首先用专有词典采用最大正向匹配分词，切分出部分结果； 剩余没有切分交给普通词典，同样采取正向最大匹配分词。 剩余没有切分交给普通词典，同样采取正向最大匹配分词。
一.什么是中文分词 把中文的汉字序列切分成有意义的词。 把中文的汉字序列切分成有意义的词。 一个/ 例：我/是/一个/学生 二.分词技术简述 1.基于字符串匹配的分词方法 按照一定的策略将待分析的汉字串与一个机器词库中的词条 进行匹配。 进行匹配。 常用分词方法： 常用分词方法： 正向最大匹配法（由左到右的方向） 正向最大匹配法（由左到右的方向） 有意/ 例：我 /有意/ 见/ 分歧 反向最大匹配法 意见/ 例：我 /有/意见/分歧
中文搜索引擎技术
第一节 中文分词技术 分词技术简述 分词技术 分词中的难题与发展 分词中的难题与发展 第二节 拼写检查错误提示 第三节相关提示功能分析 第三节相关提示功能分析 CACHE结构 第四节 CACHE结构 CACHE的实现原理 CACHE的实现原理 CACHE的设计 三级CACHE 三级CACHE的设计
四.分词中的难题 1.歧义识别 这个门把手坏了」 把手坏了 把手」 「这个门把手坏了」 －「把手」是个词 ； 把手拿开 拿开」 －「把手 不是一个词； 把手」 「请把手拿开」 －「把手」不是一个词； 元帅任命了一名中将 中将」 －「中将 是个词； 中将」 「元帅任命了一名中将」 －「中将」是个词； 产量三年中将增长两倍」 －「中将 不再是词。 中将增长两倍 中将」 「产量三年中将增长两倍」 －「中将」不再是词。 真歧义 「乒乓球拍卖完了」 乒乓球拍卖完了」 可以切分成「 可以切分成「乒乓 球拍 卖 完 了」、 也可切分成「 也可切分成「乒乓球 拍卖 完 了」。 2.新词识别 就是那些在字典中没收录过，但又确实能称为词的那些词。 就是那些在字典中没收录过，但又确实能称为词的那些词。 收录人名本身是一项巨大的工程 「吴官正在吉林考察」 吴官正在吉林考察 在吉林考察」 「听说温家宝物非常多」 过多专用人名的收录很容易出现问题 听说温家宝物非常多」 温家宝物非常多
“娱乐新闻报道”和“新闻娱乐报道”的相关提示完全一样。 娱乐新闻报道” 新闻娱乐报道”的相关提示完全一样。
三.如何计算相似性并排序输出
为什么增 加的是 “娱乐报 道”和 “新闻报 道”的相 关提示呢？ 关提示呢？
设每个单词都有一个权重值 IDF(word)＝ IDF(word) 是包含单词word的网页数目 是包含单词word的网页数目 得： IDF(娱乐 IDF(娱乐)=log(10/0.325)=1.488 娱乐)=log(10/0.325)=1.488 IDF(新闻 IDF(新闻)=log(10/0.563)=1.249 新闻)=log(10/0.563)=1.249 IDF(报道 IDF(报道)= log(10/0.172)=1.764 报道)= 权重是报道 娱乐> 报道> 权重是报道>娱乐>新闻 IDF(娱乐 新闻,报道) IDF(娱乐,新闻,报道) 娱乐, = IDF(娱乐) + IDF(娱乐) + IDF(娱乐) =4.501 IDF(娱乐 IDF(娱乐 IDF(娱乐 娱乐) 娱乐) 娱乐) IDF(娱乐 新闻,报道) >IDF(娱乐 报道)>IDF(新闻 报道) IDF(娱乐,新闻,报道) >IDF(娱乐,报道)>IDF(新闻,报道) 娱乐, 娱乐, 新闻, 查询权重相同，则按照用户查询次数由高到低排序输出。 查询权重相同，则按照用户查询次数由高到低排序输出。
感冒 感冒解痛散 感冒解痛颗粒 感冒解痛灵茶 个同音词词典, 维持着一个同音词词典, 多音字不区分
的中文纠错和拼音检索 使用的机制相同。 序标注 成拼音。 成拼音。 查询：罗华世界有风军 查询： 词长不限，专用词全部标注 词长不限，
五.最新进展 设计目标: 设计目标: 1.无长度限制 1.无长度限制 2.歧义包容 歧义包容: 2.歧义包容:将出现歧义的 各种可能性都包含进去， 各种可能性都包含进去， 作为分词的参考。 作为分词的参考。 方案：将关系数据库的词按 方案： 字打散， 字打散，并存放到层次 数据库中。 数据库中。 特色：分词长度限制 长度限制， 特色：分词长度限制，词的 长度变成了树的高度， 长度变成了树的高度， 每一次的匹配变成了树 的遍历。 的遍历。
二.错误提示流程
用户输入 匹配 查分词词典 不匹配 利用拼音标注程序对用户输入进行拼音标注 不做拼写检查
在同音词词典 里面扫描 拼音提示 流程 匹配 输出权重比较大 的几个提示结果
不匹配 不做提示
一.如何获得用户的查询信息 可对搜索引擎用户查询日志(LOG)文件做查询归类。 可对搜索引擎用户查询日志(LOG)文件做查询归类。 文件做查询归类 二.如何选择提示词 对于用户查询进行分词，然后对于分词后的结果来进行相似 对于用户查询进行分词，然后对于分词后的结果来进行相似 性计算。 性计算。
娱乐,新闻, 娱乐,新闻,报道
娱乐, 娱乐,报道
新闻, 新闻,报道
研究表明用户的查询有30%-40%是重复的 研究表明用户的查询有30%-40%是重复的。 是重复的。 一.一级Ca一级Cache 提交一个古怪的查询， 提交一个古怪的查询，
没找到 (找“叶莉”) 叶莉”
高频倒排文档（找“姚明词长： 1.最大分词词长：
小于等于3 小于等于3个中文字不切割 对于大于等于4个汉字的词将被分词。 对于大于等于4个汉字的词将被分词。
2.分词算法： 2.分词算法： 分词算法 查询: 工地方向导” 查询:“工地方向导” 正向最大匹配: 工地/方向/ 正向最大匹配: 工地/方向/导 反向最大匹配: 地方/ 反向最大匹配: 工/地方/向导