字典树原理与应用
一、概念
字典树又称单词查找树，Trie树，是一种树形结构，是哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计、搜索联想等。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
二、特点
- 根结点不包含字符，除根节点外每一个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
三、常见操作
查找、插入和删除（很少用到）。
四、实现
代码如下，这段代码实现了字典树的insert以及根据前缀匹配所有字符串的方法。
public class Trie { private TrieNode root; public Trie(){ root = new TrieNode(); } public void insert(String str){ if(str==null||str.length()==0){ return; } TrieNode node = root; char[] allChars = str.toCharArray(); for(int i=0; i<allChars.length; i++){ Character character = new Character(allChars[i]); if (!node.children.containsKey(character)){ node.children.put(character, new TrieNode(character)); } node = node.children.get(character); } node.isEnd = true; } public List<String> matchPrefix(String prefix){ List<String> result = new ArrayList<String>(); if(prefix==null||prefix.length()==0){ return result; } char[] allChars = prefix.toCharArray(); TrieNode node = root; for(int i=0; i<allChars.length; i++){ Character character = new Character(allChars[i]); if(!node.children.containsKey(character)){ return result; }else{ node = node.children.get(character); } } preTraverse(node, prefix, result); return result; } private void preTraverse(TrieNode node, String prefix, List<String> result){ if(!node.children.isEmpty()){ for (Map.Entry<Character, TrieNode> entry: node.children.entrySet()){ if (entry.getValue().isEnd){ result.add(prefix+entry.getKey().toString()); } preTraverse(entry.getValue(), prefix+entry.getKey().toString(), result); } } } private class TrieNode { private Map<Character, TrieNode> children; private boolean isEnd; private Character character; TrieNode(){ children = new HashMap<Character, TrieNode>(); isEnd = false; } TrieNode(Character character){ children = new HashMap<Character, TrieNode>(); isEnd = false; this.character = character; } } }
我们通过一段代码测试一下：
public class MainApp { public static void main(String[] argv){ ArrayList<String> strs = new ArrayList<String>(); strs.add("我爱学习"); strs.add("我爱学"); strs.add("我爱学JAVA"); strs.add("我不爱学习"); strs.add("小明也爱学习"); strs.add("我爱Python"); Trie trie = new Trie(); for(String s: strs){ trie.insert(s); } String prefix = "我爱"; List<String> res = trie.matchPrefix(prefix); System.out.println(res); } }
执行后输出：[我爱Python, 我爱学, 我爱学习, 我爱学JAVA]
五、应用
给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
示例：
输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5]
通过分析，我们可以看出，这道题目标就是保留所有不是其他单词后缀的单词，最后的结果就是这些单词长度加一的总和（因为每个单词编码后后面还需要跟一个 # 符号）。很明显这里需要使用字典表。代码如下：
class Solution { public int minimumLengthEncoding(String[] words) { Trie trie = new Trie(); HashMap<TrieNode, Integer> nodes = new HashMap<TrieNode,Integer>(); for(int k=0; k<words.length; k++){ String s = words[k]; TrieNode node = trie.insert(s); if(node!=null){ nodes.put(node, k); } } int res = 0; for(TrieNode n: nodes.keySet()){ if(n.children.isEmpty()){ res += words[nodes.get(n)].length()+1; } } return res; } } class Trie { TrieNode root; Trie(){ root = new TrieNode(); } TrieNode insert(String str){ if(str==null||str.length()==0){ return null; } TrieNode node = root; char[] allChars = str.toCharArray(); for(int i=allChars.length-1; i>=0; i--){ Character character = new Character(allChars[i]); if (!node.children.containsKey(character)){ node.children.put(character, new TrieNode(character)); } node = node.children.get(character); } node.isEnd = true; return node; } } class TrieNode { Map<Character, TrieNode> children; boolean isEnd; Character character; TrieNode(){ children = new HashMap<Character, TrieNode>(); isEnd = false; } TrieNode(Character character){ children = new HashMap<Character, TrieNode>(); isEnd = false; this.character = character; } }
这里为了方便最后的字符串统计，所以对本文前面提供的字典表代码略作修改，但是整体思路是一样的。
分类: 数据结构与算法
