Yinde's Blog

Talk is cheap. Show me the code.

目录
字典树的实现
/  

字典树的实现

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

字典树的运用其实相当常见,我们在浏览器中输入英文单词的时候,一旦发生错误的单词,就会帮你进行提示,事实上,这个过程就可以利用字典树进行快速的查询实现,与此类似的示例还有搜索建议,提前给你可能需要的搜索内容。

当然,这个过程也可以依赖遍历整个字典实现,但是这样的时间复杂度就是O(n)级别的,而前缀树的查找复杂度可以控制在O(L) L = 搜索内容的长度

以下是一颗典型的字典树构造

我们可以观察这棵树的细节,该树的每个节点拥有一个label字段,或者叫prefix也行,标记了这个节点所代表的字符,并且每个节点可以拥有多个子节点,代表从该字符开始,往下连结的字符。

所以一个典型的字典树节点大致有三个属性

  1. label 代表该节点代表的字符
  2. word 从根节点到该节点的路线能够构成一个单词 存放单词的内容(这里面和图里的做法不太相同,图里的做法其实是吧label和word进行了合并, 两种做法其实都可以,看你需求)
  3. children 该节点的所有下沿节点

当然在具体的编程之中,你可以灵活的添加自定义属性,对该算法进行改装,进一步提升性能。

字典树大致可以分为两部分,字典树的构建 字典树的查询

字典树的构建

字典树的构建非常简单,大致步骤如下

假设我们拥有一颗字典树,以及一个即将加入字典树的单词 hello

建立两个基本变量

当前节点 curNode 初始值为根节点
当前子字符 curChar 初始值为 hello 中的第一个字符 h

  1. curNode下的节点 是否有节点label等于curChar的 有>进入步骤2 没有>进入步骤3
  2. 设置curNode 为匹配的node
  3. 新建一个 label = curChar 的新节点 设置新节点为curNode 如果curChar已经到最后一位 设置node的word为 "hello"
  4. curChar继续向下延续 重复上述步骤 直到curChar处理完毕

字典树的插入过程可以被看作是把需要插入到单词,与我们的树形结构建立对应关系的过程。

字典树的查找

字典的查找事实上步骤和插入其实是完全一致的,也是一个深度优先的遍历过程。

同样是从根节点向下查询,每次向下操作都会让curChar向后延续。

查找会有一些特殊情况

  1. 如果我们已经到了叶子节点,curChar还没结尾 说明查找肯定失败了
  2. 如果我们到达了叶子节点 curChar也结束了 但是结尾的label不等于curChar 同样说明失败
  3. 还没到叶子节点 就发生匹配失败了 同样失败

出现上述的错误情况就可以直接结束循环了。

所以其实正确的情况只有一种,curChar已经结尾,并且当前的节点label == curChar

具体的实现

class ArrayStack<T> {
    private ArrayList<T> stack = new ArrayList<T>();

    public void push(T ele) {
        stack.add(ele);
    }

    public T pop() {
        T ele = stack.get(stack.size() - 1);
        stack.remove(stack.size() - 1);
        return ele;
    }

    public Boolean isEmpty() {
        return stack.size() <= 0;
    }
}

/***
 * @deprecated 字典树
 * */
class DictTree {
    private static class TreeNode {
        public ArrayList<TreeNode> children;
        public String word = "";
        public String prefix = "";
        public Boolean isRoot = false;

        TreeNode(String prefix, String word) {
            this.children = new ArrayList<TreeNode>();
            this.word = word;
            this.prefix = prefix;
        }
    }

    public TreeNode root;

    DictTree() {
        this.root = new TreeNode("", "");
        this.root.isRoot = true;
    }

    // 添加一个单词进字典树
    public void add(String word) {
        ArrayStack<TreeNode> stack = new ArrayStack<TreeNode>();
        int wordIndex = 0;
        stack.push(this.root);
        while (!stack.isEmpty() && wordIndex < word.length()) {
            TreeNode node = stack.pop();
            String wordItem = word.substring(wordIndex, wordIndex + 1);
            TreeNode foundNode = null;

            for (TreeNode child : node.children) {
                // 找到匹配 直接结束遍历
                if (child.prefix.equals(wordItem)) {
                    foundNode = child;
                    break;
                }
            }

            // 未找到匹配 手动新建
            if (foundNode == null) {
                String endWord = wordIndex < (word.length() - 1) ? "" : word;
                TreeNode newNode = new TreeNode(wordItem, endWord);
                node.children.add(newNode);
                foundNode = newNode;
            }

            wordIndex++;
            stack.push(foundNode);
        }
    }

    // 在字典树中进行搜索
    public String search(String word) {
        ArrayStack<TreeNode> stack = new ArrayStack<TreeNode>();
        int wordIndex = 0;
        stack.push(this.root);
        String result = "404 Not found";

        // stack.isEmpty() 代表没有找到能和当前 wordItem 匹配的下一个子节点
        // wordIndex < word.length() 代表要搜索的字符已经结尾
        while (!stack.isEmpty() && wordIndex < word.length()) {
            TreeNode node = stack.pop();
            String wordItem = word.substring(wordIndex, wordIndex + 1);

            for (TreeNode child : node.children) {
                if (child.prefix.equals(wordItem)) {
                    // 找到匹配 当前字符正好结尾 && node确实是一个单词 && node.word == word
                    if (wordIndex == word.length() - 1 && child.word.equals(word)) {
                        result = word;
                    } else { /* 继续循环 */
                        stack.push(child);
                        wordIndex++;
                    }
                }
            }
        }

        return result;
    }
}

class Index {

    public static void main(String[] args) throws Exception {
        DictTree dt = new DictTree();
        dt.add("geek");
        dt.add("geometry");
        println(dt.search("good")); // 404 Not Fount
        println(dt.search("geek")); // geek
    }
}

总结

字典树是一种典型的利用空间换时间的算法。

字典树可以被用于,字符串检索,词频统计,热门搜索, 字符串排序等用途。


标题:字典树的实现
作者:zhangzhengyi12
地址:https://blog.yinode.tech/articles/2019/08/09/1567739709922.html

评论