压缩集合字典树的算法

Question

我有一系列集合，想要放入一个trie中。

普通的trie由元素的字符串组成 - 也就是说，元素的顺序很重要。但是集合没有定义的顺序，因此可能会有更好的压缩效果。

例如，给定字符串"abc"，"bc"和"c"，我将创建trie：

(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
      -> ('b',1) -> ('c',1)
      -> ('c',1)

但是，考虑到集合 { 'a', 'b', 'c' }，{ 'b', 'c' }，{ 'c' }，我可以创建上述字典树或其中的任何一个字典树中的十一个：

(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
      -> ('c',2) -> ('a',1)

(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
      -> ('b',1) -> ('c',1)
      -> ('c',1)

(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
      -> ('c',2) -> ('a',1)

(*,3) -> ('b',2) -> ('a',1) -> ('c',1)
                 -> ('c',1)
      -> ('c',1)

(*,3) -> ('b',1) -> ('a',1) -> ('c',1)
      -> ('c',2) -> ('b',1)

(*,3) -> ('b',2) -> ('c',2) -> ('a',1)
      -> ('c',1)

(*,3) -> ('b',1) -> ('c',1) -> ('a',1)
      -> ('c',2) -> ('b',1)

(*,3) -> ('c',2) -> ('a',1) -> ('b',1)
      -> ('b',1) -> ('c',1)

(*,3) -> ('c',2) -> ('a',1) -> ('b',1)
                 -> ('b',1)

(*,3) -> ('c',2) -> ('b',1) -> ('a',1)
      -> ('b',1) -> ('c',1)

(*,3) -> ('c',3) -> ('b',2) -> ('a',1)

显然可以进行压缩（从7个节点到4个节点）。

我猜测，在每个节点上定义一个本地顺序，该顺序取决于其子节点的相对频率，但我不确定，而且可能过于昂贵。

因此，在我开始自己的压缩算法之前，是否存在现有的算法？它的开销有多大？它是批量处理还是可以针对每个插入/删除操作进行？

- rampion

---

我认为trie不是表示集合的很好的数据结构。一组位数组会更好吗？你希望执行哪些操作？为什么这么担心内存？ - svick

@svick：也许是这样，但我的集合涵盖了大量的元素，所以位数组可能不是很高效。可以通过（子集，频率）对进行迭代。因为我有很多数据。 - rampion

你打算进行哪些操作？传统的 Trie 可以有效地告诉你一个给定的字符串是否包含在它所表示的字符串集合中。如果你的 Trie 重新排列其字符串以最小化结构大小，那么你如何实际测试一个给定的字符集是否包含在 Trie 中呢？似乎你需要搜索每个排列。 - Weeble

@Weeble：你可以在每个节点上存储本地顺序以及每个节点的子节点。当查找节点时，迭代其子节点，并遍历到与包含元素匹配的第一个子节点。 - rampion

你是只想进行压缩以便后续解压缩，还是也想在压缩结构上执行集合操作？ - AShelly

Answer 1

我认为你应该根据项目频率对集合进行排序，这样可以得到一个很好的启发式，就像你所怀疑的那样。同样的方法在FP-growth（频繁模式挖掘）中使用，以紧凑的方式表示项目集。

- Alexander Kuznetsov

---

完整循环！我实际上正在研究这个，因为我认为FP-growth中使用的全局顺序是不足够的。 - rampion

可能你可以重新构建子树，根据该子树中项的频率，这将为您提供更好的压缩效果，但在这种情况下，我们需要执行更多的计算。 - Alexander Kuznetsov

Answer 2

我猜测最大压缩会将最常见的元素放在顶部（就像你上一个例子中那样）。

压缩算法将从整个集合和顶部节点开始，递归地为包含最常见元素的每个子集创建节点。

Compress(collection, node):
    while NOT collection.isEmpty? 
      e = collection.find_most_common_element
      c2 = collection.find_all_containing(e)
      collection = collection - c2
      if e==NIL //empty sets only
         node[END_OF_SET]=node
      else
        c2.each{set.remove(e)}
        node[e]=new Node
        Compress(c2,node[e])
      end
    end

生成的树将具有特殊的集合结束标记，以表示完整的集合在该节点结束。对于您的示例，它将是

 *->(C,3)->(B,2)->(A,1)->EOS
                ->EOS
          ->EOS

删除一个集合很容易，只需删除其 EOS 标记（以及任何变为空的父节点）。您可以实时插入 - 在每个节点上，向下遍历具有最多子元素的匹配元素，直到没有匹配项，然后使用上面的算法 - 但保持最大压缩会很棘手。当元素 B 比元素 A 获得更多子元素时，您必须将包含 A 和 B 的所有集合移动到 B 节点中，这将涉及对 A 的所有子元素进行全面搜索。但是，如果不保持压缩，则包含搜索与集合大小不再呈线性关系。

- AShelly

Answer 3

基本上，你应该构建一个依赖图。如果元素y仅在x出现时出现，请从x到y绘制一条边（如果相等，则按字典顺序排序）。得到的图是一个有向无环图（DAG）。现在，对这个图进行拓扑排序以获取带有扭曲的元素顺序。每当你可以选择两个（或更多）元素中的一个时，请选择具有更高出现次数的那个。

- ElKamina