字典树入门及实现(JAVA)

2024-09-03 13:38
文章标签 java 实现 入门 字典

本文主要是介绍字典树入门及实现(JAVA),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。 典型应用是用于统计和排序大量的字符串(但不仅限于字符串), 所以经常被搜索引擎系统用于文本词频统计。

它的优点是:
  利用字符串的公共前缀来节约存储空间,最大限度的减少无谓的字符串比较,查询效率比哈希表高。

  比如说我们想储存3个单词,sky、skyline、skymoon。如果只是单纯的按照以前的字符数组存储的思路来存储的话,那么我们需要定义三个字符串数组。但是如果我们用字典树的话,只需要定义一个树就可以了。在这里我们就可以看到字典树的优势了。

它有三个基本性质:
(1)根节点不包含字符;
(2) 除根节点外每一个节点都只包含一个字符:
(3) 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串,每个节点的所有子节点包含的字符都不相同。



字典树的插入,删除和查找都非常简单,用一个一重循环即可。
1. 从根节点开始一次搜索
2. 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索
3. 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索
4. 迭代过程...
5. 在某个节点处,关键词的所有字母已被取出,则读取附在该节点上的信息,即完成查找

例:
   Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input
  输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.

Output
对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output
2
3
1
0

代码: (字典树模板)

import java.util.LinkedList;  
public class Trie {     private int SIZE = 26;private TrieNode root;  //字典树的根Trie() {  //初始化字典树root = new TrieNode();  }  private class TrieNode {  //字典树节点private int num;//有多少单词通过这个节点,即节点字符出现的次数 private TrieNode[] son;// 所有的儿子节点private boolean isEnd;//是不是最后一个节点private char val;// 节点的值 TrieNode() {  num = 1; son = new TrieNode[SIZE];  isEnd = false;  }  }  //建立字典树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) {  node.son[pos] = new TrieNode();  node.son[pos].val = letters[i];  } else {  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 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) {  Trie tree = new Trie();  String[] strs={  "banana","band","bee","absolute","acm",};String[] prefix={"ba","b","band","abc",};for(String str : strs){  tree.insert(str);}  System.out.println(tree.has("abc"));  tree.preTraverse(tree.getRoot());  System.out.println();  //tree.printAllWords();  for(String pre : prefix){  int num=tree.countPrefix(pre);  System.out.println(pre+" "+num);  }  }  
}  
运行:


________________________________________________________________________________________________________________________________

转载出处http://www.java3z.com/cwbwebhome/article/article8/83591.html?id=4750

这篇关于字典树入门及实现(JAVA)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133113

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听