搜索引擎之基于概率语言模型的中文分词

原创
2015/05/14 17:04
阅读数 97
语言模型

预测词序列的概率

哪个词序列更有可能出现?

  • 有意见分歧

  • 有/ 意见/ 分歧 

  • 有意/ 见/ 分歧

  • 这篇文章写得太平淡了。

  • 这/篇/文章/ 写/ 得/ 太/平淡/ 了/。

  • 这/ 篇/ 文章/ 写/ 得/ 太平/ 淡/ 了/ 。

    把概率赋予词序列的方法,称为语言模型。


统计语言模型的中文分词

从统计思想的角度来看,分词问题的输入是一个字串C=C1,C2,... ,CN

输出是一个词串S=W1,W2,... ,WN

对于一个特定的字符串C,会有多个切分方案S对应,分词的任务就是在这些S中找出概率最大的一个。

根据贝叶斯公式:

其中P(C)是字串在语料库中出现的概率,只是一个用来归一化的固定值。从词串恢复到汉字串的概率只有唯一的一种方式,所以P(C|S)=1。因此,比较P(S|C)的大小变成比较P(S) 的大小。因此: 


计算P(S)

假设每个词之间的概率是上下文无关的 

最大似然法估计词语的概率:

为了避免向下溢出,取log


计算最大概率

C: 有意见分歧

S1:  有/  意见/  分歧/

S2:  有意/  见/  分歧/

P(S1) = P(有) * P(意见) * P(分歧) = 1.8 × 10-9

P(S2) = P(有意) * P(见) * P(分歧) = 1×10-11

可得P(S1) > P(S2),所以选择S1对应的切分。

为了避免向下溢出,取log的计算结果:

log P(S1) = log P(有) + log P(意见) + log P(分歧) 

=-20.135479172044292

log P(S2) = log P(有意) + log P(见) + log P(分歧) 

=-20.72326583694641

                                                                              log P(S1)> log P(S2) 


与最大长度匹配分词的区别

如果每个词出现的概率都相同,则现在的分词方法退化成最少词数的分词。

最少词数的分词,即一句话分成数量最少的词串,类似最大长度匹配切分。

因为,如果0<P(w)<1,而且n<m

则 (P(w))n > (P(w))m 


切分词图

  • 根据基本词库对句子进行全切分,找出所有可能的词,形成切分词图。

  • 边代表词,边的权重是词的概率。

  • 从切分词图中寻找概率最大的词序列,对应于从有向无环带正权重的图中找最长路径。

  • 其中:

  • 没有考虑未登录词

  • 日期、数字串等可以用规则匹配,不需要考虑它内部的概率。例如2010年3月23日 这样的日期

切分词图中的点

如果待切分的字符串有m个字符,考虑每个字符左边和右边的位置,则有 m+1个点对应,点的编号从0到m。

“有意见分歧”生成的切分词图

路径1: 0-1-3-5    对应切分方案:  有/  意见/  分歧/

路径2: 0-2-3-5    对应切分方案:  有意/  见/  分歧/ 

计算最大概率等于求切分词图的最长路径

表示切分词图

切分词图的特点:

  • 边比较少,所以是一个稀疏图(Sparse Graph)。稀疏图一般用邻接表表示。

  • 需要找一个节点的前驱词集合,所以用逆邻接表表示。


逆邻接表(Inverse adjacency list)

切分词图

逆邻接表

切分词图中的边

切分词图中的边都是词典中的词,边的起点和终点分别是词的开始和结束位置

public class CnToken{
  public String termText;//词
  public int start;//词的开始位置
  public int end;//词的结束位置
  public int freq;//词在语料库中出现的频率
  public CnToken(int vertexFrom, int vertexTo, String word) {
  start = vertexFrom;
  end = vertexTo;
  termText = word;
  }
}

单向链表 

public class CnTokenLinkedList implements Iterable<CnToken> {
  public static class Node {
  public CnToken item;
  public Node next;//记录下一个对象
  Node(CnToken item) {
  this.item = item;
  next = null;
  }
  }
  private Node head;//头对象
  public CnTokenLinkedList() {
  head = null;
  }
  public void put(CnTokenInf item) {
  Node n = new Node(item);
  n.next = head;
  head = n;
  }
  public Node getHead() {
  return head;
  }
  public Iterator<CnToken> iterator() {//叠代器
  return new LinkIterator(head);
  } 
}

邻接表表示的切分词图

public class AdjList {
  private CnTokenLinkedList list[];// AdjList的图结构
  /**
   * 构造方法
   */
  public AdjList(int verticesNum) {
  list = new CnTokenLinkedList[verticesNum];   
  //初始化链表数组
  for (int index = 0; index < verticesNum; index++) {
  list[index] = new CnTokenLinkedList();
  }
  }  
  /**
   * 增加一个边到图中
   */
  public void addEdge(AddressTokenInf newEdge) {
  list[newEdge.end].put(newEdge);
  }
  /**
   * 返回前驱词集合
   */
  public Iterator<CnToken> getPrev(int vertex) {
  CnTokenLinkedList ll = list[vertex];
  if(ll == null)
  return null;
  return ll.iterator();
  }
}

查词典形成切分词图

for(int i=0;i<len;){//遍历整个句子长度
  boolean match = dict.getMatch(sentence, i, wordMatch);//到词典中查询,返回从指定位置开始的所有词 
  if (match)//已经匹配上
  {
  for (String word:wordMatch.values) {//把查询到的词作为边加入切分词图中
  j = i+word.length();
  g.addEdge(new CnToken(i, j, 10, word));
  }
  i=wordMatch.end;
  }else{//没有匹配上
  j = i+1;
  g.addEdge(new CnToken(i,j,1,sentence.substring(i,j))); //把单字作为边加入切分词图中
  i=j;
  }
}

动态规划求解

到节点i为止的最大概率称为节点i的概率。 

如果Wj的结束节点是Nodei,就称Wj为Nodei的前驱词

这里的prev(Nodei)就是节点i的前驱词集合。

比如上面的例子中,节点1的前驱词集合是候选词“有”,节点3的前驱词集合是“意见”和“见”。

StartNode(wj)是wj 的开始节点,也是节点i的前驱节点。

因此切分的最大概率max(P(S))就是P(Nodem)也就是

P(节点m的最佳前驱节点)*P(节点m的最佳前驱词)

计算动态规划

计算最佳前驱词

int[] prevNode; //最佳前驱节点
double[] prob;//节点概率
//计算节点i的最佳前驱节点,以及它的最大概率
void getBestPrev(AdjList g,int i){
  Iterator<CnToken> it = g.getPrev(i);//得到前驱词集合,从中挑选最佳前趋词
  double maxProb = Double.NEGATIVE_INFINITY; //候选节点概率
  int maxID = -1;//候选最佳前驱节点  
  while(it.hasNext())
  {
      CnToken itr = it.next();
      double nodeProb = prob[itr.start] + Math.log(itr.freq) - logN;
      if (nodeProb > maxProb)//概率最大的算作最佳前趋
      {
      maxID = itr.start;
      maxProb = nodeProb;
      }
   }
  prob[i] = maxProb;
  prevNode[i] = maxID;
}

回溯寻找最大概率切分

ArrayList<Integer> ret = new ArrayList<Integer>();
for(int i=(g.verticesNum-1);i>0;i=prevNode[i]) // 从右向左取最佳节点
{
  ret.add(i);
}
return ret;


展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部