1. 最大匹配算法

最大匹配法是指通过词典进行单向分词，优先选择词的长度，逐步对句子扫描分词

我们举个从左向右的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
假设当前句子为：  你学会最大匹配算法了吗 
词典当中有 你 学会 学 会 最大匹配算法 了 吗(其实还有最大 匹配等等就不写了)

第一次分词   | 你学会最大匹配算法了吗
你学会最大匹配算法了吗  没有这个词
你学会最大匹配算法了  没有这个词
你学会最大匹配算法  没有这个词
你学会最大匹配算  没有这个词
...
你 对咯 那就下一个


第二次分词   | 学会最大匹配算法了吗
显然结果是   学会

第三次分词   | 最大匹配算法了吗 
这里就有个问题 选择 最大匹配算法 还是 最大|匹配|算法
我们首先要考虑的肯定是词的长度越长越好 词典之中已经拥有显著的意义就没必要在分词
所以选择 最大匹配算法

最大匹配法主要包括正向最大匹配法（FMM，刚刚这个例子就是）、反向最大匹配法（BMM）和双向最大匹配法，均是基于词典的

缺点有：

因为是基于词典的 所以如果新词没记录没更新，就会识别不出来

2. 正向匹配算法(FMM)

也就是我刚刚上面提到的 你学会最大匹配算法了吗

分词为 你|学会|最大匹配算法|了吗

下面是cpp简易的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void clearlove13()
{
    std::unordered_set<std::string> dict = {
        "你",
        "学会",
        "最大匹配算法",
        "了吗"};
    //当作词典
    std::string s = "你学会最大匹配算法了吗";
    int mx = 0;
    for (auto &w : dict) {
        mx = std::max(mx, (int)w.size());
    }
    std::vector<std::string> res;
    int n = s.size();
    for (int i = 0; i < n;) {
        int len = std::min(mx, n - i);
        bool ok = false;
        //逐长度查询
        while (len) {
            std::string cur = s.substr(i, len);
            if (dict.count(cur)) {
                res.push_back(cur);
                i += len;
                ok = true;
                break;
            }
            len--;
        }
        if (!ok) {
            res.push_back(s.substr(i, 1));
            i++;
        }
    }
    for (auto &x : res) {
        std::cout << x << '\n';
    }
}

但是呢 我们可以考虑优化 譬如说将dict按照长度在进行分层 大致如下

1
2
3
4
5
6
7
8
std::vector<std::unordered_set<std::string>> dict(max_len + 1);
dict[1].insert("你");
dict[2].insert("学会");
dict[2].insert("了吗");
dict[6].insert("最大匹配算法");


或者说 我们可以考虑引入字典树 在对比的时候直接省去查询的性能 甚至于占用的内存也没有多大 再去用BFS去找到对应的集合

输出结果就这样

3. 反向匹配算法(BMM)以及双向匹配算法

BMM就是相当于把FMM倒过来做一遍

而双向匹配算法则是比较FMM跟BMM 并选用两个标准

（1）首先看两种方法结果的分词数，分词数越少越好；

（2）分词数相同的情况下，看单个词的数量，越少越好；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
std::vector<std::string> fmm(
    std::string &s,
    std::unordered_set<std::string> &dict,
    int mx)
{
    std::vector<std::string> res;
    int n = s.size();
    for (int i = 0; i < n;) {
        int len = std::min(mx, n - i);
        bool ok = false;
        while (len) {
            std::string cur = s.substr(i, len);
            if (dict.count(cur)) {
                res.push_back(cur);
                i += len;
                ok = true;
                break;
            }
            len--;
        }
        if (!ok) {
            res.push_back(s.substr(i, 1));
            i++;
        }
    }
    return res;
}

std::vector<std::string> bmm(
    std::string &s,
    std::unordered_set<std::string> &dict,
    int mx)
{
    std::vector<std::string> res;
    int i = (int)s.size() - 1;
    while (i >= 0) {
        int len = std::min(mx, i + 1);
        bool ok = false;
        while (len) {
            std::string cur = s.substr(i - len + 1, len);
            if (dict.count(cur)) {
                res.push_back(cur);
                i -= len;
                ok = true;
                break;
            }
            len--;
        }
        if (!ok) {
            res.push_back(s.substr(i, 1));
            i--;
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}
//单个字符个数
int count_single(const std::vector<std::string> &v)
{
    int res = 0;
    for (auto &s : v) {
        if (s.size() == 1) {
            res++;
        }
    }

    return res;
}

std::vector<std::string> bidirectional(
    std::vector<std::string> &f,
    std::vector<std::string> &b)
{
    if (f.size() < b.size()) {
        return f;
    }
    if (b.size() < f.size()) {
        return b;
    }
    int sf = count_single(f);
    int sb = count_single(b);
    if (sf < sb) {
        return f;
    }
    if (sb < sf) {
        return b;
    }
    return f;
}

void clearlove13()
{
    std::unordered_set<std::string> dict = {
        "研究",
        "研究生",
        "生命",
        "命",
        "起源"};

    std::string s = "研究生命起源";
    int mx = 0;
    for (auto &w : dict) {
        mx = std::max(mx, (int)w.size());
    }
    auto f = fmm(s, dict, mx);
    auto b = bmm(s, dict, mx);
    auto ans = bidirectional(f, b);
    std::cout << "FMM:\n";
    for (auto &x : f) {
        std::cout << x << '\n';
    }
    std::cout << '\n';
    std::cout << "BMM:\n";
    for (auto &x : b) {
        std::cout << x << '\n';
    }
    std::cout << '\n';
    std::cout << "BiMM:\n";
    for (auto &x : ans) {
        std::cout << x << '\n';
    }
}

结果如此

4. 小结

可以看到在第三节双向匹配的效果不一定比单向匹配好 一方面是因为这个数据小 还有就是正如我们上面所说的词典不完善

我们也可以通过一些数据结构去优化查询性能