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

字典树(前缀树)算法实现

前言

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

字典树有3个基本性质:

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

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

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

实现的基本功能: 增删查。

算法解析

首先是结点的参数:

public class Node {
    public int pass;
    public int end;
    public Node[] nexts; //下一个字母的地址

    public Node() {
        pass = 0;
        end = 0;
        nexts = new Node[26]; //这里我们就以小写字母为例
    }
}

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

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 字典树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-09-12

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

简介 Trie树,又称为前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串.与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定.一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串. 它的主要特点如下: 根节点不包含字符,除根节点外的每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 每个节点的所有子节点包含的字符都不相同. 如下是一棵典型的Trie树: Trie的来源是Retrie

详解字典树Trie结构及其Python代码实现

字典树(Trie)可以保存一些字符串->值的对应关系.基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串. Trie 的强大之处就在于它的时间复杂度.它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关.Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题:Trie 的缺点是空间消耗很高. 至于Trie树的实现

PHP字典树(Trie树)定义与实现方法示例

本文实例讲述了PHP字典树(Trie树)定义与实现方法.分享给大家供大家参考,具体如下: Trie树的概念(百度的解释):字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高. 我的理解是用来做字符串搜索的,每个节点只包含一个字符,比如录入单词"world",则树的结构

Trie树_字典树(字符串排序)简介及实现

1.综述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie树结构的优点在于:1) 不限制子节点的数量: 2) 自定义的输入序列化,突破了具体语言.应用的限制,成为一个通用的框架: 3) 可以进行最大Tokens序列长度的限制:4) 根据已定阈值输出重复的字符串:5) 提

C#实现前向最大匹、字典树(分词、检索)的示例代码

场景:现在有一个错词库,维护的是错词和正确词对应关系.比如:错词"我门"对应的正确词"我们".然后在用户输入的文字进行错词校验,需要判断输入的文字是否有错词,并找出错词以便提醒用户,并且可以显示出正确词以便用户确认,如果是错词就进行替换. 首先想到的就是取出错词List放在内存中,当用户输入完成后用错词List来foreach每个错词,然后查找输入的字符串中是否包含错词.这是一种有效的方法,并且能够实现.问题是错词的数量比较多,目前有10多万条,将来也会不断更新扩展

Python实现简单字典树的方法

本文实例讲述了Python实现简单字典树的方法.分享给大家供大家参考,具体如下: #coding=utf8 """代码实现了最简单的字典树,只支持由小写字母组成的字符串. 在此代码基础上扩展一下,就可以实现比较复杂的字典树,比如带统计数的,或支持更多字符的字典树, 或者是支持删除等操作. """ class TrieNode(object): def __init__(self): # 是否构成一个完成的单词 self.is_word = Fal

字典树的基本知识及使用C语言的相关实现

概念 如果我们有and,as,at,cn,com这些关键词,那么trie树(字典树)是这样的: 从上面的图中,我们或多或少的可以发现一些好玩的特性. 第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符. 第二:从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串. 第三:每个单词的公共前缀作为一个字符节点保存. 使用范围 既然学Trie树,我们肯定要知道这玩意是用来干嘛的. 第一:词频统计. 可能有人要说了,词频统计简单啊,一个hash或者一个堆就可以打完收工,但问题

Python数据结构与算法之字典树实现方法示例

本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

laravel admin实现分类树/模型树的示例代码

修改模型Category.php <?php namespace App\Admin\Models; use Encore\Admin\Traits\AdminBuilder; use Encore\Admin\Traits\ModelTree; use Illuminate\Database\Eloquent\Model; class Category extends Model { use ModelTree, AdminBuilder; protected $table = 'catego

python数据类型_元组、字典常用操作方法(介绍)

元组 Python的元组与列表类似,不同之处在于元组的元素不能修改. 元组使用小括号,列表使用方括号. 元组创建很简单,只需要在括号中添加元素,并使用逗号隔开即可. tp=(1,2,3,'a','b') a = 'hello world' #这样定义是str类型 b = ('hello world') #定义元组时,如果只有一个元素,那么b的类型就是str c = ('hello world',) print(type(c)) 元组只有count和index方法,如下: tp = ('127.0