汉语分词最大匹配方法张月

如果一个词的出现仅依赖于它前面出现的一个词，那么我们就称之为 bigram。即
P(T ) P(WW Wn ) P(W1 ) P(W2 | W1 ) P(W3 | WW Wn 1 ) 1 2W3 ... 1 2 )...P (Wn | W1... P(W1 ) P(W2 | W1 ) P(W3 | W2 )...P(Wn | Wn1 )
如果一个词的出现仅依赖于它前面出现的两个词，那么我们就称之为 trigram。 在实践中用的最多的就是 bigram 和 trigram 了，而且效果很不错。高于四元的用的很 少， 因为训练它需要更庞大的语料， 而且数据稀疏严重， 时间复杂度高， 精度却提高的不多。 设 w1,w2,w3,...,wn 是长度为 n 的字符串，规定任意词 wi 只与它的前两个相关，得到三 元概率模型
优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断 点（切分标志），可将原字符串分为较小的串再来进机械分词，从而减少匹配的错 误率。
1.5 最佳匹配（OM，分正向和逆向）
1/7
对分词词典按词频大小顺序排列，并注明长度，降低时间复杂度。
第二节 基于统计的分词 主要思想：上下文中，相邻的字同时出现的次数越多，就越可能构成一个词。因此字与 字相邻出现的概率或频率能较好的反映词的可信度。 主要统计模型为： N 元文法模型 （N-gram） 、 隐马尔科夫模型(Hidden Markov Model, HMM) 2.1N-gram 模型思想 模型基于这样一种假设，第 n 个词的出现只与前面 N-1 个词相关，而与其它任何词都 不相关，整句的概率就是各个词出现概率的乘积 . 我们给定一个词，然后猜测下一个词是什么。当我说“艳照门”这个词时，你想到下一个 词是什么呢？我想大家很有可能会想到“陈冠希”，基本上不会有人会想到“陈志杰”吧。 N-gram 模型的主要思想就是这样的。 对于一个句子 T，我们怎么算它出现的概率呢？假设 T 是由词序列 W1,W2,W3,…Wn 组成的，那么

tiktoken中文分词原理1.概述在自然语言处理（NL P）领域中，中文分词是一个重要的任务，它的目标是将连续的中文字符序列切分成有意义的词语。

ti kt ok en是一个开源的中文分词工具，它基于最大匹配算法和字典树的方法来实现中文分词。

本文将介绍t ik to ke n中文分词工具的原理及其运行过程。

2.最大匹配算法最大匹配算法是一种常用的中文分词算法，它基于词典中最长的词汇进行切分。

t ik to ken利用了最大匹配算法来进行分词。

具体而言，t ik to ken首先将待切分的句子按照最大切分长度划分为几个子句。

然后，它从每个子句的起始位置开始，逐渐增大切分长度，不断寻找匹配的词汇。

当找到匹配的词汇时，t ik to ke n将该词汇作为一个分词结果，并将切分位置移动到下一个子句的起始位置。

这个过程重复进行，直到所有子句都被分词为止。

最大匹配算法的一个关键问题是如何确定最大切分长度。

t ikt o ke n使用了统计信息和机器学习的方法来动态地确定最佳的最大切分长度，以提高分词的准确性。

3.字典树字典树（Tr ie）是一种树状数据结构，它能够高效地存储和查找字符串。

ti kt ok en利用了字典树来储存中文词汇信息，以支持最大匹配算法的快速匹配过程。

字典树的每个节点代表一个字符，从根节点到叶节点的路径表示一个完整的词汇。

ti kt ok e n在分词过程中通过比对待切分句子的字符与字典树节点的字符，来确定最大匹配的词汇。

4. ti ktoken的运行过程t i kt ok en的运行过程可以概括为以下几个步骤：4.1构建字典树t i kt ok en首先从一个大型的中文词汇库中提取出所有的词汇，并构建字典树。

这个字典树将作为最大匹配算法的匹配模型。

4.2切分子句t i kt ok en将待切分的句子按照标点符号或其他符号进行划分，形成若干个子句。

每个子句都将作为最大匹配算法的输入。

4.3最大匹配对于每个子句，ti kt o ke n从起始位置开始，逐渐增大最大切分长度，利用字典树进行匹配。

最大概率法分词的问题
并不能解决所有的交集型歧义问题
“这事的确定不下来” W1= 这/ 事/ 的确/ 定/ 不/ 下来/ W2= 这/ 事/ 的/ 确定/ 不/ 下来/������
P(W1)<P(W2)
无法解决组合型歧义问题
“做完作业才能看电视” W1=做/ 完/ 作业/ 才能/ 看/ 电视/ W2= 做/ 完/ 作业/ 才/ 能/ 看/ 电视/
Max(P(W1|S), P(W2|S)) ?

最大概率法分词

提高计算效率
如何尽快找到概率最大的词串（路径）？

提高计算效率（续）

最大概率分词算法
1. 对一个待分词的字串S，按照从左到右的顺序取 出全部候选词w1, w2, …,wi, …, wn； 2. 到词典中查出每个候选词的概率值P(wi)，并记录 每个候选词的全部左邻词； 3. 按照公式1计算每个候选词的累计概率，同时比 较得到每个候选词的最佳左邻词； 4. 如果当前词wn是字串S的尾词，且累计概率P' (wn)最大，则wn就是S的终点词； 5. 从wn开始，按照从右到左顺序，依次将每个词的 最佳左邻词输出，即为S的分词结果。
从字符 串到词 串，存 在着不 确定性
������ 你认为学生会听老师的吗
������ 我家门前的小河很难过 …… Nhomakorabea语词汇处理
从字符串中识别出词(word segmentation)
“分”词——“合”词
分词的基本方法
字符串匹配法(Maximum Match based approach) 概率方法

分词歧义的类型
������ 交集型歧义
如果AB和BC都是词典中的词，那么如果待切分字串中 包含“ABC”这个子串，就必然会造成两种可能的切分： “AB/ C/ ”和“A/ BC/ ”。这种类型的歧义就是交集型歧 义。比如“网球场”就可能造成交集型歧义 （网球/ 场/ : 网/ 球场/）。

算法过程： (1) 相邻节点 v k-1 , v k 之间建立有向边 <v k-1 , v k > ，边对应的词默认为 c k ( k =1, 2, …, n) (2) 如果 w= c i c i+1 …c j (0<i<j<=n) 是一个词，则节点v i-1 , v j 之间建立有向边 <v i-1 , v j > ，边对应的词为 w
歧义切分问题
歧义字段在汉语文本中普遍存在，因此，切分歧义是中文分词研究中一个不 可避免的“拦路虎”。 （交集型切分歧义） 汉字串AJB如果满足AJ、JB同时为词（A、J、B分别为汉 字串），则称作交集型切分歧义。此时汉字串J称作交集串。 如“结合成”、“大学生”、“师大校园生活”、“部分居民生活水平”等等。 （组合型切分歧义） 汉字串AB如果满足A、B、AB同时为词，则称作多义组合 型切分歧义。 “起身”：（a）他站│起│身│来。（b）他明天│起身│去北京。 “将来”：（a）她明天│将│来│这里作报告。（b）她│将来│一定能干成大事。
中文分词的辅助原则
1. 有明显分隔符标记的应该切分之 。 2. 附着性语素和前后词合并为一个分词单位。 3. 使用频率高或共现率高的字串尽量合并为一个分词单位 。 4. 双音节加单音节的偏正式名词尽量合并为一个分词单位。 5. 双音节结构的偏正式动词应尽量合并为一个分词单位 。 6. 内部结构复杂、合并起来过于冗长的词尽量切分。
其他分词方法
▶由字构词（基于字标注）的分词方法 ▶生成式方法与判别式方法的结合 ▶全切分方法 ▶串频统计和词形匹配相结合的分词方法 ▶规则方法与统计方法相结合 ▶多重扫描法
Part 5
总结
分词技术水平
自开展中文分词方法研究以来，人们提出的各类方法不下几十种甚至上百 种，不同方法的性能各不相同，尤其在不同领域、不同主题和不同类型的汉语 文本上，性能表现出明显的差异。 总之，随着自然语言处理技术整体水平的提高，尤其近几年来新的机器学 习方法和大规模计算技术在汉语分词中的应用，分词系统的性能一直在不断提 升。特别是在一些通用的书面文本上，如新闻语料，领域内测试（训练语料和 测试语料来自同一个领域）的性能已经达到相当高的水平。但是，跨领域测试 的性能仍然很不理想。如何提升汉语自动分词系统的跨领域性能仍然是目前面 临的一个难题。 另外，随着互联网和移动通信技术的发展，越来越多的非规范文本大量涌 现，如微博、博客、手机短信等。研究人员已经关注到这些问题，并开始研究 。