定义1 交集型歧义和组合型歧义：设字符串S=A₁A₂…A_i…A_i+m…A_j…A_j+n…A_w(i, j, m, n∈{x|1≤x≤w, x∈N+}, j-i≥2，N⁺表示自然数集)，其中A_k表示字符串S中第k个字符 (k∈[1，w])。令S的子串S₁=A_i…A_i+m…A_j，S₂=A_i+m…A_j…A_j+n，S₃=S₁∩S₂ (S₃≠Φ)。如果满足S₁、S₂皆为词，则称S为交集型歧义字符串。令S的子串S₃=A_i…A_j+n，S₄=A_i+m…A_j，(S₃⊂S₄) 如果满足S₃是词，S₄也是词，则称S为子集型歧义字符串。

定义2 结点路径和结点长度：从根节点 (root) 到某个特定结点，经过的结点集合称为这个结点的结点路径。经过结点的总数称为这个结点的结点长度。

定义3 后缀结点：设结点E_a，若存在结点E_b，使得E_c∈(Q-{E_a, E_b})，都有m-f≥0，则称E_b为E_a的后缀结点。其中，结点E_a的路径为a₁a₂a₃…a_m；结点E_b的路径为b₁b₂b₃…b_n(n < m)，且满足a_m-n+i=b_i, i∈{x|1≤x≤n, x∈N⁺}；结点E_c路径为c₁c₂⋯c_f(f < m)，且满足a_m-f+i=c_i, i∈{x|1≤x≤f, x∈N⁺}。

定义4 匹配点和匹配性：若一个结点的结点路径与一个模式串的结点路径相等，称这个结点为匹配点。对于一个结点，如果它是匹配点或者它的后缀结点是匹配点，则认为该结点具有匹配性。

定义5 有限自动机^[14]：一个五元组M=(Q, Σ, g, q₀, T) 称为五元组自动机，其中：Q是状态的有限集合 (所有Tire树上的结点)；Σ是有限输入字母表 (模式串集合)；g是一个从Q×Σ到Q的函数，称作M的转移函数，这个函数指向下一个状态；q₀∈Q指的是初始结点 (Tire树上的根结点以及无关点)；T∈Q指的是自动机M上的匹配点 (接受状态)。

定义6 最长后缀模式子串^[14]：设有结点E_a，若E_b∈Q，$\forall $E_c∈(Q-{E_a, E_b})，都有n-f≥0，则b₁b₂…b_n构成的串叫作结点E_a的最长后缀模式子串；定义结点E_b为结点E_a的模式后缀结点。其中，结点E_a的路径为a₁a₂…a_m；结点E_b的路径为b₁b₂…b_n(n < m)，且满足a_m-n+i=b_i, i∈{x|1≤x≤n, x∈N⁺}，并使得b₁b₂…b_n构成的串是模式串集合中的一个串；结点E_c的路径为c₁c₂…c_f(f < m)，同时满足a_m−f+i=c_i, i∈{x|1≤x≤f, x∈Z+}，并让c₁c₂…c_f构成的串是模式串集合中的一个串。

定义7 耦合度和存在度：在封闭语料库 (有监督) 中，分别以$F (A) F (B)$表示结点路径A、结点路径B出现的次数，$F (A, B)$表示结点路径A与结点路径B作为两个相连的词出现的次数，令$CP (A, B)=\frac{{F (A, B)}}{{F (A) + F (B)}}$，则称${\rm{CP}}(A, B)$为A与B的耦合度。在开放语料库 (无监督) 中，分别以${\rm{CP}}(A, B)$表示结点路径A、结点路径B出现的次数，$f (A, B)$表示结点路径A与结点路径B相连出现的次数，令$\frac{{f (A, B)}}{{f (A) + f (B)}}$，则称${\rm{OP}}(A, B)$为A与B的存在度。

