基于字典的简单中文分词算法

做自然语言处理，尤其是中文自然语言处理，文本分词是必不可少的过程。其实不仅仅是中文，大多数亚洲的语言文字在计算机做处理时，都需要进行分词，甚至英文在识别短语时也要进行类似中文分词的过程。所以，我们需要一种有效的分词算法，这里我仅以中文做实例，其他语言可以参考，介绍一种简单的中文分词算法，并附上一个C#版的示例代码。

1. 正向最大匹配

正向最大匹配是说，对一句话，我们从第一个字开始，在字典中寻找能够最大程度匹配的词，找不到匹配时就从最后减去一个字，直到最后只剩下一个字，之后在此做切分。比如：

我们明天去野生动物园游玩。

在字典中查找时，算法运行结果如下：

我们明天去野生动物园游玩       （未找到）

我们明天去野生动物园游   （未找到）

我们明天去野生动物园        （未找到）

。。。。。。

我们/       （找到）

我们/明天去野生动物园游玩      （未找到）

我们/明天去野生动物园游 （未找到）

。。。。。。

我们/明天/     （找到）

……

我们/明天/去/野生动物园/游玩 （找到）

 

我们可以看到，最终可以将字典中包含的词以最大颗粒度切分出来。但是，这样明显可以发现，很多次匹配都是无用功，因为我们可以发现，在最初的几次匹配时，那么长的字符串明显不可能是一个登录汉语词典的词，所以，我们可以设定一个最大长度，比如6，只查找6个字以内的词，这样可以节省很多时间，或者知道了字典中最多只有5个字的词语，那么我们就没必要查找5个字以上的词。据统计，汉语中，绝大多数词都在4字或4字以内，5字以上的词数量很少，所以，在一定程度上，我们可以忽略它们。

但是，正向最大匹配有较大歧义性，所以很多人比较推荐逆向最大匹配，因为歧义性比正向要低。什么是歧义性呢？举个栗子：

团购网站的本质是什么？

如果是正向最大匹配，那么很可能切分成这样：

团购网/站/的/本质/是/什么/？

我们应该切分成“团购网站”或者“团购/网站”，可能你的字典中没有“团购网站”这个词，但是有“团购网”这个词，那么就会出现上述情况。不仅仅这样，在很多类似的情况下，正向最大匹配中，这种歧义性更明显，也更难克服。

 

2. 逆向最大匹配

逆向最大匹配是正向最大匹配的逆过程，它是从字符串结尾开始的，不过，具体的方法还是一样的，只是反过来了。而且，歧义性较低。

还是上述那句本来有歧义的切分，在逆向最大匹配分词之后，可以得到如下结果：

团购/网站/的/本质/是/什么/？

我们可以看到，句子被正确地切分了。

当然，逆向最大匹配也是有歧义性的，而且有些是在正向最大匹配中不会出错的，但是整体来说歧义没有正向那么大。如果你一定要解决的话，还有一种方案——双向最大匹配。

3. 双向最大匹配

顾名思义，就是正向和逆向的结合，在切分不一致时重新进行判断。分词的过程也是一个消除歧义的过程，进行这种算法时，两种算法都切一遍，然后根据大颗粒度词越多越好，非词典词和单字词越少越好的原则，选取其中一种分词结果输出。

我们使用这样一句话做样例：

我们在野生动物园玩

在正向最大匹配时，切分结果是：“我们/在野/生动/物/园/玩”，经过统计我们可以发现，两字词有3个，单字字典词为2个，非词典词为1。而逆向最大匹配时，切分结果是：“我们/在/野生动物园/玩”，统计结果是，五字词有1个，两字词有1个，单字字典词为2个，非词典词为0个。我们遵循上述切分规则：

非字典词：正向(1)>逆向(0)（越少越好）

单字字典词：正向(2)=逆向(2)（越少越好）

总词数：正向(6)>逆向(4)（越少越好）

因此，最终输出使用逆向切分作为结果。

 

