trie map 字典树(前缀树)

• Trie
  

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

• 从Trie树（字典树）谈到后缀树（10.28修订）
  

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3. 每个节点的所有子节点包含的字符都不相同。

Trie又被称为前缀树、字典树，所以当然是一棵树。上面这棵Trie树包含的字符串集合是{in, inn, int, tea, ten, to}。每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串，字符集就是’a’-‘z’；对于都是数字的字符串，字符集就是’0’-‘9’；对于二进制字符串，字符集就是0和1。

比如上图中3号节点对应的路径0123上的字符串是inn，8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的。

原理

下面我们来讲一下对于给定的字符串集合{W1, W2, W3, … WN}如何创建对应的Trie树。其实上Trie树的创建是从只有根节点开始，通过依次将W1, W2, W3, … WN插入Trie中实现的。所以关键就是之前提到的Trie的插入操作。

具体来说，Trie一般支持两个操作：

1. Trie.insert(W)：第一个操作是插入操作，就是将一个字符串W加入到集合中。

2. Trie.search(S)：第二个操作是查询操作，就是查询一个字符串S是不是在集合中。

假设我们要插入字符串”in”。我们一开始位于根，也就是0号节点，我们用P=0表示。我们先看P是不是有一条标识着i的连向子节点的边。没有这条边，于是我们就新建一个节点，也就是1号节点，然后把1号节点设置为P也就是0号节点的子节点，并且将边标识为i。最后我们移动到1号节点，也就是令P=1。

这样我们就把”in”的i字符插入到Trie中了。然后我们再插入字符n，也是先找P也就是1号节点有没有标记为n的边。还是没有，于是再新建一个节点2，设置为P也就是1号节点的子节点，并且把边标识为n。最后再移动到P=2。这样我们就把n也插入了。由于n是”in”的最后一个字符，所以我们还需要将P=2这个节点标记为终结点。

现在我们再插入字符串”inn”。过程也是一样的，从P=0开始找标识为i的边，这次找到1号节点。于是我们就不用创建新节点了，直接移动到1号节点，也就是令P=1。再插入字符n，也是有2号节点存在，所以移动到2号节点，P=2。最后再插入字符n这时P没有标识为n的边了，所以新建3号节点作为2号节点的子节点，边标识为n，同时将3号节点标记为终结点：

下面我们再讲一下如何查询Trie树中是不是包含字符串S，也就是之前提到的查找操作。查找其实比较简单。我们只要从根节点开始，沿着标识着S[1] -> S[2] -> S[3] … -> S[S.len]的边移动，如果最后成功到达一个终结点，就说明S在Trie树中；如果最后无路可走，或者到达一个不是终结点的节点，就说明S不在Trie树中。

下面是怪大叔版本的golang 代码实现

const (
   Find    = 1
   NotFind = 0
)

var FundTrie *TrieNode

// Trie
type TrieNode struct {
   key      string
   data     *TrieData            // 数据
   dataList map[string]*TrieNode // 子节点数据
}

type TrieData struct {
   Content string `json:"content"` // 内容 (传入json字符串 进行解析)
}

// 返回本节点的 数据
func (node *TrieNode) Get() *TrieData {
   return node.data
}

func (node *TrieNode) GetKey() string {
   return node.key
}

func (node *TrieNode) InitDataList() {
   node.dataList = make(map[string]*TrieNode)
}

