Go: 高效处理字符串的利器,前缀树及其算法研究

运维开发王义杰

发布于 2024-05-29 19:01:03

1930

发布于 2024-05-29 19:01:03

文章被收录于专栏：运维开发王义杰

介绍

前缀树（Trie），又称字典树，是一种专门处理字符串的数据结构。它能够高效地进行字符串插入、删除和查找操作。前缀树特别适用于需要快速搜索的应用场景，如自动补全、拼写检查和IP路由查找等。

前缀树的基本结构

前缀树是一种多叉树，其中每个节点表示一个字符串中的字符。从根节点到某个节点路径上的字符拼接起来，形成一个字符串。前缀树的每条边表示一个字符，每个节点代表某个字符串的前缀。

示例

假设我们要构建一个包含以下单词的前缀树："cat", "cap", "bat", "bar"。前缀树的结构如下：

       (root)
       /    \
      c      b
     / \    / \
    a   a  a   a
   /    \ /   / \
  t      p   t   r

前缀树的操作

插入操作

插入操作是将一个字符串逐字符地插入前缀树中。每次插入时，从根节点开始，依次检查每个字符是否存在于当前节点的子节点中。如果不存在，则创建新的子节点。

代码示例


go
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)}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[char]
    }
    node.isEnd = true
}

查找操作

查找操作是验证一个字符串是否存在于前缀树中。逐字符检查字符串中的每个字符是否存在于当前节点的子节点中。如果所有字符都能匹配并且最后一个字符所在的节点是一个结束节点，那么该字符串存在于前缀树中。

代码示例


go
func (t *Trie) Search(word string) bool {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            return false
        }
        node = node.children[char]
    }
    return node.isEnd
}

删除操作

删除操作相对复杂，需要逐字符检查并删除多余的节点。在删除一个字符串时，需保证不破坏其他字符串的结构。

代码示例


go
func (t *Trie) Delete(word string) bool {
    return t.deleteHelper(t.root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
    if node == nil {
        return false
    }
    if depth == len(word) {
        if !node.isEnd {
            return false
        }
        node.isEnd = false
        return len(node.children) == 0
    }
    char := rune(word[depth])
    if t.deleteHelper(node.children[char], word, depth+1) {
        delete(node.children, char)
        return !node.isEnd && len(node.children) == 0
    }
    return false
}

前缀树的应用

自动补全

在搜索框中输入时，前缀树可以提供前缀匹配的快速提示。例如，输入“ca”时，可以快速提示“cat”和“cap”。

拼写检查

通过前缀树可以快速查找词典中是否存在某个单词，帮助实现拼写检查功能。

IP路由查找

在网络路由中，前缀树可以用于存储和查找IP地址前缀，从而实现高效的路由查找。

结论

前缀树是一种高效处理字符串的数据结构，适用于多种应用场景。掌握前缀树的基本操作和应用，可以在实际开发中提升程序性能和用户体验。

完整代码


go
package trie

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)}}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, char := range word {
		if _, found := node.children[char]; !found {
			node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		node = node.children[char]
	}
	node.isEnd = true
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, char := range word {
		if _, found := node.children[char]; !found {
			return false
		}
		node = node.children[char]
	}
	return node.isEnd
}

