Trie树 | 程序员的自我修养 | 关注Java、大数据、机器学习

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了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版本。

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());
	}

}

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("hfzy");

// trie.add("hg");

// 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());

}

运行结果：

3
4
false
[hf, hfz, hfzy]
{hf=1, hfz=3, hfzy=1}
hf

false

[hf, hfz, hfzy]

{hf=1, hfz=3, hfzy=1}

参考文献

Trie

（转载本站文章请注明作者和出处程序员的自我修养 – SelfUp.cn ，请勿用于任何商业用途）

张瑞昌: 有很多，比较常见的是Jacob迭代法，一次迭代O(n^3)，迭代次数不清楚。如果是手动算的话按照定义求就可以了
Anonymous:
lc277: 你好我想问下一般删除节点要多久，要删除的datanode大概用了 1t，解除授权已经30多小时还没完成，请问是出现什么问题了吗麻烦告诉下谢谢 qq1844554123
Anonymous: 你好我想问下一般删除节点要多久，要删除的datanode大概用了 1t，解除授权已经30多小时还没完成，请问是出现什么问题了吗
Anonymous:
李雪璇: 想要完整代码，可以帮忙发给我吗
Anonymous: 请问一下,那个 user的推荐结果楼主查看了么? 为什么输入数据最高是五分,输出结果都是7分8分啥的?怎么设置输出的分数的最大值?
Anonymous: 那个 user的推荐结果楼主查看了么? 为什么输入数据最高是五分,输出结果都是7分8分啥的?
Anonymous: stopGracefullyOnShutdown在yarn- client模式下我测试的无效，你的呢
Anonymous: 另外,import的lib包能否发个列表.
Anonymous: 部分程序已经无法使用, 另外你的import代码也应该放上来哈
wzq: 赞
增达网: 受教了！呵呵！
Anonymous:
27: dsa会报错，rsa不会
Anonymous: 看错了忽略我
Anonymous: UserSideCF这个类在哪里
晴子: 在主节点初始化CM5数据库的时候报错误：Verifying that we can write to /opt/cm-5.9.0/etc/cloudera-scm -server log4j:ERROR Could not...
zhangnew: 就4题
linxh: “ 但要是遇到预先并不知道数组的长度而又需要获取正确的（或者称之为原始的）split长度时，该如何处理呢。。？ ” 印象中可以split函数参数传-1？