以上的分词方案，有它的优点，比如方法很简单，容易实现，但是同时也有很大的局限性，一词多义问题、歧义问题和未登录词识别的问题等，这对中文分词准确率有直接影响。上述3种都属于机械分词方法，而现在也有一些其他方法，比如：基于理解的分词方法，基于统计的分词等。国内外有众多的中文分词项目在研究，其中不乏开源项目，比如“结巴分词”。作为搜索引擎、人机交互等重要应用中必不可少的一个环节，中文分词在目前（2017年）的技术中，已经有很多比较成熟的产品了，这里我就不一一列举，但是追求对其技术改进的脚步是永不停止的，希望之后相关技术能够继续取得持续的进步。

 

参考文献：

[1] 李淑英. 中文分词技术[J]. 科技信息:科学·教研, 2007(36):97.

[2] 知乎网. 有哪些比较好的中文分词方案？ 2011. https://www.zhihu.com/question/19578687

[3] hfgang. 中文分词基础原则及正向最大匹配法、逆向最大匹配法、双向最大匹配法的分析 新浪博客, 2012. http://blog.sina.com.cn/s/blog_53daccf401011t74.html

 

附：

 

private void sub_dic(string datapath, string dicpath,string resultpath)
{//datapath为待分词文本文件路径，dicpath为字典路径，resultpath为结果路径
    string text = System.IO.File.ReadAllText(datapath);//语言数据读取
    //Console.WriteLine(text);

    //string[] s = ReadDic(dicpath);//对普通列表字典的读取
    
    List<string> diclst = ReadDic2(dicpath);//对包含词频统计分隔符和频数的字典的词的读入
    int wordlength = GetDicMaxLength(diclst);//获取字典中最大长度词的长度

    List<string> strlst = new List<string>() { };


    
    //核心算法
    for (int i=text.Length-1;i>=0;i--)
    {
        for(int j=0;j<=wordlength;j++)
        {
            string tmp;
            int left = 0;
            if (i - wordlength + j + 1 >= 0)
            {
                left = i - wordlength + j + 1;
                tmp = text.Substring(left, wordlength - j);
            }
            else
            {
                left = 0;
                tmp = text.Substring(left, i + 1);
            }
            if (diclst .Contains (tmp) || tmp.Length ==1)
            {
                strlst.Add(tmp);
                i = left;
                break;
            }
        }
    }
    
    int num = strlst.Count;
    string[] result = strlst.ToArray();
    Console.WriteLine(result );
    string rtxt = "";
    for(int i=num-1;i>=0;i--)
    {
        rtxt = rtxt + result[i]+"  ";
    }
    System.IO.File.WriteAllText(resultpath, rtxt);
    MessageBox.Show("ok");

}
int GetDicMaxLength(List<string> str)//获取字典中最大长度词的长度
{
    if (str.Count == 0) return 0;
    int num = 0;
    for(int i=0;i<str.Count;i++)
    {
        if(str[i].Length >num )
        {
            num = str[i].Length;
        }
    }
    return num;
}
string[] ReadDic(string dicpath)//对普通列表字典的读取
{
    string dictxt = System.IO.File.ReadAllText(dicpath);//字典数据读取
    //Console.WriteLine(dictxt);
    char[] c = { '\r', '\n' };
    string[] s = dictxt.Split(c);
    return s;
}
List<string> ReadDic2(string dicpath)//包含词频统计分隔符和频数的字典的词的读入
{
    string dictxt = System.IO.File.ReadAllText(dicpath);//字典数据读取
    //Console.WriteLine(dictxt);
    //char[] c = { '\r', '\n' };
    string[] s = dictxt.Split(Environment.NewLine.ToCharArray());//用\r\n分割文本
    List<string> ls = new List<string>();
    for(int i=0;i<s.Length;i++)
    {
        if (s[i] == "") continue;
        int n = s[i].IndexOf ('\t');
        //Console.WriteLine(Chr(9));
        ls.Add(s[i].Substring(0, n));
    }
    return ls;
}

 

写在最后：
鉴于本人水平有限，如果文章中有什么错误之处，欢迎指正，非常感谢。

 

版权声明 本博客的文章除特别说明外均为原创，本人版权所有。欢迎转载，转载请注明作者及来源链接，谢谢。 本文地址: https://blog.ailemon.net/2017/03/27/a-simple-algorithm-for-chinese-word-segmentation-based-on-dictionary/ All articles are under Attribution-NonCommercial-ShareAlike 4.0