go语言数据结构之前缀树Trie

目录
  • 介绍
  • 流程
  • 代码
  • 初始化
  • 插入
  • 查找
  • 统计以XXX开头的单词个数
  • 删除数据

介绍

Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图.

流程

  • 首先应该先创建一个结构体,里面保存的是每一个节点的信息
  • 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图
  • 插入:串转字符数组;遍历数组,如果下一个节点为空,创建,则继续遍历
  • 查找:串转字符数组,遍历如何所有字符都在树里面存在,并则最后一个字符Node中的end不为零,就视为存在
  • 删除: 字符串转数组,遍历数组,在树上找到对应的字符,path-1

代码

type Node struct {
	path     int
	end      int
	children [26]*Node
}

在这个结构体里面有一个path,它的作用是啥呢?当有经过此字符的时候这个path就加一

end又是干啥的呢?当一个单词的词尾是这个字符的时候end这个值就加一,就代表着这个字符做为一个单词的结尾

children是保存的啥呢?这个里面当然是保存的子节点啦,不用多说了叭~~~

初始化

func main() {
	list := &Node{path: 0, end: 0}
}

初始化根节点,上面说过根节点里面是不用保存数据的,这个我就把里面的参数初始化成0,当然也可以不用初始化里面的参数,children这里就没有创建出来,因为下面我就要开始插入的操作了

插入

/*
 * 插入数据
*/
func insertTrie(str string, root *Node) {
	if len(str) == 0 {
		return
	}
	tempNode := root
	for _, value := range str {
		if tempNode.children[value-'a'] == nil {
			tempNode.children[value-'a'] = &Node{path: 0, end: 0}
		}
		tempNode = tempNode.children[value-'a']
		tempNode.path++
	}
	tempNode.end++
}

在插入之前先说一点:在传入的参数中,str我传入前我将其转换成了小写的,当然也可以转换成大写或者是大小写都有的

插入之前先对字符串进行了一个判空的处理,如果为空就return了,在整个过程中,对字符串进行了遍历,像我在流程中那样说的将字符串转成字符数组,是应该这样操作,但是我发现在golang中可以直接对一个字符串进行了遍历,或许将语言换成了Java就需要将其转成字符数组了

for循环里面if判断时为什么数组的下标要用value-'a'这个东西来表示?可以想像一下,一个节点的children里面有26个子元素,比如这里的vlaue是b,那么就相当于是b-a,就是b的ASCII码减去a的ASCII码,这个就得到的是1

索引 字符
0 a
1 b
2 c

当当前的字符在数组里面没有对应的数据的时候创建一个就好,如果有的时候只要将当前数组的下标交给临时变量tempNode就好,所经过字符的path加1,将最后一个字符所对应的end加1,将其标记为一个此字符是一个单词的结尾即可.

查找

/*
 *查找数据
*/
func searchStr(str string,root *Node) bool {
	if len(str) == 0{
		return false
	}
	tempNode := root
	for _,value := range str{

		if tempNode.children[value - 'a'] == nil{
			return false
		}
		tempNode = tempNode.children[value - 'a']
	}
	if tempNode.end != 0{
		return true
	}
	return false
}

同样,在查找数据的时候也是将需要查找的字符串和前缀树的ROOT传入,字符串的判空处理也是必做的,这个里面的tempNode可以有也可以没有,我写tempNode可以是说是我的一个编码的习惯,同样,在查找单词的时候也是要遍历这个字符串(在插入的时候我就已经解释过了我这里为啥和流程中写的不一样,没有把字符串转成字符数组),在for循环里面第一个if如果第一个字符没有在前缀树中找到,那么就视为所要查找的字符串没有出现在这个前缀树里面,则将当前的字符节点交给临时变量tempNode,当整个循环遍历完成之后,也就说明我要查找的字符串中的每一个字符都在这颗前缀树里面并连续着.这个时候如果最后一个单词的end属性为大于0的一个数,那么这个要查找的字符串就一定在这颗前缀树里面,返回true

统计以XXX开头的单词个数

这个前缀树很强大,上面的解释也说到过,可以对文本的统计

strArgs:=[]string{"qQYgMU","FFpdCl","nyyJmh","XJCebb","OrCiHb","xvDdzZ","nyCebF","hi","hello","nyyJmn"}

在前缀树里面插入了这个数组里面的字符串,我现在要统计以n开头的单词有几个?如何处理呢?

这里就用到了在结构体中定义的Path属性了,在插入的时候说过当有一个字符经过这个path就会加1,所以我只需要找到所要查找前缀的最后一个单词拿到了它的path属性就可以知道以这个字符串开头的单词有几个

/*
 *查找以XX开头的数据有几个
*/
func searchPrefixCount(str string,root *Node) int{
	if len(str) == 0{
		return -1
	}
	tempNode := root
	for _,value := range str{
		if tempNode.children[value - 'a'] == nil {
			return 0
		}
		tempNode = tempNode.children[value - 'a']
		return tempNode.path
	}
	return -1
}

删除数据

删除数据的时候同样也是要遍历字符串,不过在此之前应该先查找一次这颗树里面有没有要删除的字符串,如果没有就直接return就好

/*
 * 删除数据
*/
func delStr(str string,root *Node) bool {
	if len(str) == 0{
		return false
	}
	if !searchStr(strings.ToLower(str),root) {
		return false
	}
	tempNode := root
	for _,value := range str{
		if tempNode.children[value - 'a'].path > 1 {
			tempNode.children[value - 'a'].path--
			tempNode = tempNode.children[value - 'a']
		}else{
			tempNode.children[value - 'a'] = nil
			return true
		}
	}
	return false
}

