Golang: 基於 TrieTree 的中文詞替換
這是一篇重寫的 Blog，主要解決上一版缺失實用性和存在一些錯誤的問題
Trie，又稱前綴樹或字典樹，是一種用於快速查找和插入字串的數據結構。本次實現目的是為了字串替換，所以我們必須對比 HashMap 同 TrieTree 的優勢和劣勢。
| 🔥 優勢 | TrieTree | HashMap |
|---|---|---|
| Prefix Matching | ✅ 支援前綴查詢 | ❌ 需要遍歷全部可能前綴 |
| Memory Efficiency | ✅ 共享前綴節省空間 | ❌ 獨立存儲每一個鍵 |
| Dynamic Expansion | ✅ 增量插入效率高 | ❌ 擴容時性能抖動 |
| Longest Match | ✅ 透過 DFS 自然實現 | ❌ 需要維護長度排序後多次檢索 |
| Fuzzy Matching | ✅ 支援通配符擴展 | ❌ 無法原生支援 |
| 🔥 劣勢 | TrieTree | TrieTree |
|---|---|---|
| Exactly match speed | ❌ O(k) 時間複雜度 (k為鍵長) | ✅ O(1)平均时间复杂度 |
| Implementation complexity | ❌ 需要維護樹結構 | ✅ 語言原生支援 |
| Memory Locality | ❌ 節點分散 | ✅ 桶儲存提升快取命中率 |
| Concurrency Safety | ❌ 需要自定義鎖 | ✅ sync.Map 原生支援 |
其實這 2 種數據結構在特定場景都有他們的優勢，所以在文本末尾的工程化建議中，我會給出如何組合他們的實踐方式。但是今天的主題是 TrieTree，還是介紹一下先。
Trie 數據結構
Trie 是一種多路樹數據結構，每個字串都是由根節點到某個節點的路徑表示的，所以我們需要一個結構來表示節點，把它定義為 TrieNode。每個 TrieNode 都有一個子節點映射，將字符映射到 TrieNode，這樣我們就可以通過字符來查找子節點。每個節點還需要一個標記來表示該節點是否為一個完整的字串的結束，以及一個字段來存儲該節點的值。
type TrieNode struct {
children map[rune]*TrieNode // 用 rene 類型作為 Key
isEnd bool
value string // 替換值
}
children 是一個映射，將 rune 映射到 TrieNode 指針，實現多子節點。end 是一個 Boolean 類型，表示是否是一個完整字串的結束。value 是一個 String 類型，表示該節點的值。
rune是 int32 的別名，[]rune可以用於表示 Unicode 字符串，每個rune類型對應一個 Unicode 字符，這允許我們按字符（而不是字節）操作字符串，這對處理包含非 ASCII 字符非常重要，因為這些字符通常由多個字節表示，直接切片會產生亂碼。
我現在這裏建立一個新的樹，下文會用到它
func NewTrieNode() *TrieNode {
return &TrieNode{
children: make(map[rune]*TrieNode),
}
}
插入
首先將當前節點設置為根節點，遍歷輸入的字串的每個字符，如果被遍歷到的字符不存在於當前節點的子節點中，則創建一個新的 TrieNode 並將其添加到子節點映射中。然後我們將當前節點設定為子節點，並繼續處理下一個字符。直到處理完所有字符後將 isEnd 設定為 true，表示這個節點為一個完整的字串的結束，並將 value 設置為傳入的 value，這在下面的 Search 中被用於輸出被替換的目標值。
func (t *TrieNode) Insert(word, replacement string) {
node := t
for _, ch := range word {
if node.children[ch] == nil {
node.children[ch] = NewTrieNode()
}
node = node.children[ch]
}
node.isEnd = true
node.value = replacement
}
匹配邏輯
同樣將當前節點設置為根節點，遍歷輸入的字串的每個字符，如果被遍歷到的字符存在於當前節點的子節點中，則將當前節點設置為該子節點，如果節點結束則更新最長匹配記錄。如果被遍歷到的字符不存在於當前節點的子節點中，彈出並返回上次找到的最長節點。
貪婪最長匹配，在 Trie 樹中查找輸入文本能匹配的最長字串，並返回匹配的字串長度和替換值。時間複雜度 O(k)，空間複雜度 O(1)
func (t *TrieNode) LongestMatch(text []rune) (int, string) {
var (
maxLen int
repl string
current = t
)
for i, ch := range text {
if current.children[ch] == nil {
break
}
current = current.children[ch]
if current.isEnd {
maxLen = i + 1
repl = current.value
}
}
return maxLen, repl
}
查找和替換
func ConvertWords(input string, root *TrieNode) string {
var (
output strings.Builder
runes = []rune(input)
i = 0
)
for i < len(runes) {
length, repl := root.LongestMatch(runes[i:])
if length > 0 {
output.WriteString(repl)
i += length
} else {
output.WriteRune(runes[i])
i++
}
}
return output.String()
}
時間複雜度分析
最壞情況: 傳入文本沒有任何匹配
每次只匹配一個字符就失敗:
總時間 = n * O(1) = O(n)最壞情況: 傳入文本由最長詞組成
每次需要掃描整個長度 L:
總時間 = (n/L) * O(L) = O(n)
無論匹配成功與否，每個字符僅倍處理常數次 => 嚴格 O(n)
實踐
func main() {
root := NewTrieNode()
root.Insert("蘋果", "水果")
root.Insert("蘋果派", "甜點") // 最長匹配
root.Insert("香蕉", "水果")
root.Insert("蘿蔔", "蔬菜")
input := "我喜歡蘋果派和香蕉，但是不喜歡蘿蔔"
output := ConvertWords(input, root)
fmt.Println(output)
// 输出: 我喜歡甜點和水果，但是不喜歡蔬菜。
}
匹配過程描述
傳入文本: "蘋果派"
1. 匹配 "蘋" -> 繼續
2. 匹配 "果" -> 記錄長度 2 (水果)
3. 匹配 "派" -> 記錄長度 3 (甜點)
選擇更長的匹配結果
前綴匹配下 HashMap 的性能對比
| 預處理 | 查詢 | 空間 | |
|---|---|---|---|
| TrieTree | O(m) | O(n) | 中 |
| HashMap | O(1) | O(n*L) | 高 |
工程化建議
TrieTree 的優勢在於前綴匹配，對於完全匹配的場景性能明顯低於 HashMap，所以在實際場景中可以根據字典表做混合數據結構方案
type HybridMatcher struct {
exactMatch map[string]string // 高頻詞
trieRoot *TrieNode // 處理未知詞
maxWordLen int // 最大詞長
}
func (h *HybridMatcher) Match(text string) string {
// 優先檢查精確匹配
if v, ok := h.exactMatch[text]; ok {
return v
}
// 降级到Trie树匹配
}
長度剪枝優化
將 LongestMatch 的單次操作從 O(k) 降至 O(1)，但是整體仍為 O(n)
const maxWordLen = 10 // 根據實際字典
for i < len(runes) {
end := min(i+maxWordLen, len(runes))
length, repl := root.LongestMatch(runes[i:end]) // 限制窗口
// ...
}
場景決策樹
前綴匹配？
├─ 是 → TrieTree / AC自動機
└─ 否 → 考慮以下要素：
├─ 辭典規模 < 10k → HashMap
├─ 記憶體敏感 → 雙數組 Trie
└─ 需要模糊匹配 → 後綴樹
衍生閱讀
還未寫，以後可能會有