定义8 CPACA中文分词算法：设字符串S=A₁A₂…A_w(w∈N⁺)，其中A_k表示字符串S中第k个字 (k∈[1, w])；设A_k的匹配点集合为T_k=B₁B₂…B_n(n∈N⁺)，T_k按结点长度降序排序，匹配点集合使用Aho-Corasick Automation算法取得，${P_{{\rm{(}}k{\rm{, }}j)}}$表示分词进行到k个字符时，恰以T_k的第j个匹配点B_j为结尾的匹配概率，${P_{{\rm{(0, 1}})}}=1$；${C_{{\rm{(}}k{\rm{, }}j)}}$表示B_j对应的结点路径；${D_{{\rm{(}}k{\rm{, }}j)}}$表示B_j的结点长度 (j∈[1, n])。${P_{{\rm{(}}k{\rm{, }}j)}}$的匹配概率为：${P_{(k, j)}}=\mathop {{\rm{MAX}}}\limits_{1 \le t \le n} ({\rm{MAX}}({P_{(k-{D_{(k, j)}}, t)}} \times {\rm{CP}}({C_{(k-D (k, j), t)}}, {C_{(k, j)}}){\rm{, }}$${\rm{temp}}))$，其中，t为${A_{{\rm{(k-}}{{\rm{D}}_{{\rm{(k, j)}}}})}}$的匹配点集合中选中的匹配点编号，对于每个t：1) 当${D_{(k, j)}} + {D_{(k-{D_{(k, j)}}, t)}} \le {D_{(k, 1)}}$时，temp=0；2) 当${D_{(k, j)}} + {D_{(k-{D_{(k, j)}}, t)}} > {D_{(k, 1)}}$时，${\rm{temp}}=\mathop {{\rm{MAX}}}\limits_{1 \le d \le g} ({P_{(k-{D_{(k, j)}}-{D_{(k-{D_{(k, j)}}, t)}}, d)}} \times {\rm{OP}}({C_{(k-D (k, j), t)}}, {C_{(k, j)}})$，其中，g为${A_{{\rm{(k-}}{D_{(k-{D_{(k, j)}}, t)}})}}$的匹配点总数，d为${A_{{\rm{(k-}}{D_{(k-{D_{(k, j)}}, t)}})}}$的匹配结点集合中选中的匹配点编号。根据统计概率，当${D_{(k, j)}} + {D_{(k, j), t)}} > {D_{(k, 1)}}$时，需考虑两种可能性：①当前模式串和选定的前一个词为词与词的关系；②当前模式串与选定的前一个词共同组成一个词。当${D_{(k, j)}} + {D_{(k-{D_{(k, j)}}, t)}} \le {D_{(k, 1)}}$时，即当前模式串B_j与选定的前一个词共同组成的词的长度小于或等于T_k的最长后缀模式子串长度，则仅考虑可能性。在${D_{(k, j)}} + {D_{(k-{D_{(k, j)}}, t)}} \le {D_{(k, 1)}}$的情况下，设B_j与选定的前一个词共同组成的词存在，则这个词为新词的可能性很小，如设“勤奋”“刻苦”是既有的词，同时，“勤”“奋”“刻”“苦”也分别以单字词的形式存在，出现由“奋”“刻苦”组成的未登录词“奋刻苦”使“勤奋”/“刻苦”被切分成“勤”/“奋刻苦”的可能性很小，并且如“勤”“奋”组成“勤奋”也已为既有词。故这种情况下即使能组成合法的词，极大概率下也是模式串B₁B₁…B_j-1中的一个，并非新词且已经计算过概率了，所以仅需考虑可能性②。综上，分词进行到k个字符时，恰以B_j为结尾的分词方案为${V_{(k, j)}}={V_{(k-{D_{(k, j)}}, t)}} + $#分隔符$+ {C_{(k, j)}}$或${V_{(k, j)}}={V_{{\rm{(}}k-{D_{(k-{D_{(k, j)}}, t)}}, d)}}$+#分隔符$+ {C_{(k-{D_{(k, j)}}, t)}} + {C_{(k, j)}}$。称使用上述方法取得分词方案的算法称为CPACA中文分词算法。

CPACA算法属于机械切分算法，也符合基于统计模型算法的定义。CPACA算法分为4个步骤：1) 语料训练，2) Trie树构建，3) 自动机构建，4) 字符串分割。

语料训练分为封闭语料库训练 (有监督) 与开放语料库训练 (无监督)，其中，训练封闭语料库即给定已完成切分操作的文段，作为语料，在语料中逐词计算当前词与上一个词作为词与词的关系，同时出现的次数，生成CP函数所需的语料库；开放语料库的语料为未进行切分操作的文段，逐字符计算当前字符或词与上一个字符或词同时出现的次数，生成OP函数所需的语料库。语料训练算法的本质是在线性扫描给定数据时，将当前词的模式串编号与下一个词的模式串编号同时作为语料库的索引，累加词语同时出现的次数。封闭语料库训练数据来源有如1998年1月《人民日报》语料库 (PKU) 等；开放语料库的数据可以为任意文段；开放语料库规模越大则未登陆词识别准确度越高。本算法不涉及语料制作。语料训练在现实操作中可用STL中的MAP库或再建一棵Trie树，线性遍历数据，可与本算法中建立Trie树的操作同时进行，记录结点路径两两联合出现的次数。查询时间复杂度可控制在O(1)。

