Trie 树 及Java实现
来源于英文“retrieval”. Trie树就是字符树,其核心思想就是空间换时间。
举个简单的例子。
给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,第一次出现第几个位置。
这题当然可以用hash来,但是我要介绍的是trie树。在某些方面它的用途更大。比如说对于某一个单词,我要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。
现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了……
假设有b,abc,abd,bcd,abcd,efg,hii这6个单词,我们构建的树就是这样的。
对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。
那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
我们可以看到,trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表,或者用数组来模拟动态。空间的花费,不会超过单词数×单词长度。(转自一大牛)
Trie树的java代码 实现如下:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/** *//**
* A word trie which can only deal with 26 alphabeta letters.
* @author Leeclipse
* @since 2007-11-21
*/
public class Trie{
private Vertex root;//一个Trie树有一个根节点
//内部类
protected class Vertex{//节点类
protected int words;
protected int prefixes;
protected Vertex[] edges;//每个节点包含26个子节点(类型为自身)
Vertex() {
words = 0;
prefixes = 0;
edges = new Vertex[26];
for (int i = 0; i < edges.length; i++) {
edges[i] = null;
}
}
}
public Trie () {
root = new Vertex();
}
/** *//**
* List all words in the Trie.
*
* @return
*/
public List< String> listAllWords() {
List< String> words = new ArrayList< String>();
Vertex[] edges = root.edges;
for (int i = 0; i < edges.length; i++) {
if (edges[i] != null) {
String word = "" + (char)('a' + i);
depthFirstSearchWords(words, edges[i], word);
}
}
return words;
}
/** *//**
* Depth First Search words in the Trie and add them to the List.
*
* @param words
* @param vertex
* @param wordSegment
*/
private void depthFirstSearchWords(List words, Vertex vertex, String wordSegment) {
Vertex[] edges = vertex.edges;
boolean hasChildren = false;
for (int i = 0; i < edges.length; i++) {
if (edges[i] != null) {
hasChildren = true;
String newWord = wordSegment + (char)('a' + i);
depthFirstSearchWords(words, edges[i], newWord);
}
}
if (!hasChildren) {
words.add(wordSegment);
}
}
public int countPrefixes(String prefix) {
return countPrefixes(root, prefix);
}
private int countPrefixes(Vertex vertex, String prefixSegment) {
if (prefixSegment.length() == 0) { //reach the last character of the word
return vertex.prefixes;
}
char c = prefixSegment.charAt(0);
int index = c - 'a';
if (vertex.edges[index] == null) { // the word does NOT exist
return 0;
} else {
return countPrefixes(vertex.edges[index], prefixSegment.substring(1));
}
}
public int countWords(String word) {
return countWords(root, word);
}
private int countWords(Vertex vertex, String wordSegment) {
if (wordSegment.length() == 0) { //reach the last character of the word
return vertex.words;
}
char c = wordSegment.charAt(0);
int index = c - 'a';
if (vertex.edges[index] == null) { // the word does NOT exist
return 0;
} else {
return countWords(vertex.edges[index], wordSegment.substring(1));
}
}
/** *//**
* Add a word to the Trie.
*
* @param word The word to be added.
*/
public void addWord(String word) {
addWord(root, word);
}
/** *//**
* Add the word from the specified vertex.
* @param vertex The specified vertex.
* @param word The word to be added.
*/
private void addWord(Vertex vertex, String word) {
if (word.length() == 0) { //if all characters of the word has been added
vertex.words ++;
} else {
vertex.prefixes ++;
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - 'a';
if (vertex.edges[index] == null) { //if the edge does NOT exist
vertex.edges[index] = new Vertex();
}
addWord(vertex.edges[index], word.substring(1)); //go the the next character
}
}
public static void main(String args[]) //Just used for test
{
Trie trie = new Trie();
trie.addWord("China");
trie.addWord("China");
trie.addWord("China");
trie.addWord("crawl");
trie.addWord("crime");
trie.addWord("ban");
trie.addWord("China");
trie.addWord("english");
trie.addWord("establish");
trie.addWord("eat");
System.out.println(trie.root.prefixes);
System.out.println(trie.root.words);
List< String> list = trie.listAllWords();
Iterator listiterator = list.listIterator();
while(listiterator.hasNext())
{
String s = (String)listiterator.next();
System.out.println(s);
}
int count = trie.countPrefixes("ch");
int count1=trie.countWords("china");
System.out.println("the count of c prefixes:"+count);
System.out.println("the count of china countWords:"+count1);
}
}
运行:
C:\test>java Trie
10
0
ban
china
crawl
crime
eat
english
establish
the count of c prefixes:4
the count of china countWords:4
文章来自:http://oivoiv.blog.163.com/
分享到:
相关推荐
一个简单的C语言程序:用Trie树实现词频统计和单词查询
trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
Trie 树实现的源码,用C++编写实现,做自然语言处理的朋友可以参考一下
很容易上手的Trie树入门,特别适合于acm初学者
基于Trie树模仿谷歌百度搜索框提示。写的比较简单、代码漏洞之处欢迎指正。
通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...
这是一个ACM算法,Trie树,他能很好的解决字符问题
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在...
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
ACM Trie树 模板,字典树模板,数据结构
散列索引多分支Trie树快速路由查找算法路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前 缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度...
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
trie树模板,acm竞赛,可以进行适当的修改就可以解决问题,在进行字符串处理的时候尤其能用到。
hash trie树 字典树,完整的sdk开发包 具有说明文档