NLP 分词

Trie
Trie,又称前缀树或字典树


特点:
第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

第二:从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串。

第三:每个单词的公共前缀作为一个字符节点保存。

#coding=utf-8
class LBTrie:
    """
    simple implemention of Trie in Python by authon liubing, which is not 
    perfect but just to illustrate the basis and principle of Trie. 
    """
    def __init__(self):
        self.trie = {}
        self.size = 0
       
    # add word
    def add(self, word):
        p = self.trie
        word = word.strip()
        for c in word:
            if not c in p:
                p[c] = {}
            p = p[c]
        if word != '':
            #end ''
            p[''] = '' 
      
    # search words
    def search(self, word):
        p = self.trie
        word = word.lstrip()
        for c in word:
            if not c in p:
                return False
            p = p[c]
        # end ''
        if '' in p:
            return True
        return False          
    
    #print trie api
    def output(self):
        print '{'
        self.__print_item(self.trie)    
        print '}'
        
    
    #get print private fufnct 
    def __print_item(self, p, indent=0):     
        if p:
            ind = '' + '\t' * indent
            for key in p.keys():
                label = "'%s' : " % key
                print ind + label + '{'
                self.__print_item(p[key], indent+1)
            print ind + ' '*len(label) + '}'  
            
    
if __name__ == '__main__':
    trie_obj = LBTrie()
    #add words
    trie_obj.add('hello')
    trie_obj.add('help')
    trie_obj.add('world')
    trie_obj.add('abc')
    trie_obj.add('我们')
    trie_obj.add('爱')
    trie_obj.add('的')
    trie_obj.add('祖国')
    #print
    trie_obj.output()
    #get #
    if trie_obj.search('我们'):
        print 'Yes'
    else:
        print 'No'

    if trie_obj.search('hello'):
        print 'Yes'
    else:
        print 'No'
    if trie_obj.search('China'):
        print 'Yes'
    else:
        print 'No'

 

HMM:
隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。


https://www.cnblogs.com/skyme/p/4651331.html(推荐)

 

https://engineering.leeds.ac.uk/info/20132/school_of_computing

 

https://www.cnblogs.com/iihcy/p/5106006.html

 

任何一个HMM都可以通过下列五元组来描述:

:param obs:观测序列
:param states:隐状态
:param start_p:初始概率(隐状态)
:param trans_p:转移概率(隐状态)
:param emit_p: 发射概率 (隐状态表现为显状态的概率)

伪码如下:

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}

求解最可能的隐状态序列是HMM的三个典型问题之一,通常用维特比算法解决。维特比算法就是求解HMM上的最短路径(-log(prob),也即是最大概率)的算法。

 

马尔可夫性质的离散随机过程。该过程中,每个状态的转移只依赖于之前的 n 个状态,这个过程被称为1个 n 阶的模型,其中 n 是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程,每一个状态的转移只依赖于其之前的那一个状态。注意这和确定性系统不一样,因为这种转移是有概率的,而不是确定性的。

  马尔可夫链是随机变量 X1, … , Xn 的一个数列。这些变量的范围,即他们所有可能取值的集合,被称为“状态空间”,而 Xn  的值则是在时间 的状态。如果 Xn+1 对于过去状态的条件概率分布仅是 X的一个函数,则

  这里 为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质

 

隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数,然后利用这些参数来作进一步的分析。下图是一个三个状态的隐马尔可夫模型状态转移图,其中x 表示隐含状态,y 表示可观察的输出,a 表示状态转换概率,b 表示输出概率。

  下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程,并且他们两两之间都可以相互转换。

  对 HMM 来说,有如下三个重要假设,尽管这些假设是不现实的。

 

  假设1:马尔可夫假设(状态构成一阶马尔可夫链)

  假设2:不动性假设(状态与具体时间无关)

  假设3:输出独立性假设(输出仅与当前状态有关)

