思享工具箱

基于Tire树和最大概率法的中文分词功能的Java实现

摘要：
children.containsKey）｛return；｝children.remove；｝｝2.最大概率法最大概率法是汉语分词策略的一种方法。与最大匹配方法和其他策略相比，最大概率方法更准确，其实现也更复杂。对于最大概率方法，要求短语集在语料库中出现的概率的乘积最大。以下代码是基于动态编程的最大概率方法的Java实现：packagechn.seg；importjava.io.BufferedReader；importjava.io.File；importjava.io.FileInputStream；importjava.io.io异常；importjava.io.InputStreamReader；importjava.util.ArrayList；importjava.util.List；publicclassChnSeq｛privateTireNodetire＝null；publicvoinitit（）throwsIOException，ClassNotFoundException｛Filefile＝newFile；if（！

对于分词系统的实现来说，主要应集中在两方面的考虑上：一是对语料库的组织，二是分词策略的制订。

1.   Tire树

Tire树，即字典树，是通过字串的公共前缀来对字串进行统计、排序及存储的一种树形结构。其具有如下三个性质：

1)      根节点不包含字符（或汉字），除根节点以外的每个节点只能包含一个字符（汉字）

2)      从根节点到任一节点的路径上的所有节点中的字符（汉字）按顺序排列的字符串（词组）就是该节点所对应的字符串（词组）

3)      每个节点的所有直接子节点包含的字符（汉字）各不相同

上述性质保证了从Tire树中查找任意字符串（词组）所需要比较的次数尽可能最少，以达到快速搜索语料库的目的。

如下图所示的是一个由词组集<一，一万，一万多，一万元，一上午，一下午，一下子>生成的Tire树的子树：

基于Tire树和最大概率法的中文分词功能的Java实现第1张

可见，从子树的根节点“一”开始，任意一条路径都能组成一个以“一”开头的词组。而在实际应用中，需要给每个节点附上一些数据属性，如词频，因而可以用这些属性来区别某条路径上的字串是否是一个词组。如，节点“上”的词频为-1，那么“一上”就不是一个词组。

如下的代码是Tire树的Java实现：

 

package chn.seg;

import java.util.HashMap;
import java.util.Map;

public class TireNode {
	
	private String character;
	private int frequency = -1;
	private double antilog = -1;
	private Map<String, TireNode> children;
	
	public String getCharacter() {
		return character;
	}
	
	public void setCharacter(String character) {
		this.character = character;
	}
	
	public int getFrequency() {
		return frequency;
	}
	
	public void setFrequency(int frequency) {
		this.frequency = frequency;
	}
	
	public double getAntilog() {
		return antilog;
	}
	
	public void setAntilog(double antilog) {
		this.antilog = antilog;
	}
	
	public void addChild(TireNode node) {
		if (children == null) {
			children = new HashMap<String, TireNode>();
		}
		
		if (!children.containsKey(node.getCharacter())) {
			children.put(node.getCharacter(), node);
		}
	}
	
	public TireNode getChild(String ch) {
		if (children == null || !children.containsKey(ch)) {
			return null;
		}
		
		return children.get(ch);
	}
	
	public void removeChild(String ch) {
		if (children == null || !children.containsKey(ch)) {
			return;
		}
		
		children.remove(ch);
	}
}

2.   最大概率法（动态规划）

最大概率法是中文分词策略中的一种方法。相较于最大匹配法等策略而言，最大概率法更加准确，同时其实现也更为复杂。

基于动态规划的最大概率法的核心思想是：对于任意一个语句，首先按语句中词组的出现顺序列出所有在语料库中出现过的词组；将上述词组集中的每一个词作为一个顶点，加上开始与结束顶点，按构成语句的顺序组织成有向图；再为有向图中每两个直接相连的顶点间的路径赋上权值，如A→B，则AB间的路径权值为B的费用（若B为结束顶点，则权值为0）；此时原问题就转化成了单源最短路径问题，通过动态规划解出最优解即可。

如句子“今天下雨”，按顺序在语料库中存在的词组及其费用如下：

今，a

今天，b

天，c

天下，d

下，e

下雨，f

雨，g

则可以生成如下的加权有向图：

基于Tire树和最大概率法的中文分词功能的Java实现第2张

显而易见，从“Start”到“End”的单源路径最优解就是“今天下雨”这个句子的分词结果。

那么，作为权值的费用如何计算呢？对于最大概率法来说，要求的是词组集在语料库中出现的概率之乘积最大。对应单源最短路径问题的费用来说，