将所有模式串依次逐字符插入Trie树中，插入过程中若在路径中已存在指向当前字符的结点，则访问到该结点，如无相对应的结点，则新建一个指向当前字符的结点，若一个模式串完成插入，标记其路径中最后一个结点。

Trie树在初始状态时，仅含有一个结点root (根节点，root的编号为0)，设模式串P=C₁C₂…C_n，当前字符C_i在Trie树中的结点编号为now[C_i]，C_i所在结点的子结点中通过C_i+1转移到的状态结点编号为next (now[C_i], C_i+1)，初始状态为now[C_i]=next (now[0], C_i)；通式为now[C_i+1]=next (now[C_i], C_i+1)，当now[C_i+1]=Null时，即当前无相对应结点，则创建新的结点，并用新的结点编号赋值now[C_i+1]和next (now[C_i], C_i+1)；当且仅当当前完成了一个模式串的插入，mp[now[C_i]]表示当前模式串编号的映射。done[now[C_i]]=True，length[mp[now[C_i]]]的值为该模式串的长度，mp[now[C_i]]的值为当前模式串的编号，link[now[C_i]]表示当前以C_i为结尾的结点的最长后缀模式子串的结尾结点编号。将树上所有结点的link[now[C_i]](后缀子串链表) 赋值为-1。反复执行以上所有过程，完成插入所有模式串后，Trie树构建完毕。

实例：

创建模式串集合P={“独立”“独立自主”“自主”“自主权”“自主平等”“平等”“平等互利”“互利”“互利互惠”“互利合作”“和平”“原则”“五项原则”“立”“主”，“等”“权”“利”“惠”“合”“作”“则”“项”}。如图 1所示，灰色结点表示匹配点 (该节点的done为真)。

图  1  Trie树图

通过广度优先遍历整棵树，根据KMP算法，得到每一个结点的指针fail并构建后缀子串链表。自动机在主串扫描失配时，fail指针指向失配情况发生后的可行情况 (后缀结点)。设now结点的后缀结点fail (now) 的模式串结束标志为true, 即done[*fail (now)]=true，则link[now]=fail (now)，否则，link[now]=link[*fail (now)]。

从任意一个结点now来看，首先遍历now的子字符集合，设存在通过now转移的子结点S，则将该子结点的编号加入到搜索队列然后计算link (now)，再对该结点的后缀子串链表信息进行更新。否则，计算fail (next (now, S)) 的值。构建完成后，得到全部结点的最长后缀模式子串的结点编号以及失配指针fail。

实例 模式串集合P中构建自动机后，黑色虚线箭头指向fail指针指向的对象，灰色虚线箭头指向link指针指向的对象，工作原理如图 2所示。

图  2  自动机工作原理图

字符串分割的算法是CPACA算法的关键部分，从自动机的q₀(起始状态) 开始，以字符串中每个字符为依据进行转移，逐字符遍历其最长后缀模式子串集合直至根节点，计算当前匹配点与上文联合出现的概率，直到完成字符串的匹配。

在字符串分割的过程中，设字符串T=t₁t₂…t_n。从q₀(初始状态) 开始，使用函数move (q_i, t_i+1) 进行状态转移，再使用后缀子串链表信息，更新模式串的匹配信息。归功于五元组自动机的预处理结果，在move (q_i, t_i+1) 失败的时候，当前指针直接转移到后继结点上，继续匹配 (next (q_i, t_i+1) 存储了后继结点编号)。在遍历文本时，通过指针link找到所有的后缀模式子串、计算匹配概率。当文本遍历结束后，便得到了最优的分词方案 (程序语句见算法3)。由于字符串规格与语料库规格的扩大，匹配概率也增大，故现实应用中应采用长整型存储或者高精度存储方式。

实例 使用模式串集合P对字符串“独立自主和平等互利”进行分词，运用CPACA算法，从q₀(初始状态) 开始，进行状态转移，直至字符串分词完毕，字符串分词过程如表 1所示。

目前存在的交集型歧义、组合型歧义和真歧义中，除了真歧义是不可避免的外，交集型歧义 (如“脑海里”，可被分为{“脑”“海里”}和{“脑海”“里”}) 和组合型歧义 (如“才能”，在句子“杰出的才能”和“有他才能胜出”中可被分为{“才”“能”}或{“才能”}) 是可以避免的。产生歧义的原因都是因为存在多种切分可能性，而计算机采取了错误的切分。切分具有后效性，因此，一处切分错误常导致全文分词错位，因此能否较好地解决歧义分词问题是衡量分词算法性能好坏的重要标准。

