文档章节

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

潘少online
 潘少online
发布于 2015/05/14 17:04
字数 1632
阅读 68
收藏 1
语言模型

预测词序列的概率

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

  • 有意见分歧

  • 有/ 意见/ 分歧 

  • 有意/ 见/ 分歧

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

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

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

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


统计语言模型的中文分词

从统计思想的角度来看,分词问题的输入是一个字串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;


© 著作权归作者所有

潘少online
粉丝 12
博文 58
码字总数 107019
作品 2
深圳
程序员
私信 提问
jieba中文分词源码分析(一)

一、缘由 接触自然语言处理(NLP)有段时间,理论知识有些了解,挺想动手写些东西,想想开源界关于NLP的东西肯定不少,其中分词是NLP的基础,遂在网上找了些资源,其中结巴分词是国内程序员用p...

gfsfg8545
2015/09/03
0
0
jieba中文分词的.NET版本:jieba.NET

简介 平时经常用Python写些小程序。在做文本分析相关的事情时免不了进行中文分词,于是就遇到了用Python实现的结巴中文分词。jieba使用起来非常简单,同时分词的结果也令人印象深刻,有兴趣的...

长征3号
2017/12/12
0
0
Hanlp等七种优秀的开源中文分词库推荐

中文分词是中文文本处理的基础步骤,也是中文人机自然语言交互的基础模块。由于中文句子中没有词的界限,因此在进行中文自然语言处理时,通常需要先进行分词。 纵观整个开源领域,陆陆续续做...

左手的倒影
2018/10/12
0
0
NLP系列-中文分词(基于统计)

上文已经介绍了基于词典的中文分词,现在让我们来看一下基于统计的中文分词。 统计分词: 统计分词的主要思想是把每个词看做是由字组成的,如果相连的字在不同文本中出现的次数越多,就证明这...

hiyoung
2018/09/25
0
0
NLP系列学习:CRF条件随机场(1)

大家好,今天让我们来看看条件随机场,条件随机场是一项大内容,在中文分词里广泛应用,因为我们在之前的文章里将概率图模型和基本的形式语言知识有所了解,当我们现在再去学习条件随机场会容易比...

云时之间
2018/04/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

约瑟夫环(报数游戏)java实现

开端 公司组织考试,一拿到考题,就是算法里说的约瑟夫环,仔细想想 以前老师将的都忘了,还是自己琢磨把~ package basic.gzy;import java.util.Iterator;import java.util.LinkedList;...

无极之岚
18分钟前
0
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
57分钟前
3
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
4
0
Spring中如何使用设计模式

关于设计模式,如果使用得当,将会使我们的代码更加简洁,并且更具扩展性。本文主要讲解Spring中如何使用策略模式,工厂方法模式以及Builder模式。 1. 策略模式 关于策略模式的使用方式,在S...

爱宝贝丶
昨天
4
0
前后端分离-前端搭建(vue)

前端使用vue,那么怎么搭建vue呢 先安装nodejs以及npm 现在基本的nodejs都包含有npm,下载安装后, 可以在cmd命令里输入 node -v 和npm -v 分别查看安装的版本 两个都显示了版本就是安装ok ...

咸鱼-李y
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部