费用 = log( 总词频 / 某一词组词频 )

通过上述公式就可以把“最大”问题化为“最小”问题，“乘积”问题化为“求和”问题进行求解了。

如下的代码是基于动态规划的最大概率法的Java实现：

package chn.seg;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class ChnSeq {
	private TireNode tire = null;

	public void init() throws IOException, ClassNotFoundException {		
		File file = new File("data" + File.separator + "dict.txt");
		if (!file.isFile()) {
			System.err.println("语料库不存在！终止程序！");
			System.exit(0);
		}
		
		BufferedReader in = new BufferedReader(
				new InputStreamReader(new FileInputStream(file), "utf-8"));
		String line = in.readLine();
		int totalFreq = Integer.parseInt(line);
		
		tire = new TireNode();
		
		while ((line = in.readLine()) != null) {
			String[] segs = line.split(" ");
			String word = segs[0];
			int freq = Integer.parseInt(segs[1]);
			
			TireNode root = tire;
			for (int i = 0; i < word.length(); i++) {
				String c = "" + word.charAt(i);
				TireNode node = root.getChild(c);
				if (node == null) {
					node = new TireNode();
					node.setCharacter(c);
					root.addChild(node);
				}
				root = node;
			}
			
			root.setFrequency(freq);
			root.setAntilog(Math.log((double)totalFreq / freq));
		}
		in.close();
	}

	public TireNode getTire() {
		return tire;
	}
	
	public TireNode getNodeByWord(String word) {
		if (tire == null) {
			System.err.println("需要先初始化ChnSeq对象！");
			return null;
		}
		
		TireNode node = tire;
		for (int i = 0; i < word.length(); i++) {
			String ch = word.charAt(i) + "";
			if (node == null) {
				break;
			} else {
				node = node.getChild(ch);
			}
		}
		
		return node;
	}
	
	private class Segment {
		public String word;
		public String endChar;
		public String lastChar;
		public double cost;
		
		public final static String START_SIGN = "<< STARTING >>";
		public final static String END_SIGN = "<< ENDING >>";
	}
	
	private List<Segment> preSegment(String sentence) {
		List<Segment> segs = new ArrayList<Segment>();
		
		Segment terminal = new Segment();
		terminal.word = Segment.START_SIGN;
		terminal.endChar = Segment.START_SIGN;
		terminal.lastChar = null;
		segs.add(terminal);
		for (int i = 0; i < sentence.length(); i++) {
			for (int j = i + 1; j <= sentence.length(); j++) {
				String word = sentence.substring(i, j);
				TireNode tnode = this.getNodeByWord(word);
				if (tnode == null) {
					break;
				}
				if (tnode.getFrequency() <= 0) {
					continue;
				}
				
				Segment seg = new Segment();
				seg.word = word;
				seg.endChar = word.substring(word.length() - 1, word.length());
				if (i == 0) {
					seg.lastChar = Segment.START_SIGN;
				} else {
					seg.lastChar = sentence.substring(i - 1, i);
				}
				seg.cost = tnode.getAntilog();
				segs.add(seg);
			}
		}
		terminal = new Segment();
		terminal.word = Segment.END_SIGN;
		terminal.endChar = Segment.END_SIGN;
		terminal.lastChar = sentence.substring(sentence.length() - 1, sentence.length());
		segs.add(terminal);
		
		return segs;
	}
	
	private String[] dynamicSegment(List<Segment> segs) {
		final double INFINITE = 9999999;
		
		if (segs == null || segs.size() == 0) {
			return null;
		}
			
		int n = segs.size();
		
		double[][] costs = new double[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				costs[i][j] = INFINITE;
			}
		}
		
		for (int i = 0; i < n; i++) {
			String endChar = segs.get(i).endChar;
			for (int j = 0; j < n; j++) {
				String lastChar = segs.get(j).lastChar;
				
				if (lastChar != null && lastChar.equals(endChar)) {
					costs[i][j] = segs.get(j).cost;
				}
			}
		}
		
		int sp = 0; // starting point
		int fp = n - 1; // finishing point
		
		double[] dist = new double[n];
		List<List<Integer>> sPaths = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			dist[i] = costs[sp][i];
			if (sp != i) {
				list.add(i);
			}
			if (dist[i] < INFINITE) {
				List<Integer> spa = new ArrayList<Integer>();
				sPaths.add(spa);
			} else {
				sPaths.add(null);
			}
		}
		
		while (!list.isEmpty()) {
			Integer minIdx = list.get(0);
			for (int i: list) {
				if (dist[i] < dist[minIdx]) {
					minIdx = i;
				}
			}
			
			list.remove(minIdx);
			
			for (int i = 0; i < n; i++) {
				if (dist[i] > dist[minIdx] + costs[minIdx][i]) {
					dist[i] = dist[minIdx] + costs[minIdx][i];
					List<Integer> tmp = new ArrayList<Integer>(sPaths.get(minIdx));
					tmp.add(minIdx);
					sPaths.set(i, tmp);
				}
			}
		}
		
		String[] result = new String[sPaths.get(fp).size()];
		for (int i = 0; i < sPaths.get(fp).size(); i++) {
			result[i] = segs.get(sPaths.get(fp).get(i)).word;
		}
		return result;
	}
	
	public String[] segment(String sentence) {
		return dynamicSegment(preSegment(sentence));
	}
}

