前缀树结构和Java代码实现

冷不防 2022-02-26 18:28 153阅读 0赞

以前在项目中使用过前缀对敏感词进行过滤，现在就详细说一下他的结构和如何实现吧。

**结构的3个基本性质：**  
1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。  
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。  
3. 每个节点的所有子节点包含的字符都不相同。

**前缀的好处：**  
前缀树可以最大限度地减少无谓的字符串比较，查询效率非常高。  
前缀树的核心思想是利用空间换时间，利用字符串的公共前缀来降低查询时间的开销达到提高效率的目的。

**Java代码实现**

/**
     * author: zzw5005
     * date: 2019/1/10 10:24
     */
    
    
    public class Trie {
        private class Node {
            Node[] childs = new Node[26];
            boolean isLeaf;
        }
    
        private Node root = new Node();
    
        public Trie() {
        }
    
        public void insert(String word) {
            insert(word, root);
        }
    
        private void insert(String word, Node node) {
            if (node == null) return;
            if (word.length() == 0) {
                node.isLeaf = true;
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.childs[index] == null) {
                node.childs[index] = new Node();
            }
            insert(word.substring(1), node.childs[index]);
        }
    
        public boolean search(String word) {
            return search(word, root);
        }
    
        private boolean search(String word, Node node) {
            if (node == null) return false;
            if (word.length() == 0) return node.isLeaf;
            int index = indexForChar(word.charAt(0));
            return search(word.substring(1), node.childs[index]);
        }
    
        public boolean startsWith(String prefix) {
            return startWith(prefix, root);
        }
    
        private boolean startWith(String prefix, Node node) {
            if (node == null) return false;
            if (prefix.length() == 0) return true;
            int index = indexForChar(prefix.charAt(0));
            return startWith(prefix.substring(1), node.childs[index]);
        }
    
        private int indexForChar(char c) {
            return c - 'a';
        }
    
        public static void main(String[] args) {
            Trie trie = new Trie();
    
            String[] arr = {"abc","acb","bac","bca","cab","cba"};
    
            for(int i = 0; i < arr.length; i++){
                trie.insert(arr[i]);
            }
    
            for(int i = 0; i < arr.length; i++){
                System.out.println(trie.search(arr[i]));
            }
            System.out.println(trie.search("abd"));
        }
    }