基于最小费用最大流的中文分词算法模型

马凌霄

摘 要：中文自动分词不仅是中文信息处理的基础性工作而且对后续句法分析、语义分析等中文信息处理流程有着很大的影响。本文基于最小费用最大流，提出一个具有拓展性的中文分词算法模型，实验证明了本算法能够准确地对输入文字串进行切分。

关键词：中文分词 最小费用最大流 字符串匹配 中文信息处理

中图分类号：TP319 文献标识码：A 文章编号：1672-3791（2014）09（b）-0219-01

随着人工智能的快速发展，中文信息处理已经在搜索引擎、Web文本挖掘、自动文摘、文本校对等领域发挥越来越重要的作用。中文自动分词不仅是中文信息处理的一项基础性工作而且是严重制约中文信息处理发展的瓶颈之一。本文致力于中文自动分词算法的研究，基于最小费用最大流的原理提出一个具有拓展性的中文分词算法模型。

1 中文自动分词算法简述

中文分词的基本方法是基于已有词典库或者规则库，针对输入文字的字符串做分词、过滤处理，输出最优切分的中文单词[1]。

中文分词算法主要分为以下四类[1-3]：

（1）基于字符串匹配的分词方法：按照一定的字符串匹配策略，将输入文字的字符串与词典库中的词条进行匹配，若匹配成功，则进行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐词遍历法等。

（2）基于规则的分词方法：将基于字符串匹配的分词算法与分词规则库结合，采用不同的策略对输入语句进行切分，切分一致的部分判定为切分正确，不一致的部分为歧义字段。

（3）基于统计的分词方法：采用多种切分策略对输入字符串进行切分，根据分词词典匹配出所有可能的切分情况并计算切分的概率，求出概率最大的切分策略作为切分结果。

（4）基于理解的分词方法：在分词的过程中，不仅进行字符串的切分，而且进行句法分析、语义分析，利用句法和语义信息处理切分歧义。目前此方法尚处于试验阶段。

本文提出的基于最小费用最大流的中文分词算法模型即为基于字符串匹配的分词方法，而且此分词算法模型可以拓展为基于统计的分词方法。

2 基于最小费用最大流的中文分词算法模型

2.1 最小费用最大流

最小费用最大流问题的定义如下：设是一个有向图，为起点（源点），为终点（汇点），其中每一条边均有一个非负容量、一个费用和一个不大于容量的流量，问怎样制定运输方案使得从到的流量最大且总费用最小？

最小费用最大流问题的求解途径有两种[4]：（1）保持网络中的可行流是最大流，逐步调整使得总费用逐步减小，最终得到最大流量的最小费用流；（2）保持网络中的可行流是最小费用流，逐步调整使得流量逐步增大，最终得到最小费用的最大流。显然第二种途径与已知最大流问题的求解算法相近，并可以将问题转化为一个求从点到点的最短路径问题：不断以费用为权值，使用最短路径算法，寻找一条从点到点的最小费用增广路，直至找不到从点到点的增广路。

2.2 中文分词算法模型

基于上述最小费用最大流模型，下面给出基于最小费用最大流的中文分词算法模型。

（1）将输入文字串进行全切分。

①删去输入文字串的空格、回车等非中文字符。

②将得到的字符串对切分大小从1到7进行反复切分，并在词典库中查找切分结果：找到，则在词表增加一条记录；没找到，则忽略此次切分结果。

（2）基于全切分的结果建图。

①遍历全切分结果词表：对词表每一条记录添加一个顶点。如果词表两个记录，是相邻的，则建立一条从到的有向边，容量，费用，流量。

②将源点与字符串第一个词对应的顶点建立一条从到的有向边，容量，费用，流量。

③将字符串最后一个词对应的顶点与汇点与建立一条从到的有向边，容量，费用，流量。

（3）求解此最小费用最大流问题。

①在只允许通过容量-流量>0的边的限制下，以费用为权值，使用SPFA算法[5]求从源点到汇点的一条最短路径，即最小费用增广路。

②对于（a）中求得的路径，令路径上的每一条边的流量=容量。

③重复（a）（b）过程，直至无法找到从源点到汇点的最短路径。

（4）从源点遍历整个图，对于任意一条有向边，如果流量，输出顶点和对应的中文单词。即可得到中文分词结果。

2.3 模型拓展

在上述分词算法模型的基础上，通过改变边的费用权值，可以将算法拓展为基于统计的分词方法。下面给出一种拓展方法[3]。

（1）设词典包括个词条，则为这个词条建立的马尔科夫一阶转移矩阵，其中

