因为公司使用基于词典的机械中文分词方法，需要一个完备的词典才能有好的效果。而关键词提取的效果又依赖于中文分词效果的好坏。所以开始的初衷是找出一些原始词典里没有的词，来改善中文分词的效果。后面做着做着，似乎词语提取的办法也可以用来做中文分词，只不过评价指标上当然要差很多。
1.尝试过的方法
- 基于词共现的词语挖掘方法。 参考论文:傅赛香, 袁鼎荣, 黄柏雄, et al. 基于统计的无词典分词方法[J]. 广西科学院学报, 2002, 18(4):252-255.
这种方法采用n-gram 滑动取词并且统计频率,然后通过置信度等手段进行过滤筛选，从而得到我们需要的词。但是有的高频词片并非是一个词，如 “这一”、“然不”等。通过去除停用词再滑动统计的规则手段虽然得出的词这些明显看上去不是词的没怎么出现了，但是也会导致一些原来是词的被忽略，如 停用词 “的”可能存在 “的士”这样的词。而且这种改进规则的分词做法带来的准确率提升不明显，这种做法收益达不到预期。
2.基于左右邻字信息熵和互信息的方法。 互联网时代的社会语言学：基于SNS的文本数据挖掘
这种做法根据上面的博客介绍似乎是比较可行的办法，而且也不用做停用词处理。有不少论文和博客都指向这种做法，特别是比较有影响力的开源项目 HanLP也用这种方法来做词语提取并且开源，可见这种做法有较好的效果，通过人民日报的标准分词数据评测得出达到80% 的准确率，实际使用的时候再通过一些优化可以达到更好的实用化效果。
2. 基础的技术和算法
基于左右邻字信息熵和互信息的抽词方法主要基于的一些技术点和算法有：
信息论: 信息熵、互信息
nGram 滑动窗口取词 、词频统计
双数组字典树
常用的字符串处理方法 包括正则表达式
阻塞队列 大数据存储 多线程或者多进程分治法
3.抽词实战步骤
本次抽词从单词内部凝聚度和外部自由度角度进行候选字串的筛选，计算候选词串的互信息(指示了候选字串的内部凝聚度)，计算候选字串的左右邻信息熵(指示了候选字串的外部自由度)，通过互信息及 信息熵阈值过滤掉明显不符合要求的候选词串。在剩下的候选词串中通过归一化的手段得到他们的分数，最后通过分数从大到小排序，得出最终的抽词结果。
具体的抽词步骤：
1.对待抽词文本进行预处理(待处理文本越大效果越好，因为本文采用的是基于统计的方法)，去掉非中文字符，留下候选字片段。
比如原句子：“大众汽车CEO文德森12日宣布，未来五年大众汽车将向北美市场投资70亿美元
，力争使包括奥迪在内的品牌到2018年实现年产量100万辆的目标。”，处理完后
“大众汽车”，
“文德森”，
“日宣布”，
“未来五年大众汽车将向北美市场投资”，
“亿美元”，
“力争使包括奥迪在内的品牌到”，
“年实现年产量”，
“万辆的目标”。
得到如上所示的八个候选短句。
2.对候选短句以nGram 方式进行FMM滑动取词，并统计候选词的词频
// 切分词 FMM 算法
public static void FMMSegment(String text, boolean countWordFrequency) {
// 额外统计单个字的词频
wordCountSingleWord(text);
if (text.length() == 1) {
return;
}
int temp_max_len = Math.min(text.length() + 1, MAX_WORD_LEN);
int p = 0;
while (p < text.length()) {
int q = 1;
while (q < temp_max_len) { // 控制取词的长度
if (q == 1) {
q++;
continue; // 长度为1略过,单个汉字不具有分词意义
}
// 取词串 p --> p+q
if (p + q > text.length()) {
break;
}
String strChar = text.substring(p, p + q);
// 统计词串的词频
if (countWordFrequency) {
if (wcMap.containsKey(strChar)) {
wcMap.put(strChar, wcMap.get(strChar) + 1);
} else {
wcMap.put(strChar, 1);
}
}
q++;
}
p++;
}
}
如候选短句：未来五年大众汽车将向北美市场投资
通过FMM 算法取词。设最大取词长度为5，得到以下54个候选词
[未来, 未来五, 未来五年, 未来五年大, 来五, 来五年, 来五年大, 来五年大众, 五年, 五年大, 五年大众, 五年大众汽, 年大, 年大众, 年大众汽, 年大众汽车, 大众, 大众汽, 大众汽车, 大众汽车将, 众汽, 众汽车, 众汽车将, 众汽车将向, 汽车, 汽车将, 汽车将向, 汽车将向北, 车将, 车将向, 车将向北, 车将向北美, 将向, 将向北, 将向北美, 将向北美市, 向北, 向北美, 向北美市, 向北美市场, 北美, 北美市, 北美市场, 北美市场投, 美市, 美市场, 美市场投, 美市场投资, 市场, 市场投, 市场投资, 场投, 场投资, 投资]
3. 统计计算每个候选词串的互信息，左邻字信息熵，右邻字信息熵
计算信息熵主要用到的数据结构就是双数组字典树，通过字典树取到以当前字为前缀的一批词。为使得信息熵具有可对比性，当前候选词扩展一个字的算信息熵累计和，超过一个字的不算。算左邻字信息熵时，将候选字符串逆置是一个小小技巧。
/**
* 添加所有切分词 计算互信息 信息熵等统计量
*/
public void addAllSegAndCompute(Map<String, Integer> wcMap) {
TreeMap<String, Integer> rightTreeMap = new TreeMap();
TreeMap<String, Integer> leftTreeMap = new TreeMap();
for (Map.Entry<String, Integer> entry : wcMap.entrySet()) {
rightTreeMap.put(entry.getKey(), entry.getValue()); // 右前缀字典树
leftTreeMap.put(HanUtils.reverseString(entry.getKey()), entry.getValue()); // 左前缀字典树
totalCount = totalCount + entry.getValue(); // 计算总词频
}
trieLeft.build(leftTreeMap);
trieRight.build(rightTreeMap);
for (String seg : wcMap.keySet()) {
// 1. 计算信息熵
float rightEntropy = computeRightEntropy(seg);
maxRE = Math.max(maxRE, rightEntropy); // 求最大右信息熵 //totalRE = totalRE + rightEntropy;
float leftEntropy = computeLeftEntropy(seg);
maxLE = Math.max(maxLE, leftEntropy); // 求最大左信息熵 // totalLE = totalLE + leftEntropy;
// 2. 计算互信息
float mi = computeMutualInformation(seg);
maxMI = Math.max(maxMI, mi); // 计算最大互信息 //totalMI = totalMI + mi;
Term term = new Term(seg, wcMap.get(seg), mi, leftEntropy, rightEntropy); // 这里没办法算最后得分
// 将map存入redis中
/********************** redis存取 **************************/
redis.hmset(seg, term.convertToMap());
/********************** redis存取 **************************/
}
wcMap.clear(); // 释放无用的内存
Term max_term = new Term(MAX_KEY, 0, maxMI, maxLE, maxRE);
redis.hmset(MAX_KEY, max_term.convertToMap()); // 保存最大值
System.out.println("统计量计算总耗时: " + (System.currentTimeMillis() - t1) + "ms");
}
信息熵计算：
/**
* 计算左邻熵
*/
public float computeLeftEntropy(String prefix) {
Set<Map.Entry<String, Integer>> entrySet = trieLeft.prefixSearch(HanUtils.reverseString(prefix));
return computeEntropy(entrySet, prefix);
}
/**
* 计算右邻熵
*/
public float computeRightEntropy(String prefix) {
Set<Map.Entry<String, Integer>> entrySet = trieRight.prefixSearch(prefix);
return computeEntropy(entrySet, prefix);
}
/**
* 信息熵计算
*/
private float computeEntropy(Set<Map.Entry<String, Integer>> entrySet, String prefix) {
float totalFrequency = 0;
for (Map.Entry<String, Integer> entry : entrySet) {
if (entry.getKey().length() != prefix.length() + 1) {
continue;
}
totalFrequency += entry.getValue();
}
float le = 0;
for (Map.Entry<String, Integer> entry : entrySet) {
if (entry.getKey().length() != prefix.length() + 1) {
continue;
}
float p = entry.getValue() / totalFrequency;
le += -p * Math.log(p);
}
return le;
}
4. 将候选词串以同一位置词开头划分为若干组。每组进行第一轮筛选，具体的办法为每个词进行归一化打分并逆序排序，最终召回得分最高的。在筛选的过程中进行互信息和信息熵阈值的过滤，所以第一轮筛选也可能没有候选词召回。
如候选短句：未来五年大众汽车将向北美市场投资
分为如下若干组：
[[未来, 未来五, 未来五年, 未来五年大],
[来五, 来五年, 来五年大, 来五年大众],
[五年, 五年大, 五年大众, 五年大众汽],
[年大, 年大众, 年大众汽, 年大众汽车],
[大众, 大众汽, 大众汽车, 大众汽车将],
[众汽, 众汽车, 众汽车将, 众汽车将向],
[汽车, 汽车将, 汽车将向, 汽车将向北],
[车将, 车将向, 车将向北, 车将向北美],
[将向, 将向北, 将向北美, 将向北美市],
[向北, 向北美, 向北美市, 向北美市场],
[北美, 北美市, 北美市场, 北美市场投],
[美市, 美市场, 美市场投, 美市场投资],
[市场, 市场投, 市场投资],
[场投, 场投资],
[投资]]
5. 对第一轮筛选召回的结果进行第二轮筛选，具体办法与第一轮类似，通过对候选词逆序排序，并过滤掉候选词之间有位置重叠关系的，最终得到抽词结果。
6. 如果在此基础上需要做分词，将原句以抽词结果间隔开，我们认为剩下的也很大可能是词。分词效果在开源人民日报数据上评测其分词准确率得到了还算不错的效果。不过更好的做法是把这个只用来做新词发现，然后补充用户词典，辅助词典分词。
抽取人民日报词语部分结果
抽取人民日报词语部分结果
人民日报数据上抽词的效果
人民日报数据上抽词的效果
4. 大数据量的存储和计算问题
大数据量的存储和计算问题，目前已经有成熟的大数据存储与计算开源方案来解决这类问题。但是有的实际情况下没有条件整那么多分布式集群机器，那可不可以在单机的情况下也解决一部分这样的问题，或者是缓解一些存储和计算的压力呢？答案是肯定的，一般单机的计算，在数据量和计算能力过剩的情况下，一般数据直接存内存，计算上也不要过多考虑。但是当内存空间存在瓶颈，这个时候就考虑采用外部存储的方式，但是又可以权衡io的时间消耗问题。为解决这部分问题，我采用了redis作为这样的外部存储系统，将计算的中间结果存在了redis中，利用了redis取数据常数时间复杂度的特性。存储的问题解决了，计算的问题一般是通过分治法的思想去做，一般我能够想到也可以有两种，一种是多进程，通过多个进程去分发任务，最后汇总计算结果。另一种是在一个进程里通过多线程的方式去加速计算，多线程的情况下并非越多线程越好，线程之间的切换带来了cpu的开销，但是在线程数量合理的情况下也是有一定的效果的。
Java语言多线程并发计算可以采用 线程池ThreadPoolExecutor+阻塞队列+栅栏CountDownLatch+原子类AtomicInteger这样的方案来做。基本的思路是把阻塞队列当成消息队列来用，把全量的数据生产进阻塞队列，通过多线程去队列里消费领取自己的计算任务，通过栅栏进行线程之间的协调和通信，等到所有线程执行完毕，然后汇总计算结果。
网友评论