Trie.
import java.util.*; public class Trie { private static final int R = 26; private static class TrieNode { boolean isLeaf; //是否为单词的结尾 int count; //以此节点为prefix的字符串的个数, 此属性不是必须的 TrieNode[] childs = new TrieNode[R]; } private TrieNode root = new TrieNode(); private int size; public int size() { return size; } //if the word does not exist in the dict, insert it, mark the leaf node, increment dict size public void insert(String word) { if(word==null || word.isEmpty() || contains(word)) return; TrieNode node = root; for(int i=0; i<word.length(); i++) { char c = word.charAt(i); int j = c - 'a'; if(node.childs[j] == null) { node.childs[j] = new TrieNode(); } node = node.childs[j]; node.count++; } if(!node.isLeaf) { node.isLeaf = true; size++; } } public boolean contains(String word) { TrieNode node = root; for(int i=0; i<word.length(); i++) { char c = word.charAt(i); int j = c - 'a'; node = node.childs[j]; if(node == null) return false; } return node.isLeaf; } // 1. Key may not be there in trie. Delete operation should not modify trie. // 2. Key present as unique key (no part of key contains another key (prefix), // nor the key itself is prefix of another key in trie). Delete all the nodes. // 3. Key is prefix key of another long key in trie. Unmark the leaf node. // 4. Key present in trie, having at least one other key as prefix key. Delete // nodes from end of key until first leaf node of longest prefix key. public boolean delete(String word) { if(word==null || word.isEmpty()) return false; return delete(root, word, 0); } private boolean delete(TrieNode node, String word, int d) { if(node == null) return false; if(d == word.length()) { if(node.isLeaf) { node.isLeaf = false; size--; return true; } return false; } int k = word.charAt(d) - 'a'; TrieNode next = node.childs[k]; boolean ok = delete(next, word, d+1); if(ok && --next.count == 0) { node.childs[k] = null; } return ok; } // yet another method of delete public void remove(String word) { if(word == null || word.isEmpty()) return; remove(root, word, 0); } private TrieNode remove(TrieNode node, String word, int d) { if(node == null) return null; if(d == word.length()) { if(node.isLeaf) { node.isLeaf = false; size--; } } else { int k = word.charAt(d) - 'a'; node.childs[k] = remove(node.childs[k], word, d+1); } for (int i = 0; i < R; i++) if (node.childs[i] != null) return node; return null; } public List<String> words() { return wordsWithPrefix(""); } public List<String> wordsWithPrefix(String prefix) { List<String> list = new ArrayList<>(); TrieNode node = root; for(int i=0; i<prefix.length(); i++) { node = node.childs[prefix.charAt(i) - 'a']; } StringBuilder sb = new StringBuilder(prefix); collect(node, sb, list); return list; } private void collect(TrieNode node, StringBuilder prefix, List<String> list) { if(node == null) return; if(node.isLeaf) list.add(prefix.toString()); for(int i=0; i<R; i++) { prefix.append((char)(i+'a')); collect(node.childs[i], prefix, list); prefix.deleteCharAt(prefix.length()-1); } } public String longestPrefixOf(String query) { int length = longestPrefixOf(root, query, 0, 0); return query.substring(0, length); } private int longestPrefixOf(TrieNode x, String query, int d, int length) { if (x == null) return length; if (x.isLeaf) length = d; if (d == query.length()) return length; char c = query.charAt(d); return longestPrefixOf(x.childs[c-'a'], query, d+1, length); } }
Test case:
public static void main(String[] args) { String[] words = {"the", "a", "there", "answer", "any", "by", "bye", "their", "grass"}; Trie trie = new Trie(); for (String word : words) { trie.insert(word); } System.out.println(trie.longestPrefixOf("an")); System.out.println(trie.wordsWithPrefix("an")); System.out.println(trie.size()); System.out.println(trie.contains("the")); System.out.println(trie.contains("they")); System.out.println(trie.contains("by")); System.out.println(trie.contains("byn")); System.out.println(trie.contains("any")); trie.remove("any"); System.out.println("delete ans:" + trie.delete("ans")); System.out.println(trie.contains("any")); System.out.println(trie.contains("answer")); trie.remove("answer"); System.out.println(trie.contains("answer")); trie.remove("by"); System.out.println(trie.contains("by")); System.out.println("delete by:" + trie.delete("by")); System.out.println(trie.contains("bye")); System.out.println(trie.size()); }
References:
相关推荐
trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
一个简单的C语言程序:用Trie树实现词频统计和单词查询
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在...
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
2、有序HASH(Trie)树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)...
trie-0.1.1.tar
trie树模板,acm竞赛,可以进行适当的修改就可以解决问题,在进行字符串处理的时候尤其能用到。
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
hat-trie, 一种有效的trie实现 hat 这是Askitis和Sinha的hat trie数据结构的ANSI实现,它是一个非常高效的( 空间和时间) 现代变体。这里实现的版本将字节数组映射到单词( 。例如,无符号的longs ),它可以以用来存储...
Trie 树实现的源码,用C++编写实现,做自然语言处理的朋友可以参考一下
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
libdatrie是一个泰国人写的构建双数组TRIE树的开源代码。
通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...
double-array-trie原理与算法实现探索,dat算法分析
实现一个Trie
建立trie树,并进行相关操作,包括 insert:插入一个字符串,重复插入无效 remove:删除指定的字符串,如果不存在,则不进行操作 find:判断是否有指定的字符串