随笔记录

算法-前缀树（单词查找树）

2022-4-15 diaba 算法

package code;

/**
 * 前缀树(单词查找树)
 * 是一种树形结构; 用于保存大量的字符串。
 * 优点：利用字符串的公共前缀来节约存储空间。
 * 字母放在路径上，节点上存储到该节点的字符数pass以及以该节点为终点的字符数end
 *
 * @Author jiucaiyuan  2022/4/15 23:30
 * @mail services@jiucaiyuan.net
 */

public class TrieTree {

    public static class TrieNode {
        /**
         * 到该路径的次数
         */
        public int pass;
        /**
         * 以该路径为结尾的次数
         */
        public int end;
        /**
         * 当前节点到字符x的路径是否有
         * 如果有，则路径是nexts['x'-'a'] != null，具体次数是nexts['x'-'a'].pass，作为结果的次数为nexts['x'-'a'].end
         * 如果没有，则路径是nexts['x'-'a'] == null
         * 【注意】
         * 1.如果字符不只是a~z，特别多，可以用 `HashMap<Char,Node> nexts` 类型来表示
         * 2.如果需要下游路是有序组织的，可以使用`TreeMap<Char,Node> nexts`有序表来表示
         */
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            //nexts[0] == null,表示没有走向`a`的路
            //nexts[0] != null,表示有走向`a`的路
            //...
            //nexts[25] != null,表示有走向`z`的路
            nexts = new TrieNode[26];
        }
    }

    public static class Trie {
        /**
         * root.pass 表示加入前缀树树中单词（字符串）个数
         * root.end 表示加入前缀树中空字符串的个数
         * node.pass 表示加入到前缀树中以root到当前字符的字符串为前缀的字符串个数
         * node.end 表示加入到前缀树中以root到当前字符的字符串的个数
         */
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        /**
         * 向前缀树中加入单词 （实现只支持小写字母a~z组成的单词）
         *
         * @param word
         */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            node.pass++;
            int index = 0;
            //从左往右遍历字符
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';  //由字符，对应成走哪天路
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }
                //经过某条路时，边的to节点node记录经过信息
                node = node.nexts[index];
                node.pass++;
            }
            //加完该字符串后，结尾数累加1
            node.end++;
        }

        /**
         * 删除前缀树中某个字符串
         *
         * @param word
         */
        public void delete(String word) {
            if (search(word) == 0) {  //确定在树中，再进行删除操作
                return;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            node.pass--;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (--node.nexts[index].pass == 0) {
                    node.nexts[index] = null;  //如果删除此字符串后，没有通过了，设置为null
                    return;
                }
                node = node.nexts[index];
            }
            node.end--;
        }

        /**
         * 搜索字符串，返回该字符串之前加入过几次
         *
         * @param word
         * @return
         */
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            //从左往右遍历字符
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';  //由字符，对应成走哪条路
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            //找到最后一个字符，返回该路径为结尾的次数
            return node.end;
        }

        /**
         * 加入的字符串当中，有几个是以prefix字符串为前缀的
         *
         * @param prefix
         * @return
         */
        public int prefixNumber(String prefix) {
            if (prefix == null) {
                return 0;
            }
            char[] chs = prefix.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';  //由字符，对应成走哪条路
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            //找到最后一个字符，返回该路径通过的次数
            return node.pass;
        }
    }
}