temp=0时进行。例如，“脑海里”这个交集型歧义词，现在采用CPACA算法对第X个字符 (里) 进行切分，则Y(脑海里)=max (${P_{(x-1, {t_1})}}$xCP (“脑”“海里”)，${P_{(x-2, {t_2})}}$xCP (“脑海”“里”))；对于“杰出的才能”和“有他才能胜出”这两个子集型歧义词，设当前对第X个字符 (能) 进行切分，则{杰出的才能}=max (${P_{(x-2, t)}}$xCP (“的”“才能”)，P_{(x-1, t)} xCP (“才”“能”)) 和{有他才能胜出}=max (P_{(x-2, t)}xCP (“才能”“胜出”)，P_{(x-2, t)}xCP (“能”“胜出”))。结合上下文，将所有存在的切分可能性进行比较，取正确几率最高的一种，因此，可保证输出结果为全文分词正确率最高的方案。这样既解决了机械分词方法中存在的歧义问题，同时又解决了基于概率模型“无词库”对常用词的识别精度差的问题，提高了概率模型的识别准确度。

可将未登录词分为4类：1) 形态上发生变化的词，如漂漂亮亮是漂亮的叠词；2) 固定表达，如“三百次”“一百天”；3) 命名实体，如“毛泽东”“习近平”；4) 新词，如“阅兵蓝”“学霸”。大多数情况下这些词语切分错误不会影响上下文识别，如“学霸的世界我不了解”在不进行未登录词识别时，切分结果为“学/霸/的/世界/我/不/了解”，除了“学霸”切分错误外，下文并未出现切分错位的情况。相较其他切分算法，CPACA较为容易检测出未登录词，根据定义8中处理未登录词的转移方程：

当两个字符串A、B叠加在一起的长度大于字符串B的匹配点的最长后缀模式子串 (${D_{(k, j)}} + {D_{(k, j), t)}} > {D_{(k, 1)}}$)，即A、B组成一个词的记录在封闭语料库里不存在，则组成的词有一定可能性是一个未登录词，则将A、B的耦合度CP (A, B) 与A、B的存在度OP (A, B) 对比，若存在度高于耦合度，则认为AB的组合为未登录词。这种方法将机械切分、无监督模型概率与有监督模型概率实时对比，有效地提高了识别的准确度。

英文单词间用空格隔开，不具有歧义性，但拼音串没有音节与音节间隔离的标准，如拼音串“xian”可以划分为“xi an”(代表“西安”及其同音词)，也可以划分为“xian”(表示“先”及其同音词)。对于拼音串中一段的切分错误可能会导致一整个句子出现问题，如“xianggangren”原意为“香港人”，如第一个音节被分解为“xi an”，无论后文如何切分都无法得出正确结果。诸如此类的问题使得计算机在分解、识别拼音串和拼音输入法连拼时产生麻烦。就此，根据CPACA算法，从统计的角度出发，当拼音串只为“xian”时，使用者想表达“西安”的概率远高于“先”，但对于“woxianqushangxue”，翻译为“我先去上学”的几率远高于“我西安去上学”，即在概率模型中，“xian”与“qu”组合的可能性高于“xi”“an”“qu”。采用CPACA算法的拼音输入法可以长期学习输入者输入的语句，丰富统计模型，最大程度上减少了拼音分词的错误，使得拼音分词愈发精准。

设|Q|表示字母表的规模，N是字符串规模，q表示模式串的数量，M_i表示第i个模式串的长度，模式串的规模总共为$\sum\limits_{i=1}^q {{M_i}} $，${\rm{LinkNUM}}(i)$表示i号模式串的后缀模式子串链表长度，最长后缀模式子串总指针规模为$\sum\limits_{i=1}^q {{\rm{LinkNUM}}(i)} $。

预处理这个阶段主要包括Trie树的建立和AC自动机的构建。在建立Trie树时，将每个结点都赋值为初态，这时空间规模为字母表规模，可见在Trie树建立过程中，最坏的时间复杂度是$O\left ({|Q|\sum\limits_{i=1}^q {{M_i}} } \right)$；在使用广度优先规则，遍历Trie树时 (构建AC自动机)，同样对每个结点进行询问，故遍历Trie树的最坏时间复杂度同样也为$O\left ({|Q|\sum\limits_{i=1}^q {{M_i}} } \right)$。

分词过程中，文本指针不会回溯，且保持移动为线性，枚举后缀模式子串的时间复杂度为$O\left ({|Q|\sum\limits_{i=1}^q {{\rm{LinkNUM}}(i)} } \right)$，CP函数与OP函数枚举每个模式子串之前的匹配可能性的最坏时间总复杂度为$O\left ({|Q|{{\left ({\sum\limits_{i=1}^q {{\rm{LinkNUM}}(i)} } \right)}^2}} \right)$，自动机状态转移是O (1) 时间复杂度，所以，字符串分词过程的最坏时间复杂度为$O\left ({|Q|{{\left ({\sum\limits_{i=1}^q {{\rm{LinkNUM}}(i)} } \right)}^3}N} \right)$。

