Shi Zhuolin's Blog - 分词
type: channel
link: https://www.shizhuolin.com/tag/%E5%88%86%E8%AF%8D/
items: 中文分词词性和序列标注之MEMM-4-最优化算法-IIS
items: 中文分词词性和序列标注之MEMM-3-最大熵模型求解
items: 中文分词词性和序列标注之MEMM-2-最大熵模型
items: 中文分词词性和序列标注之MEMM-1-比较HMM
items: 中文分词词性和序列标注之二阶HMM
items: 中文分词之最大概率法
items: 中文分词之最大匹配算法
items: 中文分词效果评估
items: 词频分析

中文分词词性和序列标注之MEMM-4-最优化算法-IIS
type: item
date: 2018-02-13T05:36:00+00:00
description: 5. 最优化算法1. IIS最大熵模型：$$ \begin{align} p(y|x) &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ Z_w(x) } \\ &= \frac{ \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \sum_y \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] } \end{align} $$极大对数似然估计：$$ \begin{align} L(w) &= \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x) \end{align} $$改进的迭代尺度优化算法的思路，假设把现有参数$ w=(w_1,w_2,\cdots,w_n)^T $加上一个新的参数向量$ w + \delta =(w_1 + \delta_1,w_2 + \delta_2,\cdots,w_n + \delta_n)^T $，可以使得模型的对数似然增大，如果存在这样一个参数向量，那么重复$ \imath: w \to w + \delta $，直到模型似然最大化为止。计算参数改变对应的似然改变量：$$ \begin{align} L(w + \delta) - L(w) &= \sum_{x,y} \tilde{p}(x,y) \log p_{w + \delta}(y|x) - \sum_{x,y}\tilde{p}(x,y) \log p_{w}(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} (w + \delta)_i f_i(x,y) - \sum_{x} \tilde{p}(x) \log Z_{w + \delta}(x) \\ & \quad - \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) + \sum_{x} \tilde{p}(x) \log Z_w(x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) - \sum_{x} \tilde{p}(x) \log \frac{Z_{w+\delta}(x)}{Z_w(x)} \\ & \text{because:} \sum_y \tilde{p}(x) = 1 \qquad \text{and} \qquad - \log a \geq 1-a, a > 0 \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{Z_{w+\delta}(x)}{Z_w(x)} \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{ \sum_y \exp \sum_{i=1} ( w + \delta )_i f_i (x,y) }{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) } \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) \exp \sum_{i=1} \delta_i f_i(x,y) }{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) } \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \sum_y p_w(y|x) \exp \sum_{i=1} \delta_i f_i(x,y) \end{align} $$将右端记为：$$ A(\delta|w) = \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \sum_y p_w(…

中文分词词性和序列标注之MEMM-3-最大熵模型求解
type: item
date: 2018-02-13T05:27:00+00:00
description: 3. 模型求解使用$ Lagrange $将模型转换为无约束优化问题, 设乘子$ w = \{w_0,w_1,\cdots,w_n \} $。定义$ Lagrange $函数：$$ \begin{align} L(P, w) &= -H(P) + w_0 \left[ 1 - \sum_y p(y|x) \right] + \sum_{i=1} w_i \left[ E_{\tilde{P}}(f_i) - E_P(f_i) \right] \\ &= \sum_{x, y} \tilde{p}(x) p(y|x) \log p(y|x) + w_0 \left[ 1 – \sum_y p(y|x) \right] \\ & \quad + \sum_{i=1} w_i \left[ \sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \sum_{x,y} \tilde{p}(x) p(y|x) f_i(x, y) \right] \end{align} $$原始问题和对偶问题分别为：$$ \min_P \max_w L(P, w) \quad ; \quad \max_w \min_P L(P, w) $$因$ Lagrange $函数$ L(P, w) $是P的凸函数, 因此求解对偶问题等价求解原始问题。定义对偶函数：$$ \Psi(w) = \min_P L(P, w) = L(P_w, w) $$其解为：$$ P_w = \arg\min_P L(P, w) = P_w(Y|X) $$也就是说，在$ w $不变时求得最小值参数。计算$ P_w(Y|X) $的导数，并让其为0即可。$$ \begin{align} \frac{\partial L(P,w)}{\partial p(y|x)} &= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) - \sum_y w_0 - \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\ &= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) - \sum_x \tilde{p}(x) \sum_y w_0 - \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\ & \quad \text{use:} \sum_x \tilde{p}(x) = 1; \\ &= \sum_{x,y} \tilde{p}(x) \left[ \log p(y|x) + 1 - w_0 - \sum_{i=1} w_i f_i(x,y) \right] \end{align} $$令其为0,且已知$ \tilde{p}(x) > 0 $：$$ \begin{align} \log p(y|x) &= \sum_{i=1} w_i f_i(x,y) - (1 - w_0) \\ p(y|x) &= \exp{\left[ \sum_{i=1} w_i f_i(x,y) - (1 - w_0) \right]} \\ &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \exp( 1-w_0 ) } \\ \text{because:} & \quad \sum_y p(y|x) = 1 \\ p(y|x) &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ Z_w(x) } \\ &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \sum_y \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] } \end{align} $$$ Z_w(x) $为规范化因子，求得$ P_w $后，得到最大熵模型，其中$ w_{i=1,2,\cdots,n} $可以被理解为每个特征的权重，注意在这里$ w_0 $被规范化因子给消除掉了. 而学习最大熵模型只需要调整权重的大小，极大化对偶函数$ \max_w \Psi(w) $即可.4. 极大似然估计上面已推导出最大熵模型，并已知极大化其对偶函数为模型学习结果。接下来证明对偶函数极大化估计等价于最大熵模型的极大似然估计。条件概率分布的对数似然函数为：$$ L_\tilde{P}(P_w) = \log \prod_{x,y}p(y|x)^{\tilde{p}(…

中文分词词性和序列标注之MEMM-2-最大熵模型
type: item
date: 2018-02-13T03:33:00+00:00
description: 二、最大熵模型1. 条件最大熵的意义条件熵函数是条件概率分布函数的度量，其概率分布越均匀，熵值越大。$$ H(Y|X) = - \sum_{x, y} p(x, y) log \, p(y|x) $$给定$ x $的情况下$ Y $的熵对于$ x $的期望越大，表示$ X $并未给$ Y $带来多少信息增益，也就是说$ X $对$ Y $决策帮助信息越少。这看似矛盾，因为我们需要的是根据$ X $对$ Y $分类。如果$ X $对$ Y $无帮助，那么分类毫无意义(此时$Y$均匀分布)。但在实际操作中$ X,Y $被特征函数强制约束(出现$ x $同时出现$ y $)。因此，最大熵其实只能把特征函数未约束的信息对$ Y $的影响均匀分布。承认在已知信息（特征函数约束）以外可能有未知信息会对判断$y$造成影响。但无法确定未知信息会对识别每个$ y $的具体值造成何种影响，为了风险最小化，不对未知信息对$ Y $的决策影响做任何主观倾向假设,而是认为未知信息对所有$ y $的影响程度都是趋于相同的，于是风险被平摊。例如，事件集合$ Y = \{y_1,y_2,y_3,y_4 \}; \sum^4_{i=1} p(y_i) = 1$, 已知$ P(Y=y_1) = 0.4 $, 那么在没有其他更多信息帮助下, 最大熵理论认为 $ P(Y=y_2) = P(Y=y_3) = P(Y=y_4) = ( 1.0 - P(Y=y_1) ) / 3 = 0.2 $。2 特征函数特征函数 $ f(x, y) $ 指示某事实是否成立，例如：$$ f(x, y) = \begin{cases} 1, & \text{if y='rn' and next(x) = 'is'} \\ 0, & \text{else} \end{cases} $$如果 s是人名并且下一个词是"is". 则返回1指示存在此事实。$ \text{对数线性模型}^{\text{[4]}} $并未限制特征函数的取值范围，但通常输出为 $ \{0,1\} $ 的特征函数更容易分析和直观理解。例如返回1就是存在此特征。3. 最大熵模型最大熵模型是一种对数线性模型，其目的是对样本做$ P(Y|X) $建模, 其需要在满足观测事实约束时才有意义，现描述使用特征函数约束的最大熵模型。设经验分布：$$ \begin{align} \tilde{P}(X=x) &= \frac{Count(X=x)}{N} \\ \tilde{P}(X=x, Y=y) &= \frac{Count(X=x, Y=y)}{N} \end{align} $$$ Count $是计数函数，$ N $是样本总数。使用前面介绍的特征函数对$ x,y $对约束（指示存在的事实）。那么，统计样本可得到特征函数指示事实的经验分布期望:$$ E_{\tilde{P}}(f) = \sum_{x,y} \tilde{p}(x, y) f(x, y) $$假设我们的最大熵模型对条件概率估计正确，那么很显然应可得到符合观测事实的$ P(Y|X) $分布，也就是说。使用模型估计的特征函数期望应该和在样本中统计到的特征函数期望相同。$$ \begin{align} E_{P}(f) & = E_{\tilde{P}}(f) \\ \sum_{x,y} \tilde{p}(x) p(y|x) f(x, y) & = \sum_{x,y} \tilde{p}(x,y) f(x,y) \end{align} $$同时，模型得到的条件概率分布应该合法，于是最大熵模型的完整描述如下：$$ \begin{align} \max_{P} H(P) & = – \sum_{x, y} \tilde{p}(x) p(y|x) \log \, p(y|x) \Leftrightarrow \min_{P} -H(P) \\ \text{subject to:} \\ E_{P}(f_i) & = E_{\tilde{P}}(f_i) \qquad i=1,2,\cdots,n \\ \sum_y p(y|x) & = 1 \end{align} $$$ P $是分布函数, $ p $是质量函数，因没有$ p(x, y) $, 因此使用 $ \tilde{p}(x) p(y|x) $近似。按照惯例，转换为最小化负熵。其实就是求解满足约束的最小负条件熵的条件概率分布函数。五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpayd…

中文分词词性和序列标注之MEMM-1-比较HMM
type: item
date: 2018-02-13T02:55:00+00:00
description: 一、MEMM和HMM的比较$ \require{AMScd} $$$ \text{HMM} \\ \begin{CD} q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\ @VVV @VVV @. @VVV @VVV \\ o_1 @. o_2 @. @. o_{t-1} @. o_t \end{CD} \\ p(Q,O)=\prod^T_{t=1}p(q_t|q_{t-1})p(o_t|q_t) \\ \quad \\ \quad \\ \text{MEMM} \\ \begin{CD} q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\ @AAA @AAA @. @AAA @AAA \\ o_1 @. o_2 @. @. o_{t-1} @. o_t \end{CD} \\ p(Q|O) = \prod^T_{t=1} p(q_t | q_{t-1}, o_t) $$1. MEMM是判别模型。在HMM中，观测序列由隐藏状态序列生成，在序列标注任务中寻找以最大概率生成指定观测序列的隐藏状态序列,$HMM-viterbi$计算观测序列和隐藏序列的最大联合概率。$ \lambda $ 是模型参数。$$ Q = \arg\max_{Q} P(Q,O | \lambda) $$而MEMM作为判别模型直接给出目标状态序列。$$ Q = \arg\max_{Q} P(Q | O, \lambda) $$2. 可定义更复杂的特征在 $ HMM-Viterbi $ 查找序列标注时当前隐藏状态和上个隐藏状态相关，假定各观测状态之间互相独立, 观测状态是生成目标，并不便于定义更多特征条件。$$ \delta_t(j) = \max_i \delta_{t-1}(i)a_{ij} \cdot b_j(o_t) $$在MEMM中并不要求各观测状态独立，可使用特征函数对条件$ o_t $定义更复杂的分类特征，e.g. 大小写、上下文字符)。$$ \delta_t(j) = \max_i \delta_{t-1}(i) P(q_t=S_j | q_{t-1} = S_i, o_t) $$3. MEMM的$ viterbi $算法与$ HMM-viterbi $ 类似，定义两个函数用于保存每个步骤的最大概率和最佳前驱状态。然后从前向后递归，最后回朔状态序列。但这里和HMM不同的是改联合概率定义为条件概率。$$ \begin{align} \delta_t(i) & = \max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t) \\ \psi_t(i) & = \arg\max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t) \end{align} $$第一步 此时 $ q_0 = {\emptyset} $，这里理解为，没有上一个隐藏状态本身就表示一种特殊状态（序列开始状态）$$ \begin{align} \delta_1(i) & = P(q_t=S_i | q_0={\emptyset}, O_1) \\ \psi_1(i) & = {\emptyset} \end{align} $$递归$$ \begin{align} \delta_t(j) & = \max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t) \\ \psi_t(j) & = \arg\max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t) \end{align} $$结束 后续计算和回朔和HMM相同，不再叙述。在 $ P(q_t=S_j | q_{t-1}=S_i, O_t) $ 中，工程实现时，实际传递的其实是 $ P(q_t=S_j | q_{t-1}=S_i, O, t) $ ，原因是特征函数可能需要判断 $ t $ 时刻的上下文作为特征。作为最大熵马尔可夫模型介绍，本文不考虑使用其他的概率计算方法。五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition…

