中文分词-正向最大匹配

Posted by maple Blog on March 29, 2016

中文分词-正向最大匹配

中文分词,一个很常见的问题。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。我们知道,在英文的行文中,单词之间是以空格作为自然分界符的,而中文只是字、句和段能通过明显的分界符来简单划界。

常用分词方式

  • 字符串匹配

这类分词方式有正向/反向最大匹配,等等。 实现方式简单,速度也较快; 不过缺点是比较依赖字典,对于字典里没有的词(也就是未登录词)匹配效果不好。

  • 统计学习以及机器学习

这类分词基于人工标注的词性和统计特征,建立模型,然后训练。在分词阶段,根据模型计算得到的概率来切分文本。常见的序列标注模型有HMMCRF

这次先说下相对简单的正向最大匹配

正向最大匹配:从左到右将待切分的文本与字典库中的词作匹配,匹配上了就切出一个词。

待切分的文本

小明毕业于中国科学院

dict={“小明”,”中国”,”科学”,”毕业”}

首先取出5个词,小明毕业于。为啥是5个,这个可以自己设定的,比如8,10个。。最长匹配长度

那么接下来会去字典库中查找。

小明毕业于 n

小明毕业 n

….

小明 y

1.小明毕业于在字典中没找到

2.那么右边减少一个字,变成小明毕业

3.再重复第1步。。。

直到小明匹配上,顺利切分出一个词。 然后会切分出毕业

那么在做于中国科学匹配的时候,发现5次匹配结束了,都没有一个能匹配上,那么此时需要往后挪一位,取出中国科学院。在做下一轮的切分。

整个过程简单粗暴。如果字典里没有这个词那么是无论如何都匹配不出来的。这里还有个问题就是。字典的存储问题,如果词库有几十w的词组,用hashmap?

考虑到快速查找,可以尝试使用Trie树。 具体实现: 还需要实现一个Trie树作存储和查找(可以参考我刷过的leetcode题目里的一个实现). 区别在于,英文的子节点只有26个情况,中文却有很多情况,存储子节点的地方可以改成 hashmap

void WordSplit(string s ,int maxlen,vector<string>& result)
{
    int len = maxlen;
    string ret;
    for (int i=0; i<s.size();) {
        string tmp = s.substr(i,len);
        if (isWord(tmp))
        {    
            ret = tmp;
        }
        len--;
        if (len >0) continue;
        if (!ret.empty())
        {
            result.push_back(ret);
            i = i+ret.size();
            ret="";
        }
        else
        {
            i++;
        }
        len = maxlen;
    }
}

参考

正向最大匹配中文分词