隐藏的状态和可观察到的状态之间有一种概率上的关系,也就是说某种隐藏状态 H 被认为是某个可以观察的状态 O1 是有概率的,假设为 P(O1 | H)。如果可以观察的状态有3种,那么很显然 P(O1 | H)+P(O2 | H)+ P(O3 | H) = 1

 

  这样,我们也可以得到一个另一个矩阵,称为混淆矩阵 (confusion matrix)。这个矩阵的内容是某个隐藏的状态被分别观察成几种不同的可以观察的状态的概率,在天气的例子中,这个矩阵如下图:

 在 HMM 中有三个典型问题:

  (一) 已知模型参数,计算某一给定可观察状态序列的概率

  (二) 根据可观察状态的序列找到一个最可能的隐藏状态序列

  (三) 根据观察到的序列集来找到一个最有可能的 HMM。 

viterbi算法其实就是多步骤每步多选择模型的最优选择问题,其在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价(或者最大价值)以及当前代价的情况下前继步骤的选择。依次计算完所有步骤后,通过回溯的方法找到最优选择路径。符合这个模型的都可以用viterbi算法解决,隐马模型的第三问题刚好符合这个模型,所以才采用了viterbi算法。
HMM Viterbi 伪代码
from collections import Counter
from math import log

hmm_model = {i:Counter() for i in 'sbme'}

with open('dict.txt') as f:
    for line in f:
        lines = line.decode('utf-8').split(' ')
        if len(lines[0]) == 1:
            hmm_model['s'][lines[0]] += int(lines[1])
        else:
            hmm_model['b'][lines[0][0]] += int(lines[1])
            hmm_model['e'][lines[0][-1]] += int(lines[1])
            for m in lines[0][1:-1]:
                hmm_model['m'][m] += int(lines[1])

log_total = {i:log(sum(hmm_model[i].values())) for i in 'sbme'}

trans = {'ss':0.3,
         'sb':0.7,
         'bm':0.3,
         'be':0.7, 
         'mm':0.3,
         'me':0.7,
         'es':0.3,
         'eb':0.7
         }

trans = {i:log(j) for i,j in trans.iteritems()}

def viterbi(nodes):
    paths = nodes[0]
    for l in range(1, len(nodes)):
        paths_ = paths
        paths = {}
        for i in nodes[l]:
            nows = {}
            for j in paths_:
                if j[-1]+i in trans:
                    nows[j+i]= paths_[j]+nodes[l][i]+trans[j[-1]+i]
            k = nows.values().index(max(nows.values()))
            paths[nows.keys()[k]] = nows.values()[k]
    return paths.keys()[paths.values().index(max(paths.values()))]

def hmm_cut(s):
    nodes = [{i:log(j[t]+1)-log_total[i] for i,j in hmm_model.iteritems()} for t in s]
    tags = viterbi(nodes)
    words = [s[0]]
    for i in range(1, len(s)):
        if tags[i] in ['b', 's']:
            words.append(s[i])
        else:
            words[-1] += s[i]
    return words

 

代码的第一部分,就是用一个字典来表示P(λk|ok)P(λk|ok)P(λk|ok)P(λk|ok)的计算是通过词典来获取的,比如将词典中所有的一字词都计入s标签下,把多字词的首字都计入b标签下,等等。计算过程中还使用了对数概率,防止溢出;

第二部分的转移概率,直接根据直觉估算的;

第三部分就是通过viterbi算法动态规划,求的最大概率路径了。对于概率估算,简单采用了加1平滑法,没出现的单字都算1次。

整个代码都很简单,纯Python实现,当然,效率不一定高,仅供参考。下面是一点测试

HMM在自然语言处理中的应用一:词性标注2
CRF
条件随机场(CRF)由Lafferty等人于2001年提出,结合了最大熵模型和隐马尔可夫模型的特点,是一种无向图模型,近年来在分词、词性标注和命名实体识别等序列标注任务中取得了很好的效果。条件随机场是一个典型的判别式模型,其联合概率可以写成若干势函数联乘的形式,其中最常用的是线性链条件随机场。若让x=(x1,x2,…xn)表示被观察的输入数据序列,y=(y1,y2,…yn)表示一个状态序列,在给定一个输入序列的情况下,线性链的CRF模型定义状态序列的联合条件概率为
p(y|x)=exp{} (2-14)
Z(x)={} (2-15)
其中:Z是以观察序列x为条件的概率归一化因子;fj(yi-1,yi,x,i)是一个任意的特征函数;是每个特征函数的权值。

结巴分词:
结巴分词是国内程序员用python开发的一个中文分词模块, 源码已托管在github, 地址在: https://github.com/fxsjy/jieba