path是当有字符经过的时候加一,那么在删除数据的时候只要查找到字符将这个字符串所经过的字符的path减1, 我这里还加了一个else,当path等于1的时候也就是说明当前所要删除的字符串是最后一个经过此字符的字符串,这里直接将其置空,等系统回收就好了

到此这篇关于go语言数据结构之前缀树Trie的文章就介绍到这了,更多相关go 前缀树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Go语言七篇入门教程二程序结构与数据类型

    目录 1. 程序结构 1.1 名称 1.2 声明 1.3 注释 1.4 单双引号 1.5 输出 2. 数据类型 2.1 整型 2.2 浮点型 2.3 复数 2.4 布尔型 2.5 字符串 2.6 常量 2.7 数组 2.8 切片 2.9 map 2.10 结构体 2.11 JSON 3. 流程控制 3.1 条件语句 3.2 选择语句 3.3 循环语句 如何学习Go 1. 程序结构 1.1 名称 如果一个实体名称在函数中声明,它只在函数局部有效.如果声明在函数外,它将对包里面的所有源文件可见. 实

  • 使用go实现常见的数据结构

    1 golang常见数据结构实现 1.1 链表 举单链表的例子,双向链表同理只是多了pre指针. 定义单链表结构: type LinkNode struct { Data int64 NextNode *LinkNode } 构造链表及打印链表: func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 链接到 nod

  • Go语言的数据结构转JSON

    目录 结构体转为 JSON 格式 接口转为 JSON 格式 Marshal() 函数的原型 总结 在日常工作中,除了需要从 JSON 转化为 Go 的数据结构.但往往相反的情况是:我们需要将数据以 JSON 字符串的形式发送到 Web 服务器.今天我们将学会如何从一个结构化数据编码为 JSON . Json(Javascript Object Nanotation)是一种数据交换格式,常用于前后端数据传输.任意一端将数据转换成json 字符串,另一端再将该字符串解析成相应的数据结构,如strin

  • Go 数据结构之二叉树详情

    目录 Go 语言实现二叉树 定义二叉树的结构 二叉树遍历 创建二叉树 插入值 测试 前言: 树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同. 而在其中最常用的树之一是二叉树. 二叉树是一棵树,其中每个节点最多可以有两个孩子. 一个孩子被识别为左孩子,另一个孩子被识别为右孩子. 二叉树是一种数据结构,在每个节点下面最多存在两个其他节点.即一个节点要么连接至一个.两个节点或不连接其他节点. 树形结构的深度(也被称作高度)则被定义为根节点为根节点

  • Django更新models数据库结构步骤

    有时候在我们使用Django设计了models中的数据库结构,并且已经同步了数据库之后,我们突然想在数据表中更新或者增加新的字段,也就是需要修改数据库的结构,会出现以下的问题: C:\Users\Administrator\Desktop\Web开发\Django_Demo\jkxy>python manage.py makemigrations You are trying to add a non-nullable field 'grade' to student without a def

  • Go语言模型:string的底层数据结构与高效操作详解

    Golang的string类型底层数据结构简单,本质也是一个结构体实例,且是const不可变. string的底层数据结构 通过下面一个例子来看: package main import ( "fmt" "unsafe" ) // from: string.go 在GoLand IDE中双击shift快速找到 type stringStruct struct { array unsafe.Pointer // 指向一个 [len]byte 的数组 length in

  • go语言数据结构之前缀树Trie

    目录 介绍 流程 代码 初始化 插入 查找 统计以XXX开头的单词个数 删除数据 介绍 Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图. 流程 首先应该先创建一个结构体,里面保存的是每一个节点的信息 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图 插入:串转字符数组:遍历数组,如果下一个节点为空,创建,则继续遍历 查找:串转字符数组,遍历如何所有字符都在树

  • 详解Java前缀树Trie的原理及代码实现

    目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起

  • C语言数据结构之中缀树转后缀树的实例

    C语言数据结构之中缀树转后缀树的实例 对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢? 网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构. 1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式

  • C语言数据结构系列之树的概念结构和常见表示方法

    0x00 树的概念 树是一种非线性的数据结构,它是由 n(n >= 0)个有限节点组成的一个具有层次关系的集合. 那么为什么叫 "树" 呢? 我们之所以把它成为 "树",是因为它很像我们现实生活中的树.只是它是倒过来的,根朝上叶子朝下. 0x01 树的结构 ① 有一个特殊的节点,成为根节点,根节点不存在前驱节点. ② 除根节点外,其余节点被分成 M(M>0) 个互不相交的集合 T1.T2.…….Tm,期中没一个集合 Ti(1 <= i <=

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • javascript trie前缀树的示例

    引子 Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构. 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点, 假定我们只对字母与数字进行处理,那么每个节点至少有52+10个子节点.为了节省内存,我们可以用链表或数组.在JS中我们直接用数组,因为JS的数组是动态的,自带优化

  • Go 语言前缀树实现敏感词检测

    目录 一.前言 二.敏感词检测 暴力匹配 正则匹配 三.Go 语言实现敏感词前缀树 前缀树结构 添加敏感词 匹配敏感词 过滤特殊字符 添加拼音检测 四.源代码 一.前言 大家都知道游戏文字.文章等一些风控场景都实现了敏感词检测,一些敏感词会被屏蔽掉或者文章无法发布.今天我就分享用Go实现敏感词前缀树来达到文本的敏感词检测,让我们一探究竟! 二.敏感词检测 实现敏感词检测都很多种方法,例如暴力.正则.前缀树等.例如一个游戏的文字交流的场景,敏感词会被和谐成 * ,该如何实现呢?首先我们先准备一些敏

  • C语言数据结构之平衡二叉树(AVL树)实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

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

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

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // returns true trie.search("app&

随机推荐