Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Critbit Trie

Binary Trie

Binary Trie 将字符串展开为二进制位：0 走左分支，1 走右分支。一条从根节点到叶子节点的路径因此可以表示一个字符串。以 "a"、"b"、"c"、"d" 为例：

字符二进制表示:
'a' = 01100001 (97)
'b' = 01100010 (98)  
'c' = 01100011 (99)
'd' = 01100100 (100)

按照每层固定检查一个 bit（从 bit7 到 bit0）的规则，构建的完整二进制树如下：

                            root
                           /
                      bit7=0
                         |
                       node1
                         \
                      bit6=1
                         |
                       node2
                         \
                      bit5=1
                         |
                       node3
                        /
                   bit4=0
                      |
                    node4
                     /
                bit3=0
                   |
                 node5
                 /   \
            bit2=0   bit2=1
               |       |
             node6    'd'
             /   \
        bit1=0  bit1=1
           |       |
          'a'    node7
                 /   \
            bit0=0  bit0=1
               |       |
              'b'     'c'

这种结构保留了 Trie 的前缀检索能力，但每一位都需要一层节点。上例仅处理一个字节就需要 8 层，其中多数节点只有一个分支，空间利用率很低。

Critbit Trie

Critbit Trie 只保留真正产生分叉的二进制位，从而压缩连续的单分支节点。这里的 critbit（关键位），是两个字符串在公共二进制前缀之后遇到的第一个不同位。

Critbit 的定义

以 "a"、"b"、"c"、"d" 为例：

  • 二进制表示：01100001, 01100010, 01100011, 01100100
  • 相同前缀：01100（前5位相同）
  • 第一个不同位：第2位（从右数第2位）

这个 critbit 可以把四个字符分成两组：

  • bit2=0: {a, b, c}
  • bit2=1: {d}

继续递归分析：

  • {a, b, c} 的 critbit 是第 1 位，分成 {a} 和 {b, c}
  • {b, c} 的 critbit 是第 0 位，分成 {b} 和 {c}

最终得到压缩后的 Critbit Trie：

         (pos=0,bit=2)
         /           \
    bit2=0         bit2=1
       |             |
  (pos=0,bit=1)     'd'
   /         \
bit1=0     bit1=1
  |           |
 'a'    (pos=0,bit=0)
         /         \
    bit0=0       bit0=1
       |           |
      'b'         'c'

树中只剩下三个实际产生分叉的内部节点，不再为公共二进制前缀保存单分支节点。

变长字符串

字典序的理解

对于字符串比较，字典序规则是：

  1. 从左到右逐个字符比较
  2. 字符更小的排在前面
  3. 前缀相等时，短字符串排在前面（如 “a” < “an”）

逻辑补零

为了区分 "a" 和 "aa" 这类前缀关系，Critbit Trie 将字符串结束后的字节在逻辑上视为 \0。实现并不创建补齐后的副本，而是在节点位置超出字符串长度时直接取 0。

例如，对于字符串集合 {"a", "b", "c", "d", "aa", "ab", "abc"}，比较到三个字节时，可以采用下表中的等价表示：

原字符串逻辑表示说明
“a”“a\0\0”用2个\0填充
“b”“b\0\0”用2个\0填充
“c”“c\0\0”用2个\0填充
“d”“d\0\0”用2个\0填充
“aa”“aa\0”用1个\0填充
“ab”“ab\0”用1个\0填充
“abc”“abc”无需填充

二进制表示分析

bit位置标注: 76543210 (从右到左)

字符串pos=0pos=1pos=2
“a\0\0”a(97)=01100001\0(0)=00000000\0(0)=00000000
“b\0\0”b(98)=01100010\0(0)=00000000\0(0)=00000000
“c\0\0”c(99)=01100011\0(0)=00000000\0(0)=00000000
“d\0\0”d(100)=01100100\0(0)=00000000\0(0)=00000000
“aa\0”a(97)=01100001a(97)=01100001\0(0)=00000000
“ab\0”a(97)=01100001b(98)=01100010\0(0)=00000000
“abc”a(97)=01100001b(98)=01100010c(99)=01100011

关键 bit 分析

第 1 个关键 bit：分析整个集合

集合：{a\0\0, b\0\0, c\0\0, d\0\0, aa\0, ab\0, abc}
分析位置：pos=0

各字符串在pos=0的字符：

  • a\0\0, aa\0, ab\0, abc: ‘a’(97) = 01100001
  • b\0\0: ‘b’(98) = 01100010
  • c\0\0: ‘c’(99) = 01100011
  • d\0\0: ‘d’(100) = 01100100

bit位分组分析：

  • bit7~bit3: 全部相同，无分组作用
  • bit2: 0组={a,b,c,aa,ab,abc}, 1组={d} ← 第一个有效分组！

结果：第1个关键bit = (pos=0, bit=2)

第 2 个关键 bit：分析左子树

集合：{a\0\0, b\0\0, c\0\0, aa\0, ab\0, abc} (bit2=0的组)
分析位置：pos=0

bit位分组分析：

  • bit1: 0组={a,aa,ab,abc}, 1组={b,c} ← 第一个有效分组！

结果：第2个关键bit = (pos=0, bit=1)

