分类目录归档:中文分词

Darts: Double-ARray Trie System 翻译文档

Deep Learning Specialization on Coursera

Darts: Double-ARray Trie System

开篇

Darts 是用于构建双数组 Double-Array [Aoe 1989] 的简单的 C++ Template Library . 双数组 (Double-Array) 是用于实现 Trie 的一种数据结构, 比其它的类 Trie 实现方式(Hash-Tree, Digital Trie, Patricia Tree, Suffix Array) 速度更快。 原始的 Double-Array 使能够支持动态添加删除 key, 但是 Darts 只支持把排好序的词典文件转换为静态的 Double-Array.

Darts 既可以像 Hash 一样作为简单的词典使用,也能非常高效的执行分词词典中必须的 Common Prefix Search 操作。

自2003年7月起, 两个开源的日语分词系统 MeCabChaSen 都使用了 Darts .

继续阅读

日文分词器 Mecab 文档

Deep Learning Specialization on Coursera

一、日文分词器 MeCab 简介

mecab (http://mecab.sourceforge.net/) 是奈良先端科学技術大学院的工藤拓开发的日文分词系统, 该作者写过多个 machine learning 方面的软件包, 最有名的就是 CRF++, 目前该作者在 google@Japan 工作。

mecab 是基于CRF 的一个日文分词系统,代码使用 c++ 实现, 基本上内嵌了 CRF++ 的代码, 同时提供了多种脚本语言调用的接口(python, perl, ruby 等).整个系统的架构采用通用泛化的设计, 用户可以通过配置文件定制CRF训练中需要使用的特征模板。 甚至, 如果你有中文的分词语料作为训练语料,可以在该架构下按照其配置文件的规范定制一个中文的分词系统。

日文NLP 界有几个有名的开源分词系统, Juman, Chasen, Mecab.   Juman 和 Chasen 都是比较老的系统了, Mecab 系统比较新, 在很多方面都优于 Juman 和 Chasen, mecab 目前开发也比较活跃。 Mecab 虽然使用 CRF 实现, 但是解析效率上确相当高效, 据作者的介绍, Mecab 比基于 HMM 的 Chasen 的解析速度要快。 笔者在一台 Linux 机器上粗略测试过其速度,将近达到 2MB/s, 完全达到了工程应用的需求, 该系统目前在日文 NLP 界被广泛使用。

中文和日文的有着类似的分词需求,因此mecab 对于中文处理来说有着很好的借鉴价值, 由于mecab 的内部模块化得很清晰,如果能读懂其文档的话,是比较容易能看懂整套代码的。 可惜目前中文的资料很少, 而其自带的文档又都是日文的, 所以了解它的中国人不多。

笔者把 mecab 自带的文档从日文翻译成中文, 希望mecab对于中文分词有兴趣的读者能有借鉴价值。日语水平很烂, 大家凑合着看吧。 对于自由的文档翻译,有一句话: Document is like sex. If it's good, it's very very good. If it's bad, it's better than nothing.

二、关于 MeCab (和布蕪)

Mecab 是京都大学情报学研究科-日本电信电话股份有限公司通信科学基础研究所通过 Unit Project 的合作研究共同开发的词法分析引擎。其设计的基本方针是不依赖于具体的语言,词典,语料库, 采用 Conditional Random Fields (CRF) 模型进行参数估计, 性能优于使用隐马模型的 ChaSen 。同时, 平均解析速度高于 ChaSenJumanKAKASI 这些日文词法分析器. 顺便说一下, Mecab (和布蕪, めかぶ), 是作者最喜欢的食物.

目录

继续阅读

Itenyh版-用HMM做中文分词五:一个混合的分词器

Deep Learning Specialization on Coursera

        在上一节中,我们看到了HMM分词器的优势在于它的灵活性,能够联系上文情况作出是否分词的判断,但是过于灵活又会出现一些低级的分词错误。一种扬长避短的想法是使用词典限定HMM的分词。具体的做法是,用基于词典的分词方法分出N种结果,然后用HMM挑出最有可能的分词结果。

       介绍一下分词使用的词典,在《中文分词入门之资源》有提到:

        Mandarin.dic                             分词词典,约40000条词汇

        对于一段文本,找出所有可能的切分结果叫做全切分,全切分可以保证切分结果集对正确切分结果100%的召回率,换句话说全切分中一定包含正确结果(在不包含未登录词的前提之下)。长度为n的句子,最大全切分数量可以达到2`(n-1)个,因此全切分计算量会随着句子长度增加急剧上升。举例,句子“研究生命起源”的全切分如下:

研/究/生/命

研/究/生命

研究/生/命

研究/生命

研究生/命

共有5个切分方案,其中倒数第二个是正确切分。下面讲一下我对句子进行全切分用的具体算法。

        如上图,考虑构建一颗多叉树,其中每一条从root到叶子节点的路径均为一种分词结果,所有root到叶子节点的路径就是全切分的结果。树的建立方法是使用的递归:

        对句子进行正向词典匹配,结果为:

        研            对剩余句子:究生命    进行词典匹配

        研究        对剩余句子:生命        进行词典匹配

        研究生    对剩余句子:命            进行词典匹配

        全切分结果准备就绪,下面的问题是如何从备选分词中选出最佳分词结果,因为备选结果只有有限的数量,因此可以使用枚举算法求最佳解:

                                                          ArgmaxC,O  P(C|O)

解法在第2集中已经提到,等价于求:

ArgmaxC,O  P(O|C)P(C)

       为了避免计算溢出(小数位数太多计算机无法表示),我们改为求:

                                                          ArgminC,O  -lnP(O|C) – lnP(C)

        对于句子“研究生命”,分词结果如下:

        研/究/生/命:44.24491284128293

        研/究/生命:37.12604972173189

        研究/生/命:33.59480382540995

        研究/生命:26.49050292705271

        研究生/命:32.15705471620734

        其中“研究/生命”拥有最低值,被选为最优解。再举一些有意思的分词结果:

        研究生/研究/生活

        结合/成/分子

        他/说/的/确实/在/理

        可以看出这种混合分词器能够灵活的掌握字符间的分和,消除一些歧义分词。

        下面是我对几种分词方法的实验结果,同时使用了ICTCLAS2011作为一个权威的分词效果比对,其中ICTCLAS2011使用的是它自带的词典,其他分词方法使用的词典是Mandarin.dic

                                      每秒分词     P         R            F

普通最大词匹配          5482401      0.76   0.85      0.80

扩展的最大匹配          1118591      0.79   0.75      0.77

普通的Markov           1590173      0.76   0.72      0.74

混合的Markov           46818        0.73   0.84      0.78

ICTCLAS2011           942973       0.92   0.92     0.92

          可以看出ICTCLAS果然是名不虚传,相对于混合的Markov,ICTCLAS使用的是层叠式的HMM模型,可以很好的识别出未登录词;其次ICTCLAS使用了基于N-最短路径的切分,对计算效率也有很大的提高。

          PS:因为之前没有想过要分享分词的程序,所以写得比较混乱,最近也很忙,我会尽快整理发上来的。

 

 

Itenyh版-用HMM做中文分词四:A Pure-HMM 分词器

Deep Learning Specialization on Coursera

先介绍一下使用的资源,分词使用的语料来自于SIGHAN Bakeoff 2005的 icwb2-data.rar,《中文分词入门之资源》里有很详细的介绍:

/icwb2-data.rar/training/msr_training.utf8  用以训练HMM,其中包含已分词汇约2000000个

/icwb2-data.rar/testing/pku_test.utf8           测试集

/icwb2-data.rar/scripts/score                           一个perl脚本,测试分词效果

         我们使用经典的字符标注模型,首先需要确定标注集,在前面的介绍中,我们使用的是{B,E}的二元集合,研究表明基于四类标签的字符标注模型明显优于两类标签,原因是两类标签过于简单而损失了部分信息。四类标签的集合是 {B,E,M,S},其含义如下:

B:一个词的开始

E:一个词的结束

M:一个词的中间

S:单字成词

举例:你S现B在E应B该E去S幼B儿M园E了S

用四类标签为msr_training.utf8做好标记后,就可以开始用统计的方法构建一个HMM。我们打算构建一个2-gram(bigram)语言模型,也即一个1阶HMM,每个字符的标签分类只受前一个字符分类的影响。现在,我们需要求得HMM的状态转移矩阵 A 以及混合矩阵 B。其中:

                                     Aij = P(Cj|Ci)  =  P(Ci,Cj) / P(Ci) = Count(Ci,Cj) / Count(Ci)

                                     Bij = P(Oj|Ci)  =  P(Oj,Ci) / P(Ci) = Count(Oj,Ci) / Count(Ci)

公式中C = {B,E,M,S},O = {字符集合},Count代表频率。在计算Bij时,由于数据的稀疏性,很多字符未出现在训练集中,这导致概率为0的结果出现在B中,为了修补这个问题,我们采用加1的数据平滑技术,即:

                                     Bij = P(Oj|Ci)  =  (Count(Oj,Ci) + 1)/ Count(Ci)

         这并不是一种最好的处理技术,因为这有可能低估或高估真实概率,更加科学的方法是使用复杂一点的Good—Turing技术,这项技术的的原始版本是图灵当年和他的助手Good在破解德国密码机时发明的。求得的矩阵A如下:

        B       M                    E              S

B  0.0 | 0.19922840916814916 | 0.8007715908318509 | 0.0

M  0.0 | 0.47583202978061256 | 0.5241679702193874 | 0.0

E  0.6309567616935934 | 0.0 | 0.0 | 0.36904323830640656

S  0.6343402140354506 | 0.0 | 0.0 | 0.36565844303914763

矩阵中出现的概率为0的元素表明B-B, B-S, M-B, M-S, E-M, E-E, S-M, S-E这8种组合是不可能出现的。这是合乎逻辑的。求得的矩阵B,部分如下:

   o1               o2            o3                o4

B 7.8127868094E-7 1.460991186336E-4 0.007293548529516 6.047041844505E-4……

M ……

E …….

S ……

我们设定初始向量Pi = {0.5, 0.0, 0.0, 0.5}(M和E不可能出现在句子的首位)。至此,HMM模型构建完毕。其实用统计方法构建HMM并不复杂,麻烦的是写程序,特别是需要将分类标签和字符集合进行编码,这是个极其繁琐的过程。

我用的JAVA写程序,因此使用的Jahmm这个开源项目来进行相关的计算,对于一个HMM模型,现在我们可以写入一个观察序列,用Viterbi算法获得一个隐藏序列(分词结果)。具体做法是(举例为虚构):

1 . 对测试集按标点符号,空格,换行符拆分为一条一条的只包含字符的单句:

……

中共中央总书记

国家主席

……

2. 将句子转化为对应的编码,也即观察序列:

……

101 121 101 47 1010 32 1992

332 3241 893 2111

……

3. 输入观察序列,使用Viterbi算法输出隐藏序列(0:B,1:M,2:E,3:S)

……

0112333

0202

……

4. 输出最终分词结果:

……

中共中央/总/书/记

国家/主席

……

现在我们在对测试集pku_test.utf8分词,并用perl脚本进行评测,结果如下=== SUMMARY:
=== TOTAL INSERTIONS:    5627
=== TOTAL DELETIONS:    10639
=== TOTAL SUBSTITUTIONS:    18194
=== TOTAL NCHANGE:    34460
=== TOTAL TRUE WORD COUNT:    104372
=== TOTAL TEST WORD COUNT:    99360:

=== TOTAL TRUE WORDS RECALL:  0.724   正确切分出的词的数目/应切分出的词的总数

=== TOTAL TEST WORDS PRECISION: 0.760  正确切分出的词的数目/切分出的词的总数

=== F MEASURE:      0.742   F1 = 2 * Precision*Recall / (Precision + Recall)

=== OOV Recall Rate:    0.250      未登录词召回率

精度为:76%,召回为:72.4%。一个不太让人满意的结果,我们来看看他都干了些什么:

                                                        改判/被/告人/死/刑立/即/执行

这是一个较典型的例子,可见分词结果中出现了“告人”,“刑立”等字典中不存在的词,这些是由于HMM分词的“自由度”太大造成的,当然这种较大的“自由度”也有好处,比如:

                                                        检察院/鲍绍坤/检察/长

         看!HMM成功的识别出一个人名,这是基于词典的分词方法做不到的。实际上,在ICTCLAS系统中(2004)就是用的HMM来识别人名。下一节将会介绍一个基于词典的混合HMM分词器。

Itenyh版-用HMM做中文分词三:前向算法和Viterbi算法的开销

Deep Learning Specialization on Coursera

上文中始终未提到前向算法与Viterbi算法,主要是因为想特意强调一下数学解不等同于算法解。算法解考虑进了计算的性能问题,算法是为计算机设计的。

首先看一下“评估”问题中的时间开销。回顾一下公式:

P(O) = sigmaO P(O|C)P(C)= sigmaO P(C1)P(O1|C1)P(C2|C1)P(O2|C2)…P(Ci|Ci-1)P(Oi|Ci)

如果我们使用枚举的方法来求解,那么对于C来说,设有N种状态,序列长度为T,那么所有可能的隐藏序列组合为N`T(N的T次方)个,对于每一个序列需要的乘法次数为2T次,而加法需要T次,那么总共需要的计算次数为2T*N`T的级数(精确的,需要(2T-1)N`T次乘法,N`T-1词加法)。例如N=5,T=100,那么需要约2*100*5`100约10`72次计算,显然我们需要一个更好的算法。

         考虑上图这个简单的例子,图中描述了两个隐藏序列:abb,cbb。为了求得P(O),使用枚举算法有:

Pia * P(O1|a)*Pab*P(O2|b)*Pbb*P(O3|b) + Pic * P(O1|c)*Pcb*P(O2|b)*Pbb*P(O3|b)

Pi代表初始概率,使用前向算法有:

(Pia* P(O1|a) *Pab + Pic * P(O1|c)*Pcb) *P(O2|b)*Pbb* P(O3|b)

其中前向算法中的第一个大括号中的式子为局部概率a2(b),可以清楚的看到枚举算法用了10次乘法和1次加法,而前向算法把乘法次数减少到了7次,原因就是前向算法使用了大家熟知的“乘法分配律”提取了公因式。看起来好像提升不多,不过当计算量大的话这种提升就很可观了。事实上,前向算法将计算次数减低到了N`2*T的级数,那么对于N=5,T=100只需要约3000次计算即可。

         现在使用上面的例子考虑一下Viterbi算法,使用枚举算法我们需要计算:

Pia * P(O1|a)*Pab*P(O2|b)*Pbb*P(O3|b) 和 Pic * P(O1|c)*Pcb*P(O2|b)*Pbb* P(O3|b)

并比较求得其中较大的一个,而使用Viterbi算法,我们首先比较:

Pia *P(O1|a)*Pab 与 Pic * P(O1|c)*Pcb 的大小,选出较大的一个再乘以 Pbb* P(O3|b)

10次乘法一次比较,减少到5词乘法一次比较。

         总结一下,前向算法和Viterbi算法分别从两种角度向我们展现了降低计算复杂度的方法,一种是提取公因式减少计算次数,例如计算(1+2+3)* 5 和 1*5+2*5+3*5,从数学角度来看只是表达的不同,但对于计算者(无论是人还是计算机)来说,少的计算次数意味着更小的计算时间开销;另一种是,去掉不必要的计算,要找到最大的隐藏序列,如果在子序列上都不能取得最大还有必要去计算全序列吗?

Itenyh版-用HMM做中文分词二:模型准备

Deep Learning Specialization on Coursera

本质上看,分词可以看做一个为文本中每个字符分类的过程,例如我们现在定义两个类别:E代表词尾词,B代表非词尾词,于是分词“你/现在/应该/去/幼儿园/了”可以表达为:你E现B在E应B该E去E幼B儿B园E了B,分类完成后只需要对结果进行“解读”就可以得到分词结果了。

那么如何找到这个分类序列EBEBEEBBEB呢?我们可以求得所有可能出现的分类序列的出现概率然后选择其中概率最大的一个,用数学表达为:

                                                 argmax C  P(C1,C2,C3….Ci) (1)

其中C代表一个分类标识,这里,C 属于 {E,B} 进一步的:

P(C1,C2,C3….Ci) = P(C1)P(C2,C3…..Ci|C1)=P(C1)P(C2|C1)P(C3…..Ci|C1,C2)=

P(C1)P(C2|C1)P(C3|C2,C1)P(C4|C3,C2,C1)…P(Ci|Ci-1….C1)

这里,我们假设第i个分类标记只依赖于第i-1个标记,那么我们可以得到分类标记的马尔科夫链了:

                                 P(C1,C2,C3….Ci) =P(C1)P(C2|C1)P(C3|C2)…P(Ci|Ci-1)

我们称P(Cj|Ci)为i到j的状态转移概率,可以通过在大量预料中使用统计的方法求得。如果我们用(1)这个模型为上例找到了EBEBEEBBEB这个序列,看似好像是一个好的解决方案,不难想到的问题是,对于任何一个10个字符组成的文本,我们都会得到这个相同的序列,也即相同的分词结果,这太可怕了!问题在于我们只考虑了分类标记而没有考虑被分词的对象,也即每一个具体的字符,我们称这些字符为观察值,用O表示,现在把它们考虑进来,我们要找的是:

                                argmax C  P(C1,C2,C3….Ci | O1, O2, O3……Oi) = P(C|O)(1)

         给定了O的情况下,最有可能出现的C的序列,也是HMM的“解码问题”,根据贝叶斯公式有:

                                               P(C|O) = P(O|C)P(C) / P(O)

        由于P(O)对于每一种序列来说都是一样的,因此可以去掉,因此,(1)等价于 :

                                                  argmax C P(O|C)P(C) (2)

P(C)的求法上面已经讲过了,对于P(O|C),HMM有两个假设:(a)已知类地序列,观察值在统计上是独立的; (b)某类的概率密度函数不依赖其他类。也就是说依赖性仅仅存在于产生类的序列,而在类内,观察值服从类自己的规则。因此对于:

                              P(O|C) = P(O1, O2, O3……Oi | C1,C2,C3….Ci )

根据假设a,观察序列具有统计意义上的独立性,因此:

                   P(O1, O2, O3……Oi | C1,C2,C3….Ci )=P(O1|C) * P(O2|C)……P(Oi|C)

根据假设b,对于Oi的分类Ci与Cj没有依赖关系,所以有:

                      P(O1|C) * P(O2|C)……P(Oi|C) = P(O1|C1) * P(O2|C2)……P(Oi|Ci)

同样的P(Oi|Ci) 可以通过在大量预料中使用统计的方法求得。至此我们在一个马尔科夫链上加入了观察值数据,构造了一个HMM,这个模型已经可以具备一定的分词能力啦!

尽管没有用到,顺便回顾一下HMM要解决的第一个问题“评估”,也即求一个给定观察序列的概率,即:P(O),用全概率公式展开有:P(O) = sigmaO P(O|C)P(C)(sigmaO代表对O的集合求和),同样需要计算P(O|C),因此计算上和“解码”有相似之处。

PS : 关于模型(1),在论文HMM Tutorial中写的是:

图中O是观察值,q是代表分类序列,λ指HMM模型,可见作者用的是qO的联合概率,而(1)中用的是O作为条件的条件概率。这个模型和模型(2)是相等的,因此所求的的序列也和模型(1)相等。个人认为,从理解来看,既然给定了O,是不是把O作为条件概率更合适呢?

Itenyh版-用HMM做中文分词一:序

Deep Learning Specialization on Coursera

前段时间仔细看了52nlp的关于隐马尔科夫模型(HMM)的介绍,深入浅出,真的是非常好的教材,再次感谢一下52nlp的辛勤劳作。这里,本人打算写一下个人运用HMM做分词的过程,目的有两个,一个是对之前工作的一个总结,梳理下自己的思路,另一个是和大家做一个交流。

如果对HMM不熟悉的话,推荐先看一看52nlp的系列文章《HMM学习最佳范例》,本文假设读者已经对HMM有所了解,很多地方会直接提出相关概念。理解前向算法,维特比算法是关键,关于无监督学习HMM的Baum-Welch算法在本文中没有使用,至少了解它的作用即可。

总所周知,在汉语中,词与词之间不存在分隔符(英文中,词与词之间用空格分隔,这是天然的分词标记),词本身也缺乏明显的形态标记,因此,中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序。例如,英文句子:you should go to kindergarten now 天然的空格已然将词分好,只需要去除其中的介词“to”即可;而“你现在应该去幼儿园了”这句表达同样意思的话没有明显的分隔符,中文分词的目的是,得到“你/现在/应该/去/幼儿园/了”。那么如何进行分词呢?主流的方法有三种:第1类是基于语言学知识的规则方法,如:各种形态的最大匹配、最少切分方法;第2类是基于大规模语料库的机器学习方法,这是目前应用比较广泛、效果较好的解决方案.用到的统计模型有N元语言模型、信道---噪声模型、最大期望、HMM等。第3类也是实际的分词系统中用到的,即规则与统计等多类方法的综合。

我计划在 本系列文章中完成以下工作,首先在52nlp的工作基础上对HMM模型做一些补充,然后制作一个HMM的分词器,之后分析其缺点,最后制作一个混合分词器。如果有任何不足的地方,欢迎大家拍砖!

初学者报道(3) CRF 中文分词解码过程理解

Deep Learning Specialization on Coursera

好久没有来写文章了,这段时间我研究了一下CRF,也找人请教过,下面写下自己的一些理解,在网络上也找过CRF的资料,大多为英文,对于解码的描述,就说用viterbe 实现,如何实现,却很少提及,以下为我的理解,如有错误欢迎指正,这样可以帮助我理解,先行谢过!

一,标记问题解决分词:就是将 词语开始和结束的字标记出来,就能对一个句子完成分词,假设使用两个标记B (开始),E(结束)对句子进行处理,如:“民主是普世价值”,民B主E是B普B世E价B值E, 这样标记明确,分词结果就明确了。

二,如何找到最好的标记结果:知道如何用标记的方式解决分词,那么怎么为一个句子找到一个最好的标记序列呢,CRF为这样的问题提供了一个解决方案,对于输入序列X1,X2...Xn(对于分词,就是那个句子),求这个输入序列条件下 某个 标记序列(Y1,Y2...Yn)的概率 极值。

三,解码过程:

这里用一个例子来说明,对于CRF的原理,我不做详述,我是半吊子,怕解释不好,只说一下我理解的解码过程。

CRF的公式:P(y|x,λ)=Σj λjFj(y,x)/Z(x)     //这里的j都是下标

先说问题:

使用4标记,B-开始,O-单独成词,M-词语中间的字,E-结束,

特征:一元特征,V-1 当前字的前一个字,V0当前字,V1当前字的后一个字

二元特征,各标记间的转移特征

句子如下:

民   主   是   普   世   价   值

B     B    B    B   B    B    B

O    O   O    O   O    O     O

M   M   M   M   M   M   M

E     E    E    E    E    E     E

Viterbe解码就是在以上由标记组成的 数组中 搜索一条 最优的路径。

对于每一列的每一个标记,我们都要计算到达该标记的分数,这个分数由三部分组成,它本身的一元特征权重W,它前面一个字标记的 路径分数PreScore,前面一个字标记到当前标记转移特征权重TransW,

1. 计算第一列的分数(score),对于,‘民’来说,我们要算 B,O,M,E的Score,因为是第一列,所以PreSocre和TransW都是0,就不用计算,只需要计算自己的一元特征的权重:

对于标记,B,我们计算它的Score,记为S1B=W1B=w(null,民,B)+w(民,B)+w(民,B,主)  //这些特征的意思是: (null,民,B),当前字为 ‘民’标记为B,前面一个字为空,(民,B):当前字为‘民’,标记为B,(民,B,主):当前字为'民',标记为B,当前字的后一个字为‘主’。特征的权重都是在训练时得到的。

对于标记,O,M,E,一样要计算W1O,W1M,W1E,从而得到分数S1O,S1M,S1E

2.对于第二列,首先要计算是每个标记的 一元权重W2B,W2O,W2M,W2E.

对于B,到达该标记的最大分数为:S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E))+W2B,其中v(BB)等为B到B的转移特征的权重。这个也是由训练得到的。同样对于第二列的O,M,E也要计算S2O,S2M,S2E

