-
2021-11-14 22:31:36
字典树的节点结构:
class tritree: def __init__(self): self.dicts={} self.isWord=False
将一个单词加入到字典树,首先我们看这个单词当前字母是否在当前节点的字典中,若不在则生成一个节点,让它对应当前字母,即是将当前字母加入到当前节点的字典中,然后进入下一个节点,若当前字母在当前节点的字典中,则直接进入到下一个节点,当单词遍历完毕,将isWord标记置为True,表示单词存在:
def insert(word, treeNode): for s in word: if s not in treeNode.dicts: treeNode.dicts[s]=tritree() treeNode=treeNode.dicts[s] treeNode.isWord=True
根据前缀查找单词,如前查找,当前缀中的当前字母不在当前节点的字典中时,说明当前字典树不存在该前缀的单词,直接返回空,若前缀查找完毕,那么对于剩下的部分直接进行dfs即可(dfs写的有点丑陋),一旦遇到isWord为True则加入到列表中:
def dfs(nodes,strs): ret=[] if nodes.isWord == True: ret.append(strs) for s,v in nodes.dicts.items(): tmp=strs tmp+=s ret.extend(dfs(nodes.dicts[s],tmp)) return ret def serch(prefix, treeNode): ret, strs = [], '' for s in prefix: if s not in treeNode.dicts: return [] strs += s treeNode = treeNode.dicts[s] ret=dfs(treeNode, strs) return ret
运行效果:
obj=tritree() insert("apple",obj) insert("app",obj) print(serch("aps",obj)) #[] insert("appppppple",obj) print(serch("ap",obj)) #['app', 'apple', 'appppppple']
更多相关内容 -
Python实现简单字典树的方法
2020-09-21 16:35:37主要介绍了Python实现简单字典树的方法,实例分析了Python字典树的定义、实现与使用技巧,需要的朋友可以参考下 -
一棵Java字典树(trie)和它的增删改查
2021-01-20 02:16:42一棵用List来存储子结点的字典树——当然,也可以用哈希表等形式存储。 这篇笔记记录了构建思路,文末是源码 一、构建思路 Step1 设计结点——数据结构 Step2 实现相应的操作方法——增删改查 Step1 设计结点 我们... -
字典树_字典树_
2021-10-03 06:35:54字典树代码dictionary,包含数据结构和测试例程。 -
Trie树_字典树(字符串排序)简介及实现
2020-10-26 02:50:14有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n) -
Trie树(字典树)的介绍及Java实现
2020-08-31 12:36:52Trie树,又称字典树或前缀树,关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处。下面这篇文章主要介绍了Trie树,以及Java实现如何Trie树,有需要的朋友可以参考借鉴,下面来一起看看吧... -
详解字典树Trie结构及其Python代码实现
2021-01-21 17:29:10字典树(Trie)可以保存一些字符串->值的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串。 Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间... -
哈希表与字典树原理入门
2018-06-24 14:06:21数据结构中介绍hash表与trie树的原理,图文并茂,一看就懂 -
Python数据结构与算法之字典树实现方法示例
2020-12-25 06:13:16本文实例讲述了Python数据结构与算法之字典树实现方法。分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该... -
字典树_英汉词典
2018-05-19 08:01:46字典树,文档,增删改,排序,输出字典所有单词及意思 -
PHP字典树(Trie树)定义与实现方法示例
2020-10-19 03:44:58主要介绍了PHP字典树(Trie树)定义与实现方法,简单描述了字典树的概念并结合实例形式分析了字典树的定义与使用方法,需要的朋友可以参考下 -
深度优先遍历字典树(统计单词出现的个数)
2019-04-14 01:00:17NULL 博文链接:https://128kj.iteye.com/blog/1734260 -
字典树的基本知识及使用C语言的相关实现
2020-09-03 11:01:07主要介绍了字典树的基本知识及使用C语言的相关实现,这也是ACM等计算机考试和竞赛题目的基本知识,需要的朋友可以参考下 -
基于Java链表实现的字典树(trie)
2020-05-02 18:41:30基于Java链表实现的字典树(trie),实现了增删改查等功能,它说摘要必须大于50字我还能说啥啥啥啥 -
可变长数组和字典树
2018-09-27 08:43:09可变长数组和字典树Java代码实现。比较容易复制和学习。 -
acm 算法 字典树模板
2018-05-29 14:04:33acm字典树模板!acm字典树模板!acm字典树模板!acm字典树模板! -
Java集合扩展系列 | 字典树
2022-04-03 12:29:201、什么是字典树 如下图就是一颗字典树, 这是往树里插入字符串 he、she、hers、his、shy 生成的树 特点 字典树又名前缀树 和 单词查找树, 每个字符串的公共前缀都将作为一个字符节点保存。 它本质是一颗多叉树...1、什么是字典树
如下图就是一颗字典树, 这是往树里插入字符串
he
、she
、hers
、his
、shy
生成的树特点
-
字典树又名
前缀树
和单词查找树
, 每个字符串的公共前缀都将作为一个字符节点保存。 -
它本质是一颗多叉树, 除了根节点, 每个节点只存放一个字符, 从根节点到某一
绿色节点
,路径上经过的字符连接起来,就是该节点对应的字符串。- 比如 从根节点root到 8号节点 经过的路径连接起来就是一个插入的字符串
his
- 比如 从根节点root到 8号节点 经过的路径连接起来就是一个插入的字符串
2、字典树能做什么
核心是空间换时间,
优点是
利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的,查询的时间复杂度仅与搜索的字符串的长度有关
,即时间复杂度为O(len)
, 而普通二分搜索树的时间复杂度为O(logN), 缺点是比较耗空间
, 毕竟以前一个节点可以存放一整个字符串,现在只能存放一个字符, 虽然可以通过修改为压缩字典树
, 但同时也增加了维护成本常见应用场景
词频统计
- 如果不需要用到字典树的其他特性,还是用哈希表好,毕竟时间复杂度接近O(1), 而且字典树比较耗空间
前缀匹配
- 通讯录前缀匹配
- 浏览器搜索提示匹配,自动补全
字符串搜索
- 在一个字符串集合, 判断是否存在某一个字符串
其他数据结构扩展
- 如后缀树,压缩字典树、三分搜索树、AC自动机
3、代码实现
/** * 字典树 * @author burukeyou */ public class Trie { // 树节点 @Data @EqualsAndHashCode class Node { //当前节点表示的字符 public Character name; // 子节点列表 Map<子节点字符,子节点> public TreeMap<Character,Node> next; // 是否表示一个单词的结尾 public boolean isWordEnd; // 前缀经过这个节点的字符的数量 public int prefixCount; // 父节点 private Node parent; public Node(boolean isWordEnd) { this(null,isWordEnd,0); } public Node(Character name, boolean isWordEnd, int prefixCount) { this.name = name; this.isWordEnd = isWordEnd; this.prefixCount = prefixCount; this.next = new TreeMap<>(); } public Node(Character name, boolean isWordEnd, int prefixCount, Node parent) { this(name,isWordEnd,prefixCount); this.parent = parent; } } // 根节点 private Node root; //字典树中单词的个数 private int size; public Trie() { this.root = new Node(false); this.size = 0; } /** * 添加单词word - 先将字符串拆成每个字符, 然后每个字符作为一个节点依次从上往下插入即可。 生成的树的路径结构刚好就是字符串字符的顺序。 */ public void add(String word){ // Node cur = this.root; for (char key : word.toCharArray()) { //cur节点的子节点们不存在该字符,则直接插入该子节点即可 if(!cur.next.containsKey(key)){ cur.next.put(key,new Node(key,false,1,cur)); }else{ // 存在相同前缀, 前缀数量+1 cur.next.get(key).prefixCount++; } // 更新指针 cur = cur.next.get(key); } // 此时 cur指针指向一个单词的最后一个字符节点,如果这个节点还不是表示一个单词结尾,则标记它 if (!cur.isWordEnd){ cur.isWordEnd = true; this.size++; } } /** * 删除单词 先向下搜索到此字符串的最后一个子节点。 如果字符串不存在则无需删除。 如果存在, 则看是不是 叶子节点, 如果不是叶子节点直接把节点的单词标记位清除即可。 如果是叶子节点, 则一直往上搜索是标记单词的节点 或者 是被使用过的节点就停止搜索(说明从该节点开始是无需删除的), 然后从直接删除该节点下的要被删除的子节点即可。 */ public void remove(String word){ Node node = getPrefixLastNode(word); if (node == null || !node.isWordEnd){ System.out.println("单词不存在"); return; } // 如果不是叶子节点直接把单词标记去掉即可 if (!node.next.isEmpty()){ node.isWordEnd = false; }else{ // 往上找到是标记单词的 或者 被使用过的节点 就停止 Node pre = node; //指向需要被删除的子树的第一个节点 node = node.parent; // 当前迭代指针 while (node != null && !node.isWordEnd && node.prefixCount <= 1){ pre = node; node = node.parent; } // 删除节点node的子节点pre.name if (node != null){ node.next.remove(pre.name); } } // 更新 从 root -> node路径上所有节点的 prefixCount 减1 while(node != null){ node.prefixCount--; node = node.parent; } } /** * 广度遍历 */ public void bfsTraverse() { Queue<Node> queue = new ArrayDeque<>(); queue.offer(this.root); // 上一层的最后一个节点 Node preLayerLastNode = this.root; // 本层最后一个节点 Node curLayerLastNode = this.root; int curLayer = 0; // 当前层数 while(!queue.isEmpty()){ Node tmp = queue.remove(); if (curLayer != 0){ System.out.print(tmp.name +"("+ tmp.prefixCount+"-" + tmp.isWordEnd + ")" + "\t"); } TreeMap<Character, Node> treeMap = tmp.next; if (treeMap != null && !treeMap.isEmpty()){ List<Node> arrayList = new ArrayList<>(treeMap.values()); queue.addAll(arrayList); if (!arrayList.isEmpty()){ curLayerLastNode = arrayList.get(arrayList.size()-1); } } //遍历到每一层的末尾就进行换行 if (preLayerLastNode.equals(tmp)){ curLayer++; preLayerLastNode = curLayerLastNode; System.out.print("\n" + curLayer + "| "); } } } /** * 查询单词word是否在Trie中 按照word每个字符顺序向下搜索即可 */ public boolean contains(String word) { Node node = getPrefixLastNode(word); return node != null && node.isWordEnd; } /** * 查询是否在Trie中有单词以prefix为前缀 * @param prefix 前缀 按照prefix每个字符顺序向下搜索即可 */ public boolean hasPrefix(String prefix){ return getPrefixLastNode(prefix) != null; } /** * 是否包含某个模式的单词。 如 a..b. .可代表任意单词 * 见: leetcode: 211. 添加与搜索单词 */ public boolean containPatternWord(String word) { return match(root, word, 0); } // 从 Node 开始搜索 单词word的[index, 结尾]部分 private boolean match(Node node, String word, int index){ if(index == word.length()) return node.isWordEnd; char c = word.charAt(index); if(c != '.'){ if(node.next.get(c) == null) return false; return match(node.next.get(c), word, index + 1); } else{ for(char nextChar: node.next.keySet()) if(match(node.next.get(nextChar), word, index + 1)) return true; return false; } } /** * 查找前缀为prefix的所有单词 */ public List<String> searchPrefix(String prefix) { Node cur = getPrefixLastNode(prefix); // 从这个节点往下深搜 List<String> paths = new ArrayList<>(); dfsSearchAllPath(cur,paths,prefix); return paths; } /** * 从节点开始深搜每条路径 * @param node 起始节点 * @param paths 保存结果的路径 * @param curPath 当前搜索的路径 */ private void dfsSearchAllPath(Node node, List<String> paths, String curPath) { if (node == null || node.next.isEmpty()) { paths.add(curPath); return; } for (Node child : node.next.values()) { dfsSearchAllPath(child,paths,curPath + child.name); } } /** * 词频统计 * 获取前缀prefix的数量 */ public int getPrefixCount(String prefix){ Node node = getPrefixLastNode(prefix); return node != null ? node.prefixCount : 0; } // 获取前缀表示的最后一个节点 private Node getPrefixLastNode(String prefix){ // 往下搜每个字符节点,能搜到结尾即代表存在并返回 Node cur = root; for (char key : prefix.toCharArray()) { if(!cur.next.containsKey(key)) return null; cur = cur.next.get(key); } return cur; } /** * 搜索模式串 */ public List<String> search(String patternWord){ // 去除空格特殊字符之类 patternWord = patternWord .replaceAll("\s*","") .replaceAll("((?=[\x21-\x7e]+)[^A-Za-z0-9])[\x21-\x7e]+[^A-Za-z0-9]",""); List<String> paths = new ArrayList<>(); dfsSearchAllPatternPath(root,patternWord,0,paths,""); return paths; } /** * 深搜每条路径, 如果路径经过 word就保存起来 * @param node 当前处理的节点 * @param patternWord 搜索的模式串 * @param index 当前搜索的模式串中的字符的下标 * @param paths 保存结果 * @param curPath 当前搜索的路径 */ private void dfsSearchAllPatternPath(Node node, String patternWord, int index, List<String> paths, String curPath){ if (node == null) { return; } if (node.isWordEnd && patternWord.length() == index){ paths.add(curPath); } for (Node child : node.next.values()) { int tmpIndex = index; if (tmpIndex < patternWord.length() && patternWord.charAt(tmpIndex) == child.name){ tmpIndex++; } dfsSearchAllPatternPath(child,patternWord,tmpIndex,paths,curPath + child.name); } } }
4、快速开始
4.1 生成字典树
Trie trie = new Trie(); // 添加词库 trie.add("这个杀手冷静"); trie.add("冷静的杀手"); trie.add("杀手冷静"); trie.add("杀手百度云"); trie.add("杀手冷静点说的什么"); trie.add("杀手冷静成本"); trie.add("这个杀手不太冷静完整版在线观看"); trie.add("这个杀手不太冷静电影"); trie.add("这个杀手不太冷静是什么意思"); trie.add("这个杀手不太冷静电影"); trie.add("这个杀手不太冷静迅雷下载"); trie.add("这个杀手不太冷静百度网盘"); trie.add("豆瓣这个杀手不太冷静"); trie.add("这个杀手不太冷静"); trie.add("这个杀手不太冷静"); trie.add("这个诅咒太棒了"); trie.add("这个杀手不太冷静"); trie.add("极其安静的顶尖杀手"); trie.add("这个杀手不冷漠"); trie.add("最冷酷的杀手"); trie.add("一个极其安静的顶尖杀手");
4.2 树广度遍历
也叫层序遍历, 原理就是通过队列去维护遍历的顺序, 如遍历第一层后, 下一次要遍历的就是第二层, 所以把第二层的元素都添加到队列。
trie.bfsTraverse();
结果如下:
- 冷(1-false)表示一个节点, 存放的字符是冷, 前缀词频是1, fasle表示不是一个单词的结尾
1| 一(1-false) 冷(1-false) 最(1-false) 杀(4-false) 极(1-false) 豆(1-false) 这(12-false) 2| 个(1-false) 静(1-false) 冷(1-false) 手(4-false) 其(1-false) 瓣(1-false) 个(12-false) 3| 极(1-false) 的(1-false) 酷(1-false) 冷(3-false) 百(1-false) 安(1-false) 这(1-false) 杀(11-false) 诅(1-false) 4| 其(1-false) 杀(1-false) 的(1-false) 静(3-true) 度(1-false) 静(1-false) 个(1-false) 手(11-false) 咒(1-false) 5| 安(1-false) 手(1-true) 杀(1-false) 成(1-false) 点(1-false) 云(1-true) 的(1-false) 杀(1-false) 不(10-false) 冷(1-false) 太(1-false) 6| 静(1-false) 手(1-true) 本(1-true) 说(1-false) 顶(1-false) 手(1-false) 冷(1-false) 太(9-false) 静(1-true) 棒(1-false) 7| 的(1-false) 的(1-false) 尖(1-false) 不(1-false) 漠(1-true) 冷(9-false) 了(1-true) 8| 顶(1-false) 什(1-false) 杀(1-false) 太(1-false) 静(9-true) 9| 尖(1-false) 么(1-true) 手(1-true) 冷(1-false) 完(1-false) 是(1-false) 电(2-false) 百(1-false) 迅(1-false) 10| 杀(1-false) 静(1-true) 整(1-false) 什(1-false) 影(2-true) 度(1-false) 雷(1-false) 11| 手(1-true) 版(1-false) 么(1-false) 网(1-false) 下(1-false) 12| 在(1-false) 意(1-false) 盘(1-true) 载(1-true) 13| 线(1-false) 思(1-true) 14| 观(1-false) 15| 看(1-true) 16|
4.3 搜索前缀匹配
如上图通过我们输入前缀这个,就会提示后面可以输入的所有单词如, 这时可以用前缀匹配, 先搜索到前缀的最后一个节点, 然后从该节点开始DFS深搜每条路径,找到所有符合的单词
// 搜索前缀为 “这个”的所有单词 List<String> searchPrefix = trie.searchPrefix("这个"); for (String prefix : searchPrefix) { System.out.println(prefix); }
结果:
这个杀手不冷漠 这个杀手不太冷静完整版在线观看 这个杀手不太冷静是什么意思 这个杀手不太冷静电影 这个杀手不太冷静百度网盘 这个杀手不太冷静迅雷下载 这个杀手冷静 这个诅咒太棒了
4.4 搜索单词提示
如上图, 我们搜索 两个关键字 杀手冷静, 将包含这四个字符的并且顺序一致的所有单词搜索出来。 原理也是用DFS深搜每条路径, 但是只把包含搜索字符的路径保存下来// 搜索单词杀手冷静 List<String> tmpList = trie.search("杀手冷静"); for (String tmp : tmpList) { System.out.println(tmp); }
结果:
杀手冷静 杀手冷静成本 杀手冷静点说的什么 豆瓣这个杀手不太冷静 这个杀手不太冷静 这个杀手不太冷静完整版在线观看 这个杀手不太冷静是什么意思 这个杀手不太冷静电影 这个杀手不太冷静百度网盘 这个杀手不太冷静迅雷下载 这个杀手冷静
4.5 前缀词频统计
由于在添加的时候就维护了前缀的数量, 所以搜索到单词最后一个节点后直接获取词频即可。
int prefixCount = trie.getPrefixCount(""); List<String> tmp = trie.search("杀手冷静"); for (String name : tmp) { int prefixCount = trie.getPrefixCount(name); System.out.println("关键字: "+ name + ", 前缀搜索次数: " + prefixCount); }
结果:
关键字: 杀手冷静, 前缀搜索次数: 3 关键字: 杀手冷静成本, 前缀搜索次数: 1 关键字: 杀手冷静点说的什么, 前缀搜索次数: 1 关键字: 豆瓣这个杀手不太冷静, 前缀搜索次数: 1 关键字: 这个杀手不太冷静, 前缀搜索次数: 9 关键字: 这个杀手不太冷静完整版在线观看, 前缀搜索次数: 1 关键字: 这个杀手不太冷静是什么意思, 前缀搜索次数: 1 关键字: 这个杀手不太冷静电影, 前缀搜索次数: 2 关键字: 这个杀手不太冷静百度网盘, 前缀搜索次数: 1 关键字: 这个杀手不太冷静迅雷下载, 前缀搜索次数: 1 关键字: 这个杀手冷静, 前缀搜索次数: 1
-
-
C语言字典树创建和搜索示例
2018-10-30 20:44:59一种C语言字典树创建和搜索的示例,可以创建一种无论增加多少单词,搜索速度依然 = 该语言字母数 * 单词长度 的效率的存储结构。一个demo -
字典树 —— 字符串分析算法
2020-11-19 08:10:23再比如说大家做搜索关键词,或者相同的字符串搜索类型的情况,很多时候我们就会需要用到类似字典树这样的一个结构 KMP 在长字符串里找模式(部分匹配) 它跟字典树最大的区别就是字典树是检查两个字符串是否完全匹配...这里我们继续来编程训练,在《前端进阶》这个系列里面我们已经讲过一些字符串的算法了。然后这篇文章我们就来一起学习,剩下的几个字符串中比较细节的算法。
字符串分析算法
在开始之前我们先来看看字符串算法的一个整体目录。这里我们从简单到难的算法来排列,大概就分成这样一个顺序:
- 字典树
- 大量高重复字符串的储存与分析(完全匹配)
- 比如说我们要处理 1 亿个字符串,这里面有多少出现频率前 50 的这样的字符串,1 亿这个量我们还是可以用字典树去处理的
- 再比如说大家做搜索关键词,或者相同的字符串搜索类型的情况,很多时候我们就会需要用到类似字典树这样的一个结构
- KMP
- 在长字符串里找模式(部分匹配)
- 它跟字典树最大的区别就是字典树是检查两个字符串是否完全匹配,而 KMP 是两个字符串中,一个字符串是两一个字符串的一部分,但是这个就会出现一个更为复杂的问题。
- 如果我们有一个长度为
m
的字符串和一个长度为n
的字符串,然后让他们两个互相匹配,这个时候我们有两种匹配方法 - 第一种就是暴力
破解法
,它可能是m
乘以n
的时间复杂度,显然这个算法的性能在大量的搜索字符的时候是不行的 - 所以后面几位计算机专家研究出了 KMP 算法,而 KMP 就是三个人的名字的首字母,
K
是高德纳,一个著名的写计算机程序设计的老爷子。加上另外两个计算机专家共同发明了 KMP 算法。这个算法就是在一个长字符串里面匹配一个短字符串,这个匹配算法的复杂度可以降到m + n
。所以这个算法还是非常的厉害的。
- Wildcard
- 在 KMP 的基础上加了通配符的字符串模式
- 通配符包括
问号
表示匹配任意字符,星号
表示匹配任意数量的任意字符 - 在我们做一些文件查找的时候可能就会运用到
Wildcard
的这种通配符 - 我们也可以理解它为一个弱一点的正则表达式,因为相比正则它只有两种通配符,并且这些通配符与正则有一个显著的区别,就是 Wildcard 其实也是可以在
O(n)
或者O(m+n)
的时间复杂度内去处理的。这个现象是因为 Wildcard 当中有一个贪心算法,也是它非常神奇的原因。
- 正则
- 正则一般来说都是需要用到回溯的一个系统
- 它可以说是字符串通用模式匹配的终极版本
- 状态机
- 通用的字符串分析
- 与正则表达式相比,状态机会更强大
- 正则表达式与有限状态机在理论上是完全等价的两种东西
- 但是有限状态机不同的是,我们还可以往里面嵌代码,还可以给字符串做而外的处理
- 另外就是正则写起来很方便,有限状态机写起来成本比较高
- LL LR
- 在简单的匹配和分析的基础上,如果我们要对字符串建立多层级的结构,我们就会使用 LL 和 LR 这样的语法分析的算法
- LL 在上一篇文章我们已经学习过了,但是
LR
是还没有的,实际上 LR 是一个比 LL 更强大的一个语法分析 - 但是通常我们简单写,就都用 LL 去写,因为 LR 它 的理论性比较强
- 如果同学们还记得的话,我们在讲解 HTML 的语法分析的时候,我们用了一个
stack
去处理,这个其实就是 LR 算法的一个简化版。它其实是LR(0)
的语法,但是一般来说我们去处理都会用LR(1)
,而LR(1)
是相等于LL(n)
的这样一种非常强大的分析算法。
字典树
首先我们先了解字典树到底是一个什么东西。我们平时遇到不懂得字都会去查字典对不对?那么我去查字典的时候,我们往往会根据单词的第一个字母(一般是拼音首字母)作为索引去找到这个字大概在那一页,这里用到的就是字典序。
然后如果我们把这种索引寻找方法不断地重复。当我们找好了第一个字母之后,我们再去看它的第二个字母是属于字典中的哪一个部分,最后把这些一路找过来的
线索
变成一个树形的结构。换一句话说也可以理解为 “查字典的行为变成一个树形的结构”。——而这个树形结构就是我们的字典树了
,字典树有一个英文的名字叫 “Trie
”。例子分析
接下来我们举个例子:
比如说现在我们有这 4 个字符串
[ '3499' '0015' '0002' '0007' ]
这里它们都是等长的,不过不等长也没有关系的,等一下我们再来了解为什么。那么如果我们用字典树来保存这个 4 个字符串,因给怎么保存呢?
第一层
我们首先来看所有字符串的第一个字母,它们的第一个字母只有0
和3
这两种字符,所以我们字典树的第一层就会分成3
和0
两个分支。
第二层
接下来我们看看第二层,这里有4
和0
两种字符的分支。我们可以看到第一个字符串,4
的前面是3
,并且在这个位置没有出现4
前面是另外一种字符的情况。所以这里我们就可以把
4
放到上一个3
的分支之下,然后0
也是一样,前一个字符都是 0,所以放在我们的0
的分支之下。(这里听的有点蒙不要紧,到了最后看着动画里面的效果来理解,就会更加明确了。)
第三层
0
后面的分支,发生了一个变化,第二行的0
后面出现了一个1
,然后第一行的4
后面又有一个9
。所以说我们最后出来的字典树,在
4
的后面产生了一个9
的分支,并且在0
的分支上会产生了1
、0
两个分支。
第四层
同理,在第四层这里
0
的后面出现了2
和7
这两种情况,而1
后面出现了5
这一种情况。最后的9
后面再次出现了 9,所以我们只需要再追加一个9
的分支即可。
最后我们来看看整个字典树的生成过程!
代码实现
接下来我们看看在代码中,可以如何实现这棵字典树,以及看看字典树有什么样的应用场景。
首先我们来讨论一下字典树的存储机制,这里我们会用一个
空对象
来保存字典树里面的值。因为我们字典树在实际场景里面就是一段字符串所以说我们会用一个对象来作为字典树的节点。当然如果大家愿意的话,用
Map
也是可以的,Object
和Map
就是在 JavaScript 中最适合用来保存字典树里面的分支这种数据结构的。因为字典树里面只会存字符串,所以说用对象还是 Map 没有本质的区别。
Constructor 构造方法
首先我们来加入一个
Trie
类,然后实现一个构建函数constructor()
,这里为了干净我们就选择使用Object.create(null)
来创建这个字符串。这样也可以避免受到Object.prototype
原型上的一些污染。(不过因为我们每次存的是一个字符,也不存在污染的问题,但是这个写法是一个好的习惯,能干净还是尽量干净。)class Trie { /** 构建函数 **/ constructor() { this.root = Object.create(null); } }
Insert 添加树节点方法
接下来我们需要编写一个
insert()
方法,这个方法的作用就是把一个字符串插入字典树里面。这个插入逻辑其实很简单,我们去设一个变量
node
(也就是一个节点) ,一开始让这个节点等于我们的root
(这里的root
就是我们树结构的根节点
) 。然后我们就从root
根节点,逐级地把字符串放进这个树的子树节点里面去。这里如果我们的主树不存在的话,我们就先创建主树,然后我们再让
node
到下一个层级去(相当于我们在查字典的时候,翻到对应的字母的位置)。最后我们要注意的是,字符串是会有大量的重复的。比如我们的
ab
和abc
其实它是两个不同的字符串,所以说ab
后边我们要有一个截止符。这个截止符我们就用$
来表示。其实这里我们用
$
符是不合适的,因为如果我们的字符串本身就支持$
这个内容的话,这样就会出问题了。所以说其实一个更好的方案就是我们使用Symbol()
来创建一个 Symbol
。这里我们可以使用 Symbol 来处理,这样就不会和我们字符里面的 $ 符号冲突了。使用了 Symbol 的这种
不可重复
的特点,那么我们就可以让 node 节点最后的截止符更加严谨一些。这里就讲完
insert()
方法的逻辑思路了,接下来我们看看代码:/** 创建 $ 唯一的截止符 symbol **/ let $ = Symbol('$'); class Trie { /** 构建函数 **/ constructor() { this.root = Object.create(null); } /** * 添加树节点 * @param {String} word 字符 */ insert(word) { let node = this.root; for (let c of word) { if (!node[c]) node[c] = Object.create(null); node = node[c]; } if (!($ in node)) node[$] = 0; node[$]++; } }
randomWord 随机单词
这里我们做一个
randomWord()
函数,这个函数会产生一个随机的单词。然后结合我们的字典树,我们就可以轻易的分析一些字符的数据,比如说 “出现最多的单词” 之类的逻辑。不多说,先点个赞!
这里我们来看看这个函数的实现代码:
function randomWord(length) { var s = ''; for (let i = 0; i < length; i++) { s += String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0)); } return s; }
这里面的
String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0))
这一行代码做了什么呢?其实就是在 26 个字母的字符集里面随机拿一个字母出来,因为最大是 26 个,所以我们从字符a
开始随机往后加入随机数
* 26,这样我们就可以得到一个随机的数,并且这个数是在 0 - 26 之间。好,有了这个随机生成单词的方法,我们就可以来生成大量的单词,然后使用我们的
字典树
来实现一个统计分析功能了。这里我们来构建 10 万个随机单词:
let trie = new Trie(); for (let i = 0; i < 100000; i++) { trie.insert(randomWord(4)); }
最后我们放入浏览器执行后,我们可以看到
字典树
就生成好了:这里代表什么呢?如果我们还记得在 “例子分析” 部分讲到的,这里意思就是说我们是有
aaad
、aaag
、aaam
、aaax
、aaaz
这样的一些字符。好,现在我们想实现我们的业务需求,找出出现最多的随机字符串该怎么写呢?
most 统计字符函数
回到我们的
Trie
字典树的类中,加入我们的most()
方法。在我们的 most 方法中,需要去遍历整棵树。在访问这棵树的时候,如果这棵树上没有结束,所以我们需要访问这颗树上的每一个单词,那这种情况该怎么办呢?
首先如果我们要统计所有的单词,我们就需要用递归访问整棵树的节点,然后再访问的同时记录每一个单词的出现次数。但是我们这里是一棵字典树,不是整个单词的数组集合,所以我们需要在树中找到每个字符结束的位置,并且记录这个单词的全部字母。
要找到单词结束的位置,首先我们看这棵树有没有
$
结束符,如果有$
结束符说明当前的位置就是单词的截止的点,找到了截止的点,我们就可以找max
的节点。但是我们只找到max
的节点不等于我们找到了这个词。所以我们需要在递归函数
visit()
的参数中加入word
参数,这样在我们嵌入这棵树的所有分子的时候,我们都会在这个 word 变量值上追加当前节点的字母,最后整个分支被访问后,叠加出来的就是我们单词的全部字母了!最后我们用一个变量
max
来记录最后这个word
出现的次数,也就是每一个单词出现的次数。听的一脸懵逼了没有?
没听懵的同学,我给你们点个赞,也希望我写的解释可以让大部分的同学听得懂这部分的逻辑。不过要知道要听懂这部分的算法逻辑,必须对 “
数据结构
” 中的 “树
” 有一定的了解。如果没有了解这部分的知识,推荐同学们去补一下这方面的知识。不过就算蒙了,也可以看看代码,可能就突然脑洞大开了呢?!
class Trie { /** 构建函数 **/ constructor() { this.root = Object.create(null); } /** * 添加树节点 * @param {String} word 字符 */ insert(word) { let node = this.root; for (let c of word) { if (!node[c]) node[c] = Object.create(null); node = node[c]; } if (!($ in node)) node[$] = 0; node[$]++; } /** 统计最高频单词 */ most() { let max = 0; // 出现总次数 let maxWord = null; // 单词 /** * 访问单词的递归方法 * @param {Object} 节点 * @param {String} 拼接的单词 */ let visit = (node, word) => { // 遇到单词结束符 if (node[$] && node[$] > max) { max = node[$]; maxWord = word; } // 递归树的整个分支 for (let p in node) { visit(node[p], word + p); } }; visit(this.root, ''); console.log(maxWord, max); } }
最后我们在
console
中执行trie.most()
就会输出我们出现频率最高的单词:这里我们看到
maek
这个字符在 10 万个随机单词中出现了最多次,一共是 5 次。在 26 的 4 次方的单词量中,其实这个数还是蛮大的。
等等,26 的 4 次方?这个是什么?如果我们回去看看我们随机生成单词的代码,我们随机生成了
4
个字母的单词,我们一共有 26 个字母,所以 4 个字母的单词一共有多少个组合呢?数学学的好的同学应该知道,在数学中我们可以用可能有的种类数
的 n 次方就是这组合的可能出现的组合数。这里我们是 4 个字母的组合,所以n
就是4
。不知道我讲的是什么,可以去看一下数学中的 “排列与组合” 的理论知识哦。
推荐同学直接点击这个传送门 《 “5 分钟彻底了解排列组合”》
关于这个
Trie
树,我们这里就展示了Trie
去求出现最多的次数的功能。实际上我们通过Trie
树还可以找到字典树中最小、字典树中最大,这样的值。在 1 万以内的量级,我们想在它们中求最大,求最小,不管这个数字有多少个我们都是可以比较方便地去处理的。
这就是字典树在处理大量的输入和字符串类的问题时候的能力。字典树其实他是哈希树的一种特例,这个哈希树在字符串领域里面 ,它最直接的应用的体现就是字典树。如果说我们处理数字,我们就可以用别的哈希算法来构造别的哈希树。因为我们这里不是主要学习算法,主要还是把字符串这一类常见的问题跟同学们一起了解清楚。
大家都学会了吗?学会了的点个赞,没有学会的点个收藏,觉得这些文章非常值得一看的,给我来个三连吧~谢谢!
这一期我们就讲到这里,下一期我们就来一起深入了解以下 KMP 算法的相关知识!
博主开始在B站每天直播学习,早上 06:00 点到晚上 11:30 。 欢迎过来《直播间》一起学习。我们在这里互相监督,互相鼓励,互相努力走上人生学习之路,让学习改变我们生活!
学习的路上,很枯燥,很寂寞,但是希望这样可以给我们彼此带来多一点陪伴,多一点鼓励。我们一起加油吧! (๑ •̀ㅂ•́)و
我是来自《技术银河》的三钻:“学习是为了成长,成长是为了不退步。坚持才能成功,失败只是因为没有坚持。同学们加油哦!下期见!”
推荐专栏
小伙伴们可以查看或者订阅相关的专栏,从而集中阅读相关知识的文章哦。
-
📖 《前端进阶》 — 这里包含的文章学习内容需要我们拥有 1-2 年前端开发经验后,选择让自己升级到高级前端工程师的学习内容(这里学习的内容是对应阿里 P6 级别的内容)。
-
📖 《数据结构与算法》 — 到了如今,如果想成为一个高级开发工程师或者进入大厂,不论岗位是前端、后端还是AI,算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师,前提面试就需要考算法。
-
📖 《FCC前端集训营》 — 根据FreeCodeCamp的学习课程,一起深入浅出学习前端。稳固前端知识,一起在FreeCodeCamp获得证书
-
📖 《前端星球》 — 以实战为线索,深入浅出前端多维度的知识点。内含有多方面的前端知识文章,带领不懂前端的童鞋一起学习前端,在前端开发路上童鞋一起燃起心中那团火🔥
- 字典树
-
字典树练习 POJ 1056
2019-04-13 01:45:22NULL 博文链接:https://128kj.iteye.com/blog/1733777 -
数据结构 trie树(字典树)
2022-04-05 16:16:095.trie树(字典树) 参考自leedcode宫水三叶姐姐和bilibili极客学院老师的思想 (1) 字典树的数据结构 字典树,即tire树,又称单词树或键树,是一种树形结构。 典型应用是用于统计和排序大量的字符串,所以常被应用...5.trie树(字典树)
文章目录
参考自leedcode宫水三叶姐姐和bilibili极客学院老师的思想
(1) 字典树的数据结构
字典树,即tire树,又称单词树或键树,是一种树形结构。
典型应用是用于统计和排序大量的字符串,所以常被应用来作为搜索引擎系统的文本词频统计。
优点:最大限度地减少无谓的字符串比较,查询效率比哈希表高
(2) 字典树的核心思想
利用了字母的公共前缀,进行查找操作的时候,每次只需找到下一个字母的存储地址即可。
(3)字典树的基本性质
(1)结点本身不存完整单词
(2)从根结点到某一结点,路径上经过的字符连接起来,为该结点对应的字符串。
(3)每个结点的所有自己诶单路径代表的字符都不相同
1) 通过二维数组来构建trie树
public class Trie { int N = (int)1e5+9; int[][] trie; int[] count; int index; public Trie() { trie = new int[N][26]; count = new int[N]; index = 0; } public void insert(String s) { int p = 0; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(trie[p][u] == 0) trie[p][u] = ++index; p = trie[p][u]; } count[p] ++; } public boolean search(String s) { int p = 0; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(trie[p][u] == 0) return false; p = trie[p][u]; } return count[p] != 0; } public boolean startsWith(String s) { int p = 0; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(trie[p][u] == 0) return false; p = trie[p][u]; } return true; } }
这是其中一种写法,以二维数组来巧妙的代替了链表。根据公共前缀来判断是否需要将index++来使用新的一行数组空间。
构建过程:构造函数将数组进行初始化,将index置为0,0行数组即为跟
insert函数:若插入一个单词,如‘hi’,找第0行中 h-‘a’的存储空间,看看是否已经有了c这个公共前缀,若没有,链接新的一行数组,让第0行中的[h - ‘a’]指向新一行数组的下标,此时index是1,我们要继续插入‘i’找1行中的[i - ‘a’]是否为0,若为0,则表示无此公共前缀,链接新的一行数组,让第1行的[i - ‘a’]指向新的一行数组下标,此时为2,已经将hi单词插入完毕,但是此时2行数组的所有空间全为0,即是说,叶子结点是没有存任何数据的,此时我们同时对第2行的count[2]数组进行 ++,表示此处有该单词,而不只是公共前缀。
search函数:同insert函数过程,如果可以遍历完单词的每个字母,且判断count[p]不为0,即存在该单词。
searchWith函数:和search函数唯一不同点在于,最后不用判断count[p]是不是为0,如果前面过程理解了,这一步也就好理解了,因为如果只是公共前缀的话,count[p] 是不是0不影响返回true or false,只要能保证不在遍历每个字母过程中遇到0返回false就行。
时间复杂度:Trie数的每次调用时间复杂度取决于入参字符串的长度,复杂度为O(len)
空间复杂度:二维数组的高度为n,字符集大小为k,复杂度为O(nk)
2)trie树的常规构造过程
随着数据的不断插入,根据需要不断创建TrieNode结点
package dataStructure_Tree; public class Trie { class TrieNode { boolean end; TrieNode[] tns = new TrieNode[26]; } TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String s) { TrieNode p = root; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(p.tns[u] == null) p.tns[u] = new TrieNode(); p = p.tns[u]; } p.end = true; } public boolean search(String s) { TrieNode p = root; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(p.tns[u] == null) return false; p = p.tns[u]; } return p.end; } public boolean startsWith(String s) { TrieNode p = root; for(int i = 0; i < s.length(); ++i) { int u = s.charAt(i) - 'a'; if(p.tns[u] == null) return false; p = p.tns[u]; } return true; } }
后面总结引用leedcode宫水姐姐的总结。
3)两种方式的对比
常用的方法更方便我们去理解,但二维数组巧用不用每次都去new一个对象,只需要在一开始预估好数组要开多大的空间便可,但是我们需要去估算一个行数,即二维数组开多少行,估多会导致内存开销过大,估小会导致数组越界。
同时还有另一个问题,OJ每测试一个样例会创建一个Trie对象,那这么说的话,内存就会大量浪费,此时我们可以将Trie里的数组设置为静态(static)即可,通过构造函数每次将数组中的数据进行重置。
有coding:
class Trie { // 以下 static 成员独一份,被创建的多个 Trie 共用 static int N = 100009; // 直接设置为十万级 static int[][] trie = new int[N][26]; static int[] count = new int[N]; static int index = 0; // 在构造方法中完成重置 static 成员数组的操作 // 这样做的目的是为减少 new 操作(无论有多少测试数据,上述 static 成员只会被 new 一次) public Trie() { for (int row = index; row >= 0; row--) { Arrays.fill(trie[row], 0); } Arrays.fill(count, 0); index = 0; } public void insert(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) trie[p][u] = ++index; p = trie[p][u]; } count[p]++; } public boolean search(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) return false; p = trie[p][u]; } return count[p] != 0; } public boolean startsWith(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) return false; p = trie[p][u]; } return true; } }
关于「二维数组」是如何工作 & 1e5 大小的估算
要搞懂为什么行数估算是 1e5,首先要搞清楚「二维数组」是如何工作的。在「二维数组」中,我们是通过 indexindex 自增来控制使用了多少行的。
当我们有一个新的字符需要记录,我们会将 indexindex 自增(代表用到了新的一行),然后将这新行的下标记录到当前某个前缀的格子中。
举个🌰,假设我们先插入字符串 abc 这时候,前面三行会被占掉。
第 0 行 a 所对应的下标有值,值为 1,代表前缀 a 后面接的字符串会被记录在下标为 1 的行内
第 1 行 b 所对应的下标有值,值为 2,代表前缀 ab 后面接的字符串会被记录在下标为 2 的行内
第 2 行 c 所对应的下标有值,值为 3,代表前缀 abc 后面接的字符串会被记录在下标为 3 的行内
当再插入 abcl 的时候,这时候会先定位到 abl 的前缀行(第 3 行),将 l 的下标更新为 4,代表 abcl 被加入前缀树,并且前缀 abcl 接下来会用到第 4 行进行记录。
但当插入 abl 的时候,则会定位到 ab 的前缀行(第 2 行),然后将 l 的下标更新为 5,代表 abl 被加入前缀树,并且前缀 abl 接下来会使用第 5 行进行记录。
当搞清楚了「二维数组」是如何工作之后,我们就能开始估算会用到多少行了,调用次数为 104,传入的字符串长度为 103
,假设每一次的调用都是 insertinsert,并且每一次调用都会使用到新的 103行。那么我们的行数需要开到 107 。但由于我们的字符集大小只有 26,因此不太可能在 104
次调用中都用到新的 103行。而且正常的测试数据应该是 searchsearch 和 startsWithstartsWith 调用次数大于 insertinsert 才有意义的,一个只有 insertinsert 调用的测试数据,任何实现方案都能 AC。
因此我设定了 105为行数估算,当然直接开到 106也没有问题。
作者:AC_OIer
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。首先,在纯算法领域,前缀树算是一种较为常用的数据结构。不过如果在工程中,不考虑前缀匹配的话,基本上使用 hash 就能满足。
如果考虑前缀匹配的话,工程也不会使用 Trie 。
一方面是字符集大小不好确定(题目只考虑 26 个字母,字符集大小限制在较小的 26 内)因此可以使用 Trie,但是工程一般兼容各种字符集,一旦字符集大小很大的话,Trie 将会带来很大的空间浪费。
另外,对于个别的超长字符 Trie 会进一步变深。
这时候如果 Trie 是存储在硬盘中,Trie 结构过深带来的影响是多次随机 IO,随机 IO 是成本很高的操作。
同时 Trie 的特殊结构,也会为分布式存储将会带来困难。
因此在工程领域中 Trie 的应用面不广。
至于一些诸如「联想输入」、「模糊匹配」、「全文检索」的典型场景在工程主要是通过 ES (ElasticSearch) 解决的。
而 ES 的实现则主要是依靠「倒排索引」。
作者:AC_OIer
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 -
字典树的实现与应用
2021-05-21 10:55:39字典树概念 字典树(TrieTree),又称单词查找树或键树。字典树的基本特性,根节点是不包含信息的,根节点到叶子节点之间的信息连接起来就是数据的所有信息,每个节点子节点的信息时不一样的。 2.字典树java实现 先... -
字典树的实现
2012-03-06 23:26:48字典树的实现 -
字典树的C++实现
2022-03-17 15:45:04一、字典树——Trie 字典树(前缀树)是一种特殊的多叉树,其结点设计与多叉树有所不同。 多叉树一般长这样: struct TreeNode{ int val; vector<TreeNode*> chlidren; } 而字典树的结点,假设包含了... -
字典树实例--java实现
2019-04-23 01:49:48NULL 博文链接:https://709002341.iteye.com/blog/2260944 -
[力扣刷题总结](字典树篇)
2022-01-02 17:48:17文章目录字典树字典树的概念字典树的功能字典树的实现及代码实现208. 实现 Trie (前缀树)解法1:实现Trie472. 连接词解法1:字典树+DFS820. 单词的压缩编码解法1:字典树 字典树 字典树的概念 本小节主要参考参考... -
Trie 字典树 Objective-c 算法实现
2019-03-18 02:19:55NULL 博文链接:https://auauau.iteye.com/blog/675645