第 3 个关键 bit：分析 {a, aa, ab, abc} 子集

集合：{a\0\0, aa\0, ab\0, abc} (pos=0,bit1=0的组)
分析位置：pos=1 (因为pos=0都是’a’，无法区分)

各字符串在pos=1的字符：

  • a\0\0: ‘\0’(0) = 00000000
  • aa\0: ‘a’(97) = 01100001
  • ab\0: ‘b’(98) = 01100010
  • abc: ‘b’(98) = 01100010

bit位分组分析：

  • bit6: 0组={a}, 1组={aa,ab,abc} ← 第一个有效分组！

结果：第3个关键bit = (pos=1, bit=6)

继续分析其他子集

按照相同原理，可以得到：

  • 第4个关键bit = (pos=1, bit=1) - 区分{aa\0} vs {ab\0, abc}
  • 第5个关键bit = (pos=2, bit=6) - 区分{ab\0} vs {abc}
  • 第6个关键bit = (pos=0, bit=0) - 区分{b\0\0} vs {c\0\0}

最终树结构

root = Node(pos=0, bit=2)
├─ data[0] = Node(pos=0, bit=1)  ← bit2=0: {a,b,c,aa,ab,abc}
│  ├─ data[0] = Node(pos=1, bit=6)  ← bit1=0: {a,aa,ab,abc}
│  │  ├─ data[0] = Value("a")  ← bit6=0: {a}
│  │  └─ data[1] = Node(pos=1, bit=1)  ← bit6=1: {aa,ab,abc}
│  │     ├─ data[0] = Value("aa")  ← bit1=0: {aa}
│  │     └─ data[1] = Node(pos=2, bit=6)  ← bit1=1: {ab,abc}
│  │        ├─ data[0] = Value("ab")  ← bit6=0: {ab}
│  │        └─ data[1] = Value("abc")  ← bit6=1: {abc}
│  └─ data[1] = Node(pos=0, bit=0)  ← bit1=1: {b,c}
│     ├─ data[0] = Value("b")  ← bit0=0: {b}
│     └─ data[1] = Value("c")  ← bit0=1: {c}
└─ data[1] = Value("d")  ← bit2=1: {d}

以 Node(pos=1, bit=6) 为例，"a" 在 pos=1 处按 \0 处理，因此走 data[0]；"aa"、"ab" 和 "abc" 在该位都是 1，因此走 data[1]。逻辑补零由此把字符串结束位置纳入比较，无须额外保存终止节点。

节点裂变

核心性质

内部节点按照 (pos, bit) 的顺序排列。插入时，新节点会被放到第一个更靠后的检查位置之前，因此同一组字符串形成的判定位次序不依赖插入顺序。

节点裂变机制

插入新字符串的过程可以理解为节点裂变：

  1. 找到候选叶子：按现有节点的关键位走到一个叶子
  2. 计算关键分叉点：比较叶子字符串与新字符串，找到 critbit
  3. 节点裂变：将1个节点裂变成3个节点的子结构

实例：从 {a, b, c, d} 到 {a, b, c, d, e}

原始树结构 {a,b,c,d}：

root = (pos=0, bit=2)
├─ data[0] = (pos=0, bit=1)  ← {a,b,c}
│  ├─ data[0] = 'a'           ← bit1=0
│  └─ data[1] = (pos=0, bit=0) ← bit1=1: {b,c}
│     ├─ data[0] = 'b'        ← bit0=0
│     └─ data[1] = 'c'        ← bit0=1
└─ data[1] = 'd'              ← bit2=1 (目标裂变节点)

字符分析：

  • ‘d’ = 01100100
  • ‘e’ = 01100101
  • critbit(‘d’,‘e’) = bit0 (最低位不同)

裂变过程：

裂变前（1个节点）：

Value('d')

裂变后（3个节点）：

    Node(pos=0,bit=0)
    /              \
 Value('d')     Value('e')

最终树结构 {a,b,c,d,e}：

root = (pos=0, bit=2)
├─ data[0] = (pos=0, bit=1)  ← {a,b,c}
│  ├─ data[0] = 'a'           ← bit1=0
│  └─ data[1] = (pos=0, bit=0) ← bit1=1: {b,c}
│     ├─ data[0] = 'b'        ← bit0=0
│     └─ data[1] = 'c'        ← bit0=1
└─ data[1] = (pos=0, bit=0)  ← bit2=1: {d,e} (裂变后)
   ├─ data[0] = 'd'           ← bit0=0
   └─ data[1] = 'e'           ← bit0=1

裂变机制的意义

  1. 局部更新：插入只新增一个内部节点和一个叶子
  2. 有序判定：沿路径检查的 (pos, bit) 单调向后
  3. 前缀兼容：逻辑补零可以区分字符串及其更长后缀
  4. 无需重建：新字符串加入后，不必重新生成整棵树

总结：Critbit Trie 与 Double-Array Trie 面向不同场景。前者通过关键差异位组织变长字符串，插入和查询都不需要预先构建完整字符转移表；后者更适合静态词典和高吞吐前缀检索。理解两者的差异，有助于根据数据更新方式与查询模式选择结构。

配套实现：Ismantic/Trie