前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决，但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了，记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。
简介
Trie树百度百科解释如下：又称单词查找树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie树的直观结构如图所示：
图中红色的点代表此处有字符串在此结束，上图中共有7个字符串：abc、abcd、abd、b、bcd、efg、hij（百科中的图，空白边就算作j好了）。
Trie树的使用场景
- 字符串检索，词频统计，搜索引擎的热门查询。
- 字符串最长公共前缀。
- 字符串排序。
- 作为其他数据结构和算法的辅助结构，如后缀树，AC自动机等。
至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现，就算能实现也需要大量的改变。
Trie树的缺陷
Trie树占用内存较大，例如：处理最大长度为20、全部为小写字母的一组字符串，则可能需要 \(26^{20}\) 个节点来保存数据。而这样的树实际上稀疏的十分厉害，可以采用左儿子右兄弟的方式来改善，也可以采用需要多少子节点则添加多少子节点来解决（不要类似网上的示例，每个节点初始化时就申请一个长度为26的数组）。
Wiki上提到了采用三数组Trie(Tripple-Array Trie)和二数组Trie(Double-Array Trie)来解决该问题，此外还有压缩等方式来缓解该问题。
Java代码示例
网上相关的示例很多，但没有可以做到排序、统计词频和获取最长公共前缀的，且都是采用长度为26的数组来保存信息。内存浪费且无法处理带有特殊字符或者数字的字符串。现实现一版没有以上缺点的Java版本。
|
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 |
public class Trie { private TrieNode root; //根节点 public Trie() { this.root = new TrieNode(); } private class TrieNode { //节点类 private int num; //通过的字符串数（包含在此结束的字符串） private int count; //刚好在这里结束的单词数 private Map<Character,TrieNode> son; //记录子节点 TrieNode() { num = 1; count = 0; son = new TreeMap<>(); //TreeMap用于排序 } } public void add(String word) { //在字典树中插入一个字符串 if(StringUtils.isBlank(word)) { return; } TrieNode node = root; char[] letters = word.toCharArray(); for(char c : letters) { if(node.son.containsKey(c)) { node.son.get(c).num++; } else { node.son.put(c, new TrieNode()); } node = node.son.get(c); } node.count++; } public int countWord(String word) { //计算字符串出现的次数 return count(word, false); } public int countPrefix(String prefix) { //计算前缀出现的次数 return count(prefix, true); } public boolean contain(String word) { //是否含有字符串 return count(word, false) > 0; } public int count(String word, boolean isPrefix) { //计算字符串/前缀出现的次数 if(StringUtils.isBlank(word)) return 0; TrieNode node = root; char[] letters = word.toCharArray(); for(char c : letters) { if(node.son.containsKey(c)) node = node.son.get(c); else return 0; } return isPrefix? node.num: node.count; } public Map<String, Integer> getSortedWordsAndCounts() { //获取排序号的字符串和其出现次数 Map<String, Integer> map = new TreeMap<>(); getSortedWordsAndCounts(root, map, StringUtils.EMPTY); return map; } private void getSortedWordsAndCounts(TrieNode node, Map<String, Integer> map, String pre) { for(Map.Entry<Character,TrieNode> e: node.son.entrySet()) { String prefix = pre + e.getKey(); if(e.getValue().count > 0) { map.put(prefix, e.getValue().count); } getSortedWordsAndCounts(e.getValue(), map, prefix); } } public Collection<String> getSortedWords() { //获取排好序的字符串 Collection<String> list = new ArrayList<>(); getSortedWords(root, list, StringUtils.EMPTY); return list; } private void getSortedWords(TrieNode node, Collection<String> list, String pre) { for(Map.Entry<Character,TrieNode> e: node.son.entrySet()) { String prefix = pre + e.getKey(); if(e.getValue().count > 0) { list.add(prefix); } getSortedWords(e.getValue(), list, prefix); } } public String getMaxCommonPrefix() { //获取最大公共前缀 TrieNode node = root; String maxPrefix = StringUtils.EMPTY; while(node.son.size() == 1 && node.count == 0) { for(Map.Entry<Character,TrieNode> e: node.son.entrySet()) { node = e.getValue(); maxPrefix += e.getKey(); } } return maxPrefix; } public static void main(String[] args) { //测试 Trie trie = new Trie(); // trie.add("he"); trie.add("hf"); trie.add("hfz"); trie.add("hfz"); trie.add("hfz"); trie.add("hfzy"); // trie.add("hg"); // trie.add("eh"); // trie.add("eh"); // trie.add("ek"); System.out.println(trie.countWord("hfz")); System.out.println(trie.countPrefix("hfz")); System.out.println(trie.contain("eh")); System.out.println(trie.getSortedWords()); System.out.println(trie.getSortedWordsAndCounts()); System.out.println(trie.getMaxCommonPrefix()); } } |
运行结果：
|
1 2 3 4 5 6 |
3 4 false [hf, hfz, hfzy] {hf=1, hfz=3, hfzy=1} hf |
参考文献
（转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ，请勿用于任何商业用途）