// 返回所有满足 到此节点为止的所有 子节点 共同组成的单词(数据)
// 此方法会默认遍历所有 数据集, 效率 会 很低(类似mysql的 模糊查询)
func (node *TrieNode) GetFullList(getData []string, isFind int) (list []*TrieData) {
   var (
      data *TrieNode
      str  []string
   )

   // 如果是最后一个,根据前置是否 已经发现对应元素进行 数据返回
   if len(node.dataList) == 0 {
      if isFind == Find {
         list = append(list, node.Get())
      }

      if len(getData) > 0 && node.GetKey() == getData[len(getData)-1] {
         list = append(list, node.Get())
      }
      return
   }

   if isFind == Find && node.data != nil {
      list = append(list, node.Get())
   }

   if len(getData) > 0 {
      data = node.dataList[getData[0]]
   }

   if data != nil && isFind == NotFind && len(getData) == 1 {
      isFind = Find
   }

   if isFind == NotFind && data != nil {
      str = getData[1:]
   } else if isFind == NotFind && data == nil {
      str = getData
   } else if isFind == Find && len(getData) > 0 {
      str = getData[1:]
   }

   // 未发现, 也就是 isFind 为0的时候
   for _, v := range node.dataList {
      if len(getData) == 1 && v.GetKey() != getData[0] && isFind == Find {
         for _, v2 := range v.GetFullList(getData, NotFind) {
            list = append(list, v2)
         }
         continue
      }

      for _, v2 := range v.GetFullList(str, isFind) {
         list = append(list, v2)
      }
   }

   return
}

func (node *TrieNode) GetList(getData []string, isFind int) (list []*TrieData) {
   var (
      data *TrieNode
      str  []string
   )

   // 如果是最后一个,根据前置是否 已经发现对应元素进行 数据返回
   if len(node.dataList) == 0 {
      if isFind == Find {
         list = append(list, node.Get())
      }

      if len(getData) > 0 && node.GetKey() == getData[len(getData)-1] {
         list = append(list, node.Get())
      }
      return
   }

   if isFind == Find && node.data != nil {
      list = append(list, node.Get())
   }

   if len(getData) > 0 {
      data = node.dataList[getData[0]]
   }

   if data != nil && isFind == NotFind && len(getData) == 1 {
      isFind = Find
   }

   if len(getData) > 0 {
      str = getData[1:]
   }

   // 未发现, 也就是 isFind 为0的时候
   for _, v := range node.dataList {
      if len(getData) >= 1 && v.GetKey() != getData[0] {
         continue
      }

      for _, v2 := range v.GetList(str, isFind) {
         list = append(list, v2)
      }
   }

   return
}

// 插入数据
func (node *TrieNode) Insert(key []string, insertData *TrieData, setupNum int) (err error) {
   var (
      data     *TrieNode
      trieData *TrieData
   )

   if len(key) == 0 {
      if setupNum == 1 {
         err = errors.New("请传入非空数据")
         return
      }
      return
   }

   data = node.dataList[key[0]]

   if data != nil {
      // 数据已存在, 进行递归插入
      if len(key) == 1 {
         // 插入数据
         if data.Get() == nil {
            data.data = insertData
         }
      }

      err = data.Insert(key[1:], insertData, setupNum+1)

   } else {
      if len(key) == 1 {
         trieData = insertData
      } else {
         trieData = nil
      }
      // 插入数据
      node.dataList[key[0]] = &TrieNode{
         key:      key[0],
         data:     trieData,
         dataList: make(map[string]*TrieNode),
      }

      err = node.dataList[key[0]].Insert(key[1:], insertData, setupNum+1)
   }

   return
}

测试代码:

func TestTrie(t *testing.T) {
   trie := &libs.TrieNode{}
   trie.InitDataList()
   // fmt.Println(strings.Split("content", ""))
   trie.Insert(strings.Split("content", ""), &libs.TrieData{Content: "content"}, 1)
   trie.Insert(strings.Split("context", ""), &libs.TrieData{Content: "context"}, 1)
   trie.Insert(strings.Split("contention", ""), &libs.TrieData{Content: "contention"}, 1)
   trie.Insert(strings.Split("fix", ""), &libs.TrieData{Content: "fix"}, 1)
   trie.Insert(strings.Split("jump", ""), &libs.TrieData{Content: "jump"}, 1)

   result := trie.GetList(strings.Split("x", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetList(strings.Split("con", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetList(strings.Split("", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetFullList(strings.Split("x", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetFullList(strings.Split("co", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetFullList(strings.Split("", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }

   result = trie.GetFullList(strings.Split("z", ""), libs.NotFind)
   for _, v := range result {
      fmt.Println(v.Content)
   }
}

结果: 

=== RUN   TestTrie

content

contention

context

context

fix

content

contention

context

--- PASS: TestTrie (0.00s)

PASS

Process finished with exit code 0

总结和使用场景: