【算法记事本#NLP-1】最大匹配算法分词
Oberon 人气:0
> **本文地址**：
# \#NLP-1 最大匹配算法（MM）
**最大匹配算法**（Maximum Matching）被用于对一个**文段**进行**词语划分**（Word Segmentation）。
> ## 注意
> 这是**词元化（Tokenization）算法**
> 此方法**不适用于**无分隔符的字母语言（e.g.：**德语**、使用假名替代汉字的**日语**、被取消分词符的**英文**等）
> 但是对**汉语**这类无词间分隔符但不依赖字母的语言**效果拔群**
## 输入输出
```mermaid
graph LR
input1(文段P)
input2(单词表W)
processor(MM)
output(词元表T)
input1--输入-->processor
input2--输入-->processor
processor--输出-->output
```
## 算法内容
> ## 人话版本（自然描述）
> **输入**：文段$\small P$，单词表$\small W$
> **过程**：对于给定的$\small P$和$\small W$：
> 1. 令指针$\small i$从$\small P$的起点开始
> 2. 每当找到**最长匹配**于$\small i$引领文段的单词$\small w$，则将$\small w$加入词元分析表$\small T$（一个顺序表结构）中
> 3. $\small i$向后移动$\small w$长度个位置
> 4. 回到2，直至$\small i$无法向后移动为止
>
> **输出**：词元分析表$\small T$
## 说明
### 最长匹配？？
这个概念用定义去描述其实很不容易理解，这里直接上例子，比如，有一个字符串
```text
The quick brown fox jumps over a lazy dog
```
现在给出这么几个字符串：`Th`、`The`、`The slow`、`The quick brown fox jumps over a lazy dog and a little duck`、`quick brown`
> 注意，最长匹配的前提是**能匹配得上**，此外还要求是**端点匹配**
先看`Th`，很明显，尽管`Th`不能完美的匹配上原有字符串，但却是原字符串的**子串**（Substring），也就是说它能够完美的和原字符串的局部相匹配，而且是**从起始位置相匹配**，可以**暂时认为**是原字符串的**最长匹配**。
再看`The`，和`Th`一样，其整体能够匹配上原字符串的部分，而且也是从起始位置匹配，因此也可能是最长匹配，这样一来`Th`和`The`都能匹配上原字符串，但是
> 一个字符串在一个给定的字符串集合中**只能找到一个**最长匹配，而且是**尽可能长**的那个
考虑到`The`比`Th`长，因此`The`替掉了`Th`成为了目前的**最长匹配**
接下来看看`The slow`，截止到`The `都能匹配到原字符串上，但接下来的`s`却**无法匹配原字符串**，尽管匹配部分的长度比`The`还长，但很遗憾，`The slow`只能认为是**不匹配**。
`The quick brown fox jumps over a lazy dog and a little duck`也是同理，别看它甚至是原字符串的延长串（也就是原字符串是它的子串），但后面多出来的部分匹配不回去，所以也只能认为是**不匹配**。
> 原字符串是大爷！！
最后再看看`quick brown`，当然这也是原字符串的子串，而且匹配长度为11，甚至比`The`的匹配性还强，但是也很遗憾，这并**不是从起点**匹配的，所以这个**无法认为匹配**
于是我们得到了结论：
> 在上述给出的5个字符串中，最长匹配为`The`
当然，这都是**目前的最长匹配**，如果我们继续给出`The quick`、`The quick brown`、……这个结果还是会跟着变化的，因为：
> 理论上，从**所有字符串构成的全集**寻找某一字符串的最长匹配，其结果只能是该字符串本身
### 为什么对汉语效果拔群？？
这里先说对英语吧……
因为是做词元化工作，所以这里**暂时无视英语中的空格分隔符**。
```text
We are talking about weather.
↓ 移除所有分词符
Wearetalkingaboutweather.
```
当然，我们要对下面的内容做分词，按说分词工作做完后其分割结果应该和移除之前是一样的：`We|are|talking|about|weather|.`
但如果采用MM算法使用一个标准词库进行匹配，就会是下面这样：
> 首先从`W`开始，从词库中寻找从`W`开始能够最长匹配的字符串，然后非常巧，我们在词典中找到了……`Wear`！！
> ……
于是，我们先不管后面能不能分出来，反正分完肯定是这样子：`Wear|...|...`。
很明显这种分法是不行的。
这里面的原因就在于：英语一共就26个字母，随便找若干个字母凑成一个单词的概率还是很大的，特别是移除分隔符后出现大量辅音字母+若干元音字母的情况。
而且，英语中词汇的长度方差很大，短的只有一个字母，长的可以10多个，极端情况下也有40多个的甚至更多，很多短单词会成为一些长单词的子串（`we`之于`wear`等），而移除分隔符后两个原本独立的子串被拼合成一个更长的单词也不是什么新鲜事。
一种极端情况：
```mermaid
graph LR
origin("Hear the voice")
obfuscated("Hearthevoice")
mm("Heart|he|voice")
origin--移除分隔符-->obfuscate
obfuscate--MM算法分割-->mm
```
但是汉语就不一样了，就以GB2312里面的6700多个汉字想随便挑出来几个字就凑巧拼出一个词语还是很困难的，而且词语长度的方差很低，不考虑诗句和歇后语的话，常用的词语和成语绝大多数为2~4个字，较长一些的8个字（比较少），这种情况下即使没有分隔符，两个独立的词语能够被混淆成一个的几率还是比较小的，比如：
```text
一只穿云箭，千军万马来相见
一只|穿云|箭|，|千军万马|来|相见
```
基本上分割的完全正确，而且即使把标点符号都去掉，也不太影响其分割的结果，斯坦福大学也给出了这样的评价：
> Doesn’t generally work in English!
> But works astonishingly well in Chinese!
不过其实说到底，这种算法**比较依赖于词典**（事实上很多词元化算法都挺依赖词典），如果词典编写的不够好，那么即使是汉语其词元化的质量也不尽如人意（特别是汉语需要足够完善的词汇库，其工作量是相当庞大的）。
加载全部内容