likes
comments
collection
share

算法---字典树（前缀树）

作者站长头像
站长
· 阅读数 41

字典树

1、初窥本质

  • 概念

 又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

  • 性质
    • 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
    • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
    • 每个节点的所有子节点包含的字符都不相同。

 在我们刷题的过程中常常会遇见这样的一类的问题，给你一个字符数组求取最长的公共前缀或者是查询所有以当前字符为前缀的字符数量。

 我们可以使用枚举的方式去一个一个的遍历，但是这样不够优雅，这样的问题就可以使用字典树来解决，因为字典树的一条路径上总是存在相同的前缀。

 下面我们简单的来实现一个字典树的结构，以 256 个可见字符作为存储的数据。

算法---字典树（前缀树）

2、结构设计

 2.1、字段属性

 字典树是一个存储使用的数据结构，因此他需要具有存储数据的能力，依旧是说在内部需要拥有一块数据区域来表示，这里使用一个 char 来存储就可以了。

 为了标识当前字符是否是一个完整句子的结尾，需要一个 boolean 来进行表示。

 从当前点往下我们不知道是否还存在有字符或者说是有多少字符以当前路径为前缀，因此需要保存所有往下的路径，也就是说 256 个节点。为了方便后面的方法查询，可以增加一个子节点的标记为来表示是否有以当前路径为前缀的字符串存储在字典树中，如果不存在则为 false ，存在则为 true 。

@Data
public class Trie {
    /**
     * 最大可表示字符种类
     */
    private static final Integer MAX_LEN = 256;
    /**
     * 当前路径是否存在完整字符串
     */
    private boolean isEnd;
    /**
     * 是否存在以当前路径为前缀的字符串
     */
    private boolean hasChild;
    /**
     * 当前节点的实际保存数据
     */
    private Character word;
    /**
     * 当前节点的后续节点数组
     */
    private Trie[] child;

    public Trie(char word) {
        this.isEnd = false;
        this.hasChild = false;
        this.child = new Trie[MAX_LEN];
        this.word = word;
    }
}

 2.2、方法定义

 字典树在应用过程中主要提供两个方法就可以了，一个是提供往当前字典树中添加数据的接口，二是提供外部查询数据的结构（在刷题过程中的查询主要是根据一个字符串来进行相对应的功能判断），这只是功能抽象上的方法，实际的实现需要根据具体的场景来进行，但是大致的思想相似的。

  • insert

    此方法为外界向字典树中添加数据的接口，方法需要一个字符串，字典树内部按照该字符串的序列来进行遍历添加节点，并在最后添加完整路径的标记

    public void insert(String word) {
    Trie trie = this;
    for (char c : word.toCharArray()) {
        if (trie.child[c] == null) {
            trie.child[c] = new Trie(c);
        }
        trie.hasChild = true;
        trie = trie.child[c];
    }
    trie.isEnd = true;
}

  • search

    此方法提供外界查询字典树中是否拥有一个完整字符串的接口或者是进行模糊查询等，方法同样需要一个字符串作为参数，内不按照该参数的序列来进行寻找，如果中途找不到对应的下一个字符则不存在；如果序列完全存在与该字典树中，还需要判断是否是一个完整的字符串，或者是寻找前缀的时候就不用判断了。

    public boolean search(String word) {
    Trie trie = this;
    for (char c : word.toCharArray()) {
        if (trie.child[c] == null) return false;
        trie = trie.child[c];
    }
    return trie.isEnd;
}

3、算法实战

 3.1、单词拆分

 3.2、实现一个魔法字典

 3.3、替换单词

 3.4、最短的单词编码

 3.5、添加与搜索单词 - 数据结构设计

转载自:https://juejin.cn/post/7100823522854830116
评论
请登录