中文分詞功能是一項(xiàng)常用的基礎(chǔ)功能，有很多開源的工程實(shí)現(xiàn)，目前能應(yīng)用于Android手機(jī)端的中文分詞器沒(méi)有很完善的版本。經(jīng)過(guò)調(diào)研，我選擇了結(jié)巴分詞，該開源工程思路簡(jiǎn)單，易于理解，分詞效果也還不錯(cuò)，目前有眾多語(yǔ)言版本，PYTHON、C++、JAVA、IOS等，暫時(shí)還沒(méi)有Android版本，所以我在Java版本的基礎(chǔ)上進(jìn)行了移植，開發(fā)了適用于Android手機(jī)的結(jié)巴分詞Android版(Github)。
相比于Java版本的實(shí)現(xiàn)，Android版將字典文件存放在Asset目錄下進(jìn)行讀取，同時(shí)對(duì)字典加載速度進(jìn)行了大幅優(yōu)化。原始的Java版本加載完整的字典文件在測(cè)試手機(jī)上需要28秒，時(shí)間太長(zhǎng)，經(jīng)過(guò)優(yōu)化，成功將加載時(shí)間降到1.5秒，分詞速度1秒以內(nèi)，滿足了Android手機(jī)的啟動(dòng)速度要求。
本文將結(jié)合代碼通過(guò)以下三個(gè)方面展開介紹：結(jié)巴分詞的基本原理，Android版的接入方式，以及啟動(dòng)速度優(yōu)化的實(shí)現(xiàn)。
結(jié)巴分詞的原理
結(jié)巴分詞采用兩種方式進(jìn)行分詞，基于字典的分詞和基于HMM（隱馬爾科夫模型）的分詞。模型會(huì)首先加載詞典文件生成一個(gè)字典樹，并利用該字典樹進(jìn)行一段中文的分詞，比如“我要去五道口吃肯德基”被分詞成“我/要/去/五道口/吃/肯德基”，其中被分成單蹦個(gè)的連續(xù)中文字符，如“我/要/去”會(huì)繼續(xù)經(jīng)過(guò)HMM模型進(jìn)行二次分詞，看能不能合并成完整的單詞，這種設(shè)計(jì)是為了對(duì)不在字典中的字符提供一種兜底的分詞方案，可以盡可能的避免單蹦個(gè)的分詞結(jié)果，優(yōu)化分詞的效果。
下面是進(jìn)行分詞的主函數(shù)：
private List<String> sentenceProcess(String sentence) {
List<String> tokens = new ArrayList<String>();
int N = sentence.length();
long start = System.currentTimeMillis();
// 將一段文字轉(zhuǎn)換成有向無(wú)環(huán)圖，該有向無(wú)環(huán)圖包含了跟字典文件得出的所有可能的單詞切分
Map<Integer, List<Integer>> dag = createDAG(sentence);
Map<Integer, Pair<Integer>> route = calc(sentence, dag);
int x = 0;
int y = 0;
String buf;
StringBuilder sb = new StringBuilder();
while (x < N) { // 遍歷一遍貪心算法生成的最小路徑分詞結(jié)果，對(duì)單蹦個(gè)的字符看看能不能粘合成一個(gè)詞匯
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) { // 如果兩個(gè)單詞之間只有一個(gè)單蹦個(gè)的字符，添加
tokens.add(buf);
} else {
if (wordDict.containsWord(buf)) { // 如果連續(xù)單蹦個(gè)的字符粘合成的一個(gè)單詞在字典樹里，作為一個(gè)單詞添加
tokens.add(buf);
} else {
finalSeg.cut(buf, tokens); // 如果連續(xù)單蹦個(gè)的字符粘合成的一個(gè)單詞不在字典樹里，使用維特比算法計(jì)算每個(gè)字符BMES如何選擇使得概率最大
}
}
}
tokens.add(lWord);
}
x = y;
}
buf = sb.toString();
if (buf.length() > 0) { // 處理余下的部分
if (buf.length() == 1) {
tokens.add(buf);
} else {
if (wordDict.containsWord(buf)) {
tokens.add(buf);
} else {
finalSeg.cut(buf, tokens);
}
}
}
return tokens;
}
該函數(shù)首先通過(guò)createDAG將輸入的一段文字轉(zhuǎn)換成有向無(wú)環(huán)圖（DAG），該有向無(wú)環(huán)圖包含了根據(jù)字典文件得出的所有可能的單詞切分，以每個(gè)字為單位，比如“我去五道口吃肯德基”，經(jīng)過(guò)createDAG處理后會(huì)生成每個(gè)字和后面字符可能的單詞組合，比如“我/去/五道口/吃/肯德基”/“我去/五道口/吃/肯德基”/“我去/五/道口/吃/肯德基”/“我/去/五道口/吃/肯德/基”等等。
然后經(jīng)過(guò)calc函數(shù)，對(duì)這個(gè)DAG從后向前依據(jù)貪婪算法選擇一種分詞方式。實(shí)現(xiàn)比較簡(jiǎn)單，從最后一個(gè)字開始，找出從該字符前面字符跳轉(zhuǎn)到當(dāng)前字符概率最大的切分方式，然后依次往前走，直到完成整句話的切分。概率的大小依據(jù)是字典中該單詞的頻率值。
/**
* 計(jì)算有向無(wú)環(huán)圖的一條最大路徑，從后向前，利用貪心算法，每一步只需要找出到達(dá)該字符的最大概率字符作為所選擇的路徑
*
* @param sentence
* @param dag
* @return
*/
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;
}
經(jīng)過(guò)上面calc函數(shù)的切分，整段話會(huì)被切分成一些單詞和一些單蹦個(gè)的字符的組合，對(duì)于單蹦個(gè)的字符，再調(diào)用finalSeg.cut函數(shù)進(jìn)行HMM模型切分，試圖盡可能組合成完整的單詞，優(yōu)化切詞效果。
finalSeg.cut函數(shù)實(shí)現(xiàn)如下：
public void cut(String sentence, List<String> tokens) {
StringBuilder chinese = new StringBuilder();
StringBuilder other = new StringBuilder();
for (int i = 0; i < sentence.length(); ++i) {
char ch = sentence.charAt(i);
if (CharacterUtil.isChineseLetter(ch)) { // 遇到一個(gè)漢字，就把之前累積的非漢字處理一下加入最終結(jié)果
if (other.length() > 0) {
processOtherUnknownWords(other.toString(), tokens);
other = new StringBuilder();
}
chinese.append(ch);
}
else {
if (chinese.length() > 0) { // 遇到一個(gè)非漢字符號(hào)，就把之前累加的單蹦個(gè)漢字處理一下加入最終結(jié)果
viterbi(chinese.toString(), tokens); // 處理一串單蹦個(gè)漢字的方法是維特比算法
chinese = new StringBuilder();
}
other.append(ch);
}
}
if (chinese.length() > 0) // 處理余下的漢字
viterbi(chinese.toString(), tokens);
else { // 處理余下的非漢字字符
processOtherUnknownWords(other.toString(), tokens);
}
}
finalSeg.cut函數(shù)考慮了中文字符和非中文字符的情況，將非中文字符利用正則表達(dá)式切成單個(gè)的英文單詞，將中文字符利用B(Begin)、M(Middle)、E(End)、S(Single)標(biāo)記方式對(duì)每個(gè)漢字做出標(biāo)記，標(biāo)價(jià)的依據(jù)是每個(gè)漢字選擇一個(gè)標(biāo)記符號(hào)，使得整串漢字從頭到尾行程的路徑概率最大。這樣就轉(zhuǎn)換成了每一字符到下一個(gè)字符跳轉(zhuǎn)概率給定情況下的最短路徑問(wèn)題。最短路徑問(wèn)題有兩種標(biāo)準(zhǔn)解法，維特比算法和迪杰斯特拉算法。迪杰斯特拉算法是一種貪心策略，只能保證局部最優(yōu)，不能保證全局最優(yōu)。維特比算法能保證求得全局最優(yōu)解，所以這里使用維特比算法求解。
/**
* 利用維特比算法計(jì)算對(duì)于一串單蹦個(gè)的字符，每個(gè)字符到下一個(gè)字符如何跳轉(zhuǎn)，以實(shí)現(xiàn)整條路徑的概率最大
* 例如：我 去 五 道 口
* B B B B B
* M M M M M
* E E E E E
* S S S S S
* @param sentence
* @param tokens
*/
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));
}
......
}
這樣就既保證了詞典分詞的準(zhǔn)確性，又能對(duì)沒(méi)有出現(xiàn)在詞典中的單蹦個(gè)的漢字進(jìn)行一定程度的優(yōu)化分詞，具備了一定的靈活性。
接入方式
具體接入方式可以參照結(jié)巴分詞Android版(Github)進(jìn)行接入，既可以源碼接入，也可以通過(guò)gradle接入。
使用的時(shí)候首先進(jìn)行初始化，一般在MyApplication里進(jìn)行：
// 異步初始化
JiebaSegmenter.init(getApplicationContext());
該初始化是異步進(jìn)行的，速度僅需1.5秒即可完成包含35萬(wàn)詞典的字典樹的生成。
該Android分詞器提供了三個(gè)接口用于分詞。
下面兩個(gè)簡(jiǎn)單接口分別是同步和異步分詞接口：
// 異步接口
public void getDividedStringAsync(final String query, final RequestCallback<ArrayList<String>> callback) {...}
// 同步接口
public ArrayList<String> getDividedString(String query) {...}
同時(shí)保留了結(jié)巴分詞原有的分詞接口process，可以指定分詞模式是索引模式（INDEX）或搜索引擎模式（SEARCH），兩者的差別在于搜索引擎模式分詞更精細(xì)，索引模式相對(duì)更粗粒度。
public static enum SegMode {
INDEX,
SEARCH
}
public List<SegToken> process(String query, SegMode mode) {...}
啟動(dòng)速度優(yōu)化
原始的Java版本的結(jié)巴分詞在手機(jī)上加載詞典速度很慢，35萬(wàn)的詞典需要28秒，不能直接使用。這是由于需要根據(jù)詞典生成字典樹(TireTree)，每加入一個(gè)單詞都需要進(jìn)行查找和比較，很耗時(shí)。為此，在Android版本里，我做了預(yù)處理，將加載詞典生成的字典樹按照特定格式存儲(chǔ)到了文本中，實(shí)際運(yùn)行的時(shí)候，直接從Asset下加載該中間文件，將原來(lái)單詞隨機(jī)插入字典樹的方式該為順序插入，極大的加快了速度。
首先通過(guò)loadDict函數(shù)加載詞典，生成字典樹：
public boolean loadDict(AssetManager assetManager) {
element = new Element((char) 0); // 創(chuàng)建一個(gè)根Element，只有一個(gè)，其他的Element全是其子孫節(jié)點(diǎn)
InputStream is = null;
try {
long start = System.currentTimeMillis();
is = assetManager.open(MAIN_DICT);
if (is == null) {
Log.e(LOGTAG, "Load asset file error:" + MAIN_DICT);
return false;
}
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]; // eg:一兩千塊
double freq = Double.valueOf(tokens[1]);
total += freq;
String trimmedword = addWord(word); // 將一個(gè)單詞的每個(gè)字遞歸的插入字典樹 eg:一兩千塊
freqs.put(trimmedword, freq); // 并統(tǒng)計(jì)單詞首個(gè)字的頻率
}
// normalize
for (Map.Entry<String, Double> entry : freqs.entrySet()) {
entry.setValue((Math.log(entry.getValue() / total)));
minFreq = Math.min(entry.getValue(), minFreq);
}
Log.d(LOGTAG, String.format("main dict load finished, time elapsed %d ms",
System.currentTimeMillis() - s));
} catch (IOException e) {
Log.e(LOGTAG, String.format("%s load failure!", MAIN_DICT));
return false;
} finally {
try {
if (null != is)
is.close();
}
catch (IOException e) {
Log.e(LOGTAG, String.format("%s close failure!", MAIN_DICT));
return false;
}
}
return true;
}
element是整棵字典樹的根節(jié)點(diǎn)。
然后通過(guò)saveDictToFile函數(shù)按層存儲(chǔ)該字典樹：
/**
* ROOT
* b/ -- c$/ -- d/
* e$/f/ -- #/ -- g/
* h$/ ---- #/ ---- i$/
* #/ --------- #/
* @param elementArray
*/
private void saveDictToFile(ArrayList<Element> elementArray) {
if (elementArray.size() <= 0) {
Log.d(LOGTAG, "saveDictToFile final str: " + dicLineBuild.toString());
try {
File file = new File(Environment.getExternalStorageDirectory(), MAIN_PROCESSED);
if (!file.exists()) {
file.createNewFile();
}
FileOutputStream fos = new FileOutputStream(file);
// 第一行是字典數(shù)據(jù)
dicLineBuild.append("\r\n");
// 第二行： 最小頻率 TAB 單詞1 TAB 頻率 TAB 單詞2 TAB 頻率 ...
dicLineBuild.append(minFreq);
for (Map.Entry<String, Double> entry : freqs.entrySet()) {
dicLineBuild.append(TAB);
dicLineBuild.append(entry.getKey());
dicLineBuild.append(TAB);
dicLineBuild.append(entry.getValue());
}
fos.write(dicLineBuild.toString().getBytes());
fos.close();
Log.d(LOGTAG, String.format("字典中間文件生成成功，存儲(chǔ)在%s", file.getAbsolutePath()));
} catch (Exception e) {
Log.d(LOGTAG, "字典中間文件生成失?。?);
e.printStackTrace();
}
return;
}
ArrayList<Element> childArray = new ArrayList();
// elementArray有幾個(gè)元素，就要添加TAB分割的幾個(gè)數(shù)據(jù)段，每個(gè)數(shù)據(jù)段是該Element的子節(jié)點(diǎn)的字+"/"，比如 e/f/ TAB #/ TAB g/
// 如果從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑表示一個(gè)詞，那么在后面添加$符號(hào),如 e$/f/ TAB #/ TAB g/
for (int i = 0; i < elementArray.size(); i++) {
Element element = elementArray.get(i);
// e/f/
if (element.hasNextNode()) {
for (Map.Entry<Character, Element> entry : element.childrenMap.entrySet()) {
dicLineBuild.append(entry.getKey());
if (entry.getValue().nodeState == 1) {
dicLineBuild.append(DOLLAR); // 從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑表示一個(gè)詞，那么在后面添加$符號(hào),如 e$/f/ TAB #/ TAB g/
}
dicLineBuild.append(SLASH);
// 將該節(jié)點(diǎn)的所有子節(jié)點(diǎn)入列表，供下一次遞歸
childArray.add(entry.getValue());
}
} else { // #/
dicLineBuild.append(SHARP);
dicLineBuild.append(SLASH);
}
// TAB
dicLineBuild.append(TAB);
}
saveDictToFile(childArray);
}
該文件共兩行，第一行是按層存儲(chǔ)的字典文件，第二行是每個(gè)單詞的頻率。每行都很長(zhǎng)。其中第一行的生成比較復(fù)雜，我們從根節(jié)點(diǎn)element開始，用一個(gè)列表存儲(chǔ)每一層的節(jié)點(diǎn)。首先將根節(jié)點(diǎn)加入該列表，依次遍歷列表中的同層節(jié)點(diǎn)，該列表有m個(gè)節(jié)點(diǎn)，就添加TAB分割的m個(gè)數(shù)據(jù)段，每個(gè)數(shù)據(jù)段是該節(jié)點(diǎn)的所有子節(jié)點(diǎn)字符，用"/"符號(hào)連接，比如明天/明年/明月，哦，后天/后面，三個(gè)單詞，其中明/哦/后是同一層的三個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)是明，三個(gè)子節(jié)點(diǎn)分別是天/年/月, 那么會(huì)在文本中寫入天/年/月/。哦沒(méi)有子節(jié)點(diǎn)，會(huì)寫入#/，后天/后面會(huì)寫入天/面/，通過(guò)TAB將三部分連接起來(lái)，就是天/年/月/ TAB #/ TAB 天/面/。通過(guò)這種方式，遞歸將整棵樹按層存入文件，在手機(jī)加載的時(shí)候逆向按順序完成字典樹的恢復(fù)。
恢復(fù)的字典樹的過(guò)程代碼如下，也是遞歸進(jìn)行的：
/**
* d/b/c/ g/ f/e/ #/ j/ #/ h/ #/ #/
*/
private void restoreElement(ArrayList<Element> elemArray, List<String> strArray, int startIndex) {
if (elemArray.size() <= 0) {
return;
}
ArrayList<Element> newElemArray = new ArrayList<>();
for (int i = 0; i < elemArray.size(); i++) {
String strCluster = strArray.get(startIndex);
String[] strList = strCluster.split(SLASH);
Element e = elemArray.get(i);
// #/
if (strList.length == 1 && strList[0].equalsIgnoreCase(SHARP)) {
e.nodeState = 1;
e.storeSize = 0;
} else { // f/e/
e.childrenMap = new HashMap<>();
for (int j = 0; j < strList.length; j++) {
String s = strList[j];
boolean isWord = s.length() == 2;
Character ch = new Character(s.charAt(0));
Element childElem = new Element(ch);
childElem.nodeState = isWord ? 1 : 0;
e.childrenMap.put(ch, childElem);
e.storeSize++;
newElemArray.add(childElem);
}
}
startIndex++;
}
restoreElement(newElemArray, strArray, startIndex);
}
這樣，加載35萬(wàn)詞典可以在1.5秒內(nèi)完成，分詞速度在一秒以內(nèi)，滿足了Android手機(jī)上的可用性。希望該分詞器能夠?yàn)榇蠹业腁ndroid App提供更多圍繞分詞的功能亮點(diǎn)，做出更優(yōu)秀的APP。
