"ByteTrie" （数据结构）

"ByteTrie"

表示成员是字节序列的字典树 (trie).

更多信息

  • 字节字典树可用于有效插入和成员测试：
  • CreateDataStructure["ByteTrie", start, end]为从 start 到 end 的字节序列创建一个新的空 "ByteTrie"
    Typed[x,"ByteTrie"]赋予 x 类型 "ByteTrie"
  • 对于 "ByteTrie" 类型的数据结构，可以使用以下操作：
  • ds["ByteLists"]返回存储在 ds 中的字节序列，表示为字节列表的列表时间：O(n)
    ds["ByteLists",s]返回存储在 ds 中的以序列 s 开头的字节序列时间：O(n)
    ds["ByteRange"]ds 可以容纳的字节范围时间：O(1)
    ds["Copy"]返回 ds 的副本时间：O(n)
    ds["EmptyQ"]若 ds 无元素，则为 True时间：O(1)
    ds["FreeQ",s]若字节序列 s 未储存在 ds 中，则为 True时间：O(log n)
    ds["Insert",s]将字节序列 s 插入 ds时间：O(log n)
    ds["Length"]储存在 ds 中字节序列的数量时间：O(1)
    ds["MemberQ",s]若字节序列 s 储存在 ds 中，则为 True时间：O(log n)
    ds["NumericArrays"]返回表示为数值数组的储存在 ds 中的字节序列时间：O(n)
    ds["NumericArrays",s]返回存储在 ds 中的以序列 s 开头的字节序列时间：O(n)
    ds["Strings"]返回表示为字符串列表的存储在 ds 中的字节序列时间：O(n)
    ds["Strings",s]返回存储在 ds 中的以序列 s 开头的字节序列时间：O(n)
  • 还支持以下函数：
  • dsi===dsj 若 dsi 等于 dsj，则为 True
    FullForm[ds]ds 的完整形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换为正规表达式
  • 存储在 "ByteTrie" 数据结构中的字节序列可以表示为字节列表、字符串或数值数组.
  • 字典树使用前缀来存储其元素，因而避免了其他数据结构——如使用哈希计算的数据结构——可能会遭遇的冲突问题.

范例

打开所有单元关闭所有单元

基本范例  (6)

可以使用 CreateDataStructure 创建一个新的 "ByteTrie"：

插入字典树：

检验字节序列是否被储存：

若序列未被储存，则返回 False：

可以返回表示为字符串的字节列表：

可以给出字节范围的数值：

可以插入一个字节列表：

检验字节序列是否被储存：

若序列未被储存，则返回 False：

可以返回表示为字符串的字节列表：

具有多个条目的字节字典树：

返回所有条目：

返回具有特定前缀的所有条目：

选择条目的前缀可以包含多个字节：

具有多个条目的字节字典树：

返回所有条目：

返回所有有特定前缀的条目：

选择条目的前缀可以包含多个字节：

有一些插入的字节字典树：

可以生成数据结构的可视化：

红色元素显示实际条目的结尾.

插入超出范围的字节会显示错误：

范围  (1)

信息  (1)

可使用 CreateDataStructure 创建新 "ByteTrie"：

关于数据结构 ds 的信息：

应用  (2)

命令完成  (1)

字节树的一种用途是用于命令完成. 可适用于 RandomWord 函数.

创建一个包含 1000 个单词的列表，删除连字符并将所有内容变为小写：

创建一个字节字典树并插入单词：

现在有效地找到所有以特定前缀开头的单词：

这些都可以用于命令完成系统.

储存整数  (1)

通过将整数分解为字节序列，可以将其存储在字节字典树中.

有一种方法是使用位操作，但 IntegerDigits 也很有效：

将数字插入字节字典树的实用函数：

检验是否为成员的函数：

创建比特字典树并进行插入：

检验是否为成员：

这些都可以用于命令完成系统.

巧妙范例  (1)

可视化  (1)

随机长度的随机字节序列的集合：

创建一个字节字典树并插入字节序列：

可视化图显示了数据的布局方式：