原标题：非主流自然语言处理——遗忘算法系列（三）：分词   

来源：CSDN          链接：https://blog.csdn.net/gzdmcaoyc/article/details/50085711

分词的原理

分词的原理，可以参看吴军老师《数学之美》中的相关章节，这里摘取Google黑板报版本中的部分：

从上文中，可以知道分词的任务目标：给出一个句子S，找到一种分词方案，使下面公式中的P（S）最大：

不过，联合概率求起来很困难，这种情况我们通常作马尔可夫假设，以简化问题，即：任意一个词wi的出现概率只同它前面的词 wi-1 有关。

关于这个问题，吴军老师讲的深入浅出，整段摘录如下：

另外，如果我们假设一个词与其他词都不相关，即相互独立时，此时公式最简，如下：

这个假设分词无关的公式，也是本文所介绍的分词算法所使用的。

分词的实现

1、算法分析

　　　　问：假设分词结果中各词相互无关是否可行？

　　　　答：可行，前提是使用遗忘算法系列（二）中所述方法生成的词库，理由如下：

分析ICTCLAS广受好评的分词系统的免费版源码，可以发现，在这套由张华平、刘群两位博士所开发分词系统的算法中假设了：分词结果中词只与其前面的一个词有关。

回忆我们词库生成的过程可以知道，如果相邻的两个词紧密相关，那么这两个词会连为一个粗粒度的词被加入词库中，如：除“清华”、“大学”会是单独的词外，“清华大学”也会是一个词，分词过程中具体选用那种，则由它们的概率来决定。

也就是说，我们在生成词库的同时，已经隐含的完成了相关性训练。

关于ICTCLAS源码分析的文章，可以参看吕震宇博文：《天书般的ICTCLAS分词系统代码》。

             问：如何实现分词？

　　　　答：基于前文生成的词库，我们可以假设分词结果相互无关，分词过程就比较简单，使用下面的步骤可以O(N)级时间，单遍扫描完成分词：

逐字扫描句子，从词库中查出限定字长内，以该字结尾的所有词，分别计算其中的词与该词之前各词的概率乘积，取结果值最大的词，分别缓存下当前字所在位置的最大概率积，以及对应的分词结果。

重复上面的步骤，直到句子扫描完毕，最后一字位置所得到即为整句分词结果。

2、实现代码

————————————————————————————————

 /// <summary>

        /// 分词（同时自动维护词典）

        /// </summary>

        /// <param name="text">待分词文本</param>

        /// <param name="objCharBondColl">邻键集合（用于生成词库）</param>

        /// <param name="objKeyWordColl">词库</param>

        /// <param name="maxWordLen">最大词长（建议：细粒度为4、粗粒度为7）</param>

        /// <param name="bUpdateCharBondColl">是否同时更新邻键集合</param>

        /// <param name="bUpdateKeyWordColl">是否同时更新词库</param>

        /// <returns>返回分词结果</returns>

        public static List<string> Segment(string text, MemoryBondColl<string> objCharBondColl, MemoryItemColl<string> objKeyWordColl, int maxWordLen = 7, bool bUpdateCharBondColl = true, bool bUpdateKeyWordColl = true)

        {

            if (String.IsNullOrEmpty(text)) return new List<string>();

            if (maxWordLen == 0) maxWordLen = text.Length;

            //此处使用了个技巧：偶尔发现，词库在遗忘公式作用下，其总量也为相对稳定的固定值，且与MinuteOffsetSize相当。

            //故此处以此替换所有词的遗忘后的总词频，这样可以在处理流式数据时，避免动态计算词库总词频（因其计算量较大）。

            double dLogTotalCount = Math.Log(objKeyWordColl.MinuteOffsetSize, Math.E);

            if (bUpdateCharBondColl || bUpdateKeyWordColl)

            {

                //使用当前待分词语句更新词库，此步骤可与分词同时处理以减少不必要的两遍扫描，此处为代码清晰而拆出。

                WordDictBLL.UpdateKeyWordColl(text, objCharBondColl, objKeyWordColl, bUpdateCharBondColl, bUpdateKeyWordColl);

            }

            //用于缓存各个位置对应的最佳分词结果

            Dictionary<int, List<string>> objKeyWordBufferDict = new Dictionary<int, List<string>>();

            //用于缓存各个位置对应的概率积，避免不必要的重复计算

            Dictionary<int, double> objKeyWordValueDict = new Dictionary<int, double>();

            //逐字扫描

            for (int k = 0; k < text.Length; k++)

            {

                List<string> objKeyWordList = new List<string>();

                double dKeyWordValue = 0;

                //检索以当前字结尾、指定字长内的所有词

                for (int len = 0; len <= Math.Min(k, maxWordLen); len++)

                {

                    int startpos = k - len;

                    string keyword = text.Substring(startpos, len + 1);

                    if (len > 0 && !objKeyWordColl.Contains(keyword)) continue;

                    double dTempValue = 0;

                    if (objKeyWordColl.Contains(keyword))

                    {

                        //计算该词的概率，此处使用对数形式计算，化乘除为加减的同时避免连乘导致的数值过小

                        dTempValue = -(dLogTotalCount - Math.Log(DictionaryDAL.CalcRemeberValue<string>(keyword, objKeyWordColl), Math.E));

                    }

                    if (objKeyWordValueDict.ContainsKey(startpos - 1))

                    {

                        //读取该词之前所有词的概率积对数，并累加上当前词的概率

                        dTempValue += objKeyWordValueDict[startpos - 1];

                        //判断该词的概率是否最大

                        if (dKeyWordValue == 0 || dTempValue > dKeyWordValue)

                        {

                            //如果是，则保存临时结果

                            dKeyWordValue = dTempValue;

                            objKeyWordList = new List<string>(objKeyWordBufferDict[startpos - 1]);

                            objKeyWordList.Add(keyword);

                        }

                    }

                    else

                    {

                        //如果此词是由句首开始的，则无需读取缓存

                        if (dKeyWordValue == 0 || dTempValue > dKeyWordValue)

                        {

                            dKeyWordValue = dTempValue;

                            objKeyWordList = new List<string>();

                            objKeyWordList.Add(keyword);

                        }

                    }

                }

                //记录本位置的最佳结果

                objKeyWordBufferDict.Add(k, objKeyWordList);

                objKeyWordValueDict.Add(k, dKeyWordValue);

            }

            //最后一个字的最佳结果也是整句的最佳结果，即为所求。

            return objKeyWordBufferDict[text.Length - 1];

        }

————————————————————————————————

3、算法特点

　　　　3.1、无监督学习；

　　　　3.2、O(N)级时间复杂度；

　　　　3.3、词库自维护，程序可无需人工参与的情况下，自行发现并添加新词、调整词频、清理错词、移除生僻词，保持词典大小适当；

　　　　3.4、领域自适应：领域变化时，词条、词频自适应的随之调整；

　　　　3.5、支持多语种混合分词。

演示程序下载

　　演示程序与词库生成的相同：

　　下载地址：遗忘算法（词库生成、分词、词权重）演示程序.rar

版权声明：本文为CSDN博主「gzdmcaoyc」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/gzdmcaoyc/article/details/50085711

一THE END一

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com