1. 中文分词算法-MMSeg算法原理
要理解mmseg算法，首先来理解一下chunk，它是MMSeg分词算法中一个关键的概念。Chunk中包含依据上下文分出的一组词和相关的属性，包括长度(Length)、平均长度(Average Length)、标准差的平方(Variance)和*语素度(Degree Of Morphemic Freedom)。下面列出了这4个属性：
|
属性 |
含义 |
|
长度(Length) |
chuck中各个词的长度之和 |
|
平均长度(Average Length) |
长度(Length)/词数 |
|
标准差的平方(Variance) |
同数学中的定义 |
|
*语素度(Degree Of Morphemic Freedom) |
各单字词词频的对数之和 |
Chunk中的4个属性只有在需要该属性的值时才进行计算，而且只计算一次。
其次来理解一下规则(Rule)，它是MMSeg分词算法中的又一个关键的概念。实际上我们可以将规则理解为一个过滤器(Filter)，过滤掉不符合要求的chunk。MMSeg分词算法中涉及了4个规则：
· 规则1：取最大匹配的chunk (Rule 1: Maximum matching)
· 规则2：取平均词长最大的chunk (Rule 2: Largest average word length)
· 规则3：取词长标准差最小的chunk (Rule 3: Smallest variance of word lengths)
· 规则4：取单字词*语素度之和最大的chunk (Rule 4: Largest sum of degree of morphemic freedom of one-character words)
这4个规则符合汉语成词的基本习惯。
再来理解一下匹配方式复杂最大匹配(Complex maximum matching)：
复杂最大匹配先使用规则1来过滤chunks，如果过滤后的结果多于或等于2，则使用规则2继续过滤，否则终止过滤过程。如果使用规则2得到的过滤结果多于或等于2，则使用规则3继续过滤，否则终止过滤过程。如果使用规则3得到的过滤结果多于或等于2，则使用规则4继续过滤，否则终止过滤过程。如果使用规则 4得到的过滤结果多于或等于2，则抛出一个表示歧义的异常，否则终止过滤过程。
最后通过一个例句--“研究生命起源"来简述一下复杂最大匹配的分词过程。MMSeg分词算法会得到7个chunk，分别为：
|
编号 |
chunk |
长度 |
|
0 |
研_究_生 |
3 |
|
1 |
研_究_生命 |
4 |
|
2 |
研究_生_命 |
4 |
|
3 |
研究_生命_起 |
5 |
|
4 |
研究_生命_起源 |
6 |
|
5 |
研究生_命_起 |
5 |
|
6 |
研究生_命_起源 |
6 |
使用规则1过滤后得到2个chunk，如下：
|
编号 |
chunk |
长度 |
|
4 |
研究_生命_起源 |
6 |
|
6 |
研究生_命_起源 |
6 |
计算平均长度后为：
|
编号 |
chunk |
长度 |
平均长度 |
|
4 |
研究_生命_起源 |
6 |
2 |
|
6 |
研究生_命_起源 |
6 |
2 |
使用规则2过滤后得到2个chunk，如下：
|
编号 |
chunk |
长度 |
平均长度 |
|
4 |
研究_生命_起源 |
6 |
2 |
|
6 |
研究生_命_起源 |
6 |
2 |
计算标准差的平方后为：
|
编号 |
chunk |
长度 |
平均长度 |
标准差的平方 |
|
4 |
研究_生命_起源 |
6 |
2 |
0 |
|
6 |
研究生_命_起源 |
6 |
2 |
4/9 |
使用规则3过滤后得到1个chunk，如下：
|
编号 |
chunk |
长度 |
平均长度 |
标准差的平方 |
|
4 |
研究_生命_起源 |
6 |
2 |
0 |
匹配过程终止。最终取“研究”成词，以相同的方法继续处理“生命起源”。
分词效果:
研究_生命_起源_
研究生_教育_
二. N-gram算法
1. 算法原理
N-gram是一种基于统计语言模型的算法。
统计语言模型的基本原理公式是：
假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)：
这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定：
N-Gram模型
当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。
N-Gram模型实质是一种马尔科夫链。 N的值不能太大，否则计算仍然太大。
根据最大似然估计，语言模型的参数：
其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数
在分词中的应用
我们回到句子的概率计算公式：假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)：
对于中文来说，一个句子的序列划分有多种方式，
S=w1w2w3....wn
S = a1a2a3....ak
......等等
不同的划分计算出来的句子的概率是不一样的。我们把整个句子最大概率的划分方式作为第一个词的划分结果，然后分词窗口后移，继续下一步。
三． Bm25算法
1. 算法原理
BM25算法，通常用来作搜索相关性平分。一句话概况其主要思想：对Query进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。
BM25算法的一般性公式如下：
其中，Q表示Query，qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）；d表示一个搜索结果文档；Wi表示语素qi的权重；R(qi，d)表示语素qi与文档d的相关性得分。
下面我们来看如何定义Wi。判断一个词与一个文档的相关性的权重，方法有多种，较常用的是IDF。这里以IDF为例，公式如下：
其中，N为索引中的全部文档数，n(qi)为包含了qi的文档数。
根据IDF的定义可以看出，对于给定的文档集合，包含了qi的文档数越多，qi的权重则越低。也就是说，当很多文档都包含了qi时，qi的区分度就不高，因此使用qi来判断相关性时的重要度就较低。
我们再来看语素qi与文档d的相关性得分R（qi，d）。首先来看BM25中相关性得分的一般形式：
其中，k1，k2，b为调节因子，通常根据经验设置，一般k1=2，b=0.75；fi为qi在d中的出现频率，qfi为qi在Query中的出现频率。dl为文档d的长度，avgdl为所有文档的平均长度。由于绝大部分情况下，qi在Query中只会出现一次，即qfi=1，因此公式可以简化为：
从K的定义中可以看到，参数b的作用是调整文档长度对相关性影响的大小。b越大，文档长度的对相关性得分的影响越大，反之越小。而文档的相对长度越长，K值将越大，则相关性得分会越小。这可以理解为，当文档较长时，包含qi的机会越大，因此，同等fi的情况下，长文档与qi的相关性应该比短文档与qi的相关性弱。
综上，BM25算法的相关性得分公式可总结为：
从BM25的公式可以看到，通过使用不同的语素分析方法、语素权重判定方法，以及语素与文档的相关性判定方法，我们可以衍生出不同的搜索相关性得分计算方法，这就为我们设计算法提供了较大的灵活性。
四. 内存外排序算法
1. 算法原理
外部排序基本上由两个相互独立的阶段组成。首先，按可用内存大小，将外存上含n个记
录的文件分成若干长度为k的子文件或段(segment)，依次读入内存并利用有效的内部排
序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存。通常称这些有序
子文件为归并段或顺串；然后，对这些归并段进行逐趟归并，使归并段(有序子文件)逐
渐由小到大，直至得到整个有序文件为止。
2.代码实现
在sphinx.cpp文件中的函数int CSphIndex_VLN::Build ( )中，建立索引的过程需要进行两次分析排序。第一次分析的时候，会将读取的原始数据拆分成一个个一个数据桶(bin)，数据桶内部是排序好的；第二次分析的时候，采用的是内存外排序。摘录代码如下。
五．Trie tree算法
1. 算法原理
Trie树就是字典树，其核心思想就是空间换时间。
举个简单的例子。
给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，第一次出现第几个位置。
这题当然可以用hash来，但是我要介绍的是trie树。在某些方面它的用途更大。比如说对于某一个单词，我要询问它的前缀是否出现过。这样hash就不好弄了，而用trie还是很简单。
现在回到例子中，假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了……
假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树就是这样的。
对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。如果存在，则读取附在该结点上的信息，即完成查找。
其他操作类似处理。
那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。 这样一来我们询问和插入可以一起完成。
我们可以看到，trie树每一层的节点数是26^i级别的(i表示层数)。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。
Trie树的缺点是内存耗费大，尤其对于中文，因为中文字数多，词汇排列多，导致内存耗费非常大。一般会使用double array trie的方式来实现，以便减少内存耗费。