作者的文档写的不是很全, 只写了怎么用, 有一些细节的文档没有写.

以下是作者说明文件中提到的结巴分词用到的算法:

基于Trie树结构实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图(DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
对于未登录词,采用了基于汉字成词能力的HMM模型,使用了Viterbi算法
因为最近有点兴趣想了解中文分词, 所以看了大量的资料, 对上面的三条有了一点点理解, 不再是两眼一抹黑了.转载请注明: 本文来自Django梦之队, http://ddtcms.com/blog/archive/2013/2/4/69/jieba-fenci-suanfa-lijie/

先推荐大家看 http://www.52nlp.cn/ (我爱自然语言处理)的一系列关于概率、中文分词、HMM隐马尔科夫模型的文章, 然后再回头看看结巴分词的代码。

然后推荐大家看看《解密搜索引擎技术实战:Lucene&Java精华版》,如果看不到, 可以看看这里的在线版, 虽然很短, 但是基本的思想都说明白了, 地址: http://book.51cto.com/art/201106/269050.htm (4.6 概率语言模型的分词方法)

看了这本书的第4章, 或者看了那个在线的那个章节的前后部分, 基本上可以说, 结巴分词, 在很大的程度上类似于书中说的例子。(上面的链接,是作者算法的第2条, 动态规划查找最大概率路径),当然, 结巴分词使用了HMM模型对未登录词进行识别(上面的第3条)

至于第1条, 作者的trie树,可以看这篇文章对python中如何保存trie树结构的词典进行深刻理解:http://iregex.org/blog/trie-in-python.html Trie in Python 这篇写的很好, 主要分析 Trie 实现原理,并给出 Python 的实现,还和正则联系到一起了。

上面列出的三个链接, 里面讲到的知识, 基本上将结巴分词的算法都讲到了。所以有兴趣的人, 一定要仔细看我上面给的三个链接。

下面, 结合自己看结巴分词的代码, 讲讲我自己看过资料和代码后的理解。

先从作者的三条说起。

第一条:基于Trie树结构实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图(DAG)

这个看上面的trie树的python实现, 结巴分词自带了一个叫做dict.txt的词典, 里面有2万多条词, 包含了词条出现的次数(这个次数是于作者自己基于人民日报语料等资源训练得出来的)和词性. 这个第一条的trie树结构的词图扫描, 说的就是把这2万多条词语, 放到一个trie树中, 而trie树是有名的前缀树, 也就是说一个词语的前面几个字一样, 就表示他们具有相同的前缀, 就可以使用trie树来存储, 具有查找速度快的优势.

聪明的人可能会想到把 dict.txt中所有的词汇全部删掉, 然后再试试结巴能不能分词, 结果会发现, 结巴依然能够分词, 不过分出来的词, 大部分的长度为2.这个就是第三条, 基于HMM来预测分词了.

接着说DAG有向无环图, 就是后一句的 生成句子中汉字所有可能成词情况所构成的有向无环图, 这个是说的, 给定一个句子, 要你分词, 也就是给定一个 待分词的句子, 对这个句子进行生成有向无环图. 如果对有向无环图理解不了可以百度或者google搜索, 也可以看这篇 http://book.51cto.com/art/201106/269048.htm 比较形象的用图来表示了一个待分词句子的切分情况.

作者是怎么切分的呢? 1. 根据dict.txt生成trie树, 2, 对待分词句子, 根据dict.txt生成的trie树, 生成DAG, 实际上通俗的说, 就是对待分词句子, 根据给定的词典进行查词典操作, 生成几种可能的句子切分. dag是啥玩意?记录了啥呢? 作者的源码中记录的是句子中某个词的开始位置, 从0到n-1(n为句子的长度), 每个开始位置作为字典的键, value是个list, 其中保存了可能的词语的结束位置(通过查字典得到词, 开始位置+词语的长度得到结束位置)

例如:{0:[1,2,3]} 这样一个简单的DAG, 就是表示0位置开始, 在1,2,3位置都是词, 就是说0~1, 0~2,0~3这三个起始位置之间的字符, 在dict.txt中是词语.

第二条:采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合

关于动态规划查找最大概率路径, 这个在一些大学课程中讲的很多了, 不熟悉的或者忘记了的翻翻百度就行了. 上面给的那个在线书籍的链接中也说的很明白了, 我这里就说说作者的代码:

作者的代码中讲字典在生成trie树的同时, 也把每个词的出现次数转换为了频率. 关于频率和概率, 这里在啰嗦几句: 按照定义, 频率其实也是一个0~1之间的小数, 是 事件出现的次数/实验中的总次数, 因此在试验次数足够大的情况下, 频率约等于概率, 或者说频率的极限就是概率. 不过通常人们混淆的是频率和次数, 经常把频率等同于事件出现的次数, 比如这里就是某个词语出现的次数, 所以, 频率在引起混淆的时候, 对中国人来说, 还是先理解为出现次数, 然后理解发现有问题, 就理解为出现次数/总数这个比率吧.

动态规划中, 先查找待分词句子中已经切分好的词语, 对该词语查找该词语出现的频率(次数/总数), 如果没有该词(既然是基于词典查找, 应该是有的), 就把词典中出现频率最小的那个词语的频率作为该词的频率, 也就是说P(某词语)=FREQ.get(‘某词语’,min_freq), 然后根据动态规划查找最大概率路径的方法, 对句子从右往左反向计算最大概率(一些教科书上可能是从左往右, 这里反向是因为汉语句子的重心经常落在后面, 就是落在右边, 因为通常情况下形容词太多, 后面的才是主干, 因此, 从右往左计算, 正确率要高于从左往右计算, 这个类似于逆向最大匹配), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))…依次类推, 最后得到最大概率路径, 得到最大概率的切分组合.

