接做网站单子的网站,做网站要会那些ps,企业网站免费模板,自助搭建网站单模式串匹配 BF 算法和 RK 算法 BM 算法和 KMP 算法多模式串匹配算法 Trie 树和 AC 自动机
一、 什么是“Trie树”#xff1f;
1. 他是一种树形结构#xff0c;是一种专门处理字符串匹配的数据结构#xff0c;解决在一组字符串集合中快速查找某个字符串的问题。
2. Trie…单模式串匹配 BF 算法和 RK 算法 BM 算法和 KMP 算法多模式串匹配算法 Trie 树和 AC 自动机
一、 什么是“Trie树”
1. 他是一种树形结构是一种专门处理字符串匹配的数据结构解决在一组字符串集合中快速查找某个字符串的问题。
2. Trie树的本质是利用字符串之间公共前缀将重复的前缀合并在一起
Trie 树的本质就是利用字符串之间的公共前缀将重复的前缀合并在一起。
howhiherhellososee
其中根节点不包含任何信息每个节点表示一个字符串中的字符从根节点到红色节点的一条路径表示一个字符串红色节点并不都是叶子节点。
3. 查找
当在Trie树中查找一个字符串时如“her”,就将要查找的字符串分割成单个的字符her然后从Trie树的根节点开始匹配。但假若要查找的字符串是“he”用上面同样的方法从根节点开始沿着某条路径来匹配发现路径的最后一个节点“e”不是红色的即“he”是某个字符串的前缀但不能完全匹配任何字符串。
二 、如何实现一课Trie树
1Trie树主要有两个操作一个是将字符串集合构造成Trie树。这个程可分解为
将一个字符串插入到Trie树的过程在Trie树中查询一个字符串
2如何存储一个Trie树
①Trie树是一个多叉树需要存储一个节点的所有子节点的指针。 ②一种经典的存储方式借助散列表额思想通过一个下标与字符一一映射的数组来存储子节点的指针。
class TrieNode {char data;TrieNode children[26];
}借助散列表的思想我们通过一个下标与字符一一映射的数组来存储子节点的指针。 假设字符串中只有从a到z这26个小写字母从数组中下标为0的位置存储指向子节点a的指针下标为1的位置存储指向子节点b的指针以此类推下标为25的位置储存的是指向的子节点z的指针。如果某个字符的子节点不存在就在对应的下标的位置存储null。 当在Trie树中查找字符串的时候就可以通过字符的ASCII码减去“a”的ASCII码迅速找到匹配的子节点的指针。 public class Trie {private TrieNode root new TrieNode(/); // 存储无意义字符// 往Trie树中插入一个字符串public void insert(char[] text) {TrieNode p root;for (int i 0; i text.length; i) {int index text[i] - a;if (p.children[index] null) {TrieNode newNode new TrieNode(text[i]);p.children[index] newNode;}p p.children[index];}p.isEndingChar true;}// 在Trie树中查找一个字符串public boolean find(char[] pattern) {TrieNode p root;for (int i 0; i pattern.length; i) {int index pattern[i] - a;if (p.children[index] null) {return false; // 不存在pattern}p p.children[index];}if (p.isEndingChar false) return false; // 不能完全匹配只是前缀else return true; // 找到pattern}public class TrieNode {public char data;public TrieNode[] children new TrieNode[26];public boolean isEndingChar false;public TrieNode(char data) {this.data data;}}
}3时间复杂度
构建 Trie 树 时间复杂度 O(n)n 表示所有字符串的长度和 在 Trie 树中查找某个字符串的时间复杂度 O(k)k 表示要查找的字符串的长度 在一组字符串中频繁的查询某些字符串用Trie树非常高效。
4Trie树很耗内存吗?
Trie树是使用数组来储存一个节点的子节点的指针的即便一节点只有很少的子节点远小于26个比如23个也要维护一个长度为26的数组。 Trie的本质是避免重复存储一组字符串的相同前缀子串但现在每个字符对应一个节点的存储远远大于1个字节。 如果字符串中不仅包含小写字母还包含大写字母数字甚至是中文那需要的存储空间就更多了。所以在重复前缀并不多的情况下Trie树不但不节省内存还有可能浪费更多的内存。
5Tri树的优化方案 牺牲一点查询的效率将每个节点中的数组换成其他数据结构来存储一个节点指针。如有序数组跳表散列表红黑树等。 假设用有序数组数组中的指针按照指向的子节点中的字符大小顺序排序。查询时可以通过二分查找的方法快速查找到某个字符应该匹配的子节点的指针。 缩点优化就是对只有一个子节点的节点而且此节点不是一个串的结束节点可以将此子节点合并。这样可以节省空间但却增加了编码难度。
三 、Trie数与散列表的红黑树的比较应用与局限
1字符串的匹配问题笼统上讲其实就是数据的查找问题。
2在一组字符串中查找字符串Trie数实际上表现的并不好他对要处理的字符串有极其严苛的要求
第一字符中包含的字符集不能太大如果字符集太大那么存储空间就可能浪费很多。即便优化也要付出牺牲查询插入效率的代价。第二要求字符串的前缀重合比较到不然空间消耗会变大很多。第三如果要用Trie树解决问题就需要自己从零开始实现一个Trie树还要保证没有bug这在工程上是把简单问题复杂化。第四通过指针串起来的数据是不连续的而Trie树用到了指针所以对缓存并不友好。性能上会打个折扣。
综上Trie树不适合精确匹配查找这种问题更适合用散列表或红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。Trie的这个特点可以扩展到更加广泛的一个应用上自动输入补全。比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。
笔记整理来源 王争 数据结构与算法之美