3.   测试代码

package chn.seg;

import java.io.IOException;

public class Main {

	public static void main(String[] args) throws ClassNotFoundException, IOException {
		ChnSeq cs = new ChnSeq();
		cs.init();

		String sentence = "生活的决定权也一直都在自己手上";
		
		String[] segs = cs.segment(sentence);
		for (String s: segs) {
			System.out.print(s + "	");
		}
	}

}

标签：#中文分词#概率计算 | 浏览：112 | 发布日期：

免责声明：文章转载自《基于Tire树和最大概率法的中文分词功能的Java实现》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇Eclipse中配置Ehcache提示信息php文档注释提取工具phpdocumentor的使用下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

概率图模型之：贝叶斯网络

1、贝叶斯定理 P(A∣B)=P(A)P(B∣A)P(B) P(A|B)是已知B发生后A的条件概率，也由于得自B的取值而被称作A的后验概率。P(B|A)是已知A发生后B的条件概率，也由于得自A的取值而被称作B的后验概率。P(A)是A的先验概率或边缘概率。之所以称为”先验”是因为它不考虑任何B方面的因素。P(B)是B的先验概率或边缘概率。贝叶斯定理可表述为：...

盘点一下数据平滑算法

本文参考来自于：http://blog.csdn.net/wwjiang_ustc/article/details/50732211 　　在自然语言处理中，经常要计算单词序列（句子）出现的概率估计。我们知道，算法在训练时，语料库不可能包含所有可能出现的序列。  　  因此，为了防止对训练样本中未出现的新序列概率估计值为零，人们发明了好多改善估计新序列出现概...

常用中文分词工具分词&amp;amp;词性标注简单应用（jieba、pyhanlp、pkuseg、foolnltk、thulac、snownlp、nlpir）

1、jieba分词&词性标注 import jieba import jieba.posseg as posseg txt1 =''' 文本一： 人民网华盛顿3月28日电（记者郑琪）据美国约翰斯·霍普金斯大学疫情实时监测系统显示，截至美东时间3月28日下午6时， 美国已经至少有新冠病毒感染病例121117例，其中包括死亡病例2010例。 与大约24...

机器学习模型评估方法（一）

机器学习中，将数据集划分为训练集、验证集、测试集。训练集构建模型，然后用模型计算测试数据集的测试误差，最后以测试集的测试误差近似为模型的泛化能力，根据泛化能力来评估模型的优劣。 本文首先引入数据集概率分布的概念，然后介绍模型评估方法。 1. 数据集的概率分布 总体样本服从某一分布P(X)，数据集D是从总体样本中独立随机抽样m次获取的，数据集D = {(x1...

零基础入门深度学习(5)

无论即将到来的是大数据时代还是人工智能时代，亦或是传统行业使用人工智能在云上处理大数据的时代，作为一个有理想有追求的程序员，不懂深度学习（Deep Learning）这个超热的技术，会不会感觉马上就out了？现在救命稻草来了，《零基础入门深度学习》系列文章旨在讲帮助爱编程的你从零基础达到入门级水平。零基础意味着你不需要太多的数学知识，只要会写程序就行了，...

中文分词组件：thulac及jieba试用手记

一、THULAC THULAC由《清华大学自然语言处理与社会人文计算实验室》研制推出的一套中文词法分析工具包。官网地址：http://thulac.thunlp.org，该项目提供了多种语言，本文以java版为例，先下载以下二个组件：1、THULAC_lite_v1_2分词java版可执行的jar包：THULAC_lite_java_v1_2_run.ja...

最新文章

随机推荐

思享工具箱导航