搜索引擎开发实践基于概率语言模型的中文分词.ppt

搜索引擎开发实践第五讲基于概率语言模型的中文分词主讲人：罗刚概 述l作业讲解：遍历TrieTrie树l概率语言模型分词原理l形成切分词图l动态规划算法求解最佳切分路径l作业：实现地名切分2.作业讲解：遍历Trie树/深度遍历public void deepSearch(ArrayList parentNodes,TrieNode node,StringBuilder ret,int deapth)public void deepSearch(ArrayList parentNodes,TrieNode node,StringBuilder ret,int deapth)if(node!=null)if(node!=null)for(int i=0;i deapth;i+)for(int i=0;i deapth;i+)ret.append(|);ret.append(|);ret.append(node.getPath(parentNodes)+n);ret.append(node.getPath(parentNodes)+n);ArrayList newParent=(ArrayList)parentNodes.clone();ArrayList newParent=(ArrayList)parentNodes.clone();newParent.add(node);newParent.add(node);for(TrieNode c:node.children)for(TrieNode c:node.children)deepSearch(newParent,c,ret,deapth+1);/deepSearch(newParent,c,ret,deapth+1);/递归调用 /打印树状图public String toString()public String toString()StringBuilder ret=new StringBuilder();StringBuilder ret=new StringBuilder();ArrayList parentNodes=new ArrayList();ArrayList parentNodes=new ArrayList();deepSearch(parentNodes,root,ret,0);deepSearch(parentNodes,root,ret,0);return ret.toString();return ret.toString();3.语言模型预测词序列的概率哪个词序列更有可能出现？l有意见分歧l有/意见/分歧 l有意/见/分歧l这篇文章写得太平淡了。这/篇/文章/写/得/太/平淡/了/。这/篇/文章/写/得/太平/淡/了/。把概率赋予词序列的方法，称为语言模型。4.统计语言模型的中文分词从统计思想的角度来看，分词问题的输入是一个字串C=C=输出是一个词串S=S=对于一个特定的字符串C C，会有多个切分方案S S对应，分词的任务就是在这些S S中找出概率最大的一个。根据贝叶斯公式：其中P(C)P(C)是字串在语料库中出现的概率，只是一个用来归一化的固定值。从词串恢复到汉字串的概率只有唯一的一种方式，所以P(C|S)=1P(C|S)=1。因此，比较P(S|C)P(S|C)的大小变成比较P(S)P(S)的大小。因此：5.计算P(S)独立性假设，一元语法假设每个词之间的概率是上下文无关的 为了避免向下溢出，取log最大似然法估计词语的概率：6.计算最大概率C:C:有意见分歧S1:有/意见/分歧/S2:有意/见/分歧/P(SP(S1 1)=P()=P(有)*P()*P(意见)*P()*P(分歧)=1.8 10)=1.8 10-9-9P(SP(S2 2)=P()=P(有意)*P()*P(见)*P()*P(分歧)=110)=110-11-11可得P(SP(S1 1)P(S)P(S2 2)，所以选择S S1 1对应的切分。为了避免向下溢出，取loglog的计算结果：log P(Slog P(S1 1)=log P()=log P(有)+log P()+log P(意见)+log P()+log P(分歧)=-20.135479172044292=-20.135479172044292log P(Slog P(S2 2)=log P()=log P(有意)+log P()+log P(见)+log P()+log P(分歧)=-20.72326583694641=-20.72326583694641log P(Slog P(S1 1)log P(S)log P(S2 2)词语概率有0.0180有意0.0005意见0.0010见0.0002分歧0.00017.与最大长度匹配分词的区别如果每个词出现的概率都相同，则现在的分词方法退化成最少词数的分词。最少词数的分词，即一句话分成数量最少的词串，类似最大长度匹配切分。因为，如果0P(w)10P(w)1，而且nmn(P(w)(P(w)m m 8.切分词图l根据基本词库对句子进行全切分，找出所有可能的词，形成切分词图。l边代表词，边的权重是词的概率。l从切分词图中寻找概率最大的词序列，对应于从有向无环带正权重的图中找最长路径。l其中：没有考虑未登录词日期、数字串等可以用规则匹配，不需要考虑它内部的概率。例如2010年3月23日 这样的日期9.切分词图中的点012345 有 意 见 分 歧如果待切分的字符串有m个字符，考虑每个字符左边和右边的位置，则有 m+1个点对应，点的编号从0到m。10.切分词图第11页“有意见分歧”生成的切分词图 意见 分歧 有意 分 见 意 有012345路径1 1：0 01 13 35 5 对应切分方案:有/意见/分歧/路径2 2：0 02 23 35 5 对应切分方案:有意/见/分歧/计算最大概率等于求切分词图的最长路径11.表示切分词图切分词图的特点：l边比较少，所以是一个稀疏图(Sparse GraphSparse Graph)。稀疏图一般用邻接表表示。l需要找一个节点的前驱词集合，所以用逆邻接表表示。12.逆邻接表(Inverse adjacency list)意见 分歧 有意 分 见 意 有0123450 0/0 01 1/123451 1/3 3/3 3/切分词图逆邻接表13.切分词图中的边切分词图中的边都是词典中的词，边的起点和终点分别是词的开始和结束位置public class CnTokenpublic class CnTokenpublic String termText;/public String termText;/词public int start;/public int start;/词的开始位置public int end;/public int end;/词的结束位置public int freq;/public int freq;/词在语料库中出现的频率public CnToken(int vertexFrom,int vertexTo,String word)public CnToken(int vertexFrom,int vertexTo,String word)start=vertexFrom;start=vertexFrom;end=vertexTo;end=vertexTo;termText=word;termText=word;14.单向链表 public class CnTokenLinkedList implements Iterable public class CnTokenLinkedList implements Iterable public static class Node public static class Node public CnToken item;public CnToken item;public Node next;/public Node next;/记录下一个对象Node(CnToken item)Node(CnToken item)this.item=item;this.item=item;next=null;next=null;private Node head;/private Node head;/头对象public CnTokenLinkedList()public CnTokenLinkedList()head=null;head=null;public void put(CnTokenInf item)public void put(CnTokenInf item)Node n=new Node(item);Node n=new Node(item);n.next=head;n.next=head;head=n;head=n;public Node getHead()public Node getHead()return head;return head;public Iterator iterator()/public Iterator iterator()/叠代器return new LinkIterator(head);return new LinkIterator(head);15.邻接表表示的切分词图public class AdjList public class AdjList private CnTokenLinkedList list;/AdjListprivate CnTokenLinkedList list;/AdjList的图结构/*/*构造方法*/*/public AdjList(int verticesNum)public AdjList(int verticesNum)list=new CnTokenLinkedListverticesNum;list=new CnTokenLinkedListverticesNum;/初始化链表数组for(int index=0;index verticesNum;index+)for(int index=0;index verticesNum;index+)listindex=new CnTokenLinkedList();listindex=new CnTokenLinkedList();/*/*增加一个边到图中*/public void addEdge(AddressTokenInf newEdge)public void addEdge(AddressTokenInf newEdge)listnewEdge.end.put(newEdge);listnewEdge.end.put(newEdge);/*/*返回前驱词集合*/*/public Iterator getPrev(int vertex)public Iterator getPrev(int vertex)CnTokenLinkedList ll=listvertex;CnTokenLinkedList ll=listvertex;if(ll=null)if(ll=null)return null;return null;return ll.iterator();return ll.iterator();16.查词典形成切分词图for(int i=0;ilen;)/for(int i=0;ilen;)/遍历整个句子长度boolean match=dict.getMatch(sentence,i,wordMatch);/boolean match=dict.getMatch(sentence,i,wordMatch);/到词典中查询，返回从指定位置开始的所有词 if(match)/if(match)/已经匹配上 for(String word:wordMatch.values)/for(String word:wordMatch.values)/把查询到的词作为边加入切分词图中j=i+word.length();j=i+word.length();g.addEdge(new CnToken(i,j,10,word);g.addEdge(new CnToken(i,j,10,word);i=wordMatch.end;i=wordMatch.end;else/else/没有匹配上j=i+1;j=i+1;g.addEdge(new CnToken(i,j,1,sentence.substring(i,j);/g.addEdge(new CnToken(i,j,1,sentence.substring(i,j);/把单字作为边加入切分词图中i=j;i=j;17.动态规划求解到节点i i为止的最大概率称为节点i i的概率。如果WWj j的结束节点是NodeNodei i，就称WWj j为NodeNodei i的前驱词这里的prev(Nodeprev(Nodei i)就是节点i i的前驱词集合。比如上面的例子中，节点1 1的前驱词集合是候选词“有”，节点3 3的前驱词集合是“意见”和“见”。StartNode(wStartNode(wj j)是w wj j 的开始节点，也是节点i i的前驱节点。因此切分的最大概率max(P(S)max(P(S)就是P(NodeP(Nodemm)也就是P(P(节点mm的最佳前驱节点)*P()*P(节点mm的最佳前驱词)18.计算动态规划31寻找最佳前驱词P(意见)P(见)2119.计算最佳前驱词int prevNode;/int prevNode;/最佳前驱节点double prob;/double prob;/节点概率/计算节点i i的最佳前驱节点，以及它的最大概率void getBestPrev(AdjList g,int i)void getBestPrev(AdjList g,int i)Iterator it=g.getPrev(i);/Iterator it=g.getPrev(i);/得到前驱词集合，从中挑选最佳前趋词double maxProb=Double.NEGATIVE_INFINITY;/double maxProb=Double.NEGATIVE_INFINITY;/候选节点概率int maxID=-1;/int maxID=-1;/候选最佳前驱节点while(it.hasNext()while(it.hasNext()CnToken itr=it.next();CnToken itr=it.next();double nodeProb=probitr.start+Math.log(itr.freq)-logN;double nodeProb=probitr.start+Math.log(itr.freq)-logN;if(nodeProb maxProb)/if(nodeProb maxProb)/概率最大的算作最佳前趋 maxID=itr.start;maxID=itr.start;maxProb=nodeProb;maxProb=nodeProb;probi=maxProb;probi=maxProb;prevNodei=maxID;prevNodei=maxID;20.回溯寻找最大概率切分ArrayList ret=new ArrayList();ArrayList ret=new ArrayList();for(int i=(g.verticesNum-1);i0;i=prevNodei)/for(int i=(g.verticesNum-1);i0;i=prevNodei)/从右向左取最佳节点 ret.add(i);ret.add(i);return ret;return ret;意见 分歧 有意 分 见 意 有01234521.作业1.1.根据地名词典，实现地名切分，例如 2.2.北京市/海淀区/学院路22.感谢您对猎兔搜索的支持!http:/