3.一直计算到最后一列,‘值’字的所有标记,得到S7B,S7O,S7M,S7E.比较这四个值中的最大值,即为最优路径的分数,然后以该值的标记点为始点 回溯得到最优路径(这里在计算过程中,要记录到达该标记的前一个标记,用于回溯)

终于写好!:)

 

初学者报道(2):实现 1-gram分词算法

Deep Learning Specialization on Coursera

写了个1-gram的分词算法实现:

借鉴了之前在这个blog上看到的n-gram算法中的split函数的写法,其他部分自己写的。

 

Dictionary.py:

class Dictionary:
    'Dictionary Loading and Management'
    def __init__(self,dicname):
        self.dictMap={}
        self.N = 0;
        dictfile = open(dicname,'r')
        for eachLine in dictfile:
            dictstr = eachLine.decode("cp936")
            strlist = dictstr.split("\t",2)
            self.dictMap[strlist[0]] = strlist[1].split("\n",1)[0]
            self.N+=int(self.dictMap[strlist[0]])
        dictfile.close()
        print self.N
    def getCount(self,wordname):
        if(self.dictMap.has_key(wordname)):
            return int(self.dictMap[wordname])
        else:
            return 0.5;#如果词典中没有,这个词的出现次数被定为 0.5
    def getPvalue(self,wordname):
        return float(self.getCount(wordname))/self.N
    def isAWord(self,word):
        return self.dictMap.has_key(word)
        

