第四章 4.3 分词原理 Chinese Word Parsing Algorithm

对索引网页信息的预处理包括网页分析和倒排文件索引两个部分，中文自动分次是网页分析的前提。文档由被称作特征项的索引词组成，网页分析是将一个文档表示 为特征项的过程。在提取特征项时，中文又面临了与英文处理不同的问题。中文信息和英文信息有一个明显的差别：英语单词之间用空格分隔；而在中文文本中，词 与词之间没有天然的分隔符，中文词汇大多是由两个或两个以上的汉字组成的，并且语句是连续书写的。这就要求在对中文文本进行自动分析前，先将整句切割成小 的词汇单元，即中文分词（或中文切词)。

用具体例子来说明，就是如何把“我的笔记本”这样连续书写的语句切分为“我”，“的”和“笔记本”三个词汇单元。 在检索和文档分类系统中，自动切词系统的速度影响整个系统的效率。中文信息的检索主要有两种：基于字的检索和基于词的检索。基于单字的检索系统建立单字索 引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。

1、算法介绍

自动分词的基本方法有：基于字符串匹配的分词方法和基于统计的分词方法。

基于字符串匹配的分词方法

这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：

1) 正向最大匹配；

2) 逆向最大匹配；

3) 最少切分（使每一句中切分出来的词数最小）

还可将上述各种方法相互组合，例如，可以将正向最大匹配方法和你想最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245（这可能是因为汉语的中心语靠后的特点）。对于机械分词方法，可以建立一个一般的模型，形式地表示为ASM(d,a,m)，即Automatic Segmentation Model，其中，

d：匹配方向，+表示正向，-表示逆向；

a：每次匹配失败后增加或减少字串长度（

m：最大或最小匹配标志，+为最大匹配，-为最小匹配。

例如，ASM(+, -, +)就是正向减字最大匹配法（Maximum Match based approach, MM），ASM(-, -, +)就是逆向减字最大匹配法(简记为RMM方法)，等等。对于现代汉语来说，只有m=+是实用的方法。

2、基于统计的分词方法

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。计算汉字X和Y的互现信息公式为：

其中P(X, Y)是汉字X、Y的相邻共现概率，P(X)、P(Y)分别是X、Y在语聊中出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 词汇切分算法最重要的指标是准确，在兼顾准确性的情况下也要考虑时间复杂性。下面具体介绍正向减字最大匹配法。

2、正向减字最大匹配法

正向减字最大匹配法切分的过程是从自然语言的中文语句中提取出设定的长短字串，与词典比较，如果在辞典中，就算一个有意义的词串，并用分隔符分隔输出，否则缩短字串，在词典中重新查找（辞典是预先定义好的）。

算法要求为：

输入：中文词典，待切分的文本d，d中有若干被标点符号分割的句子s1，设定的最大词长MaxLen。

输出：每个句子sl被切为若干长度不超过MaxLen的字符串，并用分隔符分开，记为s2，所有s2的连接构成d切分之后的文本。

算法思想:事先将网页预处理成每行是一个句子的纯文本格式。从d中逐句提取，对于每个句子s1从左向右以MaxLen为界选出候选字串w，如果w在词典中，处理下一个长为MaxLen的候选字段：否则，将w最邮编一个字去掉，继续与辞典比较：s1切分完之后，构成词的字符串或者此时w已经为单字，用分隔符隔开输出给s2。从s1中减去w，继续处理后续的字串。s1处理结束。

设文本含有句子的书目为m，句子的平均长度为k，辞典的条目为n。实际中m和k远远小于n，整个算法复杂度中起决定作用的步骤在于n相关的语句。因此算法的时间复杂度为O(mklogn)。

第五章 5.2 得分规则 An Simple Scoring Rule

出现关键词频度初始得分表

同一位置频度	1	2-3	4-7	8	9	>10
得分m	2	4	8	8	3	1

出现的位置初始得分表

位置	标题	段首	段尾	其余正文	URL	其他
得分比i	0.9	0.6	0.6	0.3	0.4	0.2

网页更新频度得分表

距查询的时间	一天	一天至三天	三天以后
得分比j	1.1	1.0	0.9

容易得出网页A的得分简单的计算公式

Score(A) = PageRank × β + ∑m × i × j

其中β是衰减系数，降低PageRank对最后排名的影响。

