极客笔记用Golang实现具有压缩节点的Trie
Trie是一种类似树的数据结构，用于高效存储和检索字符串，使其在自动完成、字典实现和模式匹配等任务中非常有价值。压缩节点技术通过合并节点间的共同前缀来优化空间使用，从而得到一个更节省内存的Trie。在本文中，我们将使用两种方法来实现具有压缩节点的Trie：第一种方法利用映射，第二种方法使用数组。
解释
压缩Trie是一种Trie数据结构，通过将连续节点与单一分支合并为一个压缩节点来节省空间。在下面的表示中，根节点[c]对所有分支都是相同的。在下面的结构中，“card”和“care”都代表共同前缀“car”。与为每个字符单独创建一个节点不同，一个压缩节点表示这个共享前缀。
c
/ \
ar o
/ |
red n
|
d
语法
type TrieNode struct{ children map[rune]*TrieNode; isEnd bool }
语法 TrieNode 结构包含一个名为 “children” 的映射，它使用符文（字符）作为键存储对子节点的引用。它允许在字符和子节点之间进行有效映射，使其适用于压缩后缀树节点。”isEnd” 布尔标志用于指示当前节点是否是一个单词的结束。
算法
- 创建一个名为 TrieNode 的结构来表示树中的每个节点。每个 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数据结构。在这里，我们使用压缩节点的方法，但不是用map，而是用指向TrieNode的指针数组来表示一个节点的子节点。我们创建一个Trie数据结构，将单词插入到其中，并执行搜索操作以检查特定单词是否存在于Trie中。与基于map的方法相比，这种方法提供了更快的访问速度和稍微减少的内存开销。
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
实际应用
自动完成和搜索建议
压缩节点的字典树常用于搜索引擎和文本预测系统中，用于提供自动完成和搜索建议功能。当用户输入时，系统根据他们输入的前缀快速检索建议。例如，当您在Google中开始输入搜索查询时，它会实时提供相关的搜索词。字典树高效地存储了大量单词，并且其压缩节点可以减少内存使用，同时保持快速的自动完成建议检索时间。
拼写检查和纠正
压缩节点的字典树对拼写检查和校对应用非常有用。它们可以快速确定一个单词是否存在于字典中，并提供纠正拼写错误的建议。例如，像Microsoft Word这样的文字处理软件使用类似的技术来下划线拼写错误的单词并提供纠正建议。字典树结构允许快速搜索和建议，而压缩节点可控制内存需求，实现高效的实时拼写检查和纠正。
结论
压缩字典树是一种节省空间的数据结构，通过将公共分支合并为压缩节点来节约空间。在本文中，我们看了如何在Golang中实现具有压缩节点的字典树，这里我们使用了两个不同的示例，第一个示例使用映射来表示压缩节点，而第二个示例则使用数组来达到相同的目的。压缩节点的独特之处在于它们可以通过合并节点之间的公共前缀来节省内存，从而实现更高效的字典树。