。

（2）建立从到的有向边时，令费用。

这样我们就得到一个基于统计方法的最小费用最大流中文分词算法。

3 算法分析与实验

3.1 算法的时间复杂度分析

设输入字符串长度为，每次查询词典库的时间复杂度为，则对字符串进行全切分的时间复杂度为；设有向图的顶点个数为，边的个数为，寻找最小费用增广路的次数为，则每次求解从源点到汇点的最短路径的时间复杂度为[5]，求解最小费用最大流问题的时间复杂度为。综合上述两个步骤的时间复杂度，中文分词算法总时间复杂度为。

3.2 实验

为了验证本文提出的中文分词算法的准确性，本文使用教育部语言文字应用研究所《现代汉语语料库词频表》[6]作为词典库，对50篇新闻文章进行中文分词，分词正确率达到96.81%，说明了此分词算法具有很高的准确性。

4 结语

本文提出的基于最小费用最大流的中文分词算法模型不仅能准确地切分输入字符串，而且可以通过改变费用权值拓展算法考虑的切分标准来提高切分准确度，具有很好的拓展性。

参考文献

[1] 龙树全，赵正文，唐华.中文分词算法概述[J].电脑知识与技术，2009，5（10）： 2605-2607.

[2] 黄昌宁，赵海.中文分词十年回顾[J].中文信息学报，2007，21（3）：8-19.

[3] 宋继华，杨尔弘，王强军.中文信息处理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.

[6] 教育部语言文字应用研究所.现代汉语语料库词频表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint

摘 要：中文自动分词不仅是中文信息处理的基础性工作而且对后续句法分析、语义分析等中文信息处理流程有着很大的影响。本文基于最小费用最大流，提出一个具有拓展性的中文分词算法模型，实验证明了本算法能够准确地对输入文字串进行切分。

关键词：中文分词 最小费用最大流 字符串匹配 中文信息处理

中图分类号：TP319 文献标识码：A 文章编号：1672-3791（2014）09（b）-0219-01

随着人工智能的快速发展，中文信息处理已经在搜索引擎、Web文本挖掘、自动文摘、文本校对等领域发挥越来越重要的作用。中文自动分词不仅是中文信息处理的一项基础性工作而且是严重制约中文信息处理发展的瓶颈之一。本文致力于中文自动分词算法的研究，基于最小费用最大流的原理提出一个具有拓展性的中文分词算法模型。

1 中文自动分词算法简述

中文分词的基本方法是基于已有词典库或者规则库，针对输入文字的字符串做分词、过滤处理，输出最优切分的中文单词[1]。

中文分词算法主要分为以下四类[1-3]：

（1）基于字符串匹配的分词方法：按照一定的字符串匹配策略，将输入文字的字符串与词典库中的词条进行匹配，若匹配成功，则进行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐词遍历法等。

（2）基于规则的分词方法：将基于字符串匹配的分词算法与分词规则库结合，采用不同的策略对输入语句进行切分，切分一致的部分判定为切分正确，不一致的部分为歧义字段。

（3）基于统计的分词方法：采用多种切分策略对输入字符串进行切分，根据分词词典匹配出所有可能的切分情况并计算切分的概率，求出概率最大的切分策略作为切分结果。

（4）基于理解的分词方法：在分词的过程中，不仅进行字符串的切分，而且进行句法分析、语义分析，利用句法和语义信息处理切分歧义。目前此方法尚处于试验阶段。

本文提出的基于最小费用最大流的中文分词算法模型即为基于字符串匹配的分词方法，而且此分词算法模型可以拓展为基于统计的分词方法。

2 基于最小费用最大流的中文分词算法模型

2.1 最小费用最大流

最小费用最大流问题的定义如下：设是一个有向图，为起点（源点），为终点（汇点），其中每一条边均有一个非负容量、一个费用和一个不大于容量的流量，问怎样制定运输方案使得从到的流量最大且总费用最小？

最小费用最大流问题的求解途径有两种[4]：（1）保持网络中的可行流是最大流，逐步调整使得总费用逐步减小，最终得到最大流量的最小费用流；（2）保持网络中的可行流是最小费用流，逐步调整使得流量逐步增大，最终得到最小费用的最大流。显然第二种途径与已知最大流问题的求解算法相近，并可以将问题转化为一个求从点到点的最短路径问题：不断以费用为权值，使用最短路径算法，寻找一条从点到点的最小费用增广路，直至找不到从点到点的增广路。

2.2 中文分词算法模型