综上所述，在最坏情况下，CPACA算法的时间复杂度为$O\left ({N + |Q|\sum\limits_{i=1}^q {{M_i}} + |Q|{{\left ({\sum\limits_{i=1}^q {{\rm{LinkNUM}}(i)} } \right)}^3} \times N} \right)$。通过导入1998年1月的《人民日报》语料库 (PKU) 得出，任意$O\left ({N + |Q|\sum\limits_{i=1}^q {{M_i}} + |Q|{{\left ({\sum\limits_{i=1}^q 2 } \right)}^3}N} \right)$，因此总的最坏时间复杂度约为$O\left ({N + |Q|\sum\limits_{i=1}^q {{M_i}} + |Q|{{\left ({\sum\limits_{i=1}^q 2 } \right)}^3}N} \right)$。

本文实验使用一台HP-Z800服务器 (英特尔四核处理器X5570，内存为3 GB，操作系统为Noi Linux)。

有监督训练数据采用Sighan 2005 bakeoff分词语料中由北京大学标注的数据，对CPACA所需的耦合度数据库进行训练，存在度数据库的数据取自搜狗新闻语料 (120 MB)。采取十折交叉验证，在分词实验中，首先将北京大学语料库随机平均分成10份，任意选取其中1份作为测试数据，9份作为耦合度训练数据，将分词实验步骤重复10遍，得到10次实验结果，再与已有算法的分词效果进行对比，评测分词效果的指标有以下4个 (R表示召回率、P表示准确率、F₁为F-值、O为未登录词召回率)：

碍于篇幅，本文将前5次结果与后5次结果分别取平均数据，结果如表 2所示。参与比较的算法是：改进的逆向最大匹配算法^[2](算法A)、消除中文分词中交集型歧义的方法^[3](算法B)、改进的正向最大匹配算法^[5](算法C)、基于粗分和词性标注的中文分词方法^[7](算法D)、表示学习算法^[8](算法E)、改进概率统计算法^[9](算法F)、树形结构算法^[15](算法G)、带词长词典与判断消除算法^[16](算法H)。此外，就合计准确率而言，可进行比较的分词方法有：Sighan2005最佳成绩 (封闭)，Sighan2005最佳成绩 (开放)，它们的合计准确率分别为94.6%和96.8%^[8]。

从表 2所示的数据可以看出，CPACA算法的准确率达到95%以上，对歧义字段有很好的消除效果，通过与近年提出的方法相对比，说明该方法具有较高的准确度。导致错误切分的原因主要有：1) 字符串中含有过分生僻人名或部分罕见地名；2) 字符串中含有古汉语；3) 字符串中存在错别字。

在不同的文本长度下，不同算法的分词耗时比较如图 3所示，实验数据从“腾讯大闽网”抓取，为2014年全年福建本土新闻稿随机组合形成；耦合度数据库规模和存在度数据库规模皆为固定的150万词 (随机生成)。

图  3  分词耗时比较

从图 3可见，CPACA算法分词速度在所有参加测试的算法中排第4位，与准确率相近的算法E、算法F、算法C相比具有较大优势。并且，这种优势伴随数据规模的增大而愈发明显。由此可见CPACA算法适用于屏蔽词检测或网页搜索等需高准确率且流量巨大的工程当中。

在AC自动机的基础上，提出了CPACA中文分词算法。经过实验验证，CPACA算法不仅具有很好的实用性，而且在字符串规模大、模式串规模大、数量多的现实情况下，提高了分词的准确率。

CPACA算法分词准确率很大程度上取决于耦合度与存在度，两者的语料库丰富与否都是分词准确率的决定性因素，但目前存在封闭语料库规模小的问题，华人打字习惯主要以拼写词组或短语的方式，鲜少一次性拼写一整个句子，因此，今后可研究拼音、五笔等输入法如何在用户输入的同时自动获取文段的分词方案。在拼音输入法中加入切分记录的功能，建立如云语料库等方法，使封闭语料库也可通过无监督的方式来自我学习、自动更新，及时加入新近未登录词，从而进一步提高中文分词的准确率。

CPACA算法在一定程度上使得中文分词更加准确，但随着字符集、模式串的增大，导致算法所需的空间不断加大，因此，后续研究将在保证准确率的基础上，研究怎样减小该算法的空间复杂度。