在一个三叉搜索树（Ternary Search Trie）中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向左边的树，一个指向右边的树，还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度，但是和二叉搜索树一样只需要相对较少的内存空间。
树的平衡取决于单词的读入顺序。如果按排序后的顺序插入，则生成方式最不平衡。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，就可以创建一个平衡的三叉树。
下面用三叉搜索树来构建字典树以及进行最大正向长度匹配分词：
- TSTNode.java
public final class TSTNode {
/**节点的值data可以存储词原文和词性、词频等相关的信息*/
public String data=null;
//左中右节点
protected TSTNode lNode;
protected TSTNode mNode;
protected TSTNode rNode;
protected char splitchar;//本节点表示的字符
protected TSTNode(char splitchar){
this.splitchar=splitchar;
}
public String toString(){
return "splitchar:"+splitchar;
}
/**
* 查找的过程是：输入一个词，返回这个词对应的TSTNode对象，如果该词不在词典中，则返回空。
* 查找词典的过程中，从树的根节点匹配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;//匹配过程中当前节点的位置
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;
}
}
}
/**三叉树的创建过程，就是在Trie树上创建和单词对应的节点
* 下面方法实现的是向词典树中加入一个单词的过程*/
TSTNode addWord(String key,TSTNode root){
TSTNode currentNode=root;//从树的根节点开始查找
int charIndex=0;//从词的开头匹配
while(true){
//比较词的当前字符与节点的当前字符
int charComp=key.charAt(charIndex)-currentNode.splitchar;
if(charComp==0){
charIndex++;
if(charIndex==key.length()){
currentNode.data=key;//将当前的词存到最后一个节点的data中
return currentNode;
}
//如果不存在直接后继节点
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树搜索最长匹配单词的方法
* @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;//候选最长匹配词
}
if(charIndex==key.length()){
return ret;
}
currentNode=currentNode.mNode;
}else if (charComp<0) {
currentNode=currentNode.lNode;
}else {
currentNode=currentNode.rNode;
}
}
}
/**正向最大长度分词*/
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){
//下次匹配点在这个词之后
i+=word.length();
//如果词在词典中，则就直接打印出来
System.out.print(word+" ");
}
else{
//如果在词典中没找到，则按单字切分
word=sentence.substring(i, i+1);
//打印一个字
System.out.print(word);
i++;//下次匹配点在这个字符之后
}
}
}
}
- TSNTreeTest.java
例如，Trie树的字典中包含如下词语：
大 大学 大学生 活动 生活 中 中心 心
（下面直接按照上面字典的顺序添加，所以得到的可能不是平衡Trie树）
public class TSNTreeTest {
public static void main(String[] args) {
TSTNode root=new TSTNode(' ');
root.addWord("大", root);
root.addWord("大学", root);
root.addWord("大学生", root);
root.addWord("活动", root);
root.addWord("生活", root);
root.addWord("中", root);
root.addWord("中心", root);
root.addWord("心", root);
String sentence="大学生活动中心";
String ret=root.matchLong(sentence, 0, root);
System.out.println(sentence+" match:"+ret);
root.wordSegment(sentence, root);
}
}
得到的结果是：
第一行是输入“大学生活动中心”时，返回的最长匹配词
第二行是根据正向最长匹配分词的结果
参考资料：
[1] Trie树和Ternary Search树的学习总结:
http://www.cnblogs.com/rush/archive/2012/12/30/2839996.html
网友评论