HanLP分词研究
这篇⽂章主要是记录HanLP标准分词算法整个实现流程。
HanLP的核⼼词典训练⾃⼈民⽇报2014语料，语料不是完美的，总会存在⼀些错误。这些错误可能会导致分词出现奇怪的结果，这时请打开调试模式排查问题:
ableDebug();
那什么是语料呢？通俗的理解，就是HanLP⾥⾯的⼆个核⼼词典。假设收集了⼈民⽇报若⼲篇⽂档，通过⼈⼯⼿⼯分词，统计⼈⼯分词后的词频：①统计分词后的每个词出现的频率，得到⼀元核⼼词典；②统计两个词两两相邻出现的频率，得到⼆元核⼼词典。根据贝叶斯公式：
\[P(A|B)=\frac{P(A,B)}{P(B)}\qquad=\frac{count(A,B)}{count(B)}\qquad \]weight是什么词性
其中\(count(A,B)\)表⽰词A和词B 在语料库中共同出现的频率；\(count(B)\)表⽰词B 在语料库中出现的频率。有了这两个频率，就可以计算在给定词B的条件下，下⼀个词是 A的概率。
关于HanLP的核⼼词典、⼆元⽂法词典出现错误时如何处理可参考
关于分词算法的平滑问题，可参考
分词流程
采⽤维特⽐分词器：基于动态规划的维特⽐算法。
List<Term> termList = HanLP.segment(sentence);
在进⼊正式分词流程前，可选择是否进⾏归⼀化，然后进⼊到正式的分词流程。
if (HanLP.Config.Normalization)
{
}
return segSentence(text);
第⼀步，构建词⽹WordNet，参考：
词⽹包含起始顶点和结束顶点，以及待分词的⽂本内容，⽂本内容保存在charArray数组中。vertexes表
⽰词⽹中结点的个数：vertexes = new LinkedList[charArray.length + 2]，加2的原因是：起始顶点和结束顶点。
再将每个结点初始化，每个结点由⼀个LinkedList存储，值为空
for (int i = 0; i < vertexes.length; ++i)
{
vertexes[i] = new LinkedList<Vertex>();//待分词的句⼦的每个字符对应的 LinkedList
}
最后将起始结点和结束结点初始化，LinkedList中添加进相应的顶点。
vertexes[0].wB());//添加起始顶点
vertexes[vertexes.length - 1].wE());//添加结束顶点
size = 2;//结点size
在添加起始顶点和结束顶点的时候，会从核⼼词典构建出⼀棵双数组树。⽐如，创建⼀个起始结点：
public static Vertex newB()
{
return new Vertex(Predefine.TAG_BIGIN, " ", new CoreDictionary.Attribute(Nature.begin, Predefine.MAX_FREQUENCY / 10), WordID(Predefine.TAG_BIGIN));    }
每个顶点Vertex包括如下属性：
/**
* 节点对应的词或等效词（如未##数）
*/
public String word;
/**
* 节点对应的真实词，绝对不含##
*/
public String realWord;
/**
* 词的属性，谨慎修改属性内部的数据，因为会影响到字典<br>
* 如果要修改，应当new⼀个Attribute
*/
public CoreDictionary.Attribute attribute;
/**
* 等效词ID，也是Attribute的下标
*/
public int wordID;// 每个词的编号，从下标0开始
/**
* 在⼀维顶点数组中的下标，可以视作这个顶点的id
*/
public int index;//Vertex中顶点的编号
下⾯来⼀⼀解释Vertex类中各个属性的意义：
1. 什么是等效词呢？可参考：[]。在PreDefine.java中就定义⼀些等效词串：
/**
* 结束 end
*/
public final static String TAG_END = "末##末";
/**
* 句⼦的开始 begin
*/
public final static String TAG_BIGIN = "始##始";
/**
* 数词 m
*/
public final static String TAG_NUMBER = "未##数";
也即句⼦的开始⽤符号"始##始"来表⽰，结束⽤"末##末"表⽰。也即前⾯提到的起始顶点和结束顶点。
另外，在分词过程中，会产⽣⼀些数量词，⽐如⼀⼈、两⼈……⽽这些数量词统⼀⽤"未##数"表⽰。为什么要这样表⽰呢？由于分词是基于n-gram模型的(n=2)，⼀⼈、两⼈这样的词统计出来的频率不太靠谱，导致在⼆元核⼼词典中不到词共现频率，因此使⽤等效词串来进⾏处理。
1. 真实词String realWord
真实词是待分词的⽂本字符。⽐如：“商品和服务”，真实词就是其中的每个char，“真”、“品”、“和”……
2. Attribute属性
记录这个词在⼀元核⼼词典中的词性、词频。由于⼀个词可能会有多个词性和词频，因此词性和词频都有⼀维数组来存储。
3. wordId
该词在⼀元核⼼词典中的位置(⾏号)
4. index
这个词在词⽹(词图)中的顶点的编号
构建双数组树过程
如果有bin⽂件，则直接是以⼆进制流的形式构建了⼀颗双数组树，否则从中读取词典构建双数组中。关于双数组树的原理⽐较复杂，等以后彻底弄清楚了再来解释。
基于核⼼⼀元词典构建好了双数组树之后，就可以⽤双数组树来查询结点的wordId、词频、词性……信息，
return new Vertex(Predefine.TAG_BIGIN, " ", new CoreDictionary.Attribute(Nature.begin, Predefine.MAX_FREQUENCY / 10),
⾄此，创建了⼀个Vertex对象。
WordNet wordNetAll = new WordNet(sentence)；只是(初始化了)⽣成了词⽹中的顶点，为各个顶点分配了存储空间，并初始化了起始结点和结束结点。接下来，需要初始化待分词的⽂本中的各个字符了。
GenerateWordNet(wordNetAll);⽣成完整的词⽹。
⽣成完整词⽹
⽣成完整词⽹的流程是：根据待分词的⽂本使⽤双数组树对⼀元核⼼词典进⾏最⼤匹配查询，将命中的词创建⼀个Vertex对象，然后添加到词⽹中。
while (())
{
wordNetStorage.add(searcher.begin + 1, new Vertex(new String(charArray, searcher.begin, searcher.length), searcher.value, searcher.index));
}
具体举例来说：假设待分词的⽂本是"商品和服务"，⾸先将该⽂本分解成单个的字符。
然后，对每⼀个单个的字符，在双数组树(基于⼀元核⼼词典构建的)中进⾏最⼤匹配查：对于 '商' ⽽⾔，最⼤匹配查得到：'商'--->‘商品’
对于'品'⽽⾔，最⼤匹配查得到：'品'
对于'和’⽽⾔，最⼤匹配查得到：'和'--->'和服'
对于'服'⽽⾔，最⼤匹配查得到：'服'--->'服务'
对于'务'⽽⾔，最⼤匹配查得到：'务'
下⾯来具体分析 '商' 这个顶点是如何构建的：
由于'商'这个字存在于⼀元核⼼词典中
<()肯定会命中了'商' ，于是查到了双数组树中'商'这个顶点的所有信息：
wordID：32769
词性vg，对应的词频是607；词性v对应的词频是198
因此，将双数组树中的顶点信息提取出来，⽤来构建 '商' 这个Vertex对象，并将之加⼊到LinkedList中
public Vertex(String word, String realWord, CoreDictionary.Attribute attribute, int wordID)
{
if (attribute == null) attribute = new CoreDictionary.Attribute(Nature.n, 1);  //attribute为null，就赋⼀个默认值安全起见
this.wordID = wordID;
this.attribute = attribute;
//初始时，所有词的等效词串word=null，当碰到数词/地名...时, 会为这些词⽣成等效词串.
if (word == null) word = compileRealWord(realWord, attribute);//1⼈或者 2⼈这样的词，转化为：未##数@⼈
assert realWord.length() > 0 : "构造空⽩节点会导致死循环！";
this.word = word;
}
compileRealWord()函数的作⽤是：当碰到数量词……⽣成
同理，下⼀步从双数组树中到词是'商品'，类似地，构建'商品'这个Vertex对象，并将之添加到LinkedList下⼀个元素。
关于词图的⽣成，可参考：。词图中建⽴各个节点之间的联系，是通过中提到的快速offset法实现的。其
实就是通过快速offset法来寻某个节点的下⼀个节点。因为后⾯会使⽤基于动态规划的维特⽐算法来求解词图的最短路径，⽽求解最短路径就需要根据某个节点快速定位该节点的后继节点。
下⾯，以商品和服务为例，详细解释⼀下快速offset法：
0 始##始
1 商商品
2 品
3 和和服
4 服服务
5 务
6 末##末
上表可⽤⼀个LinkedList数组存储。每⼀⾏代表⼀个LinkedList，存储该字符最⼤匹配到的所有结果。这与图：词图的链接表⽰是⼀致的。使⽤这种⽅式存储词图，不仅简单⽽且也易于查下⼀个词。
5. 从词⽹转化成词图
然后，接下来是：原⼦分词，保证图连通。这⼀部分，不是太理解
// 原⼦分词，保证图连通
LinkedList<Vertex>[] vertexes = Vertexes();
for (int i = 1; i < vertexes.length; )
{
if (vertexes[i].isEmpty())
{
int j = i + 1;
for (; j < vertexes.length - 1; ++j)
{
if (!vertexes[j].isEmpty()) break;
}
wordNetStorage.add(i, quickAtomSegment(charArray, i - 1, j - 1));
i = j;
}
else i += vertexes[i].getLast().realWord.length();
}
⾄此，得到⼀个粗分词⽹，如下：
构建好了词图之后，有了词图中各条边以及边上的权值。接下来，来到了基于动态规划的维特⽐分词，使⽤维特⽐算法来求解最短路径。
动态规划之维特⽐分词算法
List<Vertex> vertexList = viterbi(wordNetAll);
计算顶点之间的边的权值
先把词图画出来，如下：
nodes数组就是⽤来存储词图的链表数组：
计算起始顶点的权值
起始顶点"始##始"到第⼀层顶点"商"和"商品"的权值：
//始##始到第⼀层顶点之间的边以及权值构建
for (Vertex node : nodes[1])
{
node.updateFrom(nodes[0].getFirst());
}
需要注意的是，每个顶点Vertex的weight属性，保存的是从起始顶点到该顶点的最短路径。
public void updateFrom(Vertex from)
{
double weight = from.weight + MathTools.calculateWeight(from, this);
if (this.from == null || this.weight > weight)//this.weight>weight 表明寻到了⼀条⽐原路径更短的路径
{
this.from = from;//记录更短路径上的前驱顶点,⽤来回溯得到最短路径上的节点
this.weight = weight;//记录更短路径的权值
}
}
updateFrom()⽅法实现了动态规划⾃底向上计算最短路径。当计算出的weight⽐当前顶点的路径this.weight还要短时，就意味着到⼀条更短的路径。
路径上的权值的计算
MathTools.calculateWeight()⽅法计算权值。这个权值是如何得出的呢？这就涉及到核⼼⼆元词典了。
int nTwoWordsFreq = BiFrequency(from.wordID, to.wordID);
会开始加载核⼼⼆元词典到内存中，然后查这两个词：from@to 的词
共现频率。显然，这⾥的词典采⽤了延迟加载的模式，也即当需要查询词共现频率的时候，才会去加载核⼼⼆元词典，从词典中到对应的频率。⽐如始##始@商即表⽰：语料中以第⼀个字'商'开头的频率是46
有了从⼀元核⼼词典中查询到的单个词的词频，以及两个词之间的词共现频率，就可以计算“概率”了。(背后的思想是贝叶斯概率，并且需要进⾏平滑)。关于平滑，可参考这个
double value = -Math.log(dSmoothingPara * frequency / (MAX_FREQUENCY) + (1 - dSmoothingPara) * ((1 - dTemp) * nTwoWordsFreq / frequency + dTemp));
计算其他顶点的权值
for (int i = 1; i < nodes.length - 1; ++i)
{
LinkedList<Vertex> nodeArray = nodes[i];
if (nodeArray == null) continue;
for (Vertex node : nodeArray)//当前节点为 node
{
if (node.from == null) continue;
for (Vertex to : nodes[i + alWord.length()])//获取当前节点 node的下⼀个节点 to
{
to.updateFrom(node);
}
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。