压缩集合尝试的算法

Question

我有一组我想放在 trie 中的集合.

普通尝试由元素串组成——也就是说，元素的顺序很重要。集合没有定义的顺序，因此有可能进行更大程度的压缩。

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

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

但是给定集合 { 'a', 'b', 'c' }, { 'b', 'c' }, { ' c' ，我可以创建上面的 trie，或者这十一个中的任何一个:

(*,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 个)。

我怀疑根据其子节点的相对频率在每个节点定义本地顺序是否可行，但我不确定，而且它可能过于昂贵。

因此，在我打开白板并开始研究我自己的压缩算法之前，是否有现成的算法？有多贵？它是一个批量过程，还是可以在每次插入/删除时完成？

Answer 1

我认为您应该根据项目频率对集合进行排序，正如您所怀疑的那样，这会得到很好的启发式方法。在 FP-growth 中使用相同的方法(频繁模式挖掘)以紧凑的方式表示项目集。