资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注(转) 中科院分词系统概述这几天看完了中科院分词程序的代码,现在来做一个概述,并对一些关键的数据结构作出解释、总体流程考虑输入的一句话,sSentence= 张华平欢迎您总体流程:一、分词 张/华/平/欢迎/您二、posTagging 张/q 华/j 平/j 欢迎/v 您/r三、NE 识别:人名识别,音译名识别,地名识别 张/q 华/j 平/j 欢迎/v 您/r 张华平/nr四、重新分词:张华平/欢迎/您五、重新 posTagging: 张华平/nr 欢迎/v 您/r技术细节一、分词分词程序首先在其头末添加开始符和结束符sSentence=始#始张华平欢迎您末#末然后是分词,基本思想就是分词的得到的词的联合概率最大假设 张华平欢迎您 分为 w_1/w_2/./w_k 则w_1/w_2/./w_k=argmax_w_1/w_2/./w_kP(w_1,w_2,.,w_k)=argmax_w_1/w_2/./w_kP(w_1)P(w_2).P(w_k)细节:首先给原句按字划分,所有汉字一个一段,连续的字母,数字一段,比如始#始张华平 2006欢迎您 asdf 末 #末 被划为始#始/张/ 华/平/2006/ 欢 /迎/您/asdf/末#末接着找出这个句子中所有可能出现的词,比如始#始张华平欢迎您末#末,出现的词有始#始, 张,华,平,欢, 迎,您,末#末,欢迎并查找这些词所有可能的词性和这些词出现的频率。将这些词保存在一个结构中,具体实现如下:m_segGraph 中有一个(PARRAY_CHAIN)m_pHead,是一个链(PARRAY_CHAIN)p-row/记录该词的头位置(PARRAY_CHAIN)p-col/记录该词的末位置(PARRAY_CHAIN)p-value/记录该词的-log( 出现的概率 ),出现的频率指所有该词的所有词性下出现的概率的总和。(PARRAY_CHAIN)p-nPos/记录该词的词性,比如人名标记为nr,则对应的nPos=n*256+r,如果该词有很多词性,则 nPos=0(PARRAY_CHAIN)p-sWord/记录该词(PARRAY_CHAIN)p-nWordLen/记录该词的长度举个例子:0 始 #始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末# 末 8对于张来说,row=1col=2value=-log(张 出现的频率 +1)/(MAX_FREQUENCE)nPos=0/张有 5 种词性sWord=张nWordLen=2保存的顺序是按 col 升序 row 升序的次序排列m_segGraph.m_pHead 始#始张 华平欢欢迎迎您末#末m_segGraph.m_nRow=7m_segGraph.m_nCol=8然后是生成一幅给予各种组合情况的图,并按照出现的概率大小保存概率最大的前m_nValueKind 个结果。细节:初始化,(CNShortPath)sp.m_apCost=m_segGraph;(CNShortPath)sp.m_nVertex=m_segGraph.m_nCol+1(CNShortPath)sp.m_pParent=CQueuem_segGraph.m_nColm_nValueKind(CNShortPath)sp.m_pWeight=ELEMENT_TYPEm_segGraph.m_nColm_nValueKind/m_pWeight00表示 1 处的 weightsp.ShortPath()函数中,for(nCurNode=1;nCurNodeGetElement(-1,nCurNode,0,/取出col=nCurNode 的第一个 PARRAY_CHAIN 的 value,比如 nCurNode=6,则 pEdgeList 指向欢迎,eWeight=pEdgeList-valuewhile(pEdgeList&pEdgeList-col=nCurNode)/对每一个 col=nCurNode 的pEdgeListfor(i=0;irow,0,eWeight+m_pWeightpEdgeList-row-1i);/将所有 col=nCurNode 的 pEdgeList 按照其 weight 升序放到 queWork 中/比如/*欢迎 m_pWeight30=0.2 eWight=0.2 =queWork.Push(4,0,0.4);0 始#始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末#末 8欢 m_pWeight40=0.5 eWight=0.1 =queWork.Push(5,0,0.6);m_pWeight41=0.6 eWight=0.1 =queWork.Push(5,0,0.7);queWork 欢迎 0.4迎 0.6迎 0.7*/for(i=0;ivaluem_pWeightnCurNode-1i=eWeight;/取前 m_nValueKind 个结果m_pParentnCurNode-1i.Push(nPreNode,nIndex);/按照 pEdgeList-value 的升序, 也就是 P 的降序放入 m_pParent 得到 m_pParent 之后,按照 m_pWeightm_segGraph.m_nCol-1的升序, 生成 pathCNShortPath:GetPaths(unsigned int nNode,unsigned int nIndex,int *nResult,bool bBest)/nNode=m_segGraph.m_nCol,nIndex 从 0 取到 m_nValueKind-1,nResult 输出结果,bBest=true 只输出最佳结果比如始#始张华平欢迎您末#末的结果为nResult0=0,1,2,3,4,6,7,8,-1 始#始/张/华/平/ 欢迎/ 您/末#末nResult1=0,1,2,3,4,5,6,7,8,-1 始# 始/张/华/平 /欢/ 迎/您/ 末# 末没有第三种结果取出所有 nResulti作为分词结果,结果保存在 m_graphOptimum 中,m_graphOptimum 和 m_segGraph 结构一样,只不过只存 nResulti中的结果:如果 m_nValueKind=1 则m_graphOptimum.m_pHead 始#始张 华 平 欢迎您 末 #末m_graphOptimum.m_nRow=7m_graphOptimum.m_nCol=8如果 m_nValueKind=2 则m_graphOptimum.m_pHead 始#始张 华平欢欢迎迎您末#末m_graphOptimum.m_nRow=7m_graphOptimum.m_nCol=8见 bool CSegment:GenerateWord(int *nSegRoute, int nIndex)这里的nSegRoute=上面的 nResult,是输入参数;nIndex 表示第 nIndex 个分词结果同时,CResult.m_Seg.m_pWordSegnIndexk中保存了第 nIndex 个结果的第 k 个词的信息:CResult.m_Seg.m_pWordSegnIndexk.sWord/词CResult.m_Seg.m_pWordSegnIndexk.nHandle/词性CResult.m_Seg.m_pWordSegnIndexk.dValue/-logP至此,分词部分结束二、posTaggingm_POSTagger.POSTagging(m_Seg.m_pWordSegnIndex,m_dictCore,m_dictCore);/对第 nIndex 个分词结果用标准的字典标注方便起见,下面假设 m_nValueKind=1m_POSTagger 用 HMM 对分词进行标注,这里输出概率为 P(w_i|c_i),c_i 为词性,w_i 为词;转移概率为 P(c_i|c_i-1),初始状态为 P(c_0)即 P(始#始的词性)用维特比算法求出一个 c_1/c_2/./c_k=argmax_c_1/c_2/./c_kP(w_1,w_2,.,w_k)将句子分成若干段,每段以有唯一 pos 的 w 结尾,也就是分词中CResult.m_Seg.m_pWordSeg0k.nHandle0 的那些词比如,举个例子0 始 #始 1 张 2 华 3 平 4 欢迎 5 您 6 末# 末 7pos1 pos1 pos1 pos1 pos1 pos1 pos1pos2 pos2 pos2 pos2pos3 pos3 pos3pos4pos5则该句被划分为0 始 #始1 张 2 华 3 平 4 欢迎 5 您6 末 #末对每一段用维特比算法确定一个唯一的 postag细节:首先 P(w,c)的输出概率存储在 dict 中,比如 dictCore,dictUnknow,通过dict.GetFrequency(char *sWord, int nHandle)函数获取 sWord pos 为 nHandle 的函数概率 P(c)存储在 context 中,比如 m_context,通过 context.GetFrequency(int nKey, int nSymbol)函数获取 pos 为 nSymbol 的函数,nKey=0转移概率 P(c|c)存储在 context 中,比如 m_context,通过context.GetContextPossibility(int nKey, int nPrev, int nCur)函数获取 c=nPrev,c=nCur 的转移概率 ,nKey=0重要的数据结构m_nTagsik表示第 i 个 w 的第 k 个 pos在 GetFrom 函数中表示 -log(第 i 个 w 的第 k 个 pos 的输出概率)在 CSpan:Disamb()函数中m_dFrequencyik表示 -log(从第 0 个 w 到第 i 个 w 的第 k 个 pos 的联合最大输出概率), 比如w_j w_j+1m_dFrequencyj0- m_dFrequencyj+10m_dFrequencyj1 - m_dFrequencyj+11-m_dFrequencyj+12则 图中的路径的权为 W(j,0-j+1,2)=m_dFrequencyj0-log(m_context.GetContextPossibility(0,m_nTagsj0,m_nTagsj+12)这样,选择m_dFrequenc
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号