@evilking
2018-05-01T00:36:15.000000Z
字数 12840
阅读 2903
NLP
本篇我们以 java 版本的结巴分词工具为例,详细分析该工具的分词细节;最后同样演示下 R 版本的jiebaR分词工具的用法和词云的绘制.
在文本挖掘,情感分析,上下文语义分析等应用场合需要对纯文本进行分析,主要是对语句进行分析;像英文这种语句本身词与词之间有空格隔开,这种语句就容易分割,但是像中文或日文这种词与词之间没有分割界限的语言,在分割单词上就存在很大的困难;
像中文单词分割的时候如果分割的不准确,就很容易得出歧义的语句,甚至是意思完全相反的,比如”不同意”分割成”不”/”同意”。
基于字符匹配的方式
这种方式虽然准确,但是覆盖不全,需要大量的规则,对于新词就无能为力了.
基于统计分析的方式
这种方式目前来说比较普遍,大部分是与字符匹配的方式相结合,字符匹配用来做精确匹配,而统计方法用来做新词发现.
基于机器学习的方式
这种方式目前刚发展,就目前来说也是取得了很不错的效果.
这类分词方法主要是词典匹配,用于切分出已登录词,如果只使用词典的话,就对未登录词无能为力了;后来人们就在此基础上加入统计方法,比如 HMM 模型,用来识别出未登录词;最后用动态规划求分词序列的最大概率,即最有可能的分词组合。
本篇要讲的结巴分词就属于这类。
例如,”小明硕士毕业于中国科学院计算所”,最正确的分词应该分成”小明 / 硕士 / 毕业 / 于 / 中国 / 科学院 / 计算所”,这是人工分词的结果,但是对于计算机来说,可能会把”计算所”分成”计算 / 所”。
为了使用字符标注的方式来分词,我们定义了四种标签:
于是上面的例句最正确的标注应该为 BEBEBESBEBMEBME,有了这样的字符标注序列,我们就能够将语句分开,分割的结果为”BE / BE / BE / S / BE / BME / BME”,所以我们的问题就变成了 已知观测语句、字符标注标签,要求用字符标注标签对观测语句标注后的序列。如果了解隐马尔科夫过程的话,就能知道这是一个典型的HMM模型解码的问题。
基于字符标注的统计分析分词方法,像 HMM 模型、CRF 模型 等都是属于这类。
HMM 模型在《HMM 模型》这篇中详细讲了;CRF 模型分词其本质上是将分词问题转换为标注问题,其训练和标注都在 《CRF 条件随机场》一篇中详细讲了。读者可以参考学习。
机器学习做分词,原理与统计分析方法类似,都是将分词问题转换成分类问题,比如把“小明是中国共产党的接班人”这句的每个汉字进行分类,分为“B”、“M”、“E”、“S”这四类,然后根据分类的结果序列进行切分。
github下载地址: https://github.com/huaban/jieba-analysis
下载好后导入 eclipse,则maven工程目录结构如下图所示:
编写测试用例类 SegmenterTest,对句子进行分词,测试代码如下:
@Test
public void test() {
//初始化jieba分词工具类
JiebaSegmenter jieba = new JiebaSegmenter();
String content = "这里讲解的是java版本的结巴分词工具";
/**
* 对句子进行分词,
* 源码中有个方法是对整篇文章进行分词,其原理是先对文章进行分句,然后对每一句进行分词,
* 所以这里我们只考虑对一句话进行分词的过程
*/
List<String> words = jieba.sentenceProcess(content);
for(String word: words){
System.out.print(word + " ");
}
}
运行后输出结果为:
main dict load finished, time elapsed 1557 ms
model load finished, time elapsed 47 ms.
这里 讲解 的 是 java 版本 的 结巴 分词 工具
可以看出分词效果还是不错的,下面我们以这句话的分词来分析结巴分词的分词过程.
从时序图中可知,在初始化 JiebaSegment类时,会去先初始化词典表,即WordDictionary类;然后开始分句,分句又分为三步,如下:
构建 DAG图
通过动态规划求解最可能的分词结果
利用上一步求的的分词结果,对比词典,再利用viterbi算法做新词发现
在JiebaSegmenter类的初始化过程中,会初始化两个词典表,WordDictionary和FinalSeg:
private static WordDictionary wordDict = WordDictionary.getInstance();
private static FinalSeg finalSeg = FinalSeg.getInstance();
首先看看WordDictionary的初始化,这里使用了双重检查锁定的单例模式(保证在多线程环境下也只会初始化一次),在构造方法中执行 loadDict()
方法去加载词典:
_dict = new DictSegment((char) 0);
InputStream is = this.getClass().getResourceAsStream(MAIN_DICT);
......
BufferedReader br = new BufferedReader(new InputStreamReader(is, Charset.forName("UTF-8")));
long s = System.currentTimeMillis();
while (br.ready()) {
//读取词典文件中的一行
String line = br.readLine();
String[] tokens = line.split("[\t ]+");
//跳过空行
if (tokens.length < 2)
continue;
String word = tokens[0];
//计算词数
double freq = Double.valueOf(tokens[1]);
total += freq;
word = addWord(word);
freqs.put(word, freq);
}
// normalize
for (Entry<String, Double> entry : freqs.entrySet()) {
//将单词的词数转换为词频
entry.setValue((Math.log(entry.getValue() / total)));
minFreq = Math.min(entry.getValue(), minFreq);
}
......
其中 addWord(String word)
方法如下:
private String addWord(String word) {
if (null != word && !"".equals(word.trim())) {
//将单词转行小写
String key = word.trim().toLowerCase(Locale.getDefault());
//将单词添加到词典
_dict.fillSegment(key.toCharArray());
return key;
}
else
return null;
}
上面loadDict()
方法是加载工具基础词典,如果是用户自定义词典,需要使用loadUserDict()
方法,与上面的加载方法不同的是,如果用户没有设置单词的统计词数,则默认设置为 3 :
String line = br.readLine();
String[] tokens = line.split("[\t ]+");
if (tokens.length < 1) {
// Ignore empty line
continue;
}
String word = tokens[0];
//默认词数为 3
double freq = 3.0d;
if (tokens.length == 2)
freq = Double.valueOf(tokens[1]);
word = addWord(word);
freqs.put(word, Math.log(freq / total));
从代码可以看出,加载词典,无非就是读取词典表,用分隔符截取每一行,获得对应的单词,以及单词的统计词数,如果没有设置统计词数,默认为 3;同时在单词添加到_dict
词典数据结构中时,都统一转换成了小写.
然后看 FinalSeg 类的初始化,该类初始化也是使用了双重检查锁定来处理多线程环境下的单例,初始化时会调用loadModel()
方法来加载 HMM模型,即HMM模型的五个组成元素 :
private static char[] states = new char[] { 'B', 'M', 'E', 'S' };
由于是中文分词,所以隐状态定义为 B,M,E,S
;
prevStatus = new HashMap<Character, char[]>();
prevStatus.put('B', new char[] { 'E', 'S' });
prevStatus.put('M', new char[] { 'M', 'B' });
prevStatus.put('S', new char[] { 'S', 'E' });
prevStatus.put('E', new char[] { 'B', 'M' });
trans = new HashMap<Character, Map<Character, Double>>();
Map<Character, Double> transB = new HashMap<Character, Double>();
transB.put('E', -0.510825623765990);
transB.put('M', -0.916290731874155);
trans.put('B', transB);
Map<Character, Double> transE = new HashMap<Character, Double>();
transE.put('B', -0.5897149736854513);
transE.put('S', -0.8085250474669937);
trans.put('E', transE);
Map<Character, Double> transM = new HashMap<Character, Double>();
transM.put('E', -0.33344856811948514);
transM.put('M', -1.2603623820268226);
trans.put('M', transM);
Map<Character, Double> transS = new HashMap<Character, Double>();
transS.put('B', -0.7211965654669841);
transS.put('S', -0.6658631448798212);
trans.put('S', transS);
然后定义状态转移概率矩阵,这里定义的概率都是经过对数转换的,以方便计算时将乘法操作改为加法操作,下同;
start = new HashMap<Character, Double>();
start.put('B', -0.26268660809250016);
start.put('E', -3.14e+100);
start.put('M', -3.14e+100);
start.put('S', -1.4652633398537678);
这里是定义了初始状态概率;
下面给出结巴分词工具的发射矩阵资源文件格式:
M
耀 -8.47651676173
蘄 -14.3722960587
涉 -10.5600933886
B
耀 -10.4602834131
蘄 -11.0155137948
涉 -8.76640550684
M
耀 -8.47651676173
蘄 -14.3722960587
涉 -10.5600933886
E
耀 -9.2667057128
蘄 -17.3344819086
涉 -9.09647365936
举个例子,隐状态为'M'时对应的汉字为'耀'的概率的对数为 -8.47651676173,即为发射概率,其中表中所有的汉字被定义为观察值
InputStream is = this.getClass().getResourceAsStream(PROB_EMIT);
BufferedReader br = new BufferedReader(new InputStreamReader(is, Charset.forName("UTF-8")));
emit = new HashMap<Character, Map<Character, Double>>();
Map<Character, Double> values = null;
while (br.ready()) {
String line = br.readLine();
String[] tokens = line.split("\t");
if (tokens.length == 1) {
//读取为标号,B M S E
values = new HashMap<Character, Double>();
//设置发射概率矩阵
emit.put(tokens[0].charAt(0), values);
}else {
//添加值
values.put(tokens[0].charAt(0), Double.valueOf(tokens[1]));
}
}
如此,发射概率矩阵就加载完成了,到这里整个 HMM模型的几个要素就都加载完成了,剩下的就是具体分词时的解码问题了.
分词的第一步是构建词的DAG图,例如上面测试用例中的句子,DAG图如下所示:
0 [0, 1] //这
1 [1] //里
2 [2, 3] //讲
3 [3] //解
4 [4] //的
5 [5] //是
6 [6] //j
7 [7] //a
8 [8] //v
9 [9] //a
10 [10, 11] //版
11 [11] //本
12 [12] //的
13 [13, 14] //结
14 [14] //巴
15 [15, 16] //分
16 [16] //词
17 [17, 18] //工
18 [18] //具
具体是如何算的呢,我们分析createDAG()
方法:
private Map<Integer, List<Integer>> createDAG(String sentence) {
Map<Integer, List<Integer>> dag = new HashMap<Integer, List<Integer>>();
//获得词典树
DictSegment trie = wordDict.getTrie();
char[] chars = sentence.toCharArray();
int N = chars.length;
int i = 0, j = 0;
while (i < N) {
//核心的就是下面这几句,不断的增加字扩展词,去词典中查找
//如果是一个词的前缀,则可以继续往后扩展词
//如果匹配到了一个词,则将索引添加到DAG图中
Hit hit = trie.match(chars, i, j - i + 1);
if (hit.isPrefix() || hit.isMatch()) {
if (hit.isMatch()) {
if (!dag.containsKey(i)) {
List<Integer> value = new ArrayList<Integer>();
dag.put(i, value);
value.add(j);
}
else
dag.get(i).add(j);
}
j += 1;
if (j >= N) {
i += 1;
j = i;
}
}
else {
i += 1;
j = i;
}
}
//最后将没有与其他字构成词的字加上
for (i = 0; i < N; ++i) {
if (!dag.containsKey(i)) {
List<Integer> value = new ArrayList<Integer>();
value.add(i);
dag.put(i, value);
}
}
return dag;
}
举例说明,假设当前词为'版',去词典里查,发现'版'字是某个单词的前缀词;则往后添加下个字,构成词'版本',然后去词典里查,发现能匹配上'版本',于是就将'本'字的索引添加到'版'所对应的索引列表中;然后继续往后添加一个字,构成'版本的',这时查询词典,发现该词既不是前缀词,也无法匹配到单词,则最开始的索引往后移一位,当前词就变成了'本',然后从'本'开始继续往下搜索,直到结束.
构建完DAG图后,我们要分词,就要判断具体如何划分才最好,这里我们使用了动态规划,使整句划分的概率最大.
private Map<Integer, Pair<Integer>> calc(String sentence, Map<Integer, List<Integer>> dag) {
int N = sentence.length();
HashMap<Integer, Pair<Integer>> route = new HashMap<Integer, Pair<Integer>>();
//动态规划从后往前,初始化最后一步的概率
route.put(N, new Pair<Integer>(0, 0.0));
for (int i = N - 1; i > -1; i--) {
Pair<Integer> candidate = null;
for (Integer x : dag.get(i)) {
//从后往前组合,获得词的频率
double freq = wordDict.getFreq(sentence.substring(i, x + 1)) + route.get(x + 1).freq;
if (null == candidate) {
candidate = new Pair<Integer>(x, freq);
}else if (candidate.freq < freq) {
//取累计频率最大的划分
candidate.freq = freq;
candidate.key = x;
}
}
route.put(i, candidate);
}
return route;
}
动态规划是从最后一个字符开始往前逐个累加,取局部累计词频最大的分词结果,最终取使整句分词结果的累计词频达到最大.
经过上一步动态规划求最可能的分词结果,有了一个粗略的分词,需要在此基础上进一步的去准确分词,包括新词发现 :
while (x < N) {
y = route.get(x).key + 1;
String lWord = sentence.substring(x, y);
if (y - x == 1)
sb.append(lWord);
else {
if (sb.length() > 0) {
buf = sb.toString();
sb = new StringBuilder();
//一个字的可以直接添加
if (buf.length() == 1) {
tokens.add(buf);
}else {
//多个字的先去词典中查询
//如果是已登录词就直接添加
if (wordDict.containsWord(buf)) {
tokens.add(buf);
} else {
//未登录词就用Viterbi算法解码
finalSeg.cut(buf, tokens);
}
}
}
tokens.add(lWord);
}
x = y;
}
下面就是HMM模型中 Viterbi算法解码过程 :
public void viterbi(String sentence, List<String> tokens) {
Vector<Map<Character, Double>> v = new Vector<Map<Character, Double>>();
Map<Character, Node> path = new HashMap<Character, Node>();
//处理第一个隐状态
v.add(new HashMap<Character, Double>());
for (char state : states) {
Double emP = emit.get(state).get(sentence.charAt(0));
if (null == emP)
emP = MIN_FLOAT;
v.get(0).put(state, start.get(state) + emP);
path.put(state, new Node(state, null));
}
for (int i = 1; i < sentence.length(); ++i) {
Map<Character, Double> vv = new HashMap<Character, Double>();
v.add(vv);
Map<Character, Node> newPath = new HashMap<Character, Node>();
for (char y : states) {
Double emp = emit.get(y).get(sentence.charAt(i));
if (emp == null)
emp = MIN_FLOAT;
Pair<Character> candidate = null;
for (char y0 : prevStatus.get(y)) {
//从状态y0 转移到状态 y
Double tranp = trans.get(y0).get(y);
if (null == tranp)
tranp = MIN_FLOAT;
//y0状态的前向变量 + y0转移到y状态的转移概率 + y状态下是字i的发射概率
tranp += (emp + v.get(i - 1).get(y0));
if (null == candidate)
candidate = new Pair<Character>(y0, tranp);
else if (candidate.freq <= tranp) {
candidate.freq = tranp;
candidate.key = y0;
}
}
vv.put(y, candidate.freq);
newPath.put(y, new Node(y, path.get(candidate.key)));
}
path = newPath;
}
//因为'B'、'M'不可能构成最后一个字,所以只需要比较'E'、'S'就行
double probE = v.get(sentence.length() - 1).get('E');
double probS = v.get(sentence.length() - 1).get('S');
Vector<Character> posList = new Vector<Character>(sentence.length());
Node win;
if (probE < probS)
win = path.get('S');
else
win = path.get('E');
while (win != null) {
posList.add(win.value);
win = win.parent;
}
Collections.reverse(posList);
//路径回溯,得到最优的隐状态序列
int begin = 0, next = 0;
for (int i = 0; i < sentence.length(); ++i) {
char pos = posList.get(i);
if (pos == 'B')
begin = i;
else if (pos == 'E') {
tokens.add(sentence.substring(begin, i + 1));
next = i + 1;
}else if (pos == 'S') {
tokens.add(sentence.substring(i, i + 1));
next = i + 1;
}
}
if (next < sentence.length())
tokens.add(sentence.substring(next));
}
以上就是 HMM模型中 Viterbi解码过程,具体原理可参考上篇 《基于HMM的中文分词》.
到这里,java版本的结巴分词工具对每一句的分词过程就清楚了;这个工具结合词典和概率,并使用HMM模型做新词发现,总体分词结果来看,效果还可以.
由于笔者没有找到 R版本的结巴分词工具包"jiebaR"的源码,所以上面使用java版本的源码来分析处理流程,下面我们使用"jiebaR"包来做简单的分词,以及用"wordcloud"包做词云分析,以演示 R 版本的结巴分词工具的使用.
作为演示用的文本如下所示,保存在data.txt文件中,并放在Rstudio的工作目录下,工作目录可通过getwd()
命令获得:
笔者在实际项目中使用的是 java 版本的结巴分词,它是词典+HMM模型的分词工具,源码中对 HMM的Viterbi算法演示的很清楚,不过这里为了与整体风格相统一,我们使用 R语言的相关HMM包来演示;
后面我们单独用一个篇幅去讲解结巴分词,因为结巴分词工具总体上来说算是一个效果不错,而且原理简单的工具.
下面我们先导入必要的两个包,并读取文本:
install.packages("jiebaR")
library(jiebaR)
install.packages("wordcloud")
library(wordcloud)
f <- scan("data.txt",sep = "\n",what = '',encoding = "UTF-8")
head(f)
输出信息为:
> f <- scan("data.txt",sep = "\n",what = '',encoding = "UTF-8")
Read 2 items
> head(f)
[1] "笔者在实际项目中使用的是 java 版本的结巴分词,它是词典+HMM模型的分词工具,源码中对 HMM的Viterbi算法演示的很清楚,不过这里为了与整体风格相统一,我们使用 R语言的相关HMM包来演示;\n"
[2] "后面我们单独用一个篇幅去讲解结巴分词,因为结巴分词工具总体上来说算是一个效果不错,而且原理简单的工具."
>
下面开始使用 jiebaR 去分词:
#使用 qseg函数分词
> seg <- qseg[f]
#去掉单词为一个字的词
> seg <- seg[nchar(seg) > 1]
> head(seg)
[1] "笔者" "实际" "项目" "使用" "java" "版本"
>
#统计词频
> seg <- table(seg)
> seg
seg
HMM java Viterbi 版本 包来 笔者 不错 不过
3 1 1 1 1 1 1 1
词典 单独 而且 分词 风格 工具 后面 简单
1 1 1 4 1 3 1 1
讲解 结巴 来说 模型 篇幅 清楚 实际 使用
1 3 1 1 1 1 1 2
算法 算是 统一 为了 我们 相关 项目 效果
1 1 1 1 2 1 1 1
演示 一个 因为 语言 原理 源码 这里 整体
2 2 1 1 1 1 1 1
总体
1
>
# 对词频进行排序,并取前 30个词
> seg <- sort(seg,decreasing = TRUE)[1:30]
> seg
seg
分词 HMM 工具 结巴 使用 我们 演示 一个
4 3 3 3 2 2 2 2
java Viterbi 版本 包来 笔者 不错 不过 词典
1 1 1 1 1 1 1 1
单独 而且 风格 后面 简单 讲解 来说 模型
1 1 1 1 1 1 1 1
篇幅 清楚 实际 算法 算是 统一
1 1 1 1 1 1
>
文本经过分词,过滤掉一些无效词(停用词等)后,再进行词频统计并排序,取前 k个词(一般就是保留的关键词了);下一步就是利用词云工具绘制词云了,以可视化的方式展现文本特征 :
#生成一张 .bmp图,宽高个 500像素
> bmp("comment_cloud.bmp",width = 500,height = 500)
#绘图,背景设为黑色
> par(bg = "black")
# 生成词云
> wordcloud(names(seg),seg,colors = rainbow(100),random.order = F)
# 关闭绘图设备
> dev.off()
null device
1
>
这样,在工作目录下就会生成一张.bmp图,如下所示:
从图上可以看出,主要词有分词、HMM、结巴、工具,其中分词占的比重最大,其次是 HMM。这个结果与最开始的文本语料对比可以看出,效果还是不错的,主要的关键词都体现出来了.
接下来再玩点深入一点的,jiebaR包可以实现分词(分行分词)、整个文档分词(分文档分词)。library(jiebaR)加载包时,没有启动任何分词引擎,启动引擎很简单,就是一句赋值语句就可以了mixseg=worker()
详细版本请参考官方:https://jiebar.qinwf.com/section-3.html#section-3.0.1
但是实际上worker中有非常多的调节参数。
mixseg = worker(type = "mix",dict = "dict/jieba.dict.utf8",
hmm = "dict/hmm_model.utf8",
user = "dict/user.dict.utf8",
detect = T,symbol = F,
lines = 1e+05,output = NULL)
> mixseg
Worker Type: Jieba Segment
Default Method : mix
Detect Encoding : TRUE
Default Encoding: UTF-8
Keep Symbols : FALSE
Output Path :
Write File : TRUE
By Lines : FALSE
Max Word Length : 20
Max Read Lines : 1e+05
Fixed Model Components:
$dict
[1] "dict/jieba.dict.utf8"
$user
[1] "dict/user.dict.utf8"
$hmm
[1] "dict/hmm_model.utf8"
$stop_word
NULL
$user_weight
[1] "max"
$timestamp
[1] 1506665756
$default $detect $encoding $symbol $output $write $lines $bylines can be reset.
>
说明一下:
type 代表分词模型,有mix(混合模型)、mp(最大概率)、hmm(隐马尔科夫链)、query(索引)、tag(词性标注)、simhash(距离)、keywords(关键词)
hmm 代表隐马尔科夫链所使用的语料库,一般不用更改
user 代表用户自定义词典,一般我们修改的就是这个文件
detect 决定了引擎是否自动判断输入文件的编码,加载后通过cutter$detect = F
也可以设置
symbol 当输入为文档文件时,一次性最大读取行数
lines 当输入为文档文件时,一次性最大读取行数
output 代表分词内容是否变成文件写出
#设置分行输出
> mixseg$bylines = TRUE
> mixseg[c("这是第一行文本。","这是第二行文本.")]
[[1]]
[1] "这是" "第一行" "文本"
[[2]]
[1] "这是" "第二行" "文本"
>
> words = "我爱北京天安门"
# 创建词性标注的 worker
> tagger = worker("tag")
# 对句子words进行分词,并做词性标注
> tagger <= words
r v ns ns
"我" "爱" "北京" "天安门"
>
# 构建一个提取关键词的 worker
> keys = worker("keywords",topn = 4,idf = IDFPATH)
> keys <= "我爱北京天安门"
8.9954 4.6674
"天安门" "北京"
>
这里创建了一个能提取关键词的worker,topn = 4
表示提取 4 个关键词,idf = IDFPATH
表示使用逆文档率;
下一句输出结果中,第一行的数值表示 IDF,第二行表示具体关键词.
#显示词典路径
> show_dictpath()
[1] "D:/evirnment/R-3.3.3/library/jiebaRD/dict"
>
如果读者想设置自己的词典、停用词典,可以通过
show_dictpath()
显示词典路径,然后修改文件内容,并在构建 worker是指定相应文件路径.
以上,就是对结巴分词工具的使用以及分析了,其中关于 HMM模型的原理部分,可以参考《基于HMM的中文分词》一篇.
如果因为这篇文章而让读者对结巴分词有了更深入的理解,那是笔者的荣幸.