資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用壓縮節點實現 Trie 的 Go 語言程式
Trie 是一種樹形資料結構，用於高效儲存和檢索字串，使其成為自動完成、字典實現和模式匹配等任務的寶貴工具。壓縮節點技術透過合併節點之間的公共字首來最佳化空間使用，從而產生更節省記憶體的 Trie。在本文中，我們將探討使用兩種方法在 Go 語言中實現帶有壓縮節點的 Trie，第一種方法使用對映，第二種方法使用陣列。
解釋
壓縮 Trie 是一種 Trie 資料結構，它透過將具有單個分支的連續節點組合成一個壓縮節點來節省空間。在下面的表示中，根節點 [c] 對所有分支都是相同的。在下面的結構中，“card”和“care”都表示公共字首“car”。無需為每個字元建立單獨的節點，單個壓縮節點即可表示此共享字首。
c
/ \
ar o
/ |
red n
|
d
語法
type TrieNode struct{ children map[rune]*TrieNode; isEnd bool }
TrieNode 結構體包含一個名為“children”的對映，它使用 rune（字元）作為鍵來儲存對子節點的引用。它允許在字元和子節點之間進行高效對映，使其適用於壓縮 Trie 節點。“isEnd”布林標誌用於指示單詞是否在當前節點結束。
演算法
建立一個名為 TrieNode 的結構體來表示 Trie 中的每個節點。每個 TrieNode 應該有一個名為“children”的對映，用於儲存子節點，其鍵為字元，值為指向 TrieNode 的指標。
包含一個布林變數“isEnd”來指示當前節點是否表示單詞的結尾。
將空根節點初始化為 Trie 的起點。
遍歷所有字元後，透過將“isEnd”設定為 true 來將最後一個節點標記為單詞的結尾。
要在 Trie 中搜索單詞，請從根節點開始遍歷單詞的字元。如果在任何時候都找不到字元的子節點，或者到達單詞的結尾但“isEnd”為 false，則該單詞不存在於 Trie 中。
要從 Trie 中刪除單詞，請按照前面所述搜尋該單詞。
示例 1
在這個例子中，我們將使用對映實現具有壓縮節點的 Trie 資料結構。在這裡，我們建立一個 Trie 資料結構，將單詞插入其中，並執行搜尋操作以檢查 Trie 中是否存在特定單詞。這種方法可以節省記憶體並減小 Trie 的整體大小。
package main
import "fmt"
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{
root: &TrieNode{
children: make(map[rune]*TrieNode),
isEnd: false,
},
}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
if _, ok := node.children[ch]; !ok {
node.children[ch] = &TrieNode{
children: make(map[rune]*TrieNode),
isEnd: false,
}
}
node = node.children[ch]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
if _, ok := node.children[ch]; !ok {
return false
}
node = node.children[ch]
}
return node.isEnd
}
func main() {
trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("banana")
fmt.Println("Search 'apple':", trie.Search("apple"))
fmt.Println("Search 'app':", trie.Search("app"))
fmt.Println("Search 'banana':", trie.Search("banana"))
fmt.Println("Search 'orange':", trie.Search("orange"))
}
輸出
Search 'apple': true Search 'app': true Search 'banana': true Search 'orange': false
示例 2
在這個例子中，我們將使用陣列實現具有壓縮節點的 Trie 資料結構。在這裡，我們使用壓縮節點方法，但是我們使用指向 TrieNode 的陣列而不是對映來表示節點的子節點。我們建立一個 Trie 資料結構，將單詞插入其中，並執行搜尋操作以檢查 Trie 中是否存在特定單詞。與基於對映的方法相比，這種方法提供了更快的訪問速度和略微減少的記憶體開銷。
package main
import "fmt"
const alphabetSize = 26
type TrieNode struct {
children [alphabetSize]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{
root: &TrieNode{},
}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
index := ch - 'a'
if node.children[index] == nil {
node.children[index] = &TrieNode{}
}
node = node.children[index]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
index := ch - 'a'
if node.children[index] == nil {
return false
}
node = node.children[index]
}
return node.isEnd
}
func main() {
trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("banana")
fmt.Println("Search 'apple':", trie.Search("apple"))
fmt.Println("Search 'app':", trie.Search("app"))
fmt.Println("Search 'banana':", trie.Search("banana"))
fmt.Println("Search 'orange':", trie.Search("orange"))
}
輸出
Search 'apple': true Search 'app': true Search 'banana': true Search 'orange': false
現實生活中的應用
自動完成和搜尋建議
帶有壓縮節點的 Trie 常用於搜尋引擎和文字預測系統中，以提供自動完成和搜尋建議功能。當用戶鍵入時，系統會根據他們輸入的字首快速檢索建議。例如，當您在 Google 中開始鍵入搜尋查詢時，它會即時建議相關的搜尋詞。Trie 有效地儲存大量單詞，其壓縮節點有助於減少記憶體使用，同時保持自動完成建議的快速檢索時間。
拼寫檢查和糾正
帶有壓縮節點的 Trie 在拼寫糾正和檢查應用程式中非常有用。它們可以快速識別字典中是否存在單詞，並提供更正拼寫錯誤單詞的建議。例如，像 Microsoft Word 這樣的文字處理軟體使用類似的技術來下劃線拼寫錯誤的單詞並建議更正。Trie 結構允許快速搜尋和建議，而壓縮節點則可以控制記憶體需求，從而實現高效的即時拼寫檢查和糾正。
結論
壓縮 Trie 是一種節省空間的資料結構，它透過將公共分支合併到壓縮節點中來實現。在本文中，我們研究瞭如何在 Go 語言中實現帶有壓縮節點的 Trie，我們使用了兩個不同的例子，第一個例子使用對映來表示壓縮節點，而第二個例子則使用陣列來實現相同目的。壓縮節點的獨特之處在於它們能夠透過合併節點之間的公共字首來節省記憶體，從而產生更節省記憶體的 Trie。
瀏覽量：138
