`
tianyalinfeng
  • 浏览: 442358 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
社区版块
存档分类
最新评论

Trie树

    博客分类:
  • Java
 
阅读更多

lTrie原理

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

 

lTrie性质

好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

2.    branch数组的下标代表字符相对于a的相对位置

3.    采用标记的方法确定是否为字符串。

4.    插入、查找的复杂度均为O(len),len为字符串长度

lTrie的示意图

 

如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL





l
Trie的优点举例

已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

1.    最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

2.    使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

3.    使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。

 

package trie;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

public class Trie {

 private Vertex root;

 protected class Vertex {

  protected int words;

  protected int prefixes;

  protected Vertex[] edges;

  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) {

    // System.out.println("test");

    String word = "" + (char) ('a' + i);

    depthFirstSearchWords(words, edges[i], word);

   }

  }

  return words;

 }

 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));

  }

 }

 /** */
 /**
  *
  * Depth First Search words in the Trie and add them to the List.
  *
  *
  *
  * @param words
  *
  * @param vertex
  *
  * @param wordSegment
  *
  */

 private void depthFirstSearchWords(List<String> 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);

  }

 }

 /** */
 /**
  *
  * 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("crawl");

  trie.addWord("crime");

  trie.addWord("ban");

  trie.addWord("english");

  trie.addWord("establish");

  trie.addWord("eat");

  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("c");

  System.out.println("the count of c prefixes:" + count);

 }

}

分享到:
评论

相关推荐

    IT笔试面试--Trie树前缀树常考题目及解析

    ### IT笔试面试--Trie树(前缀树)常考题目及解析 #### 概述 Trie树,又称字典树或前缀树,是一种用于快速检索的多叉树结构,广泛应用于字符串处理领域。它能有效地利用字符串的公共前缀来减少存储空间,并在查询...

    Trie 树实现的源码

    ### Trie树实现详解 #### 一、Trie树简介 Trie树,也称为前缀树或字典树,是一种用于存储字符串数据结构。它利用字符串间的公共前缀来减少所需的存储空间,使得查找字符串更加高效。Trie树在很多应用中都有广泛的...

    Trie树入门,很容易上手

    "Trie树入门,很容易上手" Trie树是一种树形结构,用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。相对来说,Trie树是一种比较简单的数据结构。理解起来比较简单,但是简单的东西也得付出...

    用Trie树实现词频统计和单词查询

    一个简单的C语言程序:用Trie树实现词频统计和单词查询

    基于Trie树模仿谷歌百度搜索框提示

    这个项目“基于Trie树模仿谷歌百度搜索框提示”旨在实现类似谷歌和百度搜索引擎的自动补全功能。我们将深入探讨Trie树数据结构以及如何使用Java来构建这样的系统。 首先,我们要理解什么是Trie树,也被称为前缀树或...

    trie树的实现(C)

    trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...

    Python实现Trie树

    用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...

    C++/C Trie树算法

    用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除

    Acm Trie树

    ### ACM Trie树详解 #### 一、Trie树的基本概念 **Trie树**,又称为**字典树**或**前缀树**,是一种用于高效存储和检索字符串的树形数据结构。它通过利用字符串之间的公共前缀来减少查询时间,从而提高搜索效率。...

    从trie树谈到后缀树

    【Trie树】 Trie树,又称为字典树,是一种特殊的树形数据结构,主要用于高效地存储和检索字符串。它的设计目的是通过利用字符串的公共前缀来减少字符串比较的次数,从而提高查询效率。Trie树的核心特点是: 1. 根...

    HASH(Trie)-.rar_HashTree.h_TRIE_hash树_trie树_字典树

    **哈希 Trie 树(HashTrie)与字典树(Trie树)详解** 哈希 Trie 树,也称为 HashTrie 或者是哈希化的 Trie 树,是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数,提高了...

    论文研究-划分位无冲突哈希在trie树分组中的研究.pdf

    通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    字典树,也被称为Trie树或前缀树,是一种高效的数据结构,尤其适用于字符串相关的查找和插入操作。在计算机科学领域,它被广泛应用在字典、搜索引擎、自动补全功能以及IP路由等方面。Trie树的核心优势在于其能够通过...

    Trie树(字典数\字符树)基本原理

    "Trie树(字典树)基本原理" Trie 树,也称为字典树,是一种树形数据结构,用于高效存储和查询字符串。其核心思想是空间换时间,即通过占用更多的存储空间来换取查询速度的提高。 Trie 树的基本结构是一个节点数组...

    Trie树题解1

    【Trie树题解1】 Trie树,又称字典树或前缀树,是一种用于高效存储和检索字符串的数据结构。它的主要特点是能够快速查找一个字符串是否是另一个字符串的前缀,这对于处理大量字符串的问题非常有用。在题目描述中...

    Trie树 结构描述 实现方法 用法

    Trie树,也被称为前缀树或字典树,是一种数据结构,主要用于高效地存储和检索字符串。在Trie树中,每个节点代表一个字符串的前缀,而从根节点到某个节点的路径上的边代表了这个节点所代表的字符串。这种结构特别适合...

    DoubleArrayTrie(双数组Trie树)

    **DoubleArrayTrie(双数组Trie树)详解** DoubleArrayTrie(简称DAT),是一种高效的数据结构,常用于字符串的查找和匹配,特别是在分词检索、数据挖掘以及搜索引擎等领域有着广泛的应用。它是由日本学者高津陵...

    双数组Trie树算法优化及其应用研究.pdf

    ### 双数组Trie树算法优化及其应用研究 #### 摘要与关键词解析 本文主要探讨了一种针对双数组Trie树(Double-Array Trie)算法的优化策略,并通过实验验证了该策略的有效性。双数组Trie树是一种高效的数据结构,常...

    实现trie树的C/C++模板

    ### 实现Trie树的C/C++模板 在计算机科学领域,Trie树(又称前缀树或字典树)是一种用于存储具有共同前缀的字符串的高效数据结构。它广泛应用于各种场景,如自动补全、拼写检查以及IP路由表等。本文将详细介绍如何...

    trie树所有代码,试题打包

    Trie树,又称前缀树或字典树,是一种用于存储字符串的数据结构,它在IT领域尤其是数据结构和算法的学习中占据着重要的地位。这个压缩包包含的“王赟.doc”和“王赟.ppt”很可能是关于Trie树的详细讲解和实践题目,...

Global site tag (gtag.js) - Google Analytics