第三条, 对于未登录词,采用了基于汉字成词能力的HMM模型,使用了Viterbi算法

未登录词, 作者说的是什么意思? 其实就是词典 dict.txt 中没有记录的词. 上面说了, 把dict.txt中的所有词语都删除了, 结巴分词一样可以分词, 就是说的这个.

怎么做到的? 这个就基于作者采用的HMM模型了, 中文词汇按照BEMS四个状态来标记, B是开始begin位置, E是end, 是结束位置, M是middle, 是中间位置, S是singgle, 单独成词的位置, 没有前, 也没有后. 也就是说, 他采用了状态为(B,E,M,S)这四种状态来标记中文词语, 比如北京可以标注为 BE, 即 北/B 京/E, 表示北是开始位置, 京是结束位置, 中华民族可以标注为BMME, 就是开始, 中间, 中间, 结束.

经过作者对大量语料的训练, 得到了finalseg目录下的三个文件(来自结巴项目的issues):

要统计的主要有三个概率表:

prob_trans.py
1)位置转换概率,即B(开头),M(中间),E(结尾),S(独立成词)四种状态的转移概率;
{‘B’: {‘E’: 0.8518218565181658, ‘M’: 0.14817814348183422},
‘E’: {‘B’: 0.5544853051164425, ‘S’: 0.44551469488355755},
‘M’: {‘E’: 0.7164487459986911, ‘M’: 0.2835512540013088},
‘S’: {‘B’: 0.48617017333894563, ‘S’: 0.5138298266610544}}

P(E|B) = 0.851, P(M|B) = 0.149,说明当我们处于一个词的开头时,下一个字是结尾的概率
要远高于下一个字是中间字的概率,符合我们的直觉,因为二个字的词比多个字的词更常见。

prob_emit.py
2)位置到单字的发射概率,比如P(“和”|M)表示一个词的中间出现”和”这个字的概率;
prob_start.py
3) 词语以某种状态开头的概率,其实只有两种,要么是B,要么是S。这个就是起始向量, 就是HMM系统的最初模型状态
实际上, BEMS之间的转换有点类似于2元模型, 就是2个词之间的转移
二元模型考虑一个单词后出现另外一个单词的概率,是N元模型中的一种。
例如:一般来说,”中国”之后出现”北京”的概率大于”中国”之后出现”北海”的概率,也就是:中国北京 比 中国北海出现的概率大些, 更有可能是一个中文词语.

不过, 作者这里应该不是用的2元分词模型的, 这里的BEMS只提供了单个汉字之间的转换, 发射概率, 并没有提供粒度更大的, 基于词语的发射和转移概率, 当然, 也有可能我理解的不够深入.

