前言
前陣子面試的到時候有個面試官問到，你知不知道分詞器怎么實現(xiàn)的？當(dāng)時老實回答，確實不知道。隨后面試官就說有空的時候可以看看。
不過看歸看，總感覺如果不自己實現(xiàn)一下的話還是很難達到掌握的程度，于是有個想法，從零開始實現(xiàn)一下分詞器吧。
分詞器介紹
一直以來中文分詞都是比較頭痛的事情，因為不像英語那樣，詞語之間有空格隔開。(其實英文也有詞組分割問題)
最早的中文分詞方法就是查字典：把一個句子從左到右掃描一遍，遇到字典里有的詞就標(biāo)識出來，遇到復(fù)合詞（比如“上海大學(xué)”）就找最長的詞匹配，遇到不認識的字串分割成單詞。
比如（從左到右遍歷）：
今天天氣很好（首先分隔符在 "今"） ->
今/天天氣很好（繼續(xù)遍歷發(fā)現(xiàn) "今天"詞典中有，就把分隔符往右挪） ->
今天/天氣很好（詞典不存在“今天天”這個詞，于是在第二個“天”后面新設(shè)一個分割符) ->
今天/天/氣很好（如此類推) ->
... ->
今天/天氣/很好（完成了分詞）
存在問題：
- 復(fù)雜度太高
- 二義性問題（"發(fā)展中國家"，應(yīng)該分詞成"發(fā)展/中/國家"，而采用從左到右查字典會被分割成"發(fā)展/中國/家"）
隨后有一些學(xué)者開始注意到統(tǒng)計信息的作用，假定一個句子S可以有幾種分詞方法（假定為3種）：
A1,A2,A3,...,Ak
B1,B2,B3,...,Bm
C1,C2,C3,...,Cn
其中Ai, Bi, Ci都是漢語中的詞，那么從統(tǒng)計學(xué)的角度看，最好的分詞方法那么這個句子出現(xiàn)的概率應(yīng)該是最大的。即如果A1,A2,A3,...,Ak是最好的分詞方法，那么其概率應(yīng)該滿足：
P(A1,A2,A3,...,Ak) > P(B1,B2,B3,...,Bm)` 且`P(A1,A2,A3,...,Ak) > P(C1,C2,C3,...,Cn)
用窮舉法計算概率計算量是相當(dāng)巨大的，可以使用動態(tài)規(guī)劃進行優(yōu)化，算法過程大致如下：
通過統(tǒng)計模型能夠很好地解決分詞的二義性問題（也叫歧義性）。
分詞器實現(xiàn)思路
上面已經(jīng)介紹了中文分詞的原理：根據(jù)已有詞典形成各種組合使得句子概率最大化但是具體怎么實現(xiàn)的還是不清楚。下面就從兩個問題入手，逐漸認識分詞器。
- 詞典加載進內(nèi)存是怎么樣的，用什么數(shù)據(jù)結(jié)構(gòu)？
- 從輸入一個文本到輸出分詞結(jié)果的完整步驟是怎么樣的？
先來看看詞典，下面是github當(dāng)前比較熱門的兩個分詞器（前者是ES的中文分詞插件，后者是一個python中文分詞模塊）中的部分詞典內(nèi)容。
ik詞典：
一一列舉
一一對應(yīng)
一一道來
一丁
一丁不識
一丁點
一丁點兒
一七八不
...
# 詞語 詞頻 詞性
AT&T 3 nz
B超 3 n
c# 3 nz
C# 3 nz
c++ 3 nz
C++ 3 nz
T恤 4 n
A座 3 n
A股 3 n
A型 3 n
...
從上面摘抄的部分詞典中可以看出，詞典基本是按字典順序排，即相鄰的詞很可能有相同的前綴，聰明的同學(xué)可能很快就get到，這用前綴樹(Trie)來存儲不就很合適嗎？（如果你以前不知道前綴樹是什么東西，那看下面就知道了）
Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)，如英文字母的字典樹是一個26叉樹，數(shù)字的字典樹是一個10叉樹。
一個節(jié)點的所有子孫都有相同的前綴(prefix)，Trie樹利用字符串的公共前綴來節(jié)約存儲空間。如下圖所示，該Trie樹用11個節(jié)點保存了8個字符串tea，ted，ten，to，A，i，in，inn。
圖片來源：
https://www.cnblogs.com/rush/archive/2012/12/30/2839996.html（這篇文章也解釋了怎么實現(xiàn)前綴樹）
接下來會先從Trie的實現(xiàn)開始逐步介紹怎么實現(xiàn)一個分詞器，會比較啰嗦，如果沒耐心的話可以直接看上面的文章的TrieTree的實現(xiàn)
相信通過上面的圖你可以清楚前綴樹的物理結(jié)構(gòu)，那么我們就先把前綴樹需要的一些屬性列出來：
Trie樹所需要的屬性
這里順便說一下java的基礎(chǔ)知識： Java中char的使用的是UTF-8，所以任意一個中文其實是可以用一個單位的char來存儲的。
首先我們從一個樹節(jié)點入手，一個節(jié)點中必須會有對應(yīng)的 value 吧，然后還可能有下層子節(jié)點 children ，由于子節(jié)點可能不止一個，為了方便就使用HashMap來存儲所有的子節(jié)點：
// 最初可以確定有以下兩個屬性
char value;
Map<Character, TrieNode> childrenMap;
接下來思考，是不是缺少了點什么？假如給定任意一個節(jié)點，那如何確定怎么到達這個節(jié)點的路徑呢（即這個節(jié)點的前綴是什么）？
于是我們再引入 parent 屬性來存儲當(dāng)前節(jié)點的父節(jié)點的引用，emmm，順便再引入當(dāng)前節(jié)點的深度 deep
如果這里想不到引入這兩個屬性的話其實后續(xù)遇到打印節(jié)點的方法時也會想到
TrieNode parent;
int deep;
Trie樹的構(gòu)造方法
主要就是考慮父節(jié)點和深度的計算（這里把上面的屬性也一起列出來）
public class TrieNode {
char value;
Map<Character, TrieNode> childrenMap;
TrieNode parent;
int deep;
public TrieNode(TrieNode parent, char value) {
this.parent = parent;
this.value = value;
// 假定根節(jié)點不存儲有意義的值，深度為0
if (parent == null)
deep = 0;
else
deep = parent.deep + 1;
}
}
Trie樹的詞典加載方法
構(gòu)造完Trie樹之后，回到最初的需求，我們是要做一個能裝載詞典的數(shù)據(jù)結(jié)構(gòu)，那么首要的功能當(dāng)然是加載詞典。
- 為了處理方便，把每個傳入的字符串(詞語)轉(zhuǎn)化成隊列（這樣能夠減少subString的開銷）
- 加載一個詞其實是簡單的遞歸創(chuàng)建過程：第一個字符是否已經(jīng)存在？若存在則直接進入，若不存在則先創(chuàng)建再進入，然后繼續(xù)判斷第二個字符串是否已經(jīng)在第一個字符串的
childrenMap里面，如果不存在則創(chuàng)建...按照這種流程遞歸下去。（不用考慮溢出問題，一般單個詞不會很長）
/**
* 加載字符
* */
public void load(Queue<Character> wordQueue) {
if (wordQueue.isEmpty())
return;
// 彈出隊列中第一個字符
char c = wordQueue.poll();
if (childrenMap == null)
childrenMap = new HashMap<>();
TrieNode node = childrenMap.computeIfAbsent(c, s -> new TrieNode(this, c));
// 如果隊列非空，繼續(xù)遞歸加載剩余字符
if (!wordQueue.isEmpty())
node.load(wordQueue);
}
/**
* 將字符串轉(zhuǎn)化成字符隊列的靜態(tài)方法
* */
public static Queue<Character> string2Queue(String str) {
Queue<Character> queue = new LinkedList<>();
for (char c:str.toCharArray()) {
queue.add(c);
}
return queue;
}
在 TrieNode 類中加入上面兩個方法，基本的詞典前綴樹就完成了，下面測試一下詞典加載：
//下面代碼在 public static void main(String[] args) 方法中執(zhí)行
// 初始化樹根節(jié)點，置parent=null, value=' '
TrieNode node = new TrieNode(null, ' ');
node.load(TrieNode.string2Queue("北京大學(xué)"));
node.load(TrieNode.string2Queue("北京交通大學(xué)"));
進入DEBUG模式
可以看到，內(nèi)存中兩個詞共用了"北京"前綴，且深度屬性也正常運作
Trie樹的匹配方法
既然上面我們已經(jīng)完成了詞典的加載,接下來就應(yīng)該做詞的匹配了：
給定一串文本，如何判斷哪些詞是詞典中存在的？
再簡化下問題：給定一串文本，如何識別出文本中存在于詞典中的詞？
先來模擬一下匹配流程：
比如，之前的例子中，加載了"北京大學(xué)"和"北京交通大學(xué)"兩個詞，當(dāng)我輸入"去北京大學(xué)玩"這樣一個文本的時候，應(yīng)該要識別出其中的"北京大學(xué)"
最簡單的做法其實就是遍歷："去北京大學(xué)玩"，"北京大學(xué)玩"，"京大學(xué)玩"，"大學(xué)玩"...看下有沒有符合前綴的。如果有符合前綴的就開始遍歷。這里只有"北京大學(xué)玩"是符合前綴，然后開始遍歷這個子字符串，最終遍歷到"學(xué)"的時候發(fā)現(xiàn)存在一個滿足的詞語"北京大學(xué)"。
這里會發(fā)現(xiàn)一個問題：怎么在遍歷到"學(xué)"的時候能夠知道匹配上了一個詞？這時候其實在 TrieNode 類中補充一個標(biāo)記屬性即可
// 判斷到當(dāng)前節(jié)點是否為一個詞
boolean isWord = false;
并且在加載詞典的時候補充幾行(12~14)
public void load(Queue<Character> wordQueue) {
if (wordQueue.isEmpty())
return;
// 彈出隊列中第一個字符
char c = wordQueue.poll();
if (childrenMap == null)
childrenMap = new HashMap<>();
TrieNode node = childrenMap.computeIfAbsent(c, s -> new TrieNode(this, c));
// 如果隊列非空，繼續(xù)遞歸加載剩余字符
if (!wordQueue.isEmpty())
node.load(wordQueue);
else
// 隊列為空了，說明當(dāng)前節(jié)點是最后一個字符，剛好成一個詞
node.isWord = true;
}
梳理清楚之后，就可以開始寫對應(yīng)的匹配方法了
public static void match(TrieNode node, String word) {
if (word == null || word.length() == 0)
return;
System.out.println(String.format("開始對\"%s\"進行匹配：", word));
// 對輸入字符串的所有子串均進行前綴匹配
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)前位置的字符進行匹配
char c = word.charAt(index);
TrieNode child = node.childrenMap.get(c);
// 子節(jié)點存在對應(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)找到一個匹配的詞語時直接打印
System.out.println(String.valueOf(w));
}
match(child, word, index + 1);
}
}
回到main方法，在原來的基礎(chǔ)上多增加match的測試：
TrieNode node = new TrieNode(null, ' ');
node.load(TrieNode.string2Queue("北京大學(xué)"));
node.load(TrieNode.string2Queue("北京交通大學(xué)"));
TrieNode.match(node, "去北京大學(xué)玩");
TrieNode.match(node, "去北京交通大學(xué)玩");
TrieNode.match(node, "去北京交通大學(xué)玩北京大學(xué)");
// 輸出：
開始對"去北京大學(xué)玩"進行匹配：
北京大學(xué)
開始對"去北京交通大學(xué)玩"進行匹配：
北京交通大學(xué)
開始對"去北京交通大學(xué)玩北京大學(xué)"進行匹配：
北京交通大學(xué)
北京大學(xué)
今天就先到此為止了，后續(xù)文章再繼續(xù)深入
參考
<<數(shù)學(xué)之美>>
Trie樹和Ternary Search樹的學(xué)習(xí)總結(jié)
完整TrieNode類實現(xiàn)
此處代碼只是到當(dāng)前文章為止所介紹到內(nèi)容的實現(xiàn)，后續(xù)隨著分詞器的逐步完善會不斷修改。
package edqi.lucene.util;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
/**
* @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;
public TrieNode(TrieNode parent, char value) {
this.parent = parent;
this.value = value;
// 假定根節(jié)點不存儲有意義的值，深度為0
if (parent == null)
deep = 0;
else
deep = parent.deep + 1;
}
/**
* 將字符串轉(zhuǎn)化成字符隊列的靜態(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) {
if (wordQueue.isEmpty())
return;
// 彈出隊列中第一個字符
char c = wordQueue.poll();
if (childrenMap == null)
childrenMap = new HashMap<>();
TrieNode node = childrenMap.computeIfAbsent(c, s -> new TrieNode(this, c));
// 如果隊列非空，繼續(xù)遞歸加載剩余字符
if (!wordQueue.isEmpty())
node.load(wordQueue);
else
// 隊列為空了，說明當(dāng)前節(jié)點是最后一個字符，剛好成一個詞
node.isWord = true;
}
public static void match(TrieNode node, String word) {
if (word == null || word.length() == 0)
return;
System.out.println(String.format("開始對\"%s\"進行匹配：", word));
// 對輸入字符串的所有子串均進行前綴匹配
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)前位置的字符進行匹配
char c = word.charAt(index);
TrieNode child = node.childrenMap.get(c);
// 子節(jié)點存在對應(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)找到一個匹配的詞語時直接打印
System.out.println(String.valueOf(w));
}
match(child, word, index + 1);
}
}
}
