作者归档:ricky

初学者报道(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

真的很初级,大家轻踩!

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

多谢