PPTCON.md

A组部分PPT内容

我们做了什么

• 中文分词
• 倒排索引
• 检索服务器

中文分词

一个例子

同一句话 下雨天留客天留人不留

不同的分词 下雨，天留客，天留人不留 下雨天，留客天，留人不？留

为什么要进行中文分词

词是最小的能够独立活动的有意义的语言成分

英文单词之间是以空格作为自然分界符的

而汉语是以字为基本的书写单位，词语之间没有明显的区分标记

因此，中文词语分析是中文信息处理的基础与关键

我们是如何实现的

信息量

信息奠基人香农（Shannon）认为“信息是用来消除随机不确定性的东西”

[信息量计算公式]

冲突区间

将至少有两个词冲突的区间定义为冲突区间

如：天空洞

冲突区间的计算过程

[流程图]

分词

通过统计词频, 我们可以根据词语出现的频率计算得到每个词语的信息量

信息量越低, 则表示该词语越接近通常语义, 通过选出总信息量最低的词语组合来完成分词

算法

1. 以冲突区间为单元，根据词频字典找出区间中存在的所有可能词语, 记录其位置以及长度

2. 遍历词语的组合，并且每个组合中不存在冲突，填充上单个字

3. 找出信息量最小的组合，可以认为该组合是最接近语义的分词形式

流程图

[此处应有流程图]

为什么需要冲突区间

枚举输入字符序列的所有词语组合可能太多

使用冲突区间的方式类似于取局部最优解

可减少运算

倒排索引

倒排索引的三个部分

• 索引的建立
• 关键词的检索
• 序列化与反序列化

索引的建立

（再说索引的建立之前先要陈述一些细节）

章节次序

为了保存章节的次序，则首先需要获得次序

order("1.2.1 有理数.txt")

= 1 * 10000 + 2 * 100 + 1

= 10201

所有的文章名都会被标准化成这种形式

比如"第一章小结.txt"也被修改为"1.N.0 第一章小结.txt"

建立的步骤

记录章节顺序，省略掉在检索时再比较章节次序的时间，并按照章节顺序逐个建立索引

对每个文章，将分词结果作为关键词列表，并将每个关键词在文章中的信息记录下来

将计算结果保存为关键词映射文件信息列表的键值对容器中

关键词的检索

1. 检索关键词时，取所有关键词所映射的文件信息列表的交集
2. 对所获得到的文件信息列表进行打分排序
3. 返回排序之后的文件路径列表

打分/排序

根据以下步骤进行打分:

[流程图一张]

[

流程图表述

遍历每个关键词、文章信息列表的键值对

遍历每个文章信息

判断关键词是否出现在标题中

若出现在标题中，则该文章打分增加1000，且标记主概念文章路径

若未出现在标题中且主概念文章路径被标记，则该文章打分减少与主概念文章路径距离的绝对值*100

文章打分增加该关键词出现的次数 * 其信息量

]

序列化与反序列化

通过将建立好的倒排索引对象序列化到文件中, 实现从文件反序列化, 可以有效减少构建倒排索引对象时所需要的时间

[一份序列化之后的文件的格式图]

检索服务器

检索服务器处理哪些任务

• 监听同一台服务器上其它进程的请求
• 通过倒排索引进行检索并返回给相应的进程检索的结果

[一张检索服务器和PHP进程通信的示意图(包含多线程部分)]