package com.myway.study;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 字典树 城市相关查询 (现针对26个英文字母)
* User: zhangyong
* Date: 14-8-10
* Time: 上午11:21
* To change this template use File | Settings | File Templates.
*/
public class DictionaryTree {
private static char SPACE = ' ';
private static char[] BASE_CHARS = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
private TrieNode root = null;
public DictionaryTree() {
root = new TrieNode(SPACE);
}
public class TrieNode {
private TrieNode[] childrenNodes = null;
private char charValue;
private boolean wordEnd = false;
public TrieNode(char charValue) {
this.charValue = charValue;
childrenNodes = new TrieNode[26];
}
public void setWordEnd(boolean wordEnd) {
this.wordEnd = wordEnd;
}
public boolean isWordEnd() {
return wordEnd;
}
}
public void insert(String word) {
char[] charArray = word.toCharArray();
TrieNode currentNode = root;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
trieNode = new TrieNode(temp);
currentNode.childrenNodes[index] = trieNode;
}
currentNode = trieNode;
}
currentNode.setWordEnd(true); //是一个单词
}
public boolean search(String key) {
boolean flag = true;
char[] charArray = key.toCharArray();
TrieNode currentNode = root;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
flag = false;
break;
} else {
currentNode = trieNode;
}
}
return flag;
}
public Set<String> travel(String key) {
char[] charArray = key.toCharArray();
TrieNode currentNode = root;
boolean flag = true;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
flag = false;
break;
} else {
currentNode = trieNode;
}
}
if (flag) {
Set<String> set = new HashSet<String>();
TrieNode[] childrenNodes = currentNode.childrenNodes;
for (TrieNode child : childrenNodes) {
if (child != null) {
Recursion(child, key, set);
}
}
return set;
}
return null;
}
public void Recursion(TrieNode trieNode, String append, Set<String> set) {
TrieNode currentNode = trieNode;
if (currentNode != null) {
String temp = append + currentNode.charValue;
if (currentNode.isWordEnd()) {
set.add(temp);
}
TrieNode[] childrenNodes = currentNode.childrenNodes;
for (TrieNode child : childrenNodes) {
if (child != null) {
Recursion(child, temp, set);
}
}
}
}
public static void main(String[] args) {
//比如查询 b 输出 beijing beidaihe baoding
DictionaryTree dictionaryTree = new DictionaryTree();
dictionaryTree.insert("shanghai");
dictionaryTree.insert("shenzhen");
dictionaryTree.insert("beijing");
dictionaryTree.insert("beidaihe");
dictionaryTree.insert("baoding");
dictionaryTree.insert("guangzhou");
dictionaryTree.insert("hangzhou");
System.out.println(dictionaryTree.search("beijing"));
System.out.println(dictionaryTree.travel("b"));
System.out.println(dictionaryTree.travel("guang"));
}
}
分享到:
相关推荐
字典树代码dictionary,包含数据结构和测试例程。
实现字典树的c++代码,数据结构跟思路都很清晰
自己写的字典树简单实现代码,实现了插入和查找功能。
可变长数组和字典树Java代码实现。比较容易复制和学习。
字典树的模版,想学习的自己亲自把代码打一下就可以了。
数据结构二十六叉树/字典树的详细介绍,代码以图片形式展示。
采用的是c++11实现,用数据结构 Trie(字典树),AVL(平衡树),Hush(散列表)分别进行相应的类,没个类里面分别实现了insert(插入),delete(删除),search(查找操作) 。对于三种数据结构的具体操作会在之后进行具体说明...
Trie多被用来查找和统计字符串,利用公共前缀来减少搜索时间,下面我们就来详解字典树Trie结构及其Python代码实现
本文档主要是字典树实现AC自动机用于多模式字符串的匹配算法,包括源代码
详细的数据结构延伸介绍(包括AC自动机SBT,伸展树,字典树,并查集,笛卡尔树,二叉堆,斐波那契堆,哈希表,红黑树,后缀树,后缀数组,树状数组,线段树,左偏树,斜堆),自己整理和归纳相当长的时间,里面有网上的资料,牛人的...
主要介绍了字典树的基本知识及使用C语言的相关实现,这也是ACM等计算机考试和竞赛题目的基本知识,需要的朋友可以参考下
这是作者对《机器学习实战》中构建决策树的代码的一些心得体会,嵌套字典构建树比较难直观理解,作者给出了比较详细的构建过程
在此代码基础上扩展一下,就可以实现比较复杂的字典树,比如带统计数的,或支持更多字符的字典树, 或者是支持删除等操作。 class TrieNode(object): def __init__(self): # 是否构成一个完成的单词 self.is_...
场景:现在有一个错词库,维护的是错词和正确词对应关系。比如:错词“我门”对应的正确词“我们”。然后在用户输入的文字进行错词校验,需要判断输入的文字是否有错词,并找... Trie树,即字典树,又称单词查找树或键
Trie是一种字典树,用于存储文本字符,并利用了单词之间共享前缀的特点,所以叫做前缀树。不像平衡BST,Trie的高度只与最长的文本串的长度s有关系,而与单词的数量n无关。如果一颗Trie中有很多单词只有一个儿子结点...
自行整理的Excel版本行政区划代码表,用于数据字典的构建。
键树以及键树进行动态查找的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
1. 后缀自动机在字典树上的拓展 2. 浅谈启发式思想在信息学竞赛中的应用 3. 浅谈字符串匹配的几种方法 4. 后缀自动挤及其应用 5. 生成函数的运算与组合计数问题 6. ydc的奖金命题报告 7. 浅谈分块在一类在线问题中的...
关于lucene的具体原理,细致的分析lucenne的核心内容,并有代码展示