基于上述最小费用最大流模型，下面给出基于最小费用最大流的中文分词算法模型。

（1）将输入文字串进行全切分。

①删去输入文字串的空格、回车等非中文字符。

②将得到的字符串对切分大小从1到7进行反复切分，并在词典库中查找切分结果：找到，则在词表增加一条记录；没找到，则忽略此次切分结果。

（2）基于全切分的结果建图。

①遍历全切分结果词表：对词表每一条记录添加一个顶点。如果词表两个记录，是相邻的，则建立一条从到的有向边，容量，费用，流量。

②将源点与字符串第一个词对应的顶点建立一条从到的有向边，容量，费用，流量。

③将字符串最后一个词对应的顶点与汇点与建立一条从到的有向边，容量，费用，流量。

（3）求解此最小费用最大流问题。

①在只允许通过容量-流量>0的边的限制下，以费用为权值，使用SPFA算法[5]求从源点到汇点的一条最短路径，即最小费用增广路。

②对于（a）中求得的路径，令路径上的每一条边的流量=容量。

③重复（a）（b）过程，直至无法找到从源点到汇点的最短路径。

（4）从源点遍历整个图，对于任意一条有向边，如果流量，输出顶点和对应的中文单词。即可得到中文分词结果。

2.3 模型拓展

在上述分词算法模型的基础上，通过改变边的费用权值，可以将算法拓展为基于统计的分词方法。下面给出一种拓展方法[3]。

（1）设词典包括个词条，则为这个词条建立的马尔科夫一阶转移矩阵，其中

。

（2）建立从到的有向边时，令费用。

这样我们就得到一个基于统计方法的最小费用最大流中文分词算法。

3 算法分析与实验

3.1 算法的时间复杂度分析

设输入字符串长度为，每次查询词典库的时间复杂度为，则对字符串进行全切分的时间复杂度为；设有向图的顶点个数为，边的个数为，寻找最小费用增广路的次数为，则每次求解从源点到汇点的最短路径的时间复杂度为[5]，求解最小费用最大流问题的时间复杂度为。综合上述两个步骤的时间复杂度，中文分词算法总时间复杂度为。

3.2 实验

为了验证本文提出的中文分词算法的准确性，本文使用教育部语言文字应用研究所《现代汉语语料库词频表》[6]作为词典库，对50篇新闻文章进行中文分词，分词正确率达到96.81%，说明了此分词算法具有很高的准确性。

4 结语

本文提出的基于最小费用最大流的中文分词算法模型不仅能准确地切分输入字符串，而且可以通过改变费用权值拓展算法考虑的切分标准来提高切分准确度，具有很好的拓展性。

参考文献

[1] 龙树全，赵正文，唐华.中文分词算法概述[J].电脑知识与技术，2009，5（10）： 2605-2607.

[2] 黄昌宁，赵海.中文分词十年回顾[J].中文信息学报，2007，21（3）：8-19.

[3] 宋继华，杨尔弘，王强军.中文信息处理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.

[6] 教育部语言文字应用研究所.现代汉语语料库词频表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint

摘 要：中文自动分词不仅是中文信息处理的基础性工作而且对后续句法分析、语义分析等中文信息处理流程有着很大的影响。本文基于最小费用最大流，提出一个具有拓展性的中文分词算法模型，实验证明了本算法能够准确地对输入文字串进行切分。

关键词：中文分词 最小费用最大流 字符串匹配 中文信息处理

中图分类号：TP319 文献标识码：A 文章编号：1672-3791（2014）09（b）-0219-01

随着人工智能的快速发展，中文信息处理已经在搜索引擎、Web文本挖掘、自动文摘、文本校对等领域发挥越来越重要的作用。中文自动分词不仅是中文信息处理的一项基础性工作而且是严重制约中文信息处理发展的瓶颈之一。本文致力于中文自动分词算法的研究，基于最小费用最大流的原理提出一个具有拓展性的中文分词算法模型。

1 中文自动分词算法简述

中文分词的基本方法是基于已有词典库或者规则库，针对输入文字的字符串做分词、过滤处理，输出最优切分的中文单词[1]。

中文分词算法主要分为以下四类[1-3]：

（1）基于字符串匹配的分词方法：按照一定的字符串匹配策略，将输入文字的字符串与词典库中的词条进行匹配，若匹配成功，则进行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐词遍历法等。

（2）基于规则的分词方法：将基于字符串匹配的分词算法与分词规则库结合，采用不同的策略对输入语句进行切分，切分一致的部分判定为切分正确，不一致的部分为歧义字段。

