- 浏览: 718143 次
- 性别:
- 来自: 嘉兴
文章分类
- 全部博客 (386)
- Struts1.1 (2)
- Database (18)
- Core Java (15)
- Log4j (4)
- SSH (0)
- Dao (1)
- Architecture Design (1)
- References (2)
- Eclipse&MyEclipse (10)
- Hibernate (7)
- Spring (8)
- JavaMail (1)
- Data Structure And Algorithm (48)
- Struts 2 (2)
- SSI (1)
- SSL (2)
- JSTL (1)
- EJB3 (2)
- NET (2)
- XML (2)
- Components (2)
- Ant (3)
- Multi Thread (1)
- Performance Monitoring (1)
- Web Server (17)
- Oracle (1)
- jQuery (8)
- Regular Expression (1)
- Weblogic (1)
- Exception (1)
- Security (2)
- File Manipulation (1)
- JavaScript (12)
- JVM (2)
- HTML&DIV&CSS (4)
- Android (10)
- Beyond GFW (0)
- Business (0)
- SVN (6)
- 虚拟主机 (1)
- Virtual Host (3)
- My mentality (5)
- OS (15)
- ISPMP (3)
- Magento (5)
- Jsoup&HttpClient (7)
- LINUX (9)
- Database Design (0)
- Power Designer (1)
- TaobaoOpenPlatform (2)
- C/C++ (3)
- Maven (11)
- Quartz (1)
- Load Balance (1)
- Zabbix (4)
- Product&Business (1)
- Pay Interface (1)
- Tomcat (2)
- Redis (1)
- 集群 (1)
- Session (1)
- 共享Session (1)
- Jedis (1)
- jenkins (1)
- 持续集成 (1)
- Web前端 (1)
最新评论
-
aqq331325797:
特意注册账号上来说一句。牛逼!
swagger2.2.2 与 spring cloud feign冲突 -
KitGavinx:
跨顶级域名怎么保持sessionid一致?
Tomcat7集群共享Session 基于redis进行统一管理 -
jaychang:
dujianqiao 写道HI ,能否给一个完整的demo 啊 ...
淘宝订单同步方案 - 丢单终结者 -
GGGGeek:
找了一会儿,感觉mybatis应该没有这种操作,直到发现博主的 ...
mybatis collection list string -
dujianqiao:
HI ,能否给一个完整的demo 啊 ?
淘宝订单同步方案 - 丢单终结者
来源于英文“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.List; /** * 单词查找树 * * @author Jay Chang * @since 2012-06-13 */ class Trie { /** 单词查找树根节点,根节点为一个空的节点 */ private Vertex root = new Vertex(); /** 单词查找树的节点(内部类) */ private class Vertex { /** 单词出现次数统计 */ int wordCount; /** 以某个前缀开头的单词,它的出现次数 */ int prefixCount; /** 子节点用数组表示 */ Vertex[] vertexs = new Vertex[26]; /** * 树节点的构造函数 */ public Vertex() { wordCount = 0; prefixCount = 0; } } /** * 单词查找树构造函数 */ public Trie() { } /** * 向单词查找树添加一个新单词 * * @param word * 单词 */ public void addWord(String word) { addWord(root, word.toLowerCase()); } /** * 向单词查找树添加一个新单词 * * @param root * 单词查找树节点 * @param word * 单词 */ private void addWord(Vertex vertex, String word) { if (word.length() == 0) { vertex.wordCount++; } else if (word.length() > 0) { vertex.prefixCount++; char c = word.charAt(0); int index = c - 'a'; if (null == vertex.vertexs[index]) { vertex.vertexs[index] = new Vertex(); } addWord(vertex.vertexs[index], word.substring(1)); } } /** * 统计某个单词出现次数 * * @param word * 单词 * @return 出现次数 */ public int countWord(String word) { return countWord(root, word); } /** * 统计某个单词出现次数 * * @param root * 单词查找树节点 * @param word * 单词 * @return 出现次数 */ private int countWord(Vertex vertex, String word) { if (word.length() == 0) { return vertex.wordCount; } else { char c = word.charAt(0); int index = c - 'a'; if (null == vertex.vertexs[index]) { return 0; } else { return countWord(vertex.vertexs[index], word.substring(1)); } } } /** * 统计以某个前缀开始的单词,它的出现次数 * * @param word * 前缀 * @return 出现次数 */ public int countPrefix(String word) { return countPrefix(root, word); } /** * 统计以某个前缀开始的单词,它的出现次数(前缀本身不算在内) * * @param root * 单词查找树节点 * @param word * 前缀 * @return 出现次数 */ private int countPrefix(Vertex vertex, String prefixSegment) { if (prefixSegment.length() == 0) { return vertex.prefixCount; } else { char c = prefixSegment.charAt(0); int index = c - 'a'; if (null == vertex.vertexs[index]) { return 0; } else { return countPrefix(vertex.vertexs[index], prefixSegment.substring(1)); } } } /** * 调用深度递归算法得到所有单词 * @return 单词集合 */ public List<String> listAllWords() { List<String> allWords = new ArrayList<String>(); return depthSearchWords(allWords, root, ""); } /** * 递归生成所有单词 * @param allWords 单词集合 * @param vertex 单词查找树的节点 * @param wordSegment 单词片段 * @return 单词集合 */ private List<String> depthSearchWords(List<String> allWords, Vertex vertex, String wordSegment) { Vertex[] vertexs = vertex.vertexs; for (int i = 0; i < vertexs.length; i++) { if (null != vertexs[i]) { if (vertexs[i].wordCount > 0) { allWords.add(wordSegment + (char)(i + 'a')); if(vertexs[i].prefixCount > 0){ depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a')); } } else { depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a')); } } } return allWords; } } public class Main { public static void main(String[] args) { Trie trie = new Trie(); trie.addWord("abc"); trie.addWord("abcd"); trie.addWord("abcde"); trie.addWord("abcdef"); System.out.println(trie.countPrefix("abc")); System.out.println(trie.countWord("abc")); System.out.println(trie.listAllWords()); } }
发表评论
-
【排序算法系列】希尔排序
2015-12-05 16:14 808希尔排序的概述: a[0]...a[n-1 ... -
归并排序
2015-06-20 15:28 860public class MergeSort { pub ... -
插入排序
2015-06-20 15:27 458/** * 插入排序1 容易理解 * * ... -
有序线性链表归并
2013-10-05 11:30 1513#include<stdio.h> #incl ... -
Trie树 应用 Phone List
2012-06-15 11:21 1149Phone List 时间限 ... -
Trie树 单词查找树 键树
2012-06-12 08:59 1119转自:http://zh.wik ... -
数字金额转中文大写金额
2010-11-26 15:09 1402/** * 用来将数字金额转化成中文大写的金额 ... -
汉诺塔递归算法
2010-11-25 08:17 1320import java.util.Scanner; /* ... -
约瑟夫出圈
2010-11-24 20:45 1074#include<iostream> #incl ... -
SmartHashSet只是为了解释HashSet的原理
2010-07-26 11:11 1332写该类的目的只是为了 ... -
二叉树中序遍历非递归算法
2010-06-29 23:17 1691#include<iostream> usi ... -
二叉树的创建
2010-06-29 23:15 1103#include<iostream> usi ... -
哈弗曼树建立与哈弗曼编码
2010-06-29 23:12 1212#include<iostream> #de ... -
二叉排序树转双向链表(要求无任何新增节点)
2010-06-29 23:07 2460题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双 ... -
线索二叉树中插入结点
2010-06-29 23:05 1848#include<iostream> usi ... -
二叉排序树的递归与非递归查找
2010-06-29 22:58 2259#include<iostream> usi ... -
二叉树中序线索化及查找某一结点的前驱,后继结点
2010-06-29 22:54 2643#include<iostream> usi ... -
十字链表定义创建查找
2010-06-29 22:44 1285#include<iostream> #defi ... -
稀疏矩阵转置
2010-06-29 22:39 1600#include<iostream> #defi ... -
单链表实现集合并交差操作
2010-06-29 22:34 1937#include<iostream> usi ...
相关推荐
trie - 单词查找树实现Go实现,极快的前缀/模糊字符串搜索的数据结构和相关算法
在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。
C#,单词查找树(Trie Tree)的插入与搜索算法与源代码 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统...
什么是Trie树 Trie树通常又称为字典树、单词查找树或前缀树,是一种用于快速检索的多叉树结构。如图数字的字典是一个10叉树: 同理小写英文字母或大写英文字母的字典数是一个26叉树。如上图可知,Trie树的根结点是...
主要介绍了javascript trie单词查找树的示例,详细的介绍了trie的概念和实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Trie,又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,...
采用的是c++11实现,用数据结构 Trie(字典树),AVL(平衡树),Hush(散列表)分别进行相应的类,没个类里面分别实现了insert(插入),delete(删除),search(查找操作) 。对于三种数据结构的具体操作会在之后进行具体说明...
设计散列表实现电话号码查询系统。基本要求: ... 2、从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3、采用拉链法解决冲突;...4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录
实现字典的常用方法有: 有序线性表(Search用二分检索实现)、 AVL 树(二叉平衡搜索树)、Patricia Trie(前缀树)、散列表等, 任选一种方法实现字典的操作, 查找单词、 插入单词(插入时,先查找此,找不到插入...
您还可以非常快速地执行通用前缀搜索,这对于形态分析至关重要,例如用于CJK文本索引/搜索的单词拆分。 参考 消息 支持从构建Double-Array,将磁盘上的字典减少为Trie的一半。 查找性能提高了25%。 待办事项清单 ...
部分匹配、近似匹配、近邻查找、 缺点搜索比 naive trie 慢(naive trie 搜索时间总是 O(单词长度)) 根据设计,我们为每个字符串中的每个字符使用一个完整节点——因此对于许多插入,内存使用量可能会急剧上升,...
场景:现在有一个错词库,维护的是错词和正确词对应关系。比如:错词“我门”对应的正确词“我们”。然后在用户输入的文字进行错词校验,需要判断输入的文字是否有错词,并找... Trie树,即字典树,又称单词查找树或键
Radix Trie(有时称为Trie,数字树或前缀树)是树形的确定性自动机(DFA)。 这是一种serach trie,用于存储动态集或关联数组,其中键通常是字符串。 与二进制搜索不同,树中没有与特定关键字关联的节点。 相反,它...
字典存储在一个 trie(前缀树)中。 对字典进行类似遍历的 DFS 以查找单词。 对于每个单词,我们使用动态规划技术来确定板子是否包含该单词。 该算法的运行时间为 O(字典大小 * 版面尺寸 * 版面尺寸 * 字典中的...
快速查找时间:O(单词长度) 非常适合有大量快捷键时使用; 甚至更好,如果它们有共同的前缀。 我们可以按键提供按字母顺序排列的条目(虽然我没有在这里实现,也许是通过预排序遍历) 缺点 根据一个人的实现,...
二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理 欧拉数(递推法) 欧拉数(公式法) 十...
阿霍·科拉西克(Aho-Corasick) 相依性 在您的POM中包括此依赖项。 确保在Maven Central中检查... Aho-Corasick算法在查找多个单词时会发光。 它没有使用所有关键字来构建结构,而不是将搜索文本切碎。 关键的Aho-C
它遍历从所有节点到所有节点的所有可能路径,目的是以水平或垂直方式访问相邻节点,并在pyenchant库(第一版)的帮助下附加字母以查找单词。 新的第二个版本(已经投入生产)利用了trie数据结构,并且运行速度比第...
字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II(判断一批单词是否出现在给定的网格中) 3. 二分查找 LeetCode69 : 求x的平方根 LeetCode...