1、基本概念
字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。
时间复杂度分析:
假设建立了有N个单词的每个单词的最大长度是L的字典Trie树，那么插入一个单词的最坏时间复杂度是O(L)，所以建树的总的时间复杂度是O(NL)
查询一个单词前缀的单词个数最坏时间复杂度是O(L).
2、基本性质
根节点不包含字符，除根节点外的每一个子节点都包含一个字符
从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
每个节点的所有子节点包含的字符都不相同
3、应用场景
典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。
4、优点
利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。
二、构建过程
1、节点定义
class TrieNode // 字典树节点
{
private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
private TrieNode[] son;// 所有的儿子节点
private boolean isEnd;// 是不是最后一个节点
private char val;// 节点的值
TrieNode()
{
num = 1;
son = new TrieNode[SIZE];
isEnd = false;
}
}
2、构造函数
Trie() // 初始化字典树
{
root = new TrieNode();
}
3、建立字典树
// 建立字典树
public void insert(String str) // 在字典树中插入一个单词
{
if (str == null || str.length() == 0)
{
return;
}
TrieNode node = root;
char[] letters = str.toCharArray();//将目标单词转换为字符数组
for (int i = 0, len = str.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null) //如果当前节点的儿子节点中没有该字符，则构建一个TrieNode并复值该字符
{
node.son[pos] = new TrieNode();
node.son[pos].val = letters[i];
}
else //如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
{
node.son[pos].num++;
}
node = node.son[pos];
}
node.isEnd = true;
}
4、查找是否完全匹配一个指定的字符串
// 在字典树中查找一个完全匹配的单词.
public boolean has(String str)
{
if(str==null||str.length()==0)
{
return false;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(int i=0,len=str.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]!=null)
{
node=node.son[pos];
}
else
{
return false;
}
}
//走到这一步，表明可能完全匹配，也可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
return node.isEnd;
}
5、前序遍历字典树
// 前序遍历字典树.
public void preTraverse(TrieNode node)
{
if(node!=null)
{
System.out.print(node.val+"-");
for(TrieNode child:node.son)
{
preTraverse(child);
}
}
}
6、计算单词前缀的数量
// 计算单词前缀的数量
public int countPrefix(String prefix)
{
if(prefix==null||prefix.length()==0)
{
return-1;
}
TrieNode node=root;
char[]letters=prefix.toCharArray();
for(int i=0,len=prefix.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
return 0;
}
else
{
node=node.son[pos];
}
}
return node.num;
}
结果：
三、应用
(问题1)请你选择合适的数据结构，将所有的英文单词生成一个字典Dictionary？
(问题2)给定一个单词，判断这个单词是否在字典Dictionary中，如果在单词库中，输出这个单词出现总共出现的次数，否则输出NO？
package com.xj.test;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Trie
{
private int SIZE = 26;
private TrieNode root;// 字典树的根
class TrieNode // 字典树节点
{
private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
private TrieNode[] son;// 所有的儿子节点
private boolean isEnd;// 是不是最后一个节点
private char val;// 节点的值
TrieNode()
{
num = 1;
son = new TrieNode[SIZE];
isEnd = false;
}
}
Trie() // 初始化字典树
{
root = new TrieNode();
}
// 建立字典树
public void insert(String str) // 在字典树中插入一个单词
{
if (str == null || str.length() == 0)
{
return;
}
TrieNode node = root;
char[] letters = str.toCharArray();//将目标单词转换为字符数组
for (int i = 0, len = str.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null) //如果当前节点的儿子节点中没有该字符，则构建一个TrieNode并复值该字符
{
node.son[pos] = new TrieNode();
node.son[pos].val = letters[i];
}
else //如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
{
node.son[pos].num++;
}
node = node.son[pos];
}
node.isEnd = true;
}
// 计算单词前缀的数量
public int countPrefix(String prefix)
{
if(prefix==null||prefix.length()==0)
{
return-1;
}
TrieNode node=root;
char[]letters=prefix.toCharArray();
for(int i=0,len=prefix.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
return 0;
}
else
{
node=node.son[pos];
}
}
return node.num;
}
// 打印指定前缀的单词
public String hasPrefix(String prefix)
{
if (prefix == null || prefix.length() == 0)
{
return null;
}
TrieNode node = root;
char[] letters = prefix.toCharArray();
for (int i = 0, len = prefix.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null)
{
return null;
}
else
{
node = node.son[pos];
}
}
preTraverse(node, prefix);
return null;
}
// 遍历经过此节点的单词.
public void preTraverse(TrieNode node, String prefix)
{
if (!node.isEnd)
{
for (TrieNode child : node.son)
{
if (child != null)
{
preTraverse(child, prefix + child.val);
}
}
return;
}
System.out.println(prefix);
}
// 在字典树中查找一个完全匹配的单词.
public boolean has(String str)
{
if(str==null||str.length()==0)
{
return false;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(int i=0,len=str.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]!=null)
{
node=node.son[pos];
}
else
{
return false;
}
}
//走到这一步，表明可能完全匹配，可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
return node.isEnd;
}
// 前序遍历字典树.
public void preTraverse(TrieNode node)
{
if(node!=null)
{
System.out.print(node.val+"-");
for(TrieNode child:node.son)
{
preTraverse(child);
}
}
}
public TrieNode getRoot()
{
return this.root;
}
public static void main(String[]args) throws IOException
{
Trie tree=new Trie();
String[] dictionaryData= {"hello","student","computer","sorry","acm","people","experienced","who","reminds","everyday","almost"};
//构建字典
for(String str:dictionaryData)
{
tree.insert(str);
}
String filePath="C:\\Users\\Administrator\\Desktop\\sourceFile.txt";
File file=new File(filePath);
if(file.isFile() && file.exists())
{
InputStreamReader read = new InputStreamReader(new FileInputStream(file));
BufferedReader bufferedReader = new BufferedReader(read);
String lineTxt = null;
Map<String,Integer> countMap=new HashMap<String,Integer>();
while((lineTxt = bufferedReader.readLine())!= null)
{
if(tree.has(lineTxt))
{
if(countMap.containsKey(lineTxt))
{
countMap.put(lineTxt, countMap.get(lineTxt)+1);
}
else
{
countMap.put(lineTxt, 1);
}
}
else
{
System.out.println(lineTxt+"不在字典中！");
}
}
for(String s:countMap.keySet())
{
System.out.println(s+"出现的次数"+countMap.get(s));
}
read.close();
}
}
}
text文件内容：
结果：
相关推荐
《PyPI上的marisa-trie-0.3.4.tar.gz：Python中的高效字典树实现》 在Python的世界里，高效的数据结构和算法是优化程序性能的关键。PyPI（Python Package Index）作为Python库的主要分发平台，提供了无数的工具和...
Trie树，又称字典树或前缀树，是一种用于快速检索的多叉树结构，广泛应用于字符串处理领域。它能有效地利用字符串的公共前缀来减少存储空间，并在查询、插入和删除等方面具有较高的效率。 #### Trie树基本特性 - *...
首先，我们要理解Trie（字典树）的基本概念。Trie是一种树形数据结构，每个节点代表一个字符串的前缀，根节点不包含任何字符，而叶节点则表示完整的单词。通过这种结构，可以快速地进行前缀查找，因为从根节点到某个...
Trie，也被称为前缀树或字典树，是一种用于存储动态集合或关联数组的数据结构，特别是用于字符串。它允许高效的前缀匹配和查找操作，因此在搜索、路由或关键词过滤等领域非常有用。 在PHP中，自定义扩展可以极大地...
标题中的“HAT-trie”是一种特殊的字典树（Trie）数据结构，由Tessil在C++中实现，其特点是快速且内存效率高。这个实现被称为“Header-only”，意味着它只包含头文件，无需链接库，方便集成到其他项目中。下面将详细...
【PHP-TrieTree-master.zip】是一个包含PHP实现的字典树（Trie Tree）数据结构的资源包。这个项目由AbelZhou在GitHub上开源，提供了完整的代码库供开发者学习和使用。字典树是一种高效的数据结构，常用于字符串搜索...
Trie树，又称为前缀树或字典树，是一种用于存储字符串的有效数据结构。它通过将字符串的字符分解并存储在树的节点中，来实现高效的字符串查找、插入和删除操作。在Trie树中，每个节点代表一个字符串的前缀，叶子节点...
基于Java链表实现的字典树（trie），实现了增删改查等功能，它说摘要必须大于50字我还能说啥啥啥啥
字典树，也被称为前缀树或Trie，是一种用于高效存储和检索字符串的数据结构。它的设计灵感来源于二叉搜索树，但与之不同的是，字典树将字符串的每个字符作为节点，使得具有相同前缀的字符串共享相同的路径。这种特性...
Trie，又称为前缀树或字典树，是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的前缀来组织节点，从而快速进行前缀查询和模糊搜索。在Go语言中实现Trie，可以有效地支持字符串集合的增删查改...
Trie，也被称为前缀树或字典树，是一种用于存储键值对的数据结构，尤其适用于字符串数据。在C语言中实现Trie，可以提供快速的字符串查找服务，尤其是在处理大量字符串且需要查找是否存在某个字符串或者字符串前缀时...
总的来说，Java实现的字典树TrieTree是一个强大的工具，尤其适用于处理大量字符串数据，如四六级高频词汇的存储和查询。通过理解和运用这种数据结构，我们可以提高算法效率，优化应用程序的性能。
在IT领域，字典树（Trie，也称为前缀树或字典树）是一种用于存储动态集合或关联数组的数据结构。它允许我们快速查找、插入和删除字符串，特别是对于有公共前缀的字符串，效率非常高。这个实例是用Java语言实现的，...
**哈希 Trie 树（HashTrie）与字典树（Trie树）详解** 哈希 Trie 树，也称为 HashTrie 或者是哈希化的 Trie 树，是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数，提高了...
marisa_trie是一款高效的数据结构库，它实现了Trie（又称前缀树或字典树）数据结构。Trie是一种树形结构，用于存储字符串集合，它以键（key）为节点，每个节点可能有多个子节点，这些子节点对应键的后继字符。Trie的...
ACM Trie树 模板,字典树模板，数据结构
Trie，也称为“字典树”或“前缀树”，是一种用于存储动态集合或关联数组的数据结构，它允许我们快速查找以特定字符串开头的所有项。这种数据结构特别适用于实现自动补全功能，搜索引擎的关键词搜索，以及高效地处理...
Trie，也被称为“前缀树”或“字典树”，是一种用于存储字符串的数据结构，它在计算机科学中常被用于高效地执行字符串查找操作。在Objective-C中实现Trie算法，可以帮助开发者快速处理大量字符串数据，例如在搜索...
这个Java程序利用了数据结构——字典树（Trie），也被称为前缀树或PAT树，它在处理字符串相关的搜索问题时表现出色。下面我们将深入探讨字典树的工作原理及其在拼写检错中的应用。 字典树是一种树形数据结构，每个...