一序
本文属于NLP学习笔记系列。
上一篇整理了前向最大匹配算法与所有组合算法缺点（时间复杂度太高了）。
二 维特比算法
log(x*y*z)= log(x)+log(y)+log(z)
概率上为了避免小数练乘出现的超范围溢出，改用log，改用-log,使得原来求概率最大的小数为-log结果最小。
画一条线，把各种结果对应路径标注上（定义f8 :从节点1到8 的最短路径的值），这里求总结果最小，演变成求最短路径。
如果不使用哪个DP算法，那么就是递归的过程：举例：f(8)=f(5)+3, f(8)=f(6)+1.6,f(8)= f(7)+20 . 要求f(8)需要知道前面的节点的数据。
所以，维护一个数组，从f(1)开始导f(8),分别求出每个节点的值，也就知道f(8)的最小值（记录下所选最小值节点），也知道了你选择的路径是哪条。
结果：经常、有意见、分歧。
词典的概率数据怎么有的，老师没有讲，先理解为统计出来的吧。
这个内容老师讲的很仔细，一步步讲解推导过程，有的文章：比如达观这篇（只说结果，推导过程需要自己理解）
https://www.jiqizhixin.com/articles/2019-09-29-5
对于到最终节点E的路径Route(E)，有：
这节课老师只是简单介绍下维特比算法。后面的HMM 会继续介绍。比这里复杂多了。
分词总结
知识点总结:
- 基于匹配规则：前向最大匹配算法
- 基于概率统计方法： （我们学习了语言模型LM，还有HMM，CRF）
- 分词可以认为已经解决的问题。
需要掌握：
前向最大匹配算法+ Unigram LM 方法。
下面是从jieba分词 改了下代码，作为demo。
import com.hankcs.hanlp.collection.AhoCorasick.AhoCorasickDoubleArrayTrie;import java.util.*;/*** bohu83* jieba分词*/
public class TestSpilit {static private AhoCorasickDoubleArrayTrie<Integer> acTrie;static TreeMap<String, Integer> freqMap = new TreeMap<>();static TreeMap<String, Integer> acTrieMap = new TreeMap<>();static private List<String> words = new ArrayList<>();static private List<Integer> wordFreqs = new ArrayList<>();static private Map<Pair<Integer, Integer>, Integer> subStringFreq = new HashMap<>();static {freqMap.put("经常", 10);freqMap.put("经",5);freqMap.put("常",1);freqMap.put("有",10);freqMap.put("有意见",10);freqMap.put("歧",1);freqMap.put("意见",20);freqMap.put("分歧",20);freqMap.put("见",5);freqMap.put("意",5);freqMap.put("见分歧",5);freqMap.put("分",10);freqMap.forEach((w, f) -> {acTrieMap.put(w, words.size());words.add(w);wordFreqs.add(f);});acTrie = new AhoCorasickDoubleArrayTrie<>();acTrie.build(acTrieMap);}/*** 基于trie查询前缀，生成DAG* @param sentence* @return*/static HashMap<Integer, List<Integer>> makeDAG(String sentence) {int len = sentence.length();HashMap<Integer, List<Integer>> dag = new HashMap<>();acTrie.parseText(sentence).forEach(hit -> dag.computeIfAbsent(hit.begin, k -> new ArrayList<>()).add(hit.end - hit.begin));for (int k = 0; k < len; k++) {if (!dag.containsKey(k)) {List<Integer> lis = new ArrayList<>();lis.add(1);dag.put(k, lis);}}return dag;}/*** 采用动态规划查找最大概率路径, 找出基于词频的最大切分组合*/private static Map<Integer, Pair<Integer, Double>> calcMaxProbPath(String sentence, Map<Integer, List<Integer>> dag) {int len = sentence.length();Map<Integer, Pair<Integer, Double>> route = new HashMap<>();route.put(len, Pair.of(0, 0d));double logTotal = 100;for (int k = len - 1; k >= 0; k--) {int offset = 0;double maxProb = -Double.MAX_VALUE;for (Integer x : dag.get(k)) {int end = k + x;//查位置int idx = acTrie.exactMatchSearch((sentence.substring(k, end)));//查词频int freq = idx < 0 ? 0: wordFreqs.get(idx);subStringFreq.put(Pair.of(k, end), freq);double prob = Math.log(freq > 0 ? freq : 1) - logTotal + route.get(end).getValue();if (maxProb < prob) {maxProb = prob;offset = end - 1;}}route.put(k, Pair.of(offset, maxProb));}return route;}public static void main(String[] args){List<String> result = new ArrayList<>();String sentence ="我们经常有意见分歧";HashMap<Integer, List<Integer>> dag = TestSpilit.makeDAG(sentence);System.out.println(dag);Map<Integer, Pair<Integer, Double>> route = TestSpilit.calcMaxProbPath(sentence,dag);int st = 0;int ed;StringBuilder sb = new StringBuilder();while (st < sentence.length()) {ed = route.get(st).getKey() + 1;if (ed - st == 1 && Character.isLetterOrDigit(sentence.charAt(st))) {sb.append(sentence.charAt(st));} else {if (sb.length() > 0) {result.add(sb.toString());sb.setLength(0);}result.add(sentence.substring(st, ed));}st = ed;}if (sb.length() > 0) {result.add(sb.toString());}System.out.println(result);}
}
输出：
{0=[1], 1=[1], 2=[1, 2], 3=[1], 4=[1, 3], 5=[1, 2], 6=[1, 3], 7=[1, 2], 8=[1]}
[我们, 经常, 有意见, 分歧]
这里有些词典数据初始化是写死的，没有真正的加载txt文件。但是关键的步骤我都摘取出来。
1 创建DAG：生成句子中汉字所有可能成词情况所构成的有向无环图
jieba是基于 trie 树结构实现高效词图扫描
2 采用动态规划算法计算最佳切词组合
这个可以结合上面的手推图来理解。