中文分词词性和序列标注之二阶HMM
type: item
date: 2018-01-25T05:18:00+00:00
description: 回顾一阶HMM在一阶HMM中，下一个隐藏状态是当前隐藏状态的条件概率：$$ P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k, \cdots ) \approx P(q_{t+1} = S_j | q_t = S_i) $$即转移矩阵：$$ A = [a_{ij}] \quad \text{where} \quad a_{ij} \equiv P(q_{t+1} = S_j | q_t = S_i) $$且特定时刻观察状态只和当前隐藏状态有关。$$ b_j(m) \equiv P(O_t = \nu_m | q_t = S_j) $$即观测矩阵：$$ B = [b_j(m)] \quad \text{where} \quad b_j(m) \equiv P(O_t = \nu_m | q_t = S_j) $$二阶HMM对于字序列标记分词，当前分词标记和上一个字的分词标记相关，这是二元组 Bigram，但分析样本发现切分位置并不一定只和上一个字相关，可能会有更长远的关系，比如假设当前字标记和之前两个字标记有关，那么就成为了三元组。即 $ Trigram $：$$ P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k, \cdots ) \approx P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k) $$同时还假设当前观测到的字符除和当前分词标记（隐藏状态）相关外，也与上一个隐藏状态相关：$$ b_{ij}(m) \equiv P(O_t = \nu_m | q_t = S_j, q_{t-1} = S_i) $$对应转移矩阵和观测矩阵也改动为：$$ \begin{align} A &= [a_{ijk}] \quad \text{where} \quad a_{ijk} \equiv P(q_{t+1} = S_k | q_t = S_j , q_{t-1} = S_i ) \\ B &= [b_{ij}(m)] \quad \text{where} \quad b_{ij}(m) \equiv P(O_t = \nu_m | q_t = S_j , q_{t-1} = S_i) \end{align} $$二阶Viterbi在每次的计算在中，要考虑先后两个状态，因此viterbi对应更改：$$ \begin{align} \delta_t(i, j) & \equiv \max_{{q_1}{q_2}{\cdots}{q_{t-2}}} P( {q_1}{q_2}{\cdots}{q_{t-2},q_{t-1}=S_i, q_t = S_j, O_1 \cdots O_t | \lambda } ) \\ \psi_t(i, j) & \equiv \arg\max_{{q_1}{q_2}{\cdots}{q_{t-2}}} P( {q_1}{q_2}{\cdots}{q_{t-2},q_{t-1}=S_i, q_t = S_j, O_1 \cdots O_t | \lambda } ) \end{align} $$初始化 此时并不满足二阶条件。 继续使用一阶HMM的初始/转移矩阵，但要第一步时需忽略参数 $ i $，且不考虑改进后的观测矩阵。当然其实也可以认为$ i $事件发生概率在这里永远是1：$$ \begin{align} \text{when} \quad t=1 \text{:} \qquad & \\ \delta_1(i, j) & = \pi_j b_j(O_1) \\ \psi_1(i,j) & = 0 \\ \text{when} \quad t=2 \text{:} \qquad & \\ \delta_2(i, j) & = \delta_1( , i)a_{ij} \cdot b_{ij}(O_2) \\ \psi_2(i,j) & = 0 \\ \end{align} $$恩，似乎有点麻烦，直接从t=2作为初始化，合并到一起好了。从t=3开始计算$ \psi $。$$ \begin{align} \delta_2(i, j) & = \pi_i b_i(O_1) \cdot a_{ij} \cdot b_{ij}(O_2) \\ \psi_2(i,j) & = 0 \end{align} $$递归$$ \begin{align} \delta_t(j, k) & = \max_i \delta_{t-1}(i, j) \cdot a_{ijk} \cdot b_{jk}(O_t) \\ \psi_t(j, k) & = \arg\max_i \delta_{t-1}(i, j) \cdot…

