个人中心
gpt4 book ai didi

Java中关于字典树的算法实现

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 33 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java中关于字典树的算法实现由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

字典树（前缀树）算法实现 。

前言

字典树，又称单词查找树，是一个典型的 一对多的字符串匹配算法。“一”指的是一个模式串，“多”指的是多个模板串。字典树经常被用来统计、排序和保存大量的字符串。它利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较.

字典树有3个基本性质:

  1. 根节点不包含字符，其余的每个节点都包含一个字符；
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  3. 每个节点的所有子节点包含的字符都不相同。

Java中关于字典树的算法实现

pass参数：代表从这个点经过的单词数量。root根即就是整棵树有多少单词.

end参数： 代表在这个点结束的单词有几个。例如： 上图有两个 hello，在o结点的end参数就是2.

实现的基本功能： 增删查.

算法解析

首先是结点的参数:

?
1
2
3
4
5
6
7
8
9
10
11
public class Node {
     public int pass;
     public int end;
     public Node[] nexts; //下一个字母的地址
    
     public Node() {
         pass = 0 ;
         end = 0 ;
         nexts = new Node[ 26 ]; //这里我们就以小写字母为例
     }
}

下面就是基本功能的实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.Scanner;
 
public class Main {
     public static void main(String[] args) {
         String[] arr = { "hello" , "hello" };
 
         Trie root = new Trie();
         for ( int i = 0 ; i < arr.length; i++) {
             root.addWord(arr[i]);
         }
         //root.delWord("hello");
         Scanner sc = new Scanner(System.in);
         String s = sc.nextLine();
 
         if (root.searchWord(s) != 0 ) {
             System.out.println( "该字典树有这个" + s + " 单词" );
         }
 
     }
     public static class Node {
         public int pass;
         public int end;
         public Node[] nexts; //下一个字母的地址
 
         public Node() {
             pass = 0 ;
             end = 0 ;
             nexts = new Node[ 26 ];
         }
     }
     public static class Trie {
         private Node root;
 
         public Trie() {
             root = new Node();
         }
         //增加
         public void addWord(String str) {
             char [] arr = str.toCharArray();
             root.pass++;
             Node node = root;
             for ( char s : arr) {
                 int index = s - 'a' ; //以相应的ASCII码值差值，进行数组的下标存储
                 if (node.nexts[index] == null ) {
                     node.nexts[index] = new Node();
                 }
                 node = node.nexts[index];
                 node.pass++; //经过这个结点，pass就加1
             }
             node.end++;
         }
 
         //删除
         public void delWord(String str) {
             //删除之前，应该查询一下这颗树有没有这个单词
             while (searchWord(str) != 0 ) {
                 char [] arr = str.toCharArray();
                 Node node = root;
                   node.pass--;
                 for ( int i = 0 ; i < str.length(); i++) {
                     int index = arr[i] - 'a' ;
                     node = node.nexts[index];
                     node.pass--;
                 }
                 node.end--;
             }
         }
 
         //查找
         public int searchWord(String str) {
             if (str == null ) {
                 return 0 ;
             }
             char [] arr = str.toCharArray();
             Node node = root;
             for ( int i = 0 ; i < str.length(); i++) {
                 int index = arr[i] - 'a' ;
                 if (node.nexts[index] == null ) {
                     return 0 ;
                 }
                 node = node.nexts[index];
             }
             return node.end; //返回最后那一个结点的end值即可
         }
     }
}

到此这篇关于Java中关于字典树的算法实现的文章就介绍到这了,更多相关Java 字典树内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/x0919/article/details/118311179 。

最后此篇关于Java中关于字典树的算法实现的文章就讲到这里了,如果你想了解更多关于Java中关于字典树的算法实现的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

33 4 0
文章推荐： java应用开发之JVM运行时内存分析
文章推荐： 建行预约数字人民币红包 每周五自动开奖
文章推荐： 平安口袋银行申领电子社保领5元现金红包
文章推荐： springboot如何重定向携带数据 RedirectAttributes
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com