WOLFRAM

Wolfram 语言与系统参考资料中心

"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"：

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]

插入字典树：

Wolfram Language code: ds["Insert", "abc"]

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

Wolfram Language code: ds["MemberQ", "abc"]

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

Wolfram Language code: ds["MemberQ", "abb"]

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

Wolfram Language code: ds["Strings"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]

可以插入一个字节列表：

Wolfram Language code: ds["Insert", {97, 98, 99}]

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

Wolfram Language code: ds["MemberQ", {97, 98, 98}]

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

Wolfram Language code: ds["MemberQ", {97, 98, 98}]

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

Wolfram Language code: ds["ByteLists"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "abc"]; ds["Insert", "acb"]; ds["Insert", "bbc"];

返回所有条目：

Wolfram Language code: ds["Strings"]

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

Wolfram Language code: ds["Strings", "a"]

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

Wolfram Language code: ds["Strings", "ab"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]; ds["Insert", {97, 98, 99}]; ds["Insert", {97, 99, 98}]; ds["Insert", {98, 98, 99}];

返回所有条目：

Wolfram Language code: ds["ByteLists"]

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

Wolfram Language code: ds["ByteLists", {97}]

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

Wolfram Language code: ds["ByteLists", {97, 98}]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "ab"]; ds["Insert", "abb"]; ds["Insert", "acb"]; ds["Insert", "bbc"];

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

Wolfram Language code: ds["Visualization"]

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

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "d"]

范围  (1)

信息  (1)

可使用 CreateDataStructure 创建新 "ByteTrie"：

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]

关于数据结构 ds 的信息：

Wolfram Language code: Information[ds]

应用  (2)

命令完成  (1)

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

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

Wolfram Language code: words = ToLowerCase[ StringReplace[ RandomWord[{"CommonWords", "Noun"}, 1000], "-" -> ""]];

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "z"]; Scan[(ds["Insert", #])&, words]

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

Wolfram Language code: ds["Strings", "br"]

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

储存整数  (1)

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

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

Wolfram Language code: trie = CreateDataStructure["ByteTrie", 0, 7]; trie["Insert", IntegerDigits[ 1024, 8]]; trie["ByteLists"]

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

Wolfram Language code: insert[ trie_, num_] := trie["Insert", IntegerDigits[num, 8]]

检验是否为成员的函数：

Wolfram Language code: test[trie_, num_] := trie["MemberQ", Developer`FromPackedArray[IntegerDigits[num, 8]]]

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

Wolfram Language code: trie = CreateDataStructure["ByteTrie", 0, 7]; insert[ trie, 123456];

检验是否为成员：

Wolfram Language code: test[trie, 123456]

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

巧妙范例  (1)

可视化  (1)

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

Wolfram Language code: data = Table[ RandomChoice[{97, 98, 99}, RandomInteger[{1, 10}]], {20}]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]; Scan[ds["Insert", #]&, data]

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

Wolfram Language code: ds["Visualization"]