首页 > 其他分享 >前缀树的设计与实现

前缀树的设计与实现

时间:2022-09-01 19:11:50浏览次数:69  
标签:word 前缀 实现 str 字符串 设计 public cur

前缀树的设计与实现

作者:Grey

原文地址:

博客园:前缀树的设计与实现

CSDN:前缀树的设计与实现

前缀树即字典树,可以利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。

我们使用搜索引擎的时候,输入 test,后面会自动显示一堆前缀是 test 的东西。这就利用了前缀树结构来实现。

比如我们有一堆字符串

["Trie","apple", "insert","apple", "search", "app","search", "startsWith", "insert", "search"]

问题1.查询字符串列表里面是否有以appapx为前缀的字符串。

问题2.查询字符串列表里面有没有insertserac这两个字符串。

我们可以把字符串列表构造成一棵前缀树,如下图

image

头节点是空串,路径表示字符,节点表示一个字符串的前缀(简称 p 节点),黑色节点表示一个字符串的结尾位置(简称 e 节点)。

有了如上结构,针对问题1,判断是否存在app前缀的字符串,流程如下

头节点开始,先看有没有走向a的路径,有,则移动指针往a的路径走,
然后判断是否有走向p的路径,有,则移动指针往p的路径走,
然后判断是否有走向p的路径,有,则移动指针往p的路径走,

则存在以app为前缀的字符串。

同理,回到头节点,继续判断apx,发现到没有到x的路径,则直接返回不存在以apx为前缀的字符串。

针对问题2,判断是否有insert这个字符串,流程和判断前缀的流程一样,只不过到了末尾位置,判断是否是黑色节点,如果是黑色节点,说明存在这样的字符串,否则不存在。

更进一步,前缀树也可以支持加入元素和删除元素,此时,我们需要在 p 节点和 e 节点记录一个出现次数的信息,如上例,记录次数后,前缀树如下图

image

如果要删除一个apple字符串,前缀树在apple的路径上依次减一即可

image

如果要继续增加一个apx字符串,前缀树继续建出apx的路径即可。

image

依据上述流程,我们可以用 Hash 表实现前缀树,代码如下

import java.util.HashMap;

public class Code_0030_TrieTree {

    public static class Node2 {
        // 某个节点经历了几次
        public int pass;
        // 某个节点是否是结尾位置
        public int end;
        // 是否有走向某个节点的路
        public HashMap<Integer, Node2> nexts;

        public Node2() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    public static class Trie2 {
        private Node2 root;

        public Trie2() {
            root = new Node2();
        }

        public void insert(String word) {
            if (word == null || word.length() < 1) {
                return;
            }
            char[] str = word.toCharArray();
            Node2 cur = root;
            cur.pass++;
            int n = 0;
            for (char v : str) {
                n = v;
                if (!cur.nexts.containsKey(n)) {
                    cur.nexts.put(n, new Node2());
                }
                cur.nexts.get(n).pass++;
                cur = cur.nexts.get(n);
            }
            cur.end++;
        }

        public void delete(String word) {
            if (search(word) == 0) {
                return;
            }
            char[] str = word.toCharArray();
            Node2 cur = root;
            cur.pass--;
            for (char v : str) {
                int n = v;
                if (--cur.nexts.get(n).pass == 0) {
                    cur.nexts.remove(n);
                    return;
                }
                cur = cur.nexts.get(n);
            }
            cur.end--;
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null || word.length() < 1) {
                return 0;
            }
            char[] str = word.toCharArray();
            Node2 cur = root;
            for (char v : str) {
                int n = v;
                if (!cur.nexts.containsKey(n)) {
                    return 0;
                }
                cur = cur.nexts.get(n);
            }
            return cur.end;
        }

        // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null || pre.length() < 1) {
                return 0;
            }
            char[] str = pre.toCharArray();
            Node2 cur = root;
            for (char v : str) {
                int n = v;
                if (!cur.nexts.containsKey(n)) {
                    return 0;
                }
                cur = cur.nexts.get(n);
            }
            return cur.pass;
        }
    }
}

如果字符串只由 26 个英文字母组成,那么前缀树的数据结构可以优化成

        class Node {
            int p;
            int e;
            Node[] nodes = new Node[26];
        }

