遊戲算法系列 - 字典樹

簡介

• trie是一種搜尋樹，也稱為字典樹。最大的特點是共享字元串的公共字首來達到提高效率的目的。
• trie的核心思想是空間換時間，缺點是記憶體占用高
• 最大限度地減少無謂的字元串比較，查詢效率比哈希表高

性質

• 根節點不包含字元，除根節點外每一個節點都隻包含一個字元。
• 從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。
• 每個節點的所有子節點包含的字元都不相同。

建構

可以使用連結清單來實作，每個字元串都是一個連結清單。

應用

• 詞頻統計
• 字元串檢索
• 字元串搜尋的字首比對
• ...

遊戲屏蔽字替換

問題：假設上圖就是遊戲屏蔽字，有字元串“你來自美利堅帝國嗎？”。需要将敏感詞轉換為*。

用3個指針來進行操作，分别是p1,p2,p3。p1指向屏蔽字樹，p2和p3指向需要檢測的字元串

1. 把p1指向root節點，p2和p3指向字元串開頭的“你”字
2. “你”字（p2）不是p1的子節點（目前p1在root節點），把p2和p3移動到下個字元“來”字，p1還是指向root節點
3. “來”字（p2）不是p1的子節點（目前p1在root節點），把p2和p3移動到下個字元“自”字，p1還是指向root節點
4. “自”字（p2）不是p1的子節點（目前p1在root節點），把p2和p3移動到下個字元“美”字，p1還是指向root節點
5. “美”字（p2）是p1的子節點（目前p1在root節點），把p1指向“美”節點，把p2移動到下個字元“利”，p3還是指向字元“美”
6. “利”字（p2）是p1的子節點（目前p1指向"美"節點），把p1指向“利”節點，把p2移動到下個字元“堅”，p3還是指向字元“美”
7. “堅”字（p2）是p1的子節點（目前p1指向"利"節點），把p1指向“堅”節點，“堅”節點是最後一個節點，查找結束，是以存在敏感詞“美利堅”，p3到p2之間的區間就是敏感詞，把p3到p2之間的字元都替換成*，最後把p2和p3都移動到字元"帝"，p1移動到root節點
8. “帝”字（p2）是p1的子節點（目前p1在root節點），把p1指向“帝”節點，把p2移動到下個字元“國”，p3還是指向字元“帝”
9. “國”字（p2）不是p1的子節點（目前p1指向"帝"節點），表示以“帝”字開頭沒有找到敏感詞，把p2和p3都移動到字元“國”字，p1指向root節點
10. “國”字（p2）不是p1的子節點（目前p1指向root節點），把p2和p3都移動到下個字元“嗎”字，p1指向root節點
11. “嗎”字（p2）不是p1的子節點（目前p1在root節點），把p2和p3移動到下個字元“？”字，p1還是指向root節點
12. “？”字（p2）不是p1的子節點（目前p1在root節點），由于"？"已經是最後一個字元了，全部替換結束。

僞代碼

func SensitiveTransform(word string) string {

   t := []rune(strings.ToLower(word)) // 轉換為unicode數組
   p1 := tree.GetRoot()               // p1指向樹的根節點
   p2 := t[0]                         // p2是過濾内容的第一個字元
   var p2Index, p3Index int           // p2的位置,p3的位置,預設是過濾内容的第一個字元的位置
   newWord := word                    // 過濾後的字元串

   // p3指向最後一個字元，則結束
   for ; p3Index < len(t); {

      // 周遊從p3開始到結尾的字元串
      for i := p3Index; i < len(t); i++ {
         char := t[i]

         if !p1.Contains(p2) {

            // 如果p2不是p1子節點，說明以p3開始的内容不需要屏蔽，p3指向下一個位置，p2指向p3，并将p1重置到root節點，終止循環
            p2Index = p3Index + 1
            p3Index = p3Index + 1

            if p2Index < len(t) {
               p2 = t[p2Index]
            }
            p1 = tree.GetRoot()

            break
         } else {

            // 如果p2是p1的子節點，p1節點移動到p2内容對應的節點上，p2移動到下個位置

            // 擷取p1的子節點
            p1 = p1.GetChildNode(char)

            // 移動P2到下個位置
            p2Index = p2Index + 1
            if p2Index < len(t) {
               p2 = t[p2Index]
            }

            if !p1.HasChild() {

               // p1沒有子節點，樹的某條路徑周遊完了，說明字元串中含有敏感詞
               p1 = tree.GetRoot()

               // 将敏感詞替換成*
               temp := []rune(newWord)
               newWord = string(temp[:p3Index]) + strings.Repeat("*", p2Index-p3Index) + string(temp[p2Index:])

               // p3移動到p2的位置
               p3Index = p2Index
            }
         }
      }
   }

   return newWord
}           

時間複雜度

• 比對字元串：假設字元串的長度為n，我們需要周遊n遍，如果敏感詞的長度為m，則最壞的情況下，需要周遊m遍，是以時間複雜度為O(m*n)

• 建構：如果有t個敏感詞，每個敏感詞的長度是m，那建構trie樹的時間複雜度是O(m*t)

網絡上志同道合，我們一起學習網絡安全，一起進步，QQ群：694839022