func (t *Trie) Delete(word string) bool {
	return t.deleteHelper(t.root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
	if node == nil {
		return false
	}
	if depth == len(word) {
		if !node.isEnd {
			return false
		}
		node.isEnd = false
		return len(node.children) == 0
	}
	char := rune(word[depth])
	if t.deleteHelper(node.children[char], word, depth+1) {
		delete(node.children, char)
		return !node.isEnd && len(node.children) == 0
	}
	return false
}

单元测试用例


go
package trie

import "testing"

func TestTrie_Insert(t *testing.T) {
	trie := NewTrie()

	// Insert some words
	trie.Insert("apple")
	trie.Insert("app")
	trie.Insert("banana")
	trie.Insert("bat")

	// Check if words are found
	if !trie.Search("apple") {
		t.Errorf("Expected 'apple' to be found")
	}
	if !trie.Search("app") {
		t.Errorf("Expected 'app' to be found")
	}
	if !trie.Search("banana") {
		t.Errorf("Expected 'banana' to be found")
	}
	if !trie.Search("bat") {
		t.Errorf("Expected 'bat' to be found")
	}

	// Check if non-existent words are not found
	if trie.Search("orange") {
		t.Errorf("Expected 'orange' to not be found")
	}
	if trie.Search("appl") {
		t.Errorf("Expected 'appl' to not be found")
	}
	if trie.Search("b") {
		t.Errorf("Expected 'b' to not be found")
	}
}

func TestTrie_Insert_WithEmptyRoot(t *testing.T) {
	trie := NewTrie()

	// Insert a word
	trie.Insert("apple")

	// Check if the word is found
	if !trie.Search("apple") {
		t.Errorf("Expected 'apple' to be found")
	}

	// Check if non-existent words are not found
	if trie.Search("orange") {
		t.Errorf("Expected 'orange' to not be found")
	}
	if trie.Search("appl") {
		t.Errorf("Expected 'appl' to not be found")
	}
	if trie.Search("b") {
		t.Errorf("Expected 'b' to not be found")
	}
}

func TestTrie_Insert_WithExistingRoot(t *testing.T) {
	trie := NewTrie()

	// Insert a word
	trie.Insert("apple")

	// Insert another word
	trie.Insert("app")

	// Check if the words are found
	if !trie.Search("apple") {
		t.Errorf("Expected 'apple' to be found")
	}
	if !trie.Search("app") {
		t.Errorf("Expected 'app' to be found")
	}

	// Check if non-existent words are not found
	if trie.Search("orange") {
		t.Errorf("Expected 'orange' to not be found")
	}
	if trie.Search("appl") {
		t.Errorf("Expected 'appl' to not be found")
	}
	if trie.Search("b") {
		t.Errorf("Expected 'b' to not be found")
	}
}

func TestTrie_Insert_WithLongerWord(t *testing.T) {
	trie := NewTrie()

	// Insert a word
	trie.Insert("apple")

	// Insert a longer word
	trie.Insert("applet")

	// Check if the words are found
	if !trie.Search("apple") {
		t.Errorf("Expected 'apple' to be found")
	}
	if !trie.Search("applet") {
		t.Errorf("Expected 'applet' to be found")
	}

	// Check if non-existent words are not found
	if trie.Search("orange") {
		t.Errorf("Expected 'orange' to not be found")
	}
	if trie.Search("appl") {
		t.Errorf("Expected 'appl' to not be found")
	}
	if trie.Search("b") {
		t.Errorf("Expected 'b' to not be found")
	}
}

func TestTrie_Insert_WithMultipleWords(t *testing.T) {
	trie := NewTrie()

	// Insert multiple words
	trie.Insert("apple")
	trie.Insert("app")
	trie.Insert("banana")
	trie.Insert("bat")
	trie.Insert("batmobile")
	trie.Insert("bike")

	// Check if the words are found
	if !trie.Search("apple") {
		t.Errorf("Expected 'apple' to be found")
	}
	if !trie.Search("app") {
		t.Errorf("Expected 'app' to be found")
	}
	if !trie.Search("banana") {
		t.Errorf("Expected 'banana' to be found")
	}
	if !trie.Search("bat") {
		t.Errorf("Expected 'bat' to be found")
	}
	if !trie.Search("batmobile") {
		t.Errorf("Expected 'batmobile' to be found")
	}
	if !trie.Search("bike") {
		t.Errorf("Expected 'bike' to be found")
	}

	// Check if non-existent words are not found
	if trie.Search("orange") {
		t.Errorf("Expected 'orange' to not be found")
	}
	if trie.Search("appl") {
		t.Errorf("Expected 'appl' to not be found")
	}
	if trie.Search("b") {
		t.Errorf("Expected 'b' to not be found")
	}
	if trie.Search("batp") {
		t.Errorf("Expected 'batp' to not be found")
	}
	if trie.Search("bi") {
		t.Errorf("Expected 'bi' to not be found")
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除

trie

算法

字符串

本文分享自运维开发王义杰微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

trie

算法

字符串

登录后参与评论

0 条评论

热度