（3）基于统计的分词方法：采用多种切分策略对输入字符串进行切分，根据分词词典匹配出所有可能的切分情况并计算切分的概率，求出概率最大的切分策略作为切分结果。

（4）基于理解的分词方法：在分词的过程中，不仅进行字符串的切分，而且进行句法分析、语义分析，利用句法和语义信息处理切分歧义。目前此方法尚处于试验阶段。

本文提出的基于最小费用最大流的中文分词算法模型即为基于字符串匹配的分词方法，而且此分词算法模型可以拓展为基于统计的分词方法。

2 基于最小费用最大流的中文分词算法模型

2.1 最小费用最大流

最小费用最大流问题的定义如下：设是一个有向图，为起点（源点），为终点（汇点），其中每一条边均有一个非负容量、一个费用和一个不大于容量的流量，问怎样制定运输方案使得从到的流量最大且总费用最小？

最小费用最大流问题的求解途径有两种[4]：（1）保持网络中的可行流是最大流，逐步调整使得总费用逐步减小，最终得到最大流量的最小费用流；（2）保持网络中的可行流是最小费用流，逐步调整使得流量逐步增大，最终得到最小费用的最大流。显然第二种途径与已知最大流问题的求解算法相近，并可以将问题转化为一个求从点到点的最短路径问题：不断以费用为权值，使用最短路径算法，寻找一条从点到点的最小费用增广路，直至找不到从点到点的增广路。

2.2 中文分词算法模型

基于上述最小费用最大流模型，下面给出基于最小费用最大流的中文分词算法模型。

（1）将输入文字串进行全切分。

①删去输入文字串的空格、回车等非中文字符。

②将得到的字符串对切分大小从1到7进行反复切分，并在词典库中查找切分结果：找到，则在词表增加一条记录；没找到，则忽略此次切分结果。

（2）基于全切分的结果建图。

①遍历全切分结果词表：对词表每一条记录添加一个顶点。如果词表两个记录，是相邻的，则建立一条从到的有向边，容量，费用，流量。

②将源点与字符串第一个词对应的顶点建立一条从到的有向边，容量，费用，流量。

③将字符串最后一个词对应的顶点与汇点与建立一条从到的有向边，容量，费用，流量。

（3）求解此最小费用最大流问题。

①在只允许通过容量-流量>0的边的限制下，以费用为权值，使用SPFA算法[5]求从源点到汇点的一条最短路径，即最小费用增广路。

②对于（a）中求得的路径，令路径上的每一条边的流量=容量。

③重复（a）（b）过程，直至无法找到从源点到汇点的最短路径。

（4）从源点遍历整个图，对于任意一条有向边，如果流量，输出顶点和对应的中文单词。即可得到中文分词结果。

2.3 模型拓展

在上述分词算法模型的基础上，通过改变边的费用权值，可以将算法拓展为基于统计的分词方法。下面给出一种拓展方法[3]。

（1）设词典包括个词条，则为这个词条建立的马尔科夫一阶转移矩阵，其中

。

（2）建立从到的有向边时，令费用。

这样我们就得到一个基于统计方法的最小费用最大流中文分词算法。

3 算法分析与实验

3.1 算法的时间复杂度分析

设输入字符串长度为，每次查询词典库的时间复杂度为，则对字符串进行全切分的时间复杂度为；设有向图的顶点个数为，边的个数为，寻找最小费用增广路的次数为，则每次求解从源点到汇点的最短路径的时间复杂度为[5]，求解最小费用最大流问题的时间复杂度为。综合上述两个步骤的时间复杂度，中文分词算法总时间复杂度为。

3.2 实验

为了验证本文提出的中文分词算法的准确性，本文使用教育部语言文字应用研究所《现代汉语语料库词频表》[6]作为词典库，对50篇新闻文章进行中文分词，分词正确率达到96.81%，说明了此分词算法具有很高的准确性。

4 结语

本文提出的基于最小费用最大流的中文分词算法模型不仅能准确地切分输入字符串，而且可以通过改变费用权值拓展算法考虑的切分标准来提高切分准确度，具有很好的拓展性。

参考文献

[1] 龙树全，赵正文，唐华.中文分词算法概述[J].电脑知识与技术，2009，5（10）： 2605-2607.

[2] 黄昌宁，赵海.中文分词十年回顾[J].中文信息学报，2007，21（3）：8-19.

[3] 宋继华，杨尔弘，王强军.中文信息处理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.

[6] 教育部语言文字应用研究所.现代汉语语料库词频表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint