-
前缀树-Trie树
前缀树—Trie树，也叫作“单词查找树”、“字典树”
它属于多叉树结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高
前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发，按照存储字符串的每个字符，创建对应字符路径
存储结果如下
3个基本性质：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符(词组)；
2.从根节点到某一节点，路径上经过的字符(词组)连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。基本操作有：查找、插入和删除, 删除操作不会删除节点
前缀树插入逻辑图如下
前缀树查找逻辑图如下
前缀树删除逻辑
实现逻辑如下
前缀树节点定义////// 前缀树节点 /// public class TrieNode { // 节点存的值 public string value = string.Empty; // 经过该节点的次数 public int passCount = 0; // 以此节点为终点的数量 public int endCount = 0; // 子节点 public Dictionary<string, TrieNode> childMap = new Dictionary<string, TrieNode>(); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
前缀树实现
public class TrieTree { private TrieNode rootNode = null; // 下面代码中处理的字符串是以下划线分割的字符串，如 A_B_C_D public TrieTree() { rootNode = new TrieNode(); } ////// 添加数据 /// /// public void Insert(string msg) { string[] arr = msg.Split('_'); int index = 0; TrieNode node = rootNode; while (index < arr.Length) { string key = arr[index]; TrieNode childNode = null; // 子节点中不包含 key 则创建一个节点添加 if (!node.childMap.TryGetValue(key, out childNode)) { childNode = new TrieNode(); childNode.value = key; childNode.passCount = 0; childNode.endCount = 0; node.childMap[key] = childNode; } // 经过该节点的次数 +1 childNode.passCount++; if (index >= arr.Length - 1) { // 如果是结尾，则结尾数+1 childNode.endCount++; } // 令 node 等于 子节点 node = childNode; ++index; } } /// /// 搜索 /// /// /// public TrieNode Search(string msg) { if (string.IsNullOrEmpty(msg)) { return rootNode; } string[] arr = msg.Split('_'); int index = 0; TrieNode node = rootNode; // 深度优先遍历 while (index < arr.Length) { string key = arr[index]; TrieNode childNode = null; // 子节点中以 key 查找 if (!node.childMap.TryGetValue(key, out childNode)) { break; } // 令 node 等于子节点 node = childNode; ++index; } if (index < arr.Length || node.endCount <= 0) { return null; } return node; } /// /// 删除 msg /// 前缀树不会删除节点，只是修改节点记录的 passCount、endCount /// /// public void Remove(string msg) { TrieNode node = Search(msg); if (null == node) { return; } string[] arr = msg.Split('_'); int index = 0; node = rootNode; while (index < arr.Length) { string key = arr[index]; // 子节点中以 key 查找 if (!node.childMap.TryGetValue(key, out node)) { break; } // 经过该节点的次数 -1 node.passCount--; if (index == arr.Length - 1) { // 如果是结尾，则结尾数 -1 node.endCount--; } ++index; } } /// /// 计算以 msg 为前缀的数量 /// /// /// public int PrefixCount(string msg) { TrieNode node = Search(msg); if (null == node) { return 0; } return node.passCount; } /// /// 计算存储的 msg 个数 /// /// /// public int EndCount(string msg) { TrieNode node = Search(msg); if (null == node) { return 0; } return node.endCount; } /// /// 打印所有前缀为 msg 的信息 /// /// public void PrefixTraverse(string msg) { // 先查找以 msg 为前缀的节点 TrieNode node = Search(msg); if (null == node) { return; } List<string> list = new List<string>(); list.Add(msg); // 遍历 所有子节点 foreach (var childNode in node.childMap.Values) { BackTracing(childNode, list); } } /// /// 回溯的查找所有子节点 /// /// /// private void BackTracing(TrieNode node, List<string> list) { // 将节点的值添加到 list list.Add(node.value); // 如果节点是结尾则，将整个字符串打印出来 if (node.endCount > 0) { string msg = string.Empty; foreach (var value in list) { msg += value; } Console.WriteLine(msg); } // 遍历所有子节点 foreach (var childNode in node.childMap.Values) { // 递归调用回溯算法 BackTracing(childNode, list); } // 将节点的值从 list 中删除 (此为回溯) list.RemoveAt(list.Count - 1); } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
测试代码如下
public class TrieTreeTest { private static TrieTree tree = new TrieTree(); private static List<string> list = new List<string>() { "A_B", "A_B_C_D", "A_B_C_D", "A_B_C_D", "A_B_C_F", "A_B_E", "A_B_E_D", "B_C", "B_C_D", "B_C_E" }; public static void Test() { foreach (var msg in list) { tree.Insert(msg); } TrieNode node = tree.Search("A"); foreach (var msg in list) { int preCount = tree.PrefixCount(msg); int endCount = tree.EndCount(msg); Console.WriteLine(msg + " pre:" + preCount + " end:" + endCount); } Console.WriteLine("=======================\n"); tree.PrefixTraverse(""); Console.WriteLine("=======================\n"); tree.Remove("A_B_C_D"); tree.Remove("A_B_C_D"); tree.Remove("B_C_D"); foreach (var msg in list) { int preCount = tree.PrefixCount(msg); int endCount = tree.EndCount(msg); Console.WriteLine(msg + " pre:" + preCount + " end:" + endCount); } Console.WriteLine("=======================\n"); tree.PrefixTraverse(""); Console.WriteLine("=======================\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
前缀树是一种非常有用的字符串存储结构，它解决了像 HashMap 这种存储结构无法实现的问题——前缀统计，并且由于是复用节点，也很好的节约了存储空间
-
相关阅读:
计算机网络 —— 运输层（TCP三次握手）
02 线程安全问题
Golang开发--计时器（Timer）和定时器（Ticker）
JAVA最全面试题汇总基础篇（一）
车载通信V2X
C++证明四方定理
轻量级网络结构
联邦学习中的优化算法
Linux下找出吃内存的方法
电脑蓝屏怎么办 七大原因及解决办法来帮你
- 原文地址：https://blog.csdn.net/LIQIANGEASTSUN/article/details/133313401