中文分词之最大概率法
type: item
date: 2018-01-21T02:52:00+00:00
description: 最大概率法分词是在最大匹配分词算法上的改进。在某些语句切分时，按最大长度切分词语可能并不是最优切分。而不按最优长度切分词语，则同一语句会出现多种切分结果。计算每种切分结果的概率，选取概率最高的切分作为最优分词切分。一、计算切分概率$W$：所有可能的切分组合$S$：待切分语句最佳切分：$$ {\arg\max}_w{P(W|S=s)} $$切分概率:$$ p(w|s) = \frac{p(w)p(s|w)}{p(s)} $$因为始终是同一语句，$ p(s) $ 未曾改变, $ p(s|w) $ 始终为1. 仅需计算 $ p(w) $.在词表中需记录每个词语的词频，计算每个独立词语出现的联合概率. 使用一元语法（不考虑词语上下文关系）则.$$ \begin{align} p(w^n_1) &= p(w_1,w_2, \cdots, w_n) \\ &= p(w_1)p(w_2){\cdots}p(w_n) \\ &= {\prod}^{n}_{1}p(w_n) \\ \end{align} $$在实践中一般用对数求和替代求积，原因是词语概率一般会很小，多次连乘后可能造成溢出.$$ \log{p(w)} = {\sum}^{n}_{1}\log{p(w_n)} $$只需要比较大小，所以最后计算结果无需再做一次 $ \log $二、平滑词表中不可能记录所有可能存在的词语和其词频，对于词表中没有的词如果认为其概率为0，则会存在0概率切分，为了解决零切分问题，给新词指定一个比较低的概率. 例如指定为词表中出现频数最低的词概率,或将其看待为只出现过一次，在这里 $N$ 表示词表词条总数。$ p(w_i) $ 是词表中的词语概率。将新词指定为词表中的最低词频率。 $$ p(w_{new}) = \min_i{p(w_i)} $$加$1$平滑。 假设在建造词表时所有词语都被漏计1次。所以刚好在词表中查询不到在待切分样本中碰到的新词（因为在切分特定位置时，新词只出现了1次）。因此在计算词表中的词语词频和新词词频时，给所有的词语词频$+1$。新的词语概率计算如下：$$ p(w)=\frac{c(w)+1}{N+V} \qquad c(w)=\begin{cases} 0, & \text{} \\ count(w), & \text{ \( {w} \in {dict} \) } \end{cases} $$$ N $ 词表中所有词语总计词频.$ V $ 词语总数，新词也算一个词语。$ c (w)$ 词表中对应词语频数，新词词频为$0$。三、切分词语切分词语时从语句中每个字作为词语前缀字符查询词表，查询结果构造为DAG图，如此表中无此词汇，则单字成词。以下代码摘录自*结巴分词。def get_DAG(sentence): global pfdict, FREQ DAG = {} N = len(sentence) for k in range(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in pfdict: if frag in FREQ: tmplist.append(i) i += 1 frag = sentence[k:i+1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG四、选择最优切分有两种方法计算对DAG图做DFS搜索，得到所有切分组合，分别计算各组合概率，取最大概率组合输出。 segment_sent = [] def dfs(words, x): for y in DAG[x]: if y < N: new = words.copy() new.append(sentence[x:y]) dfs(new, y) else: new = words.copy() new.append(sentence[x:y]) segment_sent.append( new ) dfs([], 0) bestseg = max([(sum(fdist.get(w, math.log(1.0/total)) for w in seg), seg) for seg in segment_sent])很显然，这个计算复杂度非常高 $ O(\overline{word-length}^{(N-1)}) $ 以语句长度呈指数增长。对DAG图做动态规划DP算法, 从深度搜索这里可以看到, 其实很多局部计算过程是重复的。因此这里从图后面向前面反向计算, 每次累计最大概率结果。计算每个字为前缀的不同切分词语概率和后续最大切分概率的乘积，取最大结果为最佳切分，依次向语句前方递推。最后得到语句第一个字开始的最…

中文分词之最大匹配算法
type: item
date: 2018-01-20T16:56:00+00:00
description: 正向最大匹配分词和逆向最大匹配分词词表词表为所有可能出现的词语组成的集合。当然，实践中不可能准备包含全所有已知和未知词语词表。建立词表从人工标注语料中得到词表。 由多人讨论并且得到共识的分词标注语料建立词表。这是效果最好，但也是成本最高的方案。从未标注语料中建立词表。 可以认为经常重复出现连续字符串属于词语。统计大量未标注语料中的连续字串重复出现频率，将多次重复出现的连续字串作为词语，以此建立词典。使用输入法，辞典，翻译（例如中英词语互译）词表.这是比较容易实现的方法，且这些数据大多能免费下载，有些输入法词表还带词频。正向最大匹配分词算法将待分词语句以每个字为开始词语前缀按从左到右的切分顺序与词表匹配，查找到的最长词语为分词结果，并将当前切分位置作为下个词语切分开始位置，如切分片段在在词表中无对应词语，则顺移到下一个字继续切分，把跳过的片段切分为新词（未登陆词）。此方法分词效果很大程度取决词表，且词表就算包含所有待切分词语，也可能造成分词效果不理想，原因是很多时候按最大长度切分词语可能并不是最优切分。例如:待切分词语句: 产量三年中将增长两倍正向最大匹配: 产量 三年 中将 增长 两倍最优切分词语: 产量 三年 中 将 增长 两倍词表中没有 “三年中”，但是有 “中将”, 而事实上 “三年中” 除非作为一个熟词，否则难以作为一个独立词语切分，毕竟还有四年中，五年中，这组合可就多了.与正向最大匹配分词算法类似的反/逆向最大匹配分词算法, 其改变切分顺序为从右到左.参考代码摘自 icwb2-data/scripts/mwseg.plwhile (<>) { chop; s/\s*//g; my $text = $_; while ($text ne "") { $sub = substr($text, 0, $maxwlen); while ($sub ne "") { if ($dict{$sub}) { print "$sub "; for (my $i = 0; $i < length($sub); ++$i) { $text =~ s/^.//; } last; } $sub =~ s/.$//; } if ($sub eq "") { if ($text =~ /^([\x21-\x7e])/) { print "$1 "; $text =~ s/^.//; } elsif ($text =~ /^([^\x21-\x7e].)/) { print "$1 "; $text =~ s/^..//; } else { ## shouldn't happen print STDERR "Oops: shouldn't be here: $n\n"; print "$1 "; $text =~ s/^.//; } } } print "\n"; ++$n; }用于PKU封闭测试效果=== SUMMARY: === TOTAL INSERTIONS: 9829 === TOTAL DELETIONS: 1359 === TOTAL SUBSTITUTIONS: 8648 === TOTAL NCHANGE: 19836 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 112842 === TOTAL TRUE WORDS RECALL: 0.904 === TOTAL TEST WORDS PRECISION: 0.836 === F MEASURE: 0.869 === OOV Rate: 0.058 === OOV Recall Rate: 0.059 === IV Recall Rate: 0.956

中文分词效果评估
type: item
date: 2018-01-15T08:35:00+00:00
description: 将算法分词结果与人工标注的分词结果对比，以此评估分词效果优劣。人工标注分词文本通常被看作公认的“黄金”标准。主要使用处理速度、精确率、召回率和F值四个指标衡量分词算法的性能。一、评估指标$TP$：正确分词数量$FP$：错误分词数量$N$：黄金分词数量$W$：算法处理样本字数$T$：算法运行时间（秒）分词算法处理速度使用每秒处理文本字数（或字节数）作为评估单位。$$ Speed=\frac{W}{T} $$精确率：算法分词结果中正确切分的词数占总切分词数的比例。$$ Precision=\frac{TP}{TP+FP} $$召回率：算法分词结果中正确切分的词数占黄金样本中应该被切分出的词数比例。$$ Recall=\frac{TP}{N} $$F值：精确率和召回率的调和值，可以理解为综合考虑结果。$$ F1=\frac{{2}\times{Precision}\times{Recall}}{{Precision} + {Recall}} $$注意：判断正确/错误切分时要注意切分词语的顺序，如顺序颠倒那么即使切分出词语也是错误。也就是说，不能用"if 词语 in 黄金分词"这种方法判断对错, icwb2使用"diff"命令实现分词对比。二、封闭测试和开放测试分词算法可能需要使用词表、统计/训练语料等相关数据，如固定黄金标准数据且提供词表和训练集用于算法设计和训练或参考，则属于封闭测试，可以理解为训练集（参考）和测试集是指定的。反之则属于开放测试。很显然封闭测试效果通常比开放测试好，在实际应用中不同行业或场景的词语切分差异很大，因此开放测试并不便于工程使用。多还是使用封闭测试，测试样本和训练样本来自相同行业/场景。三、简体中文分词封闭测试实战访问 Second International Chinese Word Segmentation Bakeoff Data，下载 icwb2-data 评估数据集和脚本。解压icwb2-data.zip后可得到多个数据集用于评估分词效果, 其中 PKU(北大), MSR（微软研究院）数据集用于评估简体中文分词. 使用其自带的最大正向匹配分词算法作为分词算法性能比较基准。PKU分词封闭测试使用最大正向匹配分词算法切分pku_test.utf8待文件。使用gold文件夹下的pku词表(封闭测试)。执行score对比人工标注的黄金分词样本和之前算法切分结果差异。# cd icwb2-data # perl scripts/mwseg.pl gold/pku_training_words.utf8 testing/pku_test.utf8 > test_segmentation.utf8 # perl scripts/score gold/pku_training_words.utf8 gold/pku_test_gold.utf8 test_segmentation.utf8等待执行完成后可看到如下报告，这里其自带mwseg.pl切分的性能为精确率：0.836、召回率：0.904、新词识别率：0.058、新词识别召回率：0.059。词表中未存在的词语为新词（也称为未登陆词），在某些分词算法中词表并不是必须的，不用过多关注新词识别指标。=== SUMMARY: === TOTAL INSERTIONS: 9829 === TOTAL DELETIONS: 1359 === TOTAL SUBSTITUTIONS: 8648 === TOTAL NCHANGE: 19836 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 112842 === TOTAL TRUE WORDS RECALL: 0.904 召回率 === TOTAL TEST WORDS PRECISION: 0.836 精度 === F MEASURE: 0.869 F调和 === OOV Rate: 0.058 新词率(此值同语料不会改变,毕竟词表以外都是未登陆词) === OOV Recall Rate: 0.059 未登陆词招回率 === IV Recall Rate: 0.956 已登陆词召回率scripts/mwseg.pl 是其自带的 最大正向匹配 分词算法，此脚本分词效果作为分词评估基准。

词频分析
type: item
date: 2014-03-01T06:46:00+00:00
description: 和JS版功能相同,只是为了提高性能才用C#重写一次.Form1.csusing System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.Threading; using System.Net; using System.IO; using System.Text.RegularExpressions; using MySql.Data; using MySql.Data.MySqlClient; namespace 网页关键词处理 { public partial class keywords : Form { public keywords() { InitializeComponent(); } private Thread t; delegate void SetTextCallback(string text); private void start_Click(object sender, EventArgs e){ if (start.Text.Equals("stop")) { this.t.Abort(); start.Text = "start"; }else{ this.t = new Thread(new ThreadStart(this.threadsafe)); this.t.Start(); start.Text = "stop"; } } private void threadsafe() { //获取数据库连接 string _sha1 = ""; string _url = ""; if (url.Text.Trim().Equals("")) { MySqlConnection conn = new MySqlConnection("server=" + db_servers.Text.Trim() + ";user=" + db_uid.Text.Trim() + ";database=" + db_db.Text.Trim() + ";port=3306;password=" + db_pwd.Text.Trim() + ";charset=utf8"); try { conn.Open(); MySqlCommand cmd = new MySqlCommand("SELECT url_sha1,url_link FROM url ORDER BY url_update,url_error ASC LIMIT 1", conn); MySqlDataReader rdr = cmd.ExecuteReader(); while (rdr.Read()) { _sha1 = rdr.GetString(0).Trim(); _url = rdr.GetString(1).Trim(); } rdr.Close(); cmd.Dispose(); rdr.Dispose(); rdr = null; cmd = null; conn.Close(); } catch (Exception ex) { MessageBox.Show(ex.Message); } conn.Dispose(); conn = null; }else { _sha1 = ""; _url = url.Text.Trim(); } show("访问:"+_url); try { html h = new html(gethttp(_url)); string title = h.Title; string body = h.Body; MySqlConnection conn = new MySqlConnection("server=" + db_servers.Text.Trim() + ";user=" + db_uid.Text.Trim() + ";database=" + db_db.Text.Trim() + ";port=3306;password=" + db_pwd.Text.Trim() + ";charset=utf8"); conn.Open(); MySqlCommand cmd = new MySqlCommand("UPDATE url SET url_title='"+title+"',url_keywords = '"+body+"',url_update = now() WHERE url_s…