package com.trie.base.bean;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class TrieNode implements Comparable<TrieNode>{
/**
* 节点的key
*
*/
protected int key;
/**
*节点对应的字符串
*/
protected String word;
/**
* 节点的前缀节点
*/
protected TrieNode fatherNode;
/**
* 以该节点作为前缀的子节点
*/
protected List<TrieNode> childNodes;
/**
* 在list的index和char的int值之间建立映射
*/
protected Map<Integer,Integer> indexMap;
/**
* 搜索次数
*/
protected int click=0;
protected Object obj;
public List<TrieNode> getChildNodes() {
if(null==childNodes){
childNodes=new ArrayList<TrieNode>();
indexMap =new HashMap<Integer, Integer>();
}
return childNodes;
}
public void setChildNodes(List<TrieNode> childNodes) {
this.childNodes = childNodes;
}
public TrieNode getFatherNode() {
return fatherNode;
}
public void setFatherNode(TrieNode fatherNode) {
this.fatherNode = fatherNode;
}
public String getWord() {
return word;
}
public void setWord(String word) {
this.word = word;
}
/**
* @param key
*/
public TrieNode(int key,String word) {
super();
this.key = key;
this.word=word;
}
/**
* @param key
*/
public TrieNode() {
super();
}
public boolean add(TrieNode childNode){
childNode.setFatherNode(this);
getChildNodes().add(childNode);
getIndexMap().put(childNode.getKey(),getChildNodes().size());
return true;
}
public TrieNode get(char c){
return get((int)c);
}
public TrieNode get(int c){
Integer o=getIndexMap().get(c);
if(null==o){
return null;
}
return getChildNodes().get(o-1);
}
public TrieNode addClick(){
this.click++;
return this;
}
public Map<Integer, Integer> getIndexMap() {
if(null==indexMap){
indexMap=new HashMap<Integer, Integer>();
}
return indexMap;
}
public void setIndexMap(Map<Integer, Integer> indexMap) {
this.indexMap = indexMap;
}
public int getClick() {
return click;
}
public void setClick(int click) {
this.click = click;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public List<TrieNode> getAllChild(){
List<TrieNode> list = new ArrayList<TrieNode>();
for(Iterator<TrieNode> it=getChildNodes().iterator();it.hasNext();){
TrieNode node=it.next();
list.add(node);
if(node.getChildNodes().size()>0){
list.addAll(node.getAllChild());
}
}
return list;
}
public int compareTo(TrieNode o) {
if(null==o||o.getClick()<this.click){
return -1;
}else if(o.getClick()==this.click){
return 0;
}else{
return 1;
}
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
if(obj==null){
return;
}
this.obj = obj;
}
}
package com.trie.base;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import com.trie.base.bean.TrieNode;
public class Trie {
//该字符树所有节点的数量
protected int entityTrieNodeSize=0;
//该字符树所有节点的数量
protected int trieNodeSize=0;
//第一层Node
protected TrieNode firstLvNode;
//禁用词
protected Set<String> filterWords;
//搜索链表
protected List<TrieNode> entityNodes;
/**
* 插入节点
*/
public TrieNode insert(String word,Object obj){
if(filter(word)){
return null;
};
char[] words=word.toCharArray();
TrieNode temp=null;
TrieNode tempFather=null;
for(int i=0;i<words.length;i++){
int c=(int)words[i];
//首字符,从第一层Node中搜索
if(0==i){
temp=getFirstLvNode().get(c);
//第一层node内不存在此字符,增加
if(null==temp){
temp=addNewTrieNode(getFirstLvNode(),words, i);
}
tempFather=temp;
//其他字符
}else{
temp=tempFather.get(c);
//node内不存在此字符,增加
if(null==temp){
temp=addNewTrieNode(tempFather,words, i);
}
tempFather=temp;
}
}
tempFather.setObj(obj);
getEntityNodes().add(tempFather);
entityTrieNodeSize++;
return tempFather;
}
public TrieNode insert(String word){
return insert(word,null);
}
public TrieNode addNewTrieNode(TrieNode tempFather,char[] words,int i){
TrieNode trieNode = new TrieNode((int)words[i],new String(words,0,i+1));
trieNodeSize++;
tempFather.add(trieNode);
return trieNode;
}
/**
* 搜索输入的词 返回节点 并在搜索次数中+1
*/
public TrieNode search(String word){
TrieNode node= get(word);
if(null==node){
return null;
}
return node.addClick();
};
public TrieNode get(String word){
char[] words=word.toCharArray();
TrieNode temp=null;
for(int i=0;i<words.length;i++){
int c=(int)words[i];
//首字符
if(0==i){
temp=getFirstLvNode().get(c);
if(temp==null){
return null;
}
//其他层的字符
}else{
if(temp==null){
return null;
}
temp=temp.get(c);
}
}
return temp;
};
/**
* 根据设定的禁用词来过滤节点
*/
public boolean filter(String word){
if(null==filterWords){
return false;
}
boolean result = filterWords.add(word);
if(result){
filterWords.remove(word);
}
return !result;
}
/**
* 搜索输入的词与该词所有前缀
*/
public List<TrieNode> searchAndPrefix(String word){
List<TrieNode> nodes=new ArrayList<TrieNode>();
char[] words=word.toCharArray();
TrieNode temp=null;
for(int i=0;i<words.length;i++){
int c=(int)words[i];
//首字符
if(0==i){
temp=getFirstLvNode().get(c);
if(temp==null){
return null;
}
//其他层的字符
}else{
if(temp==null){
return null;
}
temp=temp.get(c);
}
nodes.add(temp);
}
temp.addClick();
return nodes;
};
public List<TrieNode> searchAndPrefix(String word,int lv){
List<TrieNode> nodes=new ArrayList<TrieNode>();
char[] words=word.toCharArray();
TrieNode temp=null;
for(int i=0;i<words.length;i++){
int c=(int)words[i];
if(0==i){
temp=getFirstLvNode().get(c);
if(temp==null){
return null;
}
}else{
if(temp==null){
return null;
}
temp=temp.get(c);
}
if(i>lv-1){
nodes.add(temp);
}
}
temp.addClick();
return nodes;
};
/**
* 搜索前缀找出相关的词,按顺序取词
*/
public List<TrieNode> searchByPrefix(String word){
return searchByPrefix(word,true,0);
};
/**
* 搜索前缀找出相关的词,并根据排序取词
*/
public List<TrieNode> searchByPrefix(String word,boolean desc,int size){
List<TrieNode> list=new ArrayList<TrieNode>();
TrieNode node=get(word);
if(null==node){
return list;
}
list.add(node);
list.addAll(node.getAllChild());
return sort(list,desc,size);
};
public List<TrieNode> sort(boolean desc,int size){
return sort(getEntityNodes(),desc,size);
}
/**
* 对所有实体根据click进行排序，取出规定数量的节点
* desc true为默认逆序，false默认顺序
*/
public List<TrieNode> sort(List<TrieNode> elist,boolean desc,int size){
java.util.Collections.sort(elist);
if(size<=0||size>elist.size()){
size=elist.size();
}
if(desc){
return elist.subList(0,size);
}else{
List<TrieNode> list =elist.subList(elist.size()-size,elist.size());
java.util.Collections.reverse(list);
return list;
}
}
public TrieNode getFirstLvNode() {
if(null==firstLvNode){
setFirstLvNode(new TrieNode());
}
return firstLvNode;
}
public void setFirstLvNode(TrieNode firstLvNode) {
this.firstLvNode = firstLvNode;
}
public Set<String> getFilterWords() {
if(null==filterWords){
filterWords=new HashSet<String>();
}
return filterWords;
}
public void setFilterWords(Set<String> filterWords) {
this.filterWords = filterWords;
}
public int getTrieNodeSize() {
return trieNodeSize;
}
public void setTrieNodeSize(int trieNodeSize) {
this.trieNodeSize = trieNodeSize;
}
public void addFilterWord(String word){
getFilterWords().add(word);
}
public int getEntityTrieNodeSize() {
return entityTrieNodeSize;
}
public void setEntityTrieNodeSize(int entityTrieNodeSize) {
this.entityTrieNodeSize = entityTrieNodeSize;
}
public List<TrieNode> getEntityNodes() {
if(null==entityNodes){
entityNodes=java.util.Collections.synchronizedList(new ArrayList());
}
return entityNodes;
}
public void setEntityNodes(List entityNodes) {
this.entityNodes = entityNodes;
}
}
分享到：
相关推荐
Trie数据结构详解与应用 Trie，又称为前缀树或字典树，是一种用于存储字符串的树形数据结构。它的主要特点是通过关联字符来构建树的节点，从而实现快速的字符串查找、插入和删除操作。Trie在信息技术、搜索引擎优化...
在这个背景下，了解并掌握如何在Go中实现Trie（单词查找树）这种数据结构对于提升代码质量具有重要意义。 Trie，又称为前缀树或字典树，是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的...
- libdatrie 提供了 C 语言接口，包括 trie_load() 函数加载词典，trie_insert() 插入新词，trie_search() 查找单词，以及 trie_delete() 删除单词等方法。 - 库还支持 Trie 的序列化和反序列化，便于在内存和磁盘...
### Trie树实现详解 #### 一、Trie树简介 Trie树，也称为前缀树或字典树，是一种用于存储字符串数据结构。它利用字符串间的公共前缀来减少所需的存储空间，使得查找字符串更加高效。Trie树在很多应用中都有广泛的...
【Trie树】 Trie树，又称为字典树，是一种特殊的树形数据结构，主要用于高效地存储和检索字符串。它的设计目的是通过利用字符串的公共前缀来减少字符串比较的次数，从而提高查询效率。Trie树的核心特点是： 1. 根...
**DoubleArrayTrie（双数组Trie树）详解** DoubleArrayTrie（简称DAT），是一种高效的数据结构，常用于字符串的查找和匹配，特别是在分词检索、数据挖掘以及搜索引擎等领域有着广泛的应用。它是由日本学者高津陵...
"Trie树入门，很容易上手" Trie树是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。相对来说，Trie树是一种比较简单的数据结构。理解起来比较简单，但是简单的东西也得付出...
《严蔚敏数据结构与算法：TrieTree详解》 在计算机科学中，数据结构是组织、管理和存储数据的方式，而算法则是解决特定问题的精确步骤。数据结构的选择直接影响到程序的效率和可读性。在众多的数据结构中，TrieTree...
Trie，也被称为前缀树或字典树，是一种用于存储键值对的数据结构，尤其适用于字符串数据。在C语言中实现Trie，可以提供快速的字符串查找服务，尤其是在处理大量字符串且需要查找是否存在某个字符串或者字符串前缀时...
### 实现Trie树的C/C++模板 在计算机科学领域，Trie树（又称前缀树或字典树）是一种用于存储具有共同前缀的字符串的高效数据结构。它广泛应用于各种场景，如自动补全、拼写检查以及IP路由表等。本文将详细介绍如何...
trie.c中定义了trie树的操作函数； trie.h为相应的头文件； test.c用于测试相关的函数。 在trie.c中，关于查找定义了两个函数，一个是find()，一个是search()，二者的区别是，前者仅判断一个字符串是否在树中出现，...
### IT笔试面试--Trie树（前缀树）常考题目及解析 #### 概述 Trie树，又称字典树或前缀树，是一种用于快速检索的多叉树结构，广泛应用于字符串处理领域。它能有效地利用字符串的公共前缀来减少存储空间，并在查询...
### 双数组Trie优化算法及其应用研究 #### 摘要 本文主要探讨了双数组Trie树(Double-Array Trie)算法的一种优化方法，并详细分析了其在实际应用中的表现，特别是在词典管理和自动分词领域。双数组Trie树作为一种...
2、Trie树SDK中的API支持以下功能 1）插入节点 2）精确删除节点 3）正向模糊匹配 4）反向模糊匹配 5）精确查询节点 6）获取头（尾）节点 7）删除头（尾）节点 8）排序 9）支持多级树 10）支持强大的查询节点功能 ...
KMP算法和Trie搜索树是两种在计算机科学中用于字符串处理的重要算法，它们在文本检索、模式匹配和数据结构优化等领域有着广泛的应用。 首先，我们来深入了解一下KMP算法。KMP（Knuth-Morris-Pratt）算法是一种高效...
Trie树，也被称为前缀树或字典树，是一种数据结构，主要用于高效地存储和检索字符串。在Trie树中，每个节点代表一个字符串的前缀，而从根节点到某个节点的路径上的边代表了这个节点所代表的字符串。这种结构特别适合...
Trie，又称为字典树或前缀树，是一种用于存储关联数组的数据结构，它允许我们高效地进行字符串的查找、插入和删除操作。在Java中实现Trie数据结构，可以帮助我们快速处理大量字符串数据，例如在搜索引擎中进行关键词...
一个简单的C语言程序：用Trie树实现词频统计和单词查询