nodes[0] != null:表示有走向a的路,否则则没有走向a的路;

nodes[1] != null:表示有走向b的路,否则则没有走向b的路;

nodes[2] != null:表示有走向c的路,否则则没有走向c的路;

...

nodes[25] != null:表示有走向z的路,否则则没有走向z的路;

LeetCode 有对应的题目链接:见:LeetCode 208. Implement Trie (Prefix Tree)

完整代码如下

class Trie {
        class Node {
            int p;
            int e;
            Node[] nodes = new Node[26];
        }

        Node root;

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

        public void insert(String word) {
            char[] str = word.toCharArray();
            Node cur = root;
            for (char c : str) {
                cur.p++;
                if (cur.nodes[c - 'a'] == null) {
                    cur.nodes[c - 'a'] = new Node();
                }
                cur = cur.nodes[c - 'a'];
            }
            cur.e++;
        }

        public boolean search(String word) {
            char[] str = word.toCharArray();
            Node cur = root;
            for (char c : str) {
                if (cur.nodes[c - 'a'] == null) {
                    return false;
                }
                cur = cur.nodes[c - 'a'];
            }
            return cur.e != 0;
        }

        public boolean startsWith(String prefix) {
            char[] str = prefix.toCharArray();
            Node cur = root;
            for (char c : str) {
                if (cur.nodes[c - 'a'] == null) {
                    return false;
                }
                cur = cur.nodes[c - 'a'];
            }
            return true;
        }
    }

本文的所有图例见: processon:前缀树的设计和实现

更多

算法和数据结构笔记

标签:word,前缀,实现,str,字符串,设计,public,cur
From: https://www.cnblogs.com/greyzeng/p/16647565.html

相关文章

  • canvas实现图片压缩
    有时候页面上传的图片太大,难以进行图片识别,就需要在传给接口前先做压缩的处理,使用canvas进行图片压缩可以等比例压缩,不会出现失真模糊的情况。/***imgData原图base64*i......
  • js 实现冒泡排序及优化方案
    //冒泡排序//原理就是每一轮循环,将一个最大的值放冒泡到最后//1.每一趟都是比较相邻两个元素,如果后一个元素大于前一个,则交换两个元素//2.第一趟从第一个元素开始......
  • Vector底层实现
    Vector底层实现vector的三个私有成员:_start  记录初始位置 ,_finish 记录有效字符 ,_endofstoage 记录容量大小vector会存储的类型不同,所以要用模版来定......
  • 文本编辑器如何能实现直接粘贴把图片上传到服务器中
    ​这种方法是servlet,编写好在web.xml里配置servlet-class和servlet-mapping即可使用后台(服务端)java服务代码:(上传至ROOT/lqxcPics文件夹下)<%@ page language="java" i......
  • 智能科学与技术 毕业设计 - 选题建议 题目推荐
    项目分享,毕设指导:https://gitee.com/yaa-dc/BJH/blob/master/gg/python/README.md1选题建议以下为学长手动整理的关于智能科学与技术毕设项目,完全可以作为当前较新的......
  • mysql 储存过程 如何使用递归循环来实现sql数据恢复
    CREATEPROCEDURE`relation_update`(inePIDvarchar(100),indeptidint)BEGINDECLAREtuivarchar(100);declarectint;declareiint;DECLAREcur1CURSORFORselect......
  • 4.实现CRUD功能
    1.逆向工程生成代码参考:https://gitee.com/renrenio/renren-generator1.把renren-generator项目加入到webshop项目中2.修改renren-generator项目数据库配置applicatio......
  • 使用Pads设计一个简单模块(二)
    前言上次我们已经把原理图画好了,那么这一次我们要开始设计PCB准备元器件封装首先我们打开PADSlayout,layout是PADS用来做PCB布局的子软件,打开后我们选择文件->新建来先......
  • Java接口自动化测试框架系列(二)表格设计与数据读取
    一、测试系统分析不同系统有不同的接口,通过分析这些接口,提取共同点可以得到不同地区的系统共有的接口。如:登录、登出、用户信息完善等接口二、表格设计  不同列......
  • SPI协议的数据读写实现(spi_slave)
    SPI协议的数据读写实现(spi_slave)  ......