前缀树的结构


上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:
①根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
②从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
③每个节点的所有子节点包含的字符互不相同。
④从第一字符开始有连续重复的字符只占用一个节点,比如上面的to,和ten,中重复的单词t只占用了一个节点。

前缀树的应用

1、前缀匹配
2、字符串检索
3、词频统计
4、字符串排序

下面看看怎样使用前缀树来实现前缀匹配的。

前缀匹配

了解了前缀树的结构后,就可以利用前缀树的性质来解决现实中的问题。比如说查找一个字符串数组中是否含有前缀单词,什么是前缀单词:上面的 in,就是 inn 的前缀单词。如果有十几万条单词,并且每个单词的长度都是5-10以内,这样必定存在大量重复的字符,因此利用前缀树来求解不仅速度快而且空间复杂度也比较好。
①定义前缀树结构

 class TrieNode{
private TrieNode[] links;

private boolean isEnd;

private final int R=26;

private TrieNode root;

/** Initialize your data structure here. */
public TrieNode() {
    links=new TrieNode[R];
}

public boolean isContainsKey(char ch){
    return links[ch-'a']!=null;
}
public TrieNode get(char ch){
    return links[ch-'a'];
}
public  void put(char ch,TrieNode node){
    links[ch-'a']=node;
}
public void setEnd(){
    isEnd=true;
}
public boolean isEnd(){
    return isEnd;
}
 }

②建立前缀树

public class Trie {

private TrieNode root;

public Trie(){
    root=new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
    TrieNode node=root;
    for(int i=0;i<word.length();i++){
        char currentword=word.charAt(i);
        if(!node.isContainsKey(currentword)){
            node.put(currentword,new TrieNode());
        }
        node=node.get(currentword);
    }
    node.setEnd();
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
    TrieNode node=searchPrefix(word);
    return node!=null&&node.isEnd();
}
private TrieNode searchPrefix(String word){
    TrieNode  node=root;
    for(int i=0;i<word.length();i++){
        char curLetter=word.charAt(i);
        if(node.isContainsKey(curLetter)){
            node=node.get(curLetter);
        }else{
            return null;
        }
    }
    return node;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
    TrieNode node=searchPrefix(prefix);
    return node!=null;
  }
12-25 05:33