在一個(gè)三叉搜索樹（Ternary Search Trie）中，每一個(gè)節(jié)點(diǎn)包括一個(gè)字符，但和數(shù)字搜索樹不同冠场，三叉搜索樹只有三個(gè)指針：一個(gè)指向左邊的樹秆剪，一個(gè)指向右邊的樹赊淑，還有一個(gè)向下爵政，指向單詞的下一個(gè)數(shù)據(jù)單元。三叉搜索樹是二叉搜索樹和數(shù)字搜索樹的混合體陶缺。它有和數(shù)字搜索樹差不多的速度钾挟，但是和二叉搜索樹一樣只需要相對(duì)較少的內(nèi)存空間。
樹的平衡取決于單詞的讀入順序饱岸。如果按排序后的順序插入掺出，則生成方式最不平衡。通過(guò)選擇一個(gè)排序后數(shù)據(jù)單元集合的中間值苫费，并把它作為開始節(jié)點(diǎn)汤锨，就可以創(chuàng)建一個(gè)平衡的三叉樹。
下面用三叉搜索樹來(lái)構(gòu)建字典樹以及進(jìn)行最大正向長(zhǎng)度匹配分詞：
- TSTNode.java
public final class TSTNode {
/**節(jié)點(diǎn)的值data可以存儲(chǔ)詞原文和詞性百框、詞頻等相關(guān)的信息*/
public String data=null;
//左中右節(jié)點(diǎn)
protected TSTNode lNode;
protected TSTNode mNode;
protected TSTNode rNode;
protected char splitchar;//本節(jié)點(diǎn)表示的字符
protected TSTNode(char splitchar){
this.splitchar=splitchar;
}
public String toString(){
return "splitchar:"+splitchar;
}
/**
* 查找的過(guò)程是：輸入一個(gè)詞闲礼，返回這個(gè)詞對(duì)應(yīng)的TSTNode對(duì)象，如果該詞不在詞典中铐维，則返回空柬泽。
* 查找詞典的過(guò)程中，從樹的根節(jié)點(diǎn)匹配Key嫁蛇，從前往后匹配Key*/
protected TSTNode getNode(String key,TSTNode startNode){
if(null==key){
return null;
}
int len=key.length();
if(len==0)
return null;
TSTNode currentNode=startNode;//匹配過(guò)程中當(dāng)前節(jié)點(diǎn)的位置
int charIndex=0;
char cmpChar=key.charAt(charIndex);
int charComp;
while(true){
if(null==currentNode){
return null;
}
charComp=cmpChar-currentNode.splitchar;
if(charComp==0){//equal
charIndex++;
if(charIndex==len){//找到
return currentNode;
}
else
cmpChar=key.charAt(charIndex);
currentNode=currentNode.mNode;
}else if(charComp<0){//小于
currentNode=currentNode.lNode;
}else {
currentNode=currentNode.rNode;
}
}
}
/**三叉樹的創(chuàng)建過(guò)程锨并，就是在Trie樹上創(chuàng)建和單詞對(duì)應(yīng)的節(jié)點(diǎn)
* 下面方法實(shí)現(xiàn)的是向詞典樹中加入一個(gè)單詞的過(guò)程*/
TSTNode addWord(String key,TSTNode root){
TSTNode currentNode=root;//從樹的根節(jié)點(diǎn)開始查找
int charIndex=0;//從詞的開頭匹配
while(true){
//比較詞的當(dāng)前字符與節(jié)點(diǎn)的當(dāng)前字符
int charComp=key.charAt(charIndex)-currentNode.splitchar;
if(charComp==0){
charIndex++;
if(charIndex==key.length()){
currentNode.data=key;//將當(dāng)前的詞存到最后一個(gè)節(jié)點(diǎn)的data中
return currentNode;
}
//如果不存在直接后繼節(jié)點(diǎn)
if(currentNode.mNode==null){
currentNode.mNode=new TSTNode(key.charAt(charIndex));
}
currentNode=currentNode.mNode;
}else if (charComp<0) {
if(currentNode.lNode==null){
currentNode.lNode=new TSTNode(key.charAt(charIndex));
}
currentNode=currentNode.lNode;
}else {
if(currentNode.rNode==null){
currentNode.rNode=new TSTNode(key.charAt(charIndex));
}
currentNode=currentNode.rNode;
}
}
}
/**Trie樹搜索最長(zhǎng)匹配單詞的方法
* @param key 待匹配字符串
* @param offset 匹配開始位置*/
public String matchLong(String key,int offset,TSTNode root){
String ret=null;
if(key==null||root==null||"".equals(key)){
return ret;
}
TSTNode currentNode=root;
int charIndex=offset;
while(true){
if(currentNode==null){
return ret;
}
int charComp=key.charAt(charIndex)-currentNode.splitchar;
if(charComp==0){
charIndex++;
if(currentNode.data!=null){
ret=currentNode.data;//候選最長(zhǎng)匹配詞
}
if(charIndex==key.length()){
return ret;
}
currentNode=currentNode.mNode;
}else if (charComp<0) {
currentNode=currentNode.lNode;
}else {
currentNode=currentNode.rNode;
}
}
}
/**正向最大長(zhǎng)度分詞*/
public void wordSegment(String sentence,TSTNode root){
int senLen=sentence.length();
int i=0;
while(i<senLen){
String word=root.matchLong(sentence, i, root);
if(word!=null){
//下次匹配點(diǎn)在這個(gè)詞之后
i+=word.length();
//如果詞在詞典中，則就直接打印出來(lái)
System.out.print(word+" ");
}
else{
//如果在詞典中沒(méi)找到棠众，則按單字切分
word=sentence.substring(i, i+1);
//打印一個(gè)字
System.out.print(word);
i++;//下次匹配點(diǎn)在這個(gè)字符之后
}
}
}
}
- TSNTreeTest.java
例如琳疏，Trie樹的字典中包含如下詞語(yǔ)：
大 大學(xué) 大學(xué)生 活動(dòng) 生活 中 中心 心
（下面直接按照上面字典的順序添加，所以得到的可能不是平衡Trie樹）
public class TSNTreeTest {
public static void main(String[] args) {
TSTNode root=new TSTNode(' ');
root.addWord("大", root);
root.addWord("大學(xué)", root);
root.addWord("大學(xué)生", root);
root.addWord("活動(dòng)", root);
root.addWord("生活", root);
root.addWord("中", root);
root.addWord("中心", root);
root.addWord("心", root);
String sentence="大學(xué)生活動(dòng)中心";
String ret=root.matchLong(sentence, 0, root);
System.out.println(sentence+" match:"+ret);
root.wordSegment(sentence, root);
}
}
得到的結(jié)果是：
第一行是輸入“大學(xué)生活動(dòng)中心”時(shí)闸拿，返回的最長(zhǎng)匹配詞
第二行是根據(jù)正向最長(zhǎng)匹配分詞的結(jié)果
參考資料：
[1] Trie樹和Ternary Search樹的學(xué)習(xí)總結(jié):
http://www.cnblogs.com/rush/archive/2012/12/30/2839996.html
