go語言數(shù)據(jù)結(jié)構(gòu)之前綴樹Trie
介紹
Trie樹:又稱為單詞查找樹,是一種樹形結(jié)構(gòu),可以應(yīng)用于統(tǒng)計字符串,會在搜索引擎系統(tǒng)中用于對文本的詞頻統(tǒng)計,下圖是一個Trie樹的結(jié)構(gòu),同時它也是在插入數(shù)時的一個順序圖.
流程
- 首先應(yīng)該先創(chuàng)建一個結(jié)構(gòu)體,里面保存的是每一個節(jié)點的信息
- 初始化根節(jié)點,根節(jié)點應(yīng)該初始化啥?啥也不用初始化,給個空就好看上圖
- 插入:串轉(zhuǎn)字符數(shù)組;遍歷數(shù)組,如果下一個節(jié)點為空,創(chuàng)建,則繼續(xù)遍歷
- 查找:串轉(zhuǎn)字符數(shù)組,遍歷如何所有字符都在樹里面存在,并則最后一個字符Node中的end不為零,就視為存在
- 刪除: 字符串轉(zhuǎn)數(shù)組,遍歷數(shù)組,在樹上找到對應(yīng)的字符,path-1
代碼
type Node struct { path int end int children [26]*Node }
在這個結(jié)構(gòu)體里面有一個path,它的作用是啥呢?當有經(jīng)過此字符的時候這個path就加一
end又是干啥的呢?當一個單詞的詞尾是這個字符的時候end這個值就加一,就代表著這個字符做為一個單詞的結(jié)尾
children是保存的啥呢?這個里面當然是保存的子節(jié)點啦,不用多說了叭~~~
初始化
func main() { list := &Node{path: 0, end: 0} }
初始化根節(jié)點,上面說過根節(jié)點里面是不用保存數(shù)據(jù)的,這個我就把里面的參數(shù)初始化成0,當然也可以不用初始化里面的參數(shù),children這里就沒有創(chuàng)建出來,因為下面我就要開始插入的操作了
插入
/* * 插入數(shù)據(jù) */ 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++ }
在插入之前先說一點:在傳入的參數(shù)中,str我傳入前我將其轉(zhuǎn)換成了小寫的,當然也可以轉(zhuǎn)換成大寫或者是大小寫都有的
插入之前先對字符串進行了一個判空的處理,如果為空就return了,在整個過程中,對字符串進行了遍歷,像我在流程中那樣說的將字符串轉(zhuǎn)成字符數(shù)組,是應(yīng)該這樣操作,但是我發(fā)現(xiàn)在golang
中可以直接對一個字符串進行了遍歷,或許將語言換成了Java就需要將其轉(zhuǎn)成字符數(shù)組了
for循環(huán)里面if判斷時為什么數(shù)組的下標要用value-'a'
這個東西來表示?可以想像一下,一個節(jié)點的children
里面有26個子元素,比如這里的vlaue是b,那么就相當于是b-a,就是b的ASCII碼減去a的ASCII碼,這個就得到的是1
索引 | 字符 |
---|---|
0 | a |
1 | b |
2 | c |
當當前的字符在數(shù)組里面沒有對應(yīng)的數(shù)據(jù)的時候創(chuàng)建一個就好,如果有的時候只要將當前數(shù)組的下標交給臨時變量tempNode
就好,所經(jīng)過字符的path加1,將最后一個字符所對應(yīng)的end加1,將其標記為一個此字符是一個單詞的結(jié)尾即可.
查找
/* *查找數(shù)據(jù) */ 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 }
同樣,在查找數(shù)據(jù)的時候也是將需要查找的字符串和前綴樹的ROOT
傳入,字符串的判空處理也是必做的,這個里面的tempNode
可以有也可以沒有,我寫tempNode
可以是說是我的一個編碼的習慣,同樣,在查找單詞的時候也是要遍歷這個字符串(在插入的時候我就已經(jīng)解釋過了我這里為啥和流程中寫的不一樣,沒有把字符串轉(zhuǎn)成字符數(shù)組),在for循環(huán)里面第一個if
如果第一個字符沒有在前綴樹中找到,那么就視為所要查找的字符串沒有出現(xiàn)在這個前綴樹里面,則將當前的字符節(jié)點交給臨時變量tempNode
,當整個循環(huán)遍歷完成之后,也就說明我要查找的字符串中的每一個字符都在這顆前綴樹里面并連續(xù)著.這個時候如果最后一個單詞的end
屬性為大于0的一個數(shù),那么這個要查找的字符串就一定在這顆前綴樹里面,返回true
統(tǒng)計以XXX開頭的單詞個數(shù)
這個前綴樹很強大,上面的解釋也說到過,可以對文本的統(tǒng)計
strArgs:=[]string{"qQYgMU","FFpdCl","nyyJmh","XJCebb","OrCiHb","xvDdzZ","nyCebF","hi","hello","nyyJmn"}
在前綴樹里面插入了這個數(shù)組里面的字符串,我現(xiàn)在要統(tǒng)計以n
開頭的單詞有幾個?如何處理呢?
這里就用到了在結(jié)構(gòu)體中定義的Path
屬性了,在插入的時候說過當有一個字符經(jīng)過這個path就會加1,所以我只需要找到所要查找前綴的最后一個單詞拿到了它的path屬性就可以知道以這個字符串開頭的單詞有幾個
/* *查找以XX開頭的數(shù)據(jù)有幾個 */ 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 }
刪除數(shù)據(jù)
刪除數(shù)據(jù)的時候同樣也是要遍歷字符串,不過在此之前應(yīng)該先查找一次這顆樹里面有沒有要刪除的字符串,如果沒有就直接return就好
/* * 刪除數(shù)據(jù) */ 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是當有字符經(jīng)過的時候加一,那么在刪除數(shù)據(jù)的時候只要查找到字符將這個字符串所經(jīng)過的字符的path減1, 我這里還加了一個else,當path等于1的時候也就是說明當前所要刪除的字符串是最后一個經(jīng)過此字符的字符串,這里直接將其置空,等系統(tǒng)回收就好了
到此這篇關(guān)于go語言數(shù)據(jù)結(jié)構(gòu)之前綴樹Trie的文章就介紹到這了,更多相關(guān)go 前綴樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Golang?基于flag庫實現(xiàn)一個簡單命令行工具
這篇文章主要介紹了Golang基于flag庫實現(xiàn)一個簡單命令行工具,Golang標準庫中的flag庫提供了解析命令行選項的能力,我們可以基于此來開發(fā)命令行工具,下文詳細介紹。需要的小伙伴可以參考一下2022-08-08golang結(jié)構(gòu)體與json格式串實例代碼
本文通過實例代碼給大家介紹了golang結(jié)構(gòu)體與json格式串的相關(guān)知識,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-10-10go語言中sort包的實現(xiàn)方法與應(yīng)用詳解
golang中也實現(xiàn)了排序算法的包sort包,所以下面這篇文章主要給大家介紹了關(guān)于go語言中sort包的實現(xiàn)方法與應(yīng)用的相關(guān)資料,文中通過示例代碼介紹的非常詳細,需要的朋友們可以參考借鑒,下面隨著小編來一起學習學習吧。2017-11-11Go使用Gin+mysql實現(xiàn)增刪改查的詳細實例
golang本身沒有提供連接mysql的驅(qū)動,但是定義了標準接口供第三方開發(fā)驅(qū)動,下面這篇文章主要給大家介紹了關(guān)于Go使用Gin+mysql實現(xiàn)增刪改查的相關(guān)資料,需要的朋友可以參考下2022-12-12GO 函數(shù)式選項模式(Functional Options Pattern)
Option模式支持傳遞多個參數(shù),并且在參數(shù)個數(shù)、類型發(fā)生變化時保持兼容性,任意順序傳遞參數(shù),下面給大家介紹GO 函數(shù)式選項模式(Functional Options Pattern)的相關(guān)知識,感興趣的朋友一起看看吧2021-10-10