NLP-中文分词：最大正向匹配算法

一、前言

1、什么是分词

在讲分词算法之前，先来研究一下什么是分词？
分词是将语句按照语境，以字词为单位划分的一个过程，如下图所示：

image.png

2、为什么需要分词

那为什么需要分词呢？笔者认为主要有一下几个原因：

1、汉语的基本组成单位是字词，造成了字词成为了理解语句的基本单位（这其实是文化思维定式）
2、中文的自然语言处理技术好多事借鉴于英文的，而英文语句是最为真实单词构成语句，以空格分隔，在处理上也就就从单词角度为起点
3、人类的思维方式很容易以自我意识为主导，习惯于将自己的认知方式赋予其他生物或者机器，我们从字词开始理解语言，也认为机器需要从字词开始...

二、最大正向匹配算法

1、原理

本文主要讲述一种比较传统的分词算法--最大正向匹配算法，所谓的最大正向，也就是从句子左侧开始匹配，匹配到的词以最大长度为准，当然有最大正向，也就有最大逆向，双向等等。从匹配两个字可以看出该算法的核心在于匹配，而且是彻彻底底地基于词典的匹配，看到这里你可能会觉得很low，没错，就是很low，但这是因为我们站在高等生物的角度去俯瞰它，俯瞰的同时，我们心中还有个对比参照的词，那就是智能！
你想象那是一个机器，一个只认识01代码的家伙，更深了说，它连0和1都不认识，只认识有电和没电，这样一想，你或许觉得该算法也没那么low！
扯完了题外话，下面说一说他的原理。

（1）第一步：定义词典

既然是基于词典的匹配，那我们首先的有个词典，这个词典里包含了我们所要使用各种词语：

dict = ["你好"，"查询"，"城市"，"天气"，"明天"，"后天"，"今天"，"如花似玉"...]

（2）定义需要分词句子

input_sentence = "你好，帮我查询一下明天的天气"

（3）选取最大匹配长度

max_match_length = len("如花似玉") = 4

（4）开始匹配

截取input_sentence的前四位：

match_sentence = input_sentence[0:4] = "你好，帮"

在词典dict中无法匹配，此时去掉match_sentence的最后一位，剩下的匹配句子为：

match_sentence = "你好，"

在词典dict中依旧无法匹配，此时去掉match_sentence的最后一位，剩下的匹配句子为：

match_sentence = "你好"

发现“你好”在词典中，那么得到第一个分词结果

cut_result = ["你好"]

此时，剩下需要分词的句子为：

input_sentence = input_sentence - match_sentence 
                             = "你好，帮我查询一下明天的天气" - "你好" = "，帮我查询一下明天的天气"

依旧截取input_sentence的前四位：

match_sentence = input_sentence[0:4] = "，帮我查"

在词典dict中无法匹配，此时去掉match_sentence的最后一位，剩下的匹配句子为：

match_sentence = "，帮我"
# 没有匹配上，去除最后一位
match_sentence = "，帮"
# 没有匹配上，去除最后一位
match_sentence = "，"
# 遇到单字没有匹配上，独立为一个词
# 此时分词结果为
cut_result = ["你好","，"]
# 还剩余的句子
input_sentence = "帮我查询一下明天的天气"

重复上述的过程，最后得到分词结果为：

cut_result = ["你好","，","帮","我","查询","一下","明天","的","天气"]

2、代码实战

由于本人懒，之前写过Java的，直接搬过来了，就不转化为Python版本了，相信表达方式的差异化并不会影响到事物的原理本身！

    /**
     * 分词功能 基于最大正向匹配算法
     * @param message
     */
    public List<String > cut(String message) {
        List<String > cutResult = new ArrayList <String>();
        while (message.length() > 0) {
            String matchMessage = message.substring(0, this.maxWordLength>message.length()?message.length():this.maxWordLength);
            while (!this.words.contains(matchMessage)) {
                if (matchMessage.length() > 1) {
                    matchMessage = matchMessage.substring(0, matchMessage.length() - 1);
                } else{
                    break;
                }
            }
            cutResult.add(matchMessage);
            message = message.substring(matchMessage.length());
        }
        return cutResult;
    }