但是这么做有一个明显的缺陷，一个内容比较长的网页比一个内容比较短的网页在排序过程中有绝对的优势，即m的取值不够恰当，并且实际中并非重复出现的关键词就意味着高的相关度。那么如果做呢？我们需要根据网页的长度，对关键词的次数进行归一化， 也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)，比如，在某个一共有一千词的网页中keyword_1和keyword_2分别出现了12次和5次，那么它们的词频就分别是 0.012和 0.005。 我们将这两个个数相加，其和 0.017 就是相应网页和查询keyword_1和keyword_2相关性的一个简单的度量。概括地讲，如果一个查询包含关键词 w1,w2,...,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, ..., TFN。 （TF: term frequency)。 那么，这个查询和该网页的相关性M就是:TF1 + TF2 + ... + TFN。于是，得分规则变为Score(A) = PageRank × β + ∑M × i × j。

现在看来的得分公式还是有一个比较大的缺陷，直觉告诉我们相关性实质上是文章主题的相关性体现，从关键词的词频为主要入口还是有欠考虑到同时出现这些关键词之间的文章怎么突出他们之间的得分差异。如果一个关键词只在很少的网页中出现，通过它就容易限定搜索目标，它的权重也就应该大。反之如果一个词在大量网页中出现，我们看到它仍然不很清楚要找什么内容，因此它的权重应该小。概括地讲，假定一个关键词 w 在 Dw 个网页中出现过，那么 Dw 越大，w 产生的相关性权重越小，反之亦然。在信息检索中，使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为IDF），它的公式为log(D/Dw)其中D是全部网页数。于是上述相关性计算个公式就由词频的简单求和变成了加权求和，即M’ = TF1*IDF1 + TF2*IDF2 ＋... + TFN*IDFN。因此，得分计算公式改进为：Score(A) = PageRank × β +∑M’ × i × j。

第五章 5.1 网页等级算法全面阐释 Analysis of PageRank Algorithm

互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数，并用页面长度和html标签的重要性提示等进行权重修订。链接流行度技术通过其它文档链接到当前页面链入数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。PageRank计算页面的重要性，对每个链入赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。一个网页的重要性是一种内在的主观事情,这取决于读者兴趣,知识和态度. 但仍有许多可说是客观的相对重要性的网页. 简单地介绍如何给网页评级,有效衡量人们对网页的兴趣和重视程度。

PageRank的数学定义:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中：PR(A):页面A的网页级别,
PR(Ti)：页面Ti的网页级别，页面Ti链向页面A，
C(Ti)：页面Ti链出的链接数量，
d：阻尼系数，取值在0.85－0.95之间，一般取值为0.85，此因素直接影响迭代计算PageRank过程中的收敛速度

由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值 是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A 的排序贡献。

公式的来历：Google公司的创始人Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上 链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼 系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的 网页级别。PageRank的计算是封闭流通模型，所有页面的网页级别之和等于网页初始级别的和。

容易从PageRank的数学定义得出一个恒等表达式：

p = A p

其中p表示网页级别向量，A是链接矩阵。

求网页等级的问题转化为求A的特征向量，于是可以用迭代的方法求出。

给定任意一个初始向量S，不妨设为A，PageRank的计算可以如下

R₀ = S

Loop:

R_i+1 = A R_i

d = ||R_i||₁ - ||R_i+1||₁

R_i+1 = R_i+1 + dE

δ = ||R_i+1 - R_i||₁

while δ > ε

参数d表示迭代的收敛速度，一般取值为0.85。因为链接矩阵巨大，所以改进该算法的瓶颈在于无法用空间换取效率的做法，只有在精度和效率之间作折衷。

第五章 排序规则 Ranking Rules

用户输入查询关键词的时候需要对结果集作排序，如何排序这些网页使得最佳的结果呈现在前二十条结果中呢？主要因素有网页等级，关键词位置、关键词出现频率，用户点击日志等。

第四章 4.2 倒排索引基本原理 Principle of Inverted Index

Trie是效率最高的索引形式，下图表示由文本到的前缀树的创建过程。

插入操作的时间复杂度O(l)，其中l = max(length of word)；

查询的操作的时间复杂度O(l)；

删除操作的复杂度为O(n)，其中n = length of dictionary