if __name__=='__main__':
    dict1=Dictionary("dict.txt")
class Ngram:
    def __init__(self,dictionary):
        self.mDict=dictionary
        self.wordList=()
        self.valueMap = {}
        self.segMap={}
    def splitsentence(self,sentence):
        wordlist = []        
        for eachNum in range(len(sentence)):
            wordlist.append((sentence[:eachNum+1],sentence[eachNum+1:]))
        return wordlist
    def maxP(self, sentence):
        if(len(sentence)<=1):
            return self.mDict.getPvalue(sentence)
        SenSplitList = self.splitsentence(sentence);
        maxPvalue = 0;
        wordPair = [];
        wordP = 0;
        for eachPair in SenSplitList:
            if(len(eachPair[0])>0 and len(eachPair[1])>0):
                p1=0;
                p2=0
                if(self.valueMap.has_key(eachPair[0])):
                    p1=self.valueMap[eachPair[0]]
                else:
                    p1=self.maxP(eachPair[0])
                if(self.valueMap.has_key(eachPair[1])):
                    p2=self.valueMap[eachPair[1]]
                else:
                    p2=self.maxP(eachPair[1])                    
                wordP=p1*p2
            if(maxPvalue<wordP):
                maxPvalue = wordP
                wordPair = eachPair
        
        v=self.mDict.getPvalue(sentence)
        if((v)>maxPvalue and self.mDict.isAWord(sentence)):
            self.valueMap[sentence]=v
            self.segMap[sentence]=sentence
            return v
        else:
            self.valueMap[sentence]=maxPvalue
            self.segMap[sentence]=wordPair
            return maxPvalue
    def getSeg(self):
        return self.segMap
