Python自然语言处理第三章 - 详解一个简单的分词方法

有些语言的书写系统，由于没有词边界的可视表示这一事实，使得文本分词变得更加困难。
这里介绍一种简单的分词方法。

一，分词问题描述

对以下没有明显词边界的句子进行分词：

1. doyouseethekitty
2. seethedoggy
3. doyoulikethekitty
4. likethedoggy

遇到的第一个挑战仅仅是表示这个问题：我们需要找到一种方法来分开文本内容与分词
标志。
我们可以给每个字符标注一个布尔值来指示这个字符后面是否有一个分词标志。

例如：

>>> text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
>>> seg1 = "0000000000000001000000000010000000000000000100000000000"
>>> seg2 = "0100100100100001001001000010100100010010000100010010000"

其中seg1和seg2表示两个分词结果，0表示当前字符不是分词结束位置，1表示在当前字符下分开。

可以用如下函数来将seg分词标志对原文本进行分词。

def segment(text, segs):
words = []
last = 0
for i in range(len(segs)):
if segs[i] == '1':
words.append(text[last:i+1])
last = i+1
words.append(text[last:])
return words
>>> text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
>>> seg1 = "0000000000000001000000000010000000000000000100000000000"
>>> seg2 = "0100100100100001001001000010100100010010000100010010000"
>>> segment(text, seg1)
['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy']
>>> segment(text, seg2)
['do', 'you', 'see', 'the', 'kitty', 'see', 'the', 'doggy', 'do', 'you',
'like', 'the', kitty', 'like', 'the', 'doggy']

二，怎样评价分词结果的好坏？

现在分词的任务变成了一个搜索问题：找到将文本字符串正确分割成词汇的字位串。我
们假定学习者接收词，并将它们存储在一个内部词典中。给定一个合适的词典，是能够由词
典中的词的序列来重构源文本的。读过(Brent & Cart-wright, 1995)之后：

我们可以定义一个目标函数，一个打分函数，我们将基于词典的大小和从词典中重构源文本所需的信息量尽力优化它的值。我们在图3-6 中说明了这些。

打分函数如下：

def evaluate(text, segs):
words = segment(text, segs)
text_size = len(words)
lexicon_size = len(' '.join(list(set(words))))
return text_size + lexicon_size
>>> text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
119
>>> seg1 = "0000000000000001000000000010000000000000000100000000000"
>>> seg2 = "0100100100100001001001000010100100010010000100010010000"
>>> seg3 = "0000100100000011001000000110000100010000001100010000001"
>>> segment(text, seg3)
['doyou', 'see', 'thekitt', 'y', 'see', 'thedogg', 'y', 'doyou', 'like',
'thekitt', 'y', 'like', 'thedogg', 'y']
>>> evaluate(text, seg3)
46
>>> evaluate(text, seg2)
47
>>> evaluate(text, seg1)
63

三，寻找最优的分词结果

最后一步就是寻找最大化目标函数值的0和1的分词标志序列。

我们可以按顺序寻找到最优分词结果（太费时间）或者利用最优化理论中的确定性最优化方法寻找到最优分词结果（需要将问题形式化建模），当然也可以利用一些启发式的随机寻优算法来找到最优的分词结果，例如模拟退化算法。

模拟退火算法：
模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。
模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

这里我们就使用模拟退火算法的非确定性搜索：一开始仅搜索短语分词；随机扰动0 和1，它们与“温度”成比例；每次迭代温度都会降低，扰动边界会减少。

from random import randint
def flip(segs, pos):
    return segs[:pos] + str(1-int(segs[pos])) + segs[pos+1:]
def flip_n(segs, n):
    for i in range(n):
        segs = flip(segs, randint(0,len(segs)-1))
    return segs
def anneal(text, segs, iterations, cooling_rate):
    temperature = float(len(segs))
    while temperature > 0.5:   #在不稳定之前，一直在随机变换状态，温度越高变化越大。
        best_segs, best = segs, evaluate(text, segs)
        for i in range(iterations): #迭代次数可以看做在固定温度下，随机变化的次数。
            guess = flip_n(segs, int(round(temperature)))
            score = evaluate(text, guess)
            if score < best:
                best, best_segs = score, guess
        score, segs = best, best_segs
        temperature = temperature / cooling_rate
        print evaluate(text, segs), segment(text, segs)
    print
    return segs
>>> text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
>>> seg1 = "0000000000000001000000000010000000000000000100000000000"
>>> anneal(text, seg1, 5000, 1.2)
60 ['doyouseetheki', 'tty', 'see', 'thedoggy', 'doyouliketh', 'ekittylike', 'thedoggy']
58 ['doy', 'ouseetheki', 'ttysee', 'thedoggy', 'doy', 'o', 'ulikethekittylike', 'thedoggy']
56 ['doyou', 'seetheki', 'ttysee', 'thedoggy', 'doyou', 'liketh', 'ekittylike', 'thedoggy']
54 ['doyou', 'seethekit', 'tysee', 'thedoggy', 'doyou', 'likethekittylike', 'thedoggy']
120
53 ['doyou', 'seethekit', 'tysee', 'thedoggy', 'doyou', 'like', 'thekitty', 'like', 'thedoggy']
51 ['doyou', 'seethekittysee', 'thedoggy', 'doyou', 'like', 'thekitty', 'like', 'thedoggy']
42 ['doyou', 'see', 'thekitty', 'see', 'thedoggy', 'doyou', 'like', 'thekitty', 'like', 'thedoggy']
'0000100100000001001000000010000100010000000100010000000'

有了足够的数据，就可能以一个合理的准确度自动将文本分割成词汇。这种方法可用于为那些词的边界没有任何视觉表示的书写系统分词。