go語言資料結構之字首樹Trie

介紹

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

噹噹前的字元在陣列裡面沒有對應的資料的時候建立一個就好,如果有的時候只要將當前陣列的下標交給臨時變數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 字首樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！