if(__name__ =="__main__"):
    ngram1 = Ngram("dict1")
    print ngram1.splitsentence("ABC")
from Dictionary import Dictionary
from ngram import Ngram

def printSeg(segMap,sentence):
    if(segMap.has_key(sentence)):
        pair = segMap[sentence]
        if(isinstance(pair,tuple)):
            printSeg(segMap,pair[0])
            printSeg(segMap,pair[1])
        else:
            if(sentence==pair):
                print sentence
            else:
                printSeg(segMap,pair)
    else:
        print sentence
    

dict1 = Dictionary("dict.txt")
while(True):
    ngram1 =Ngram(dict1)
    sentence = raw_input("please input a Chinese Sentence:").decode("cp936");
    print ngram1.maxP(sentence)
    segmap=ngram1.getSeg()
    #for eachkey in segmap:
               
     #   if(isinstance(segmap[eachkey],tuple)):
      #      print (eachkey+":"+segmap[eachkey][0]+','+segmap[eachkey][1])
       # else:
        #    print (eachkey+":"+segmap[eachkey])
    printSeg(segmap,sentence)


					

初学者报到: 实现了一个最大匹配的分词算法

Deep Learning Specialization on Coursera

看了一段时间了的自然语言,不过还是很初级。

今天下载了一个分词的字典,自己用python写了一个分词的函数。