给定一个 待分词的句子, 就是观察序列, 对HMM(BEMS)四种状态的模型来说, 就是为了找到一个最佳的BEMS序列, 这个就需要使用viterbi算法来得到这个最佳的隐藏状态序列, 具体的python版的viterbi算法请看维基百科:http://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95 维特比算法

通过作者之前训练得到的概率表和viterbi算法, 就可以得到一个概率最大的BEMS序列, 按照B打头, E结尾的方式, 对待分词的句子重新组合, 就得到了分词结果. 比如 对待分词的句子 ‘全世界都在学中国话’ 得到一个BEMS序列 [S,B,E,S,S,S,B,E,S] 这个序列只是举例, 不一定正确, 通过把连续的BE凑合到一起得到一个词, 单独的S放单, 就得到一个分词结果了: 上面的BE位置和句子中单个汉字的位置一一对应, 得到全/S 世界/BE 都/S 在/S 学/S 中国/BE 话/S 从而将句子切分为词语.

以上, 就是作者这三条介绍的全部理解和分析, 对于其中任何术语不理解, 请使用搜索引擎.

结巴分词的过程:

1. 加载字典, 生成trie树

2. 给定待分词的句子, 使用正则获取连续的 中文字符和英文字符, 切分成 短语列表, 对每个短语使用DAG(查字典)和动态规划, 得到最大概率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词.

3. 使用python的yield 语法生成一个词语生成器, 逐词语返回. 当然, 我认为直接返回list, 效果也差不到哪里去.

另外谈谈结巴分词的不足和局限:

1 在中文分词的时候, 字典起到的作用貌似不大, 因为基于单字的HMM(BEMS)模型貌似就可以分词了, 不管正确率如何, 总算能分了.字典起到的作用在后面说.说作用不大, 是因为没有字典也能分词. 另外, 生成了DAG之后, 又用动态规划, 觉得浪费步骤.小概率连乘下限可能溢出已修正, 就不多说了.

2. 中文分词加载dict.txt这个字典后, 占用的内存为140多M, 觉得占用内存过多. 专业化的词典生成, 还不方便. 怎么训练自己的专用概率表, 就没有提供工具, 如果提供了训练自己的HMM模型工具, 估计更好.

3. 没有那个字典的话, Trie和DAG都不起作用, 仅靠HMM模型的viterbi算法起作用, 因此看出词典的作用就是用来矫正HMM模型的分词结果, 但是HMM分词的结果生成方式是把B开始E结束的序列, 组合成一个词, 因此, 这种判断方法不一定正确, 比如BES能不能算作一个词的序列我觉得值得考虑.

4. HMM是不是真的能够识别新词呢? 我认为是肯定的, 但是是要打折扣的. 这个跟作者训练的词库有关系, 新词的字出现的概率在一段时间内会井喷, 但在长期的语言现象中, 应该还是平稳的, 除非这个词从一出现就很流行, 而且会流行很长的时间.因此HMM识别新词的功能在时效性上是不足的, 他只能识别2个字的词, 对于3个字的新词, 估计就能力有限了. 这个有待于BEMS序列组合成词的算法的改变和新词获取算法的改变, 才能得到改善.

5. 引入二元分词的判断, 可能对词典的依赖会降低一点, 现在的词典的使用就是为了弥补HMM在识别多字词方面能力欠佳的问题, 所以词典中保存的是3 ,4 个字的词语.

6. 词性标注的问题, 在分词的时候, 不能同时识别词性, 因为分词的时候没有处理词性, 也就是说分词的时候, 没有语义分析的.词性标注的部分, 是使用另外的posseg模块进行的.还有一个问题是新词的词性可能没法识别, 同样这个是说那些3, 4字词.

7. 对专有名词比如人名 地名 机构名 的识别, 不能说好.

8. 文档太少了, 关于词性标注, 得到的结果没有一点分析, 词性来源于哪里都没有说明. 不利于大家一起改进.句法分析, 语义分析都是没有的.

9. 词性标注应该也是基于BEMS标注进行的. 不知道是不是可以独立出来.就是说基于语义来标示词性或者基于词语在句子中的位置来做推断进行标注词性.

10. 分词过程中, 不能获得这个句子中出现的词的次数信息, 或者说出现频率高的词, 不能用于抽取文章的关键词.

Leave a Reply

Your email address will not be published. Required fields are marked *