先回顧一下上一篇文章的內(nèi)容：我們簡(jiǎn)單介紹了中文分詞的原理，并且實(shí)現(xiàn)了一個(gè)前綴樹(shù)署穗，以及實(shí)現(xiàn)了加載詞典的方法寥裂，還實(shí)現(xiàn)了給定一個(gè)句子輸出里面收錄于詞典中的詞語(yǔ)。
我們最終目標(biāo)是實(shí)現(xiàn)一個(gè)分詞器（并且最好能夠?qū)崿F(xiàn)歧義消除）案疲，現(xiàn)在距離我們的目標(biāo)已經(jīng)很近了封恰。這篇文章會(huì)繼續(xù)完善我們的分詞器，真正實(shí)現(xiàn)基于詞典的分詞褐啡。
接下來(lái)會(huì)實(shí)現(xiàn)的功能：
- 將輸入的待分詞文本構(gòu)建成一個(gè)DAG圖诺舔。
- 使用動(dòng)態(tài)規(guī)劃的思想，基于DAG圖計(jì)算出文本的最佳分詞方式（上一篇文章說(shuō)到過(guò)备畦，最優(yōu)分詞方案就是使得句子出現(xiàn)頻率最高）
在構(gòu)建DAG圖之前低飒，需要這里需要新引入一個(gè)元素：
- 為了能夠?qū)Σ煌衷~情況進(jìn)行對(duì)比，需要給每個(gè)詞語(yǔ)增加一個(gè)權(quán)重屬性
frequency（這樣不同的句子就可以用所有詞語(yǔ)權(quán)重之和來(lái)衡量句子的權(quán)重了懂盐，權(quán)重最高的句子也就出現(xiàn)概率最大）
前綴樹(shù)加載詞典的方法需要改成：
/**
* 加載字符
*/
public void load(Queue<Character> wordQueue, int frequency) {
if (wordQueue.isEmpty())
return;
// 彈出隊(duì)列中第一個(gè)字符
char c = wordQueue.poll();
if (childrenMap == null)
childrenMap = new HashMap<>();
TrieNode node = childrenMap.computeIfAbsent(c, s -> new TrieNode(this, c));
// 如果隊(duì)列非空褥赊，繼續(xù)遞歸加載剩余字符
if (!wordQueue.isEmpty())
node.load(wordQueue, frequency);
else {
// 隊(duì)列為空了，說(shuō)明當(dāng)前節(jié)點(diǎn)是最后一個(gè)字符莉恼，剛好成一個(gè)詞
node.isWord = true;
node.frequency = frequency;
}
}
對(duì)輸入文本構(gòu)建DAG圖
首先是實(shí)現(xiàn)將輸入文本轉(zhuǎn)化成DAG圖
- 了解過(guò)jieba分詞的實(shí)現(xiàn)的同學(xué)都知道拌喉，jieba實(shí)現(xiàn)的動(dòng)態(tài)規(guī)劃是從右往左開(kāi)始迭代求解的。這是因?yàn)樯傻腄AG圖是由詞的首個(gè)字符指向最后一個(gè)字符俐银。比如輸入"抗日戰(zhàn)爭(zhēng)"司光，剛好"抗日戰(zhàn)爭(zhēng)"是一個(gè)詞，（不考慮其他詞）生成的鄰接矩陣就是： {0:[3], 1:[], 2:[], 3:[]}悉患。這個(gè)DAG圖正向迭代（從左到右）是無(wú)法求出最優(yōu)解的，因?yàn)槿绻麖淖箝_(kāi)始遍歷榆俺，決定經(jīng)過(guò)某個(gè)字符的最優(yōu)路徑不是看這個(gè)字符是哪些詞的前綴售躁，而是看他是哪些詞的后綴。反向迭代則反過(guò)來(lái)茴晋，看到是組成前綴的情況陪捷。（可能描述的還不是很清楚， 最好自己實(shí)現(xiàn)一下）
- 為了容易理解诺擅，下面實(shí)現(xiàn)反向DAG市袖，然后正向迭代來(lái)進(jìn)行求解
/**
* 這里需要構(gòu)建反向的DAG，
* 假設(shè)三個(gè)點(diǎn)的圖1,2,3構(gòu)建成DAG之后是：1 -> 2 -> 3
* 原鄰接矩陣應(yīng)該是
* 1 -> 2 -> null
* 2 -> 3 -> null
* 3 -> null
* <p>
* 但此處要構(gòu)建成
* 1 -> null
* 2 -> 1 -> null
* 3 -> 2 -> null
* <p>
* 這樣做是為了后面尋找最近路徑的時(shí)候能夠根據(jù)詞的最后一個(gè)字符迅速定位其對(duì)應(yīng)的首個(gè)字符
*/
public static List<Map<Integer, Integer>> buildDAG(TrieNode head, String str) {
List<Map<Integer, Integer>> dag = new ArrayList<>(str.length());
for (int i = 0; i < str.length(); i++) {
dag.add(i, new HashMap<>());
}
// 詞典為空直接返回空鄰接矩陣
if (head == null || head.childrenMap == null)
return dag;
// 前綴遍歷字符串
for (int i = 0; i < str.length() - 1; i++) {
char c = str.charAt(i);
TrieNode node = head.childrenMap.get(c);
if (node == null)
continue;
TrieNode n = node;
int offset = i;
while (n != null) {
if (n.isWord) {
dag.get(offset).put(i, n.frequency);
}
if (n.childrenMap == null || offset == str.length() - 1)
break;
n = n.childrenMap.get(str.charAt(++offset));
}
}
return dag;
}
基于DAG圖求最優(yōu)分詞方案
構(gòu)建出DAG圖，之后就是使用DAG圖來(lái)尋找最優(yōu)路徑了苍碟，可以通過(guò)動(dòng)態(tài)規(guī)劃法來(lái)求解酒觅。
先來(lái)闡述一下動(dòng)態(tài)規(guī)劃的思路：假設(shè)輸入文本為“天下第一”，現(xiàn)在詞典中有三個(gè)關(guān)聯(lián)的詞語(yǔ)“天下”微峰，“第一”舷丹，“天下第一”，其對(duì)應(yīng)詞頻分別是 1,1,3
首先生成反向DAG圖：
// 位置0 對(duì)應(yīng)天蜓肆，3對(duì)應(yīng)上
0: null
1: 0 -> null
2: null
3: 0 -> 2 -> null
從最左開(kāi)始遍歷：(設(shè)w(i)是第i個(gè)位置上的最優(yōu)路徑權(quán)重颜凯，f(s)是詞s的權(quán)重）
->"天"：因?yàn)?天"是第一個(gè)字符，且詞典中不存在"天"這個(gè)詞仗扬，因此位置0的權(quán)重是0症概，即w(0)=0
->"下"：（根據(jù)鄰接矩陣）此時(shí)有兩條路徑可選：
- "天下"："與"天"組成詞"天下"，此時(shí)路徑權(quán)重=w(0-1)+f("天下")=f("天下")=1 （這里的w(0-1)的0表示"天下"中首個(gè)字符"天"的位置早芭，w(0-1)表示"天"前一個(gè)字符的路徑權(quán)重彼城，由于"天"是第一個(gè)字符，所以這里直接去掉了）
- "天/下"：不與"天"組成詞逼友，此時(shí)路徑權(quán)重=w(1-1)=w(0)=0
明顯第一條路徑權(quán)重更高精肃，即w(1)=max(w(0), w(0-1)+f("天下")) = 1
->"第"：此時(shí)因?yàn)榕c前面的字符不能組成詞語(yǔ)，所以只能與前面字符分開(kāi)一條路徑帜乞，此時(shí)權(quán)重為：w(2)=w(2-1)=1
->"一"：（根據(jù)鄰接矩陣）此時(shí)有三條路徑可選：
- "天下第一"：w = w(0-1)+f("天下第一")=3
- "天下/第一"：w = w(2-1)+f("第一")=1+1=2
- "天下/第/一"：w = w(3-1)=w(2)=1
因此 w(3) = 3司抱，
按照這種方法進(jìn)行迭代求解，最終最后一個(gè)字符的最優(yōu)權(quán)重路徑其實(shí)就是整個(gè)輸入文本的最優(yōu)分詞方案黎烈。
即整詞"天下第一"就是輸入文本"天下第一"的最優(yōu)分詞方案习柠。
下面來(lái)實(shí)現(xiàn)一下相關(guān)求解代碼
/**
* 使用動(dòng)態(tài)規(guī)劃求解
* 狀態(tài)轉(zhuǎn)移方程： w(x) = max(w(x-1), w(k1-1) + f(k1), ..., w(kn-1) + f(kn))
* x是字符位置
* w(x)表示位置x上的最優(yōu)路徑權(quán)重
* k1~kn是以位置x上字符結(jié)尾的不同詞
*/
public static void findOptimalPath(String str, List<Map<Integer, Integer>> list) {
int[] indexArr = new int[str.length()];
int[] weightArr = new int[str.length()];
indexArr[0] = 0;
weightArr[0] = 0;
for (int i = 1; i < str.length(); i++) {
int index = i;
int weight = weightArr[index - 1];
Map<Integer, Integer> m = list.get(i);
for (Integer inx : m.keySet()) {
int w = m.get(inx);
if (inx != 0)
w += weightArr[inx - 1];
if (w > weight) {
weight = w;
index = inx;
}
}
indexArr[i] = index;
weightArr[i] = weight;
}
// 到這一步就已經(jīng)求出結(jié)果了，indexArr[str.length()-1]就是最終結(jié)果
// 剩下的就是往回推導(dǎo)出整個(gè)分詞路徑
// 往回推導(dǎo)并輸出分詞結(jié)果
LinkedList<String> l = new LinkedList<>();
int offset = str.length() - 1;
while (offset >= 0) {
int start = indexArr[offset];
l.addFirst(str.substring(start, offset + 1));
offset = start - 1;
}
// 以/的形式表示分詞
for (String s : l) {
System.out.print(s+"/");
}
System.out.println();
}
-
findOptimalPath方法追加到buildDAG方法末尾就可以構(gòu)建完DAG圖之后直接計(jì)算分詞結(jié)果了照棋。
回到我們的main方法：
TrieNode node = new TrieNode(null, ' ');
node.load(TrieNode.string2Queue("中華"), 10);
node.load(TrieNode.string2Queue("華人"), 8);
node.load(TrieNode.string2Queue("人民"), 15);
node.load(TrieNode.string2Queue("共和國(guó)"), 6);
node.load(TrieNode.string2Queue("中華人民"), 24);
node.load(TrieNode.string2Queue("中華人民共和國(guó)"), 30);
node.load(TrieNode.string2Queue("國(guó)歌"), 8);
node.load(TrieNode.string2Queue("共和"), 5);
TrieNode.buildDAG(node, "中華人民共和國(guó)萬(wàn)歲");
>>分詞結(jié)果：
中華/人民/共和國(guó)/萬(wàn)/歲/
// 如果將"中華人民共和國(guó)"權(quán)重調(diào)整到50资溃，分詞結(jié)果將發(fā)生變化：
>>分詞結(jié)果：
中華人民共和國(guó)/萬(wàn)/歲/
至此，我們已經(jīng)實(shí)現(xiàn)了一個(gè)分詞器粗糙的模型了：
- 加載詞典樹(shù)
- 輸出文本中所有詞語(yǔ)
- 對(duì)輸入文本進(jìn)行分詞烈炭，且進(jìn)行歧義消除（尋找最優(yōu)分詞路徑）
本文僅作學(xué)習(xí)用途溶锭，如有錯(cuò)誤，歡迎指出
參考
<<數(shù)學(xué)之美>>
完整代碼
import java.util.*;
/**
* @Description
* @auther edqi
* @create 2020-05-21 23:33
*/
public class TrieNode {
char value;
Map<Character, TrieNode> childrenMap;
TrieNode parent;
int deep;
boolean isWord = false;
int frequency = 0;
String word;
public TrieNode(TrieNode parent, char value) {
this.parent = parent;
this.value = value;
// 假定根節(jié)點(diǎn)不存儲(chǔ)有意義的值符隙，深度為0
if (parent == null)
deep = 0;
else
deep = parent.deep + 1;
}
@Override
public String toString() {
return "TrieNode{" + nodePath() + "}";
}
String nodePath() {
if (word == null) {
char[] w = new char[deep];
TrieNode n = this;
while (n != null && n.deep != 0) {
w[n.deep - 1] = n.value;
n = n.parent;
}
word = String.valueOf(w);
}
return word;
}
/**
* 將字符串轉(zhuǎn)化成字符隊(duì)列的靜態(tài)方法
*/
public static Queue<Character> string2Queue(String str) {
Queue<Character> queue = new LinkedList<>();
for (char c : str.toCharArray()) {
queue.add(c);
}
return queue;
}
/**
* 加載字符
*/
public void load(Queue<Character> wordQueue, int frequency) {
if (wordQueue.isEmpty())
return;
// 彈出隊(duì)列中第一個(gè)字符
char c = wordQueue.poll();
if (childrenMap == null)
childrenMap = new HashMap<>();
TrieNode node = childrenMap.computeIfAbsent(c, s -> new TrieNode(this, c));
// 如果隊(duì)列非空趴捅，繼續(xù)遞歸加載剩余字符
if (!wordQueue.isEmpty())
node.load(wordQueue, frequency);
else {
// 隊(duì)列為空了，說(shuō)明當(dāng)前節(jié)點(diǎn)是最后一個(gè)字符霹疫，剛好成一個(gè)詞
node.isWord = true;
node.frequency = frequency;
}
}
public static void match(TrieNode node, String word) {
if (word == null || word.length() == 0)
return;
System.out.println(String.format("開(kāi)始對(duì)\"%s\"進(jìn)行匹配：", word));
// 對(duì)輸入字符串的所有子串均進(jìn)行前綴匹配
for (int i = 0; i < word.length(); i++)
match(node, word, i);
}
private static void match(TrieNode node, String word, int index) {
// 要考慮邊界情況
if (index >= word.length() || node.childrenMap == null)
return;
// 取出當(dāng)前位置的字符進(jìn)行匹配
char c = word.charAt(index);
TrieNode child = node.childrenMap.get(c);
// 子節(jié)點(diǎn)存在對(duì)應(yīng)字符才能往下遍歷/判斷
if (child != null) {
if (child.isWord) {
char[] w = new char[child.deep];
TrieNode n = child;
while (n != null && n.deep != 0) {
w[n.deep - 1] = n.value;
n = n.parent;
}
// 當(dāng)找到一個(gè)匹配的詞語(yǔ)時(shí)直接打印
System.out.println(String.valueOf(w));
}
match(child, word, index + 1);
}
}
/**
* 這里需要構(gòu)建DAG的反向引用拱绑，
* 1 -> 2 -> 3
* 原鄰接矩陣應(yīng)該是
* 1 -> 2 -> null
* 2 -> 3 -> null
* 3 -> null
* <p>
* 但此處要構(gòu)建成
* 1 -> null
* 2 -> 1 -> null
* 3 -> 2 -> null
* <p>
* 這是為了后面尋找最近路徑的時(shí)候能夠根據(jù)詞的最后一個(gè)字符迅速定位其對(duì)應(yīng)的首個(gè)字符
*/
public static List<Map<Integer, Integer>> buildDAG(TrieNode head, String str) {
List<Map<Integer, Integer>> dag = new ArrayList<>(str.length());
for (int i = 0; i < str.length(); i++) {
dag.add(i, new HashMap<>());
}
// 詞典為空直接返回空鄰接矩陣
if (head == null || head.childrenMap == null)
return dag;
// 前綴遍歷字符串
for (int i = 0; i < str.length() - 1; i++) {
char c = str.charAt(i);
TrieNode node = head.childrenMap.get(c);
if (node == null)
continue;
TrieNode n = node;
int offset = i;
while (n != null) {
if (n.isWord) {
dag.get(offset).put(i, n.frequency);
}
if (n.childrenMap == null || offset == str.length() - 1)
break;
n = n.childrenMap.get(str.charAt(++offset));
}
}
findOptimalPath(str, dag);
return dag;
}
/**
* 使用動(dòng)態(tài)規(guī)劃求解
* 狀態(tài)轉(zhuǎn)移方程： w(x) = max(w(x-1), w(k1-1) + f(k1), ..., w(kn-1) + f(kn))
* x是字符位置
* w(x)表示位置x上的最優(yōu)路徑權(quán)重
* k1~kn是以位置x上字符結(jié)尾的不同詞
*/
public static void findOptimalPath(String str, List<Map<Integer, Integer>> list) {
int[] indexArr = new int[str.length()];
int[] weightArr = new int[str.length()];
indexArr[0] = 0;
weightArr[0] = 0;
for (int i = 1; i < str.length(); i++) {
int index = i;
int weight = weightArr[index - 1];
Map<Integer, Integer> m = list.get(i);
for (Integer inx : m.keySet()) {
int w = m.get(inx);
if (inx != 0)
w += weightArr[inx - 1];
if (w > weight) {
weight = w;
index = inx;
}
}
indexArr[i] = index;
weightArr[i] = weight;
}
// 到這一步就已經(jīng)求出結(jié)果了，indexArr[str.length()-1]就是最終結(jié)果
// 剩下的就是往回推導(dǎo)出整個(gè)分詞路徑
// 往回推導(dǎo)并輸出分詞結(jié)果
LinkedList<String> l = new LinkedList<>();
int offset = str.length() - 1;
while (offset >= 0) {
int start = indexArr[offset];
l.addFirst(str.substring(start, offset + 1));
offset = start - 1;
}
// 以/的形式表示分詞
for (String s : l) {
System.out.print(s+"/");
}
System.out.println();
}
}
測(cè)試用例
public class Main {
public static void main(String[] args) {
// 初始化樹(shù)根節(jié)點(diǎn)丽蝎，置parent=null, value=' '
TrieNode node = new TrieNode(null, ' ');
node.load(TrieNode.string2Queue("中華"), 10);
node.load(TrieNode.string2Queue("華人"), 8);
node.load(TrieNode.string2Queue("人民"), 15);
node.load(TrieNode.string2Queue("共和國(guó)"), 6);
node.load(TrieNode.string2Queue("中華人民"), 24);
node.load(TrieNode.string2Queue("中華人民共和國(guó)"), 50);
node.load(TrieNode.string2Queue("國(guó)歌"), 8);
node.load(TrieNode.string2Queue("共和"), 5);
TrieNode.buildDAG(node, "中華人民共和國(guó)萬(wàn)歲");
}
}