放上来,给大家踩,不吝赐教!

用的是最大匹配算法。

# -*- coding: cp936 -*-

import string

def loaddict():
filename=raw_input('Enter file name:')
f = open(filename,'r')

DICT={}
for eachLine in f:
dictStr = eachLine.decode('cp936')
strList=dictStr.split("\t",2)
DICT[strList[0]]=strList[1].split("\n",1)[0]
global DIC_MAXL
if(DIC_MAXL<len(strList[0])):
DIC_MAXL = len(strList[0])
f.close()
print("max length:")
print(DIC_MAXL)
return DICT;

def segmentation(dic):
sentence = unicode(raw_input('请输入中文句子:'),'cp936')
print sentence
length=len(sentence)
print('length:')
print length
global DIC_MAXL
if(length<DIC_MAXL):
wlen=length
else:
wlen=DIC_MAXL
testS=sentence
wordList=[]
while(len(testS)>0):
word=testS[0:wlen]
meet=False;
while((not meet )and (len(word)>0) ):
if(dic.has_key(word)):
wordList.append(word)
testS=testS[len(word):len(testS)]
meet=True;
else:
if(len(word)==1):
wordList.append(word)
testS=testS[len(word):len(testS)]
meet=True;
else:
word=word[0:len(word)-1]
return wordList

DIC_MAXL=0
dictionary=loaddict()
print DIC_MAXL
while(True):
wordl=segmentation(dictionary)
for eachChar in wordl:
print eachChar

真的很初级,大家轻踩!

也别不好意思踩,踩了我就能进步了!

多谢