Trie有消耗了大量内存且难以分块的缺点，同时伴随着I/O和瓶颈，一般来说用分块的倒排索引来解决内存不足问题，最后对分块的索引块做一次归并。倒排索引一般分成两个文件来存储，其中一个称为位置文件，纪录了词出现的文档和位置信息；另外一个是词典文件，纪录索引文本出现过的词，按照字符的顺序来存储。其中每个词有个指针，表示对应了第一个文件中的那个纪录。这样的结构保证了检索的时候词典能被保存在内存中，进一步的意义在于，检索词出现在哪些文档中以及位置能被迅速地找到。用一个例子来说明，有个这样的句子该怎么索引？
Tom lives in Guangzhou, I live in Guangzhou too.
分析过后剩下为
tom live guangzhou I live guangzhou
从词的角度出发一共有五个词，可以得出这样的一张词表

name	position	frequency
tom	1	1
live	5,22	2
guangzhou	10,27	2
i	20	1

文本的内容经过分析之后抽取出的内容见上表，即索引文件的内容，可以加对表的内容压缩存储优化，通常只对位置字段做差分压缩，最后将内容按照存储格式存储起来。

归并两个索引需要归并排序词典文件和合并位置文件：如果词典中的词不相同，连接相应的位置文件内容；如果词相同，连接相应位置条目的内容。一次归并操作的时间复杂度为O(n1 + n2)，其中n1和n2分别为索引词典的长度。索引器的效率一般在4Mb/min到1Gb/min之间，其中20%-30%的时间在做归并操作。对于归并操作没有很好的理论精确地得出最优的归并方式，本人采用词典长度接近的优先归并的方式，类似哈夫曼编码规则的顺序来归并，并取得了约10%的性能升。

第四章 4.1 准备工作 Prepare for Indexing

网页的内容经过爬虫爬取之后，按照不同的类型进行分析，成为相对“清洁”的文本之后就可以开始建立全文索引了。分析的过程包括大小写转换，过滤标点符号、没有意义的虚词和网页的格式代码。可以把分析看成是一个过滤的过程。

第三章 3.4 缓存 Search Engine Caching

缓存优化的核心思想是从避免无谓和重复的CPU计算、I/O调度来提高查询器的吞吐量。传统的缓存有两级：一是对结果集的缓存，纪录了查询的关键词和返回结果。如果相同的关键词被再次访问将得到快速地响应，同时过滤导致重复查询的计算量，提高系统的吞吐量。另外一个是对倒排索引的缓存，索引通常只保留最近、频繁被访问的索引段在内存中。这样的两级体系的优点在Rank-Preserving Two-Level Caching for Scalable Search Engines一文中做了详细地分析。
要介绍的是三级缓存结构:
第一级是结果缓存
查询分析器在内存和磁盘保存了大量的查询结果。分析所有的访问日志可以确定所有高频查询的关键词结果，然后保存起来。
第二级为集合缓存
一般查询的关键词为一些词的组合，例如：查询的关键词为A B C（检索的逻辑为AND），包含关键词A、B的各自命中文档列表都很大，而包含C的文档很少，不在一个数量级上，于是对A、B的交集结果进行缓存，并跟踪这些缓存数据在集群中的分布。这样的优化是针对大于等于三个词的情况，一般意义上看是在第一级缓存基础上的提升。
第三级为索引列表缓存
内存总是有限的，无法导入整个索引表，于是总是把最近/频繁访问到的索引置于内存中。
参考文献：Three-Level Caching for Efficient Query Processing in Large Web Search Engines

第三章 3.3 排队系统的优化 Application of Queueing Theory

排队系统的优化在集群计算中有着举足轻重的地位。此类优化问题分为两类：系统的最优设计和最优控制，前者称为静态最优问题，目的在于是系统达到最大效益，或者说在一定指标下是系统最为经济；后者为动态最优问题，是指对一给定的系统，如何运营可使给定的目标函数达到最优。
只对静态优化分析，对动态优化超出了目前以有的固定俗成的分析方法。
一般情形下，提高服务水平可减少用户等待的费用，却常常增加了服务器等硬件的投入成本。因此优化的目标之一就是使两者的费用之和为最小，并确定达到最优目标值的服务水平。假定在稳定状态下，个中费用都是按照单位时间来考虑的。一般来说，服务费用是比较容易估计出来，而用户的等待费用需要按不同的情况来分析。在处理方法上，一般根据变量的类型是离散还是连续，相应地采用边际分析方法或微分法，对教为复杂的优化问题需要用非线性规划或动态规划等方法。一般的套路从简单的模型开始一步步去逼近，直到得出对系统解释和最后的结果拟合得较好的模型。