用于压缩集合尝试的算法

Question

我有一系列套装,我想把它放在一个特里.

正常尝试由元素串组成 - 也就是说,元素的顺序很重要.设置缺少定义的顺序,因此可能会有更大的压缩.

例如,给定字符串"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个节点).

我怀疑在每个节点上定义一个本地订单,取决于它的孩子的相对频率会这样做,但我不确定,它可能过于昂贵.

所以在我点击白板之前,开始破解我自己的压缩算法,是否存在一个？这有多贵？它是批量处理,还是可以按插入/删除完成？

Answer 1

基本上你应该构建一个依赖图。如果元素 y 仅当 x 出现时才出现，则从 x 到 y 绘制一条边（如果相等，只需按字典顺序排序）。生成的图是 DAG。现在，对该图进行拓扑排序，以得到元素的顺序。每当您可以选择两个（或多个元素）之一时，请选择出现次数较多的一个。