Tire Tree

Tire Tree称为查找树或字典树，插入和查询的复杂度为O(K)（K为被插入或查询的关键字长度）。

原理

Tire Tree的基本性质如下，

  • 根节点不包含任何字符
  • 除根节点外每一个节点都仅包含一个字符
  • 树的每一条路径的所有节点连接起来代表一个被添加的字符串

Tire Tree的核心思想是空间换时间，并利用字符串的公共前缀来降低查询时间的开销以及节约存储空间。

如图所示，“故事”和“故乡”拥有共同的前缀“故”，所以“故”只需要存储一次，达到了节约存储空间的目的。

应用

统计词频

对于哈希和堆来说，Tire Tree的公共前缀可以有效降低内存空间，当需要统计的数据越多时，这个压缩的效果越明显。

前缀匹配

由于Tire Tree是按照前缀匹配来存储字符串的，那么查询字符串的复杂度只是O(K)，K为字符串的长度，因此，可以用来加载分词的词库。

实现

这里使用go来实现简单的tire树，完整代码：https://github.com/yxd123/simWS/blob/master/tire/tire.go。

节点的定义

树的节点需要包含节点值、子节点指针、节点状态。

  • 节点值：当前节点存储的值
  • 子节点指针：当前节点的子节点的指针（记录了当前节点的所有子节点）
  • 节点状态：记录当前节点是否为代表字符串的结尾（用于判断以当前节点为结尾的字符串是否被添加过）
1
2
3
4
5
6
type Node struct {
    value     byte //当前节点存储的值
    nextNodes []*Node // 子节点指针
    nextNums  int  //子节点个数
    flag      bool //是否为结尾字符
}

节点的添加

节点的添加需要考虑几种情况：

  • 是否为公共前缀
  • 是否为结尾字符

values代表需要添加的字符串，place代表当前需要处理的字符位置，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func (t *Node) add(values []byte, place int) {
    // 达到字符串的末尾
    if place >= len(values) {
        t.flag = true
        return
    }

   //如果没有子节点，需要添加新节点
    if t.nextNodes == nil {
        log.Println("new nextNodes")
        t.nextNodes = make([]*Node, 0, 26)
        t.nextNums = 0
    }

    if t.nextNums > 0 {
        for _, node := range t.nextNodes {
            // 如果子节点中包含待添加字符，则递归添加下一节点
            if node.value == values[place] {
                log.Println("duplicate byte:", string(node.value))
                node.add(values, place + 1)
                return
            }
        }
    }

    // 子节点无待添加字符，则添加新的子节点
    node := NewNode(values[place])
    node.add(values, place + 1)
    t.nextNodes = append(t.nextNodes, node)
    t.nextNums += 1
    log.Println("add new Node:", string(node.value), t.nextNums)
}

节点的查找

节点的查找和添加类似，都是从树的根节点开始，递归到目的节点。

节点的查找需要注意结尾标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (t *Node) find(values []byte, place int) bool {
    //如果没有子节点，则未查到
    if t == nil || t.nextNums == 0 {
        log.Println("can't cmp", string(values[place]), "nextNums:", string(t.value), t.nextNums)
        return false
    }

    for _, node := range t.nextNodes {
        log.Println("cmp:", string(node.value), string(values[place]))
        // 找到待查找字符
        if node.value == values[place] {
            //当前待查找字符为结尾，则找到目标字符串
            if place == len(values) - 1 {
                return node.flag
            }
            // 非结尾字符串，递归查找下一字符
            return node.find(values, place + 1)
        }
    }

    return false
}