网站建设公司不给ftp,c#如何做公司网站,wordpress插件seo,北京网站空间引言
前缀树——trie /ˈtraɪ//树#xff0c;也叫作“单词查找树”、“字典树”。
它属于多叉树结构#xff0c;典型应用场景是统计、保存大量的字符串#xff0c;经常被搜索引擎系统用于文本词频统计。它的优点是利用字符串的公共前缀来减少查找时间#xff0c;最大限度…引言
前缀树——trie /ˈtraɪ//树也叫作“单词查找树”、“字典树”。
它属于多叉树结构典型应用场景是统计、保存大量的字符串经常被搜索引擎系统用于文本词频统计。它的优点是利用字符串的公共前缀来减少查找时间最大限度的减少无谓字符串的比较和存储空间。 trie 来自于 retrieval 的中间部分。在wiki百科中有关于 trie 一词的由来 Tries were first described by René de la Briandais in 1959.The term trie was coined two years later by Edward Fredkin, who pronounces it /ˈtriː/(as tree), after the middle syllable of retrieval.However, other authors pronounce it/ˈtraɪ/(as try), in an attempt to distinguish it verbally from tree. 一、前缀树的逻辑结构
前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发按照存储字符串的每个字符创建对应字符路径。
由“路径”记载字符串中的字符由节点记载经过的字符数以及结尾字符结尾数例如一个简单的记录了abc、abd、bcf、abcd 这四个字符串的前缀树如下图所示 二、前缀树的添加过程
经典的前缀树都是以“路径”以下简称路记录字符的由节点记录统计信息 pass 代表经过的字符个数end代表有多少个字符串以这条路径结尾。
2.1 逻辑过程
前缀树添加字符串的过程以 abc、bcd、abcd为例
1、首先会有一个初始化的根节点 root : 2、添加 a 字符根节点 pass , 由于字符串还没有结束后面还有 b、cend 不变并在路的另一端创建一个节点因为两个节点才能形成一条路并将新节点的 passend 同样不变 3、添加 b 字符同样创建一个新的节点来表示 b 的路并在新节点上 passend不变 4、添加c 字符创建一个新的节点表示 c 的路在新节点上 pass此时字符串已经结束end 到此为止就完成了abc字符串的添加以同样的方法添加 bcd、abcd注意每次添加都要从 root 开始root 作为前缀树的第一个节点其 pass 可以表示树中一共存储了多少字符串。前缀树的最大特点就是复用字符如果从 root 没有可复用的前缀那么就需要创建新的路径如果有就需要复用已有路径并标记经过的字符个数 2.2 代码实现
前缀树的路是一种抽象结构无法用具体的代码直接描述在代码中基于最简单的小写英文的前缀树通常就是以一个数组表示 26 个字母的通道以每个通道是否存在 Node 节点来表示到达这个Node节点的路是否存在
private static class Node {public int pass;public int end;public Node[] nexts;public Node() {pass 0;end 0;// 26种可能nexts new Node[26];}
}
那么添加的过程就是
public class Code01_TrieTree {private Node root;public Code01_TrieTree() {root new Node();}private static class Node {// ...}public void insert(String word) {if (word null)return;char[] chars word.toCharArray();Node node root;// 以 root 出发node.pass;// 初始化路径int path 0;// 遍历字符数组for (int i 0; i chars.length; i) {// 26个槽位与26个字母对应a-0字符相减就可以获得路径的偏移量path chars[i] - a;// 计算出偏移量后判断是否存在节点如果是 null 表示不存在这条路径if (node.nexts[path] null)node.nexts[path] new Node();// 指针移动到路径的尾节点node node.nexts[path];// 路径的尾节点passnode.pass;}// 遍历完成后node一定就是最后一个路径的尾节点此时记录结尾数量node.end;}
}
三、前缀树的查找
前缀树有两种常用查找第一种是最普通的字符串出现的次数第二种是某个字符串前缀出现的次数。
3.1 指定字符串出现次数
前缀树的查找思路是先获取到 root 引用由此出发。
遍历整个字符串如果在遍历途中发现某个路径不存在即路径的尾节点null则表示前缀树从未存储过该字符串。
经过遍历后节点指针一定会来到最后一个字符路径的尾节点这个节点的 end 记录了总共有多少个字符串以这个字符路径结尾所以直接返回 end 即可代码如下
public int search(String word) {if (word null)return 0;char[] chars word.toCharArray();// 由 root出发的节点指针Node node root;// 初始化路径int path 0;// 遍历字符串for (int i 0; i chars.length; i) {// 计算路径偏移path chars[i] - a;// 路径不存在表示该字符串不存在if (node.nexts[path] null)return 0;// 移动节点指针node node.nexts[path];}// 遍历结束后节点指针来到字符串的尾节点直接返回end统计值return node.end;
}
3.2 指定前缀出现次数
前缀查找统计的逻辑和字符串查找的逻辑几乎完全一样唯一不同的是在最后返回时返回的是字符串尾节点的 pass 值它代表有多少个字符串经过了这个节点。
public int searchPre(String pre) {if (pre null) return 0;Node node root;char[] chars pre.toCharArray();int path 0;for (int i 0; i chars.length; i) {path chars[i] - a;if (node.nexts[path] null) {return 0;}node node.nexts[path];}return node.pass;
}
四、前缀树的删除
前缀树的删除逻辑主体结构和插入、查找相同都是遍历参数字符串在途径的节点上分别 count down pass 和end 两个变量。
需要注意的两个点
1、在开始执行真正的删除逻辑之前一定要先调用 search 方法判断是否存在该字符串。
2、如果 node 的pass 属性-1 后是0那么需要将节点引用置为 null以便回收内存同时也契合 insert、search等逻辑中 判断路径是否存在的方式。
public void delete(String word) {if (search(word) 0)return;char[] chars word.toCharArray();Node node root;// 根节点 -1node.pass--;int path 0;// 遍历字符串for (int i 0; i chars.length; i) {// 计算路径偏移path chars[i] - a;// 如果路径的尾节点 pass-1 后为 0将这个尾节点置为 null直接返回if (--node.nexts[path].pass 0) {node.nexts[path] null;return;}// 移动节点指针node node.nexts[path];}// 遍历后沿途的 pass 都已经 -1最后 end - 1node.end--;
}
五、以HashMap描述路径的前缀树
数组的适用场景较为局限由于数组本身扩容不便在实际的前缀树实现上往往可以用HashMap作为路径的替代这种方式还可以实现中文字符的存储。
public class Code02_TrieTree {private Node root;public Code02_TrieTree() {this.root new Node();}private static class Node {public int pass;public int end;public HashMapInteger, Node nexts;public Node() {this.pass 0;this.end 0;this.nexts new HashMap();}}public void insert(String word) {if (word null || .equals(word)) return;char[] chars word.toCharArray();Node node root;node.pass;Integer path 0;for (int i 0; i chars.length; i) {// 以字符的ASCII码作为路径path (int) chars[i];if (!node.nexts.containsKey(path))node.nexts.put(path, new Node());node node.nexts.get(path);node.pass;}node.end;}public int search(String word) {if (word null || .equals(word)) return 0;char[] chars word.toCharArray();Node node root;Integer path 0;for (int i 0; i chars.length; i) {// 计算路径path (int) chars[i];if (node.nexts.get(path) null)return 0;node node.nexts.get(path);}return node.end;}public int searchPre(String pre) {if (pre null || .equals(pre)) return 0;char[] chars pre.toCharArray();Node node root;Integer path 0;for (int i 0; i chars.length; i) {path (int) chars[i];if (node.nexts.get(path) null)return 0;node node.nexts.get(path);}return node.pass;}public void delete(String word) {if (search(word) 0) return;char[] chars word.toCharArray();Node node root;node.pass--;Integer path 0;for (int i 0; i chars.length; i) {path (int) chars[i];if (--node.nexts.get(path).pass 0) {node.nexts.remove(path);return;}node node.nexts.get(path);}node.end--;}public int size() {return root.pass;}
}
六、前缀的时间复杂度
如果一个字符串长度为 k那么插入前缀树需要的时间就是 O(k)。
因为每个字符都需要比较一遍在比较和计算路径的逻辑中不论是数组实现的方式还是HashMap实现的方式其路径的计算前者是使用相减得到的偏移量后者是 containsKey 的 hashcode计算都是常数时间复杂度。
而其余的代码步骤也都是常数时间复杂度因此整个insert的过程就是 O(k)。
而查找的时间复杂度同样是 O(k)依然取决于字符串长度。
总结
前缀树是一种非常有用的字符串存储结构它解决了像 HashMap 这种存储结构无法实现的问题——前缀统计并且由于是复用节点也很好的节约了存储空间。
它的增删逻辑是遍历参数字符串找到对应路径如果没有则创建节点。
路径是以节点是否存在的形式来抽象表示的。
在删除字符串的时候一定要先判断是否存在该字符串以免造成误操作途经节点的 pass属性。
对于 pass 属性 -1后为0此时可以将这个节点置为null并直接返回这是因为 pass 如果 0就表明 end 一定0反之 end 0pass 不一定 0。
插入、查询的大体流程是
由根节点出发通过参数中的每个字符计算 path 路径判断路径是否存在如果是添加操作就创建节点如果是查询操作就根据情况判断是否要直接返回结果。
