> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/zi-ran-yu-yan-chu-li/nlp-chang-jian-ren-wu/xin-ci-fa-xian/ji-yu-qie-fen-de-fang-fa.md).

# 基于切分的方法

## 寻找切分点

在[基于备选片段的方法](/garnet/zi-ran-yu-yan-chu-li/nlp-chang-jian-ren-wu/xin-ci-fa-xian/ji-yu-bei-xuan-pian-duan-de-fang-fa.md)中介绍的新词发现方案, 需要消耗的算力和内存资源是很多的:

* 为了得到$$n$$字词, 需要找到 $$1$$ \~ $$n$$ 字的切片(文本片段), 然后分别计算. 当$$n$$较大时, 消耗的资源很多
* 计算每个切片的左右信息熵, 需要使用大量的资源记录每个切片的左右邻字的分布情况

重新考虑上面的方案, 当凝固度大于一定的阈值后, 这个文本片段就可能成词(接下来要去考虑它的边界熵), 但反过来, 如果片段的凝固度低于一定程度时, 这个片段就不可能成词, 那么我们就可以在原来的语料中把它断开了.

仍然使用互信息来表示文本片段内部的凝固程度, 当互信息小于一定的阈值$$\alpha$$时, 在语料中把这两个字断开. 这种断开的操作, 实际上就是**初步的分词**. 在通过这种方法分词完毕后, 就可以统计词频, 根据词频的阈值来筛选.

