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

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

  1. 正向最大匹配

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

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

在字典中查找时,算法运行结果如下:

我们明天去野生动物园游玩       (未找到)

我们明天去野生动物园游   (未找到)

我们明天去野生动物园        (未找到)

。。。。。。

我们/       (找到)

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

我们/明天去野生动物园游 (未找到)

。。。。。。

我们/明天/     (找到)

……

我们/明天/去/野生动物园/游玩 (找到)

 

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

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

团购网站的本质是什么?

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

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

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

 

  1. 逆向最大匹配

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

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

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

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

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

  1. 双向最大匹配

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

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

我们在野生动物园玩

在正向最大匹配时,切分结果是:“我们/在野/生动/物/园/玩”,经过统计我们可以发现,两字词有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;
}

 

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

 

打赏作者
很喜欢这篇文章,赞赏一下作者,以激励其创作出更多好文!

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

分享到社交网络:

发表评论

电子邮件地址不会被公开。 必填项已用*标注