`
jaychang
  • 浏览: 734756 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

Trie树 单词查找树 键树(JAVA版附分析说明)

 
阅读更多

来源于英文“retrieval”.   Trie树就是字符树,其核心思想就是空间换时间。

举个简单的例子。
   给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,第一次出现第几个位置。
这题当然可以用hash来,但是我要介绍的是trie树。在某些方面它的用途更大。比如说对于某一个单词,我要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。

   现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是 O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开 头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的……这样一个树的 模型就渐渐清晰了……

   我们可以看到,trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表,或者用数组来模拟动态。空间的花费,不会超过单词数×单词长度。(转自一大牛)

Trie树的java代码 实现如下:

import java.util.ArrayList;
import java.util.List;

/**
 * 单词查找树
 * 
 * @author Jay Chang
 * @since 2012-06-13
 */
class Trie {
	/** 单词查找树根节点,根节点为一个空的节点 */
	private Vertex root = new Vertex();

	/** 单词查找树的节点(内部类) */
	private class Vertex {
		/** 单词出现次数统计 */
		int wordCount;
		/** 以某个前缀开头的单词,它的出现次数 */
		int prefixCount;
		/** 子节点用数组表示 */
		Vertex[] vertexs = new Vertex[26];

		/**
		 * 树节点的构造函数
		 */
		public Vertex() {
			wordCount = 0;
			prefixCount = 0;
		}
	}

	/**
	 * 单词查找树构造函数
	 */
	public Trie() {

	}

	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param word
	 *            单词
	 */
	public void addWord(String word) {
		addWord(root, word.toLowerCase());
	}

	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            单词
	 */
	private void addWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			vertex.wordCount++;
		} else if (word.length() > 0) {
			vertex.prefixCount++;
			char c = word.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				vertex.vertexs[index] = new Vertex();
			}
			addWord(vertex.vertexs[index], word.substring(1));
		}
	}

	/**
	 * 统计某个单词出现次数
	 * 
	 * @param word
	 *            单词
	 * @return 出现次数
	 */
	public int countWord(String word) {
		return countWord(root, word);
	}

	/**
	 * 统计某个单词出现次数
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            单词
	 * @return 出现次数
	 */
	private int countWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			return vertex.wordCount;
		} else {
			char c = word.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				return 0;
			} else {
				return countWord(vertex.vertexs[index], word.substring(1));
			}
		}
	}

	/**
	 * 统计以某个前缀开始的单词,它的出现次数
	 * 
	 * @param word
	 *            前缀
	 * @return 出现次数
	 */
	public int countPrefix(String word) {
		return countPrefix(root, word);
	}

	/**
	 * 统计以某个前缀开始的单词,它的出现次数(前缀本身不算在内)
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            前缀
	 * @return 出现次数
	 */
	private int countPrefix(Vertex vertex, String prefixSegment) {
		if (prefixSegment.length() == 0) {
			return vertex.prefixCount;
		} else {
			char c = prefixSegment.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				return 0;
			} else {
				return countPrefix(vertex.vertexs[index], prefixSegment.substring(1));
			}
		}
	}
	
	/**
	 * 调用深度递归算法得到所有单词
	 * @return 单词集合
	 */
	public List<String> listAllWords() {
		List<String> allWords = new ArrayList<String>();
		return depthSearchWords(allWords, root, "");
	}

	/**
	 * 递归生成所有单词
	 * @param allWords 单词集合
	 * @param vertex 单词查找树的节点
	 * @param wordSegment 单词片段
	 * @return 单词集合
	 */ 
	private List<String> depthSearchWords(List<String> allWords, Vertex vertex,
			String wordSegment) {
		Vertex[] vertexs = vertex.vertexs;
		for (int i = 0; i < vertexs.length; i++) {
			if (null != vertexs[i]) {
				if (vertexs[i].wordCount > 0) {
					allWords.add(wordSegment + (char)(i + 'a'));
					if(vertexs[i].prefixCount > 0){
						depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a'));
					}
				} else {
					depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a'));
				}
			}
		}
		return allWords;
	}
}

public class Main {
	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.addWord("abc");
		trie.addWord("abcd");
		trie.addWord("abcde");
		trie.addWord("abcdef");
		System.out.println(trie.countPrefix("abc"));
		System.out.println(trie.countWord("abc"));
		System.out.println(trie.listAllWords());
	}
}
分享到:
评论

相关推荐

    Go-trie-单词查找树实现Go实现

    在这个背景下,了解并掌握如何在Go中实现Trie(单词查找树)这种数据结构对于提升代码质量具有重要意义。 Trie,又称为前缀树或字典树,是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的...

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

    每当用户键入一个字符时,我们会调用Trie树的查找方法,获取所有匹配当前前缀的单词,并将这些单词显示在搜索框下方作为提示。为了优化用户体验,可以设置一个最小的触发字符数,例如3个,避免过多的提示干扰用户。 ...

    trie树的实现(C)

    在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。

    从trie树谈到后缀树

    在实际应用中,Trie树特别适合处理大量字符串的集合,比如搜索引擎的关键词统计、文本词频分析等。例如,给定100000个长度不超过10的单词,如果使用Trie树,可以快速判断一个单词是否存在于集合中,并找到其首次出现...

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

    在 HashTrie 中,每个节点包含一个哈希表,表中的键是 Trie 树中的字符,值是对应的子节点。当插入一个新的字符串时,我们从根节点开始,对每个字符应用哈希函数,得到对应的槽位,然后在该槽位下创建或查找子节点。...

    Acm Trie树

    #### 六、Trie树的时间和空间复杂度分析 - **时间复杂度**:插入和查找操作的时间复杂度均为O(L),其中L是字符串的平均长度。这是因为每个操作都沿着字符路径向下遍历,最多遍历L次。 - **空间复杂度**:在最坏的...

    Trie树题解1

    利用Trie树,我们可以先构建一个包含所有单词的树,然后对矩阵的每个位置进行深度优先搜索或广度优先搜索,检查当前位置及周围位置组成的字符串是否为树中的单词。 3. POJ2001 - 这题需要找到每个单词的最短前缀,...

    从Trie树(字典树)谈到后缀树.pdf

    Trie树适合解决单词查找以及统计问题,而后缀树则在字符串模式匹配、最长公共子串等问题上有着出色的表现。 首先,Trie树是一种树形结构,用于高效存储和检索字符串数据集中的键。它能够快速查找字符串是否出现以及...

    C#,单词查找树(Trie Tree)的插入与搜索算法与源代码

    C#,单词查找树(Trie Tree)的插入与搜索算法与源代码 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统...

    trie树所有代码,试题打包

    Trie树是一种有序树,每个节点代表一个字符串的前缀,根节点不包含任何字符,而叶子节点代表完整单词。通过这种结构,我们可以快速查找具有特定前缀的字符串,且插入和查询的时间复杂度接近O(k),其中k是查询字符串...

    Trie树(字典树)的介绍及Java实现

    Trie树,也被称为字典树或前缀树,是一种数据结构,主要用于高效地存储和检索字符串集合中的数据。...在Java中实现Trie树,需要理解其结构特点并构建相应的节点类和树类,通过递归方法处理插入、删除和查找操作。

    Java实现字典树TrieTree

    在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...

    数据结构实验报告-----trie树

    它同样逐字符地遍历单词,检查每个字符对应的子节点,如果遍历到最后一个字符且该节点存在,说明单词存在于Trie树中。 4. **查找单词前缀出现的次数**:`SearchTrieNode`函数可以找出以特定前缀开头的单词的总数。...

    数据结构课设Trie树

    与传统的二叉查找树不同,Trie树以字符串为键,每个节点代表一个字符串的前缀。根节点通常不包含任何字符,而从根节点到叶子节点的路径上的边代表了字符串中的字符,路径上的字符组合起来就是该节点对应的关键字。...

    Trie树的插入、查询、删除和部分应用(单词的查询、单词出现频率/DFS和非DFS两种遍历)

    在Trie树中,BFS通常用于查找最短匹配的单词,因为它是按字母顺序访问节点的。 在这个项目中,`main.cpp`可能是实现这些功能的主程序,`TrieTree.cbp`是工程文件,`main.exe`是编译后的可执行文件,`TrieTree....

    35丨Trie树:如何实现搜索引擎的搜索关键词提示功能?1

    【Trie树】,又称字典树或前缀树,是一种高效处理字符串匹配的数据结构,常用于搜索引擎的搜索关键词提示功能。它的设计思路是利用字符串之间的公共前缀,将重复的前缀合并,以提高查找效率。在搜索引擎的场景中,...

    算法-单词查找树(信息学奥赛一本通-T1337)(包含源程序).rar

    《算法-单词查找树(信息学奥赛一本通-T1337)》是一本针对信息学竞赛的教程,特别关注了数据结构中的一个重要部分——单词查找树。这本书旨在帮助参赛者理解和掌握如何利用单词查找树来解决实际的编程问题,特别是...

    一个基于trie树的具有联想功能的文本编辑器.zip

    3. **查找操作**:设计一个方法来查找以特定前缀开头的单词,通过遍历Trie树来实现。 4. **删除操作**(可选):如果需要支持删除单词功能,那么需要实现一个删除方法,这通常比插入和查找复杂,因为它需要处理节点...

    TIRE 字典树 论文

    3. **前缀匹配**:Trie树特别适合进行前缀匹配查询,例如查找所有以特定字符串开头的单词。 4. **插入和删除操作**:Trie树的插入和删除操作相对复杂,但仍然比平衡二叉搜索树等其他数据结构更为高效。 在论文...

Global site tag (gtag.js) - Google Analytics