- 浏览: 122716 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
yingtaier:
[i][4/i]引用-[*]引用---[size=x-larg ...
使用Cxf在中的自定义拦截器来输出日志信息 -
风雨故都:
Page 里面有什么属性
WebService(cxf框架)返回一个包含有map的一个page对象 -
ys20081411:
请问这个乱码和jdk的版本有关系么?我用了你的代码,但是报错了 ...
JSPWiki使用说明书 -
thrillerzw:
哈哈,难啊。
我想找个女朋友,但是不会表白。 -
thrillerzw:
不能 把每带过的地方,只是当成一个路过的地方,从来没有付出过 ...
活在一个有梦想的世界里
举个简单的例子。
给你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/
给你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/
发表评论
-
微信公众账号与网站信息对接
2013-07-10 17:37 8800最近做了一个微信 ... -
原子操作实现并发
2012-06-14 17:02 1172使用synchronized: 使用synchroni ... -
velocity配置与springMVC
2012-06-07 11:30 5212web.xml <?xml version=&quo ... -
activiti使用
2011-07-25 15:25 2416使用activiti报错 Caused by: java.l ... -
Struts2请求乱码问题
2011-05-06 16:25 1035ie6中的bug 在jsp请求Action ... -
软件开发流程图
2011-03-25 11:36 1165自己对软件开发流程理解 -
使用AOP实现异常处理
2011-03-16 15:08 5421@Aspect public class Service ... -
使用Freemarker和Struts2做动态表单
2011-03-01 09:49 4771由于项目中需要用到一个可定制的动态表单功能,管理员可以根 ... -
JSPWiki使用说明书
2010-08-31 16:26 7657在使 ... -
jsp 下载出现乱码和空格问题
2010-08-31 13:21 2153关于中文文件下载的问 ... -
代理服务器的缓存问题
2010-06-24 17:00 1166如果要使用代理服务器时,会出现页面信息串。 处理方法(写一个过 ... -
浅谈Eclipse调用Tomcat服务的原理
2010-06-11 14:23 3281转:http://www.173it.cn/Html/?5 ... -
w3c 中doc生成一个基于hibernate的hbm.xml文件
2010-06-03 13:01 1379package com.gosophia.metadata ... -
如何让eclipse辅助提示struts.xml文件的编写
2010-05-21 19:06 2159一般情况下,如果计算机连接上了internet,eclipse ... -
Eclipse 常用设置
2010-05-21 13:40 855转: http://www.blogjava.net/Todd ... -
Java程序执行原理
2010-05-02 17:10 970<o:p> </o:p>首先 ... -
什么是线程安全
2010-04-30 16:14 890如果你的代码所在 ... -
Servlet的线程安全问题
2010-04-30 15:46 690转:http://zjeers.iteye.com/blog/ ... -
JSR(转)
2010-04-26 13:35 1439J2ME 配置规范 ========= JSR 30 --- ... -
Jpa
2010-04-09 10:20 1903来自:http://www.oracle.com/ ...
相关推荐
Trie树,又称字典树或前缀树,关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处...下面这篇文章主要介绍了Trie树,以及Java实现如何Trie树,有需要的朋友可以参考借鉴,下面来一起看看吧。
基于Java链表实现的字典树(trie),实现了增删改查等功能,它说摘要必须大于50字我还能说啥啥啥啥
java数组 java数组_基于java实现的双数组Trie树
Java实现字典树TrieTree,可用于计算出四六级试题的高频词.
Prefix Trie数据结构的Java实现。 介绍 尝试是类似于基于有序树的数据结构的地图,可快速搜索O(k)的顺序,其中k是键的长度。 阅读有关trie的更多信息。 动机 它最初是为在我的Android应用程序T9 App Launcher中使用...
主要介绍了Java中实现双数组Trie树实例,双数组Trie就是一种优化了空间的Trie树,本文给出了实现代码、测试代码和测试结果,需要的朋友可以参考下
DoubleArrayTrie Java编写的DoubleArrayTrie介绍用法// construct and buildDoubleArrayTrie dat = new DoubleArrayTrie(); for(String word: words) { dat.Insert(word); } System.out.println(dat.Base.length); ...
给定算术表达式的DFA图,利用Java语言构建Trie树,实现对输入文法的判断
在 Java 中实现的并发非阻塞 patricia 树。 此树支持整数键并使用基于边缘的锁定来改进内存和性能。 这是作为德切夫博士在 UCF 的并行算法和编程 (COP4520) 课程的最终项目完成的。 该存储库还包括一篇用 LaTeX 编写...
Java字典树实现。 精简优化版处理。适合Java屏蔽字并进行。进行检测并处理的情况
Java中的Trie和Levenshtein距离混合实现,可实现极快的前缀字符串搜索和字符串相似性。 作者:Umberto Griffo 推特:@UmbertoGriffo内容特里定义Trie [1]是使用字符串作为键的有序树数据结构。 这是一种有效的信息...
一棵用List来存储子结点的字典树——当然,也可以用哈希表等形式存储。 这篇笔记记录了构建思路,文末是源码 一、构建思路 Step1 设计结点——数据结构 Step2 实现相应的操作方法——增删改查 Step1 设计结点 我们...
后缀Trie树的java实现 标签:suffixTrie
字典树(Trie)可以保存一些字符串->值的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都...至于Trie树的实现,可以用数组,也可以用指针动态分配,我做题时为了方便就用了数组,静态分配空间。 Trie树,又称单词
基数树(也称为 patricia trie、radix trie或紧凑前缀树)是一种空间优化的树数据结构,它允许仅使用键的前缀插入键(以及与这些键相关联的可选值)以供后续查找而不是整个密钥。 基数树在字符串或文档索引和扫描...
复杂度 时间复杂度 空间复杂度 线性数据结构动态数组(ArrayList) ...Trie 线性+树形数据结构 集合(HashSet) 映射(HashMap、LinkedHashMap) 二叉堆(BinaryHeap) 优先级队列(PriorityQueue)
实施为Java NavigableMap的自适应基数树 该库基于ICDE 2013“自适应基数树:主存数据库的ARTful索引”,以的形式提供了自适应基数树(ART)的实现。 在有序数据结构的空间中,特别有趣,因为它们的高度和时间...
Java的灵活的实现,提供了与前缀相关的操作的丰富功能。 它实现了接口,并且可以使用任何类型的对象作为键,只要可以通过专门的BitwiseComparator将它们按位进行比较BitwiseComparator 。 与相比,它具有相对的性能...
Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构。 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。 Trie...
使用BinaryTrie的路由方案网络路由方案的实现: 每个路由器都有一个IP地址,并且通过使用二进制特里(trie)的最长前缀匹配将数据包转发到下一跳路由器。 使用斐波那契堆为无向图实现Dijkstra的单一源最短路径(ssp...