$$
\begin{aligned}
\text{MI}(a,b) &= \frac{P(a,b)}{P(a)P(b)} \\
&= \frac{N \cdot #(a,b)}{#a \cdot #b} < \alpha
\end{aligned}
$$

相比于上面的方法, 使用判断条件由**频数**, **凝固度**, **自由度**三个指标下降为**频数**, **凝固度**两个指标, 省去了大量的计算边缘信息熵的消耗. 而且在计算凝固度时, 我们只需要计算二字片段的凝固度, 省掉了更多字片段的凝固度计算. 由于我们是基于**切分**的方式做的, **理论上却能够得任意长度的词语**.

代码参考: [【中文分词系列】 2. 基于切分的新词发现](https://kexue.fm/archives/3913#%E5%AE%9E%E7%8E%B0).

为了得到更细粒度(更短)的词, 可以将凝固度筛选的阈值$$\alpha$$选的较大, 但同时可能将一些较长的词在内部进行了切分, 损失了发现这个词的机会. 超参数$$\alpha$$的选择, 也要根据实际语料反复调参选取.

## 方法改进

分词的主要目的之一, 就是**将句子分为若干个相关性比较弱的部分**, 便于进一步处理, 因此分词就是在相关性弱的地方切断了. 前面认为文本的相关性仅由相邻两字来决定, 这在很多时候都是不合理的, 比如`林心如`中的`心如`, `共和国`中的`和国`, 两个字之间的凝固度都不是很强, 容易错切.

因此, 可以同时考虑多字的内部的凝固度, 比如, 定义三字的字符串内部凝固度为:

$$
\min\left{\frac{P(abc)}{P(ab)P(c)},\frac{P(abc)}{P(a)P(bc)}\right}
$$

也就是说, 要枚举n-gram中**所有可能的切法**, 因为**一个词应该是处处都很结实的**. 一般地, 只需要考虑到4字就好(依旧是可以切出4字以上的词来的).

考虑了多字后, 相比于只考虑两字, 我们可以设置比较高的凝固度阈值, 因为`和国`中的`和`与`国`凝固度低, 但`共`与`和国`以及`共和`与`国`之间的凝固度都比较高, `共和国`就显得相当结实了. 高阈值防止诸如`共和国`之类的词不会被切错.

这样切分完毕后, 就能得到一个初始的词表. 对2-grams, 3-grams, 4-grams, 分别计算它们的内部凝固度, 只保留高于某个阈值的片段. 每个n-gram对应的阈值不同, 在进行完这一步后, 就得到了2-grams, 3-grams, 4-grams的词表, 词表中每个词的凝固度都很高.

接下来就是利用上面得到的词表, 对语料中的所有句子进行分词. 这一步的原则是`宁放过, 勿切错`, 为了尽量不将本应成词的文本片段错切, 可以接受一些不应成词的冗余片段. 切分的规则是, 只要一个片段出现在前一步得到的词表中, 这个片段就不切分. 这样就会导致如`各项`和`项目`这两个词都在词表中, 并且连在一起出现, 导致`各项目`也成词., 类似的还有`支撑着`, `球队员`等例子.

但这些例子在3-gram中来看, 凝固度是很低的, 因此还需要有一个**回溯**的过程, 在前述步骤得到分词结果后, 再过滤一遍词表. 过滤的规则是, 对于一个$$n$$字词, 如果不在原来的高凝固度的n-grams词表中, 这个$$n$$字分词就被剔除.

完整的步骤如下:

**第一步**, 统计得到词表. 选取某个固定的$$n$$, 统计2-grams, 3-grams, ..., n-grams, 分别计算它们的内部凝固度, 只保留高于某个阈值的文本片段, 得到一个高凝固度词表集合$$G$$.

这一步, 2-grams, 3-grams, ..., n-grams需要设置不同的阈值, 因为字数越大, 一般来说统计就越不充分, 互信息的值就会偏高, 因此阈值也要对应的提高.

```python
# 遍历样本中的所有句子
for t in texts():
    # 从句子的第0个位置开始
    for i in range(len(t)):
        # 判断每个位置的 1-grams ~ n-grams
        for j in range(1, n+1):
            if i+j <= len(t):
                ngrams[t[i:i+j]] += 1

# 根据流行度筛选, 使用的出现频数
ngrams = {i:j for i,j in ngrams.iteritems() if j >= min_count}
# 统计语料中字的数量
total = 1.*sum([j for i,j in ngrams.iteritems() if len(i) == 1])

# n就是需要考虑的最长片段的字数, 只考虑2-grams凝聚度容易照成长词的误分, 因此n至少为3
min_proba = {2:5, 3:25, 4:125}

def is_keep(s, min_proba):
    # 计算n-grams的内部凝固度, 计算公式见上面
    if len(s) >= 2:
        score = min([total*ngrams[s]/(ngrams[s[:i+1]]*ngrams[s[i+1:]]) for i in range(len(s)-1)])
        if score > min_proba[len(s)]:
            return True
    else:
        return False

# 过滤上面得到的初步词表,
ngrams_ = set(i for i,j in ngrams.iteritems() if is_keep(i, min_proba))
```

**第二步**, 使用上一步得到的词表$$G$$对语料句子进行切分, 并统计频率. 这一步可以看做粗糙的分词, 切分的规则是, 只要一个片段相连的子片段都出现在前一步得到的词表$$G$$中, 这个文本片段就不切分. 例如`各项目`, `各项`和`项目`都出现在$$G$$中, 则在这一步分词中, `各项目`就不会被分开, 保留作为待选词汇.

```python
def cut(s):
    r = np.array([0]*(len(s)-1))
    for i in range(len(s)-1):
        for j in range(2, n+1):
            if s[i:i+j] in ngrams_:
                r[i:i+j-1] += 1
    w = [s[0]]
    for i in range(1, len(s)):
        if r[i-1] > 0:
            w[-1] += s[i]
        else:
            w.append(s[i])
    return w

words = defaultdict(int)
for t in texts():
    for i in cut(t):
        words[i] += 1

words = {i:j for i,j in words.iteritems() if j >= min_count}
```

**第三步**, 回溯, 将第二步粗分得到的备选词, 如果这个词的长度不大于$$n$$, 检测它是否在第一步得到的词表$$G$$中, 不在则这个词被剔除掉, 只有在词表$$G$$中的分词, 才能作为真正的词.

对于长度大于$$n$$的备选词, 需要检测它的每个n-gram是否都在词表$$G$$中, 只有所有的片段都在$$G$$中, 才能把这个长词作为真正的词汇.

```python
def is_real(s):
    if len(s) >= 3:
        for i in range(3, n+1):
            for j in range(len(s)-i+1):
                if s[j:j+i] not in ngrams_:
                    return False
        return True
    else:
        return True

w = {i:j for i,j in words.iteritems() if is_real(i)}
```

通过以上的方法, 实现了**无监督构造词库**. 与原来的词库对比, 就可以得到新词了.

## 参考资料

* [【中文分词系列】 2. 基于切分的新词发现](https://kexue.fm/archives/3913)
* [【中文分词系列】 8. 更好的新词发现算法](https://kexue.fm/archives/4256)
* [重新写了之前的新词发现算法：更快更好的新词发现](https://kexue.fm/archives/6920)