go语言数据结构之前缀树Trie
作者:呆呆灿 发布时间:2023-08-05 18:15:50
介绍
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的时候也就是说明当前所要删除的字符串是最后一个经过此字符的字符串,这里直接将其置空,等系统回收就好了
来源:https://juejin.cn/post/6977643579149647886
猜你喜欢
- 今天在写BLOG的Trackback时,需要用到当前页的URL地址,并且包括?后的所有参数。在网上看到以下的这段ASP代码,它的
- 很多网站需要将好的会员号留着,或用于日后的盈利。实现方法不是本文讨论范围,本文仅列出用于检测靓号类型的一些正则。靓号检测:主要可以检测连号(
- 1,jdk配置由于jdk官网的链接不直接支持wget,可以使用下面的方法下载jdk,其中jdk版本为jdk1.8.0_91:wget --n
- 现在我们常见到有些网站常有这样个功能:有个按钮(如工作职位或省份或地区的选择等等)你一点就跳出一个图层(对话框)让你选择之类的。关闭它就点右
- 需求说明当用户申请售后,商家未在n小时内处理,系统自动进行退款。商家拒绝后,用户可申请客服介入,客服x天内超时未处理,系统自动退款。用户收到
- 1、800*600下,网页宽度保持在778以内,就不会出现水平滚动条,高度则视版面和内容决定。2、1024*768下,网页宽度保持在1002
- 首先看一下这三个函数:rtrim() ltrim() trim();rtrim()定义以及用法: rtrim() 函数移除字符串右侧的空白字
- 看了不少朋友的个人网站,有一个小问题,似乎很多朋友都忽略了,那就是版权声明的写法。虽然那只是一小行字,不过作为设计师也好,作为个人的爱好也好
- 初步介绍 当然,我知道现在有成千上万个关于 用CSS处理圆角 的教程,但不管怎么说,我仍然想把这篇文章展示给您。也希望您会发现这篇文章会非常
- 方法一:利用Cookies对象 因为Cookies对象把变量的值保存在浏览器客户端,所以可以根据Cookies保存的IsVoted的值来判断
- image.jsp------------------------------生成随机验证码图片的Jsp页面 代码如下: <
- 步骤——1:定位在通过与客户,或与和客户接触的业务人员交流,做出一个准确的定位.定位的准确与否,虽然不能决定一定通过,但如果定位不准或相差太
- 是建立一个数据集 前面应该先定义此数据集 dim rs as adodb.recordset 然后就可以用 set rs=server.Cr
- 由于现在在公司负责制作标准的静态页面,为了增强客户体验,所以经常要做些AJAX效果,也学你也和我一样在,学习AJAX。而设计AJAX时使用的
- 本文实例为大家分享了python实现图像拼接的具体代码,供大家参考,具体内容如下1.待拼接的图像2. 基于SIFT特征点和RANSAC方法得
- 因为正则不够完善,所以代码中不能直接出现 <? 和 ?>如果是字符串,可以拆开写 "<" + &quo
- asp正则表达式检测字符串是否是数字及字母。<% '函数:CheckString(strng) '
- 简介显示大量已经按类别(不是很多)排序的数据但没有类别分界线,用户很难找到所需要的类别。例如,数据库中只有9个类别(8个不同的类别和1个nu
- 最近在做一个程序正好需要用到此方面,在网上找到过相应的程序,但用起来都非常恶,于是乎只好自己实现一个了。 首先实现两个函数用来操作光标:
- 一年前网上还找不到关于 inline-block 属性的文章,为了方便大家更好的理解该属性,当时总结整理了篇《display:inline-