algorithm - 找到多组数字之间交集的最有效方法

Question

我正在尝试有效地压缩看起来像这样的数字集(每行一组):

19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 179 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 179 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206 45387
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206 45387 45392
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206 45387
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206 45392
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 206 45392 144554
19 20 23 24 27 29 32 35 69 97 99 119 122 129 130 134 136 137 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205
19 20 23 24 27 29 32 35 69 97 99 119 122 129 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 45392 144554
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205
19 20 23 24 27 29 32 35 69 97 99 119 122 129 132 134 136 137 139 141 147 148 152 157 158 160 170 173 174 175 176 178 182 183 185 186 188 189 190 192 194 195 197 198 199 200 201 202 203 204 205 45392 144554

您可以轻松拥有约 10K 个集合，每个集合有约 10K 个条目。然而，正如您从样本数据中看到的那样，集合中的大部分数据都是冗余的——每个新集合都有一些删除和一些添加。 (偶尔会有很大的变化，但这种情况很少见)。

我想将其压缩为:

• 占用少量存储空间
• 解压缩时使用最少的 CPU(随机访问)
• 理想情况下是逐步压缩(但回想起来压缩它也可以)。

为了在扩展时实现最少的 CPU，我尝试从一组公共(public)子集构建每个集 - 即分解出最常见的重复数据子集，一层深(即无递归)。

为了确定要分解的公共(public)子集，我尝试逐行考虑这些集合，并查看添加了哪些项目以及删除了哪些项目。这些添加被视为新的子集，并且随着这些子集随着时间的推移而积累，大小相等的子集被成对地合并成新的子集。例如，对于第 N 个集合为整数 0 到 N 的简单情况，您将得到:

({0}),
({0, 1}),
({0, 1}),({2}),
({0, 1, 2, 3}),
({0, 1, 2, 3}),({4}),
({0, 1, 2, 3}),({4, 5}),
({0, 1, 2, 3}),({4, 5}),({6}),
({0, 1, 2, 3, 4, 5, 6, 7}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9}),({10}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9, 10, 11}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9, 10, 11}),({12}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9, 10, 11}),({12, 13}),
({0, 1, 2, 3, 4, 5, 6, 7}),({8, 9, 10, 11}),({12, 13}),({14}),
({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}),

然后，如果您跟踪每个子集的“父”组件，当一个项目被删除时，您可以将给定的子集分解成它的组件(随着时间的推移，这些组件随后会再次合并)。例如，删除第 4 项会产生如下内容:

({0, 1, 2, 3}),({5, 6, 7}),({8, 9, 10, 11}),({12, 13}),({14}),

...然后合并为...

({0, 1, 2, 3, 8, 9, 10, 11}),({5, 6, 7}),({12, 13}),({14}),

根据经验，这相当有效(磁盘空间大约增加了 5 倍)，但我担心我缺少一种更明显的方法来发现哪些子集可以在整个数据集中最有效地分解出来。

我还尝试构建一个前缀 trie 来跟踪哪些前缀最常出现，然后将它们分解出来 - 除了这会使用相当多的存储空间，并且无助于压缩不是前缀的子集。它也没有利用集合无序这一事实。

我也尝试过查看签名树 (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.7315&rep=rep1&type=pdf)，但当您的数据集很大而不是那么稀疏时，这些似乎会使用大量磁盘存储。

我也可以进行 O(N^2) 搜索来比较每个集合彼此的交集，并跟踪子集重复次数最多的直方图，但 O(N^2) 对于大型数据集来说会很痛苦，并且在比较交叉点以发现底层公共(public)子集时如何调出噪声并不明显。

TL;DR:发现大量集合的结构相似性以提取重复子集的最佳方法是什么？

编辑:已阐明解压缩时需要随机访问。另外，我已经发布了一个真实的数据集到 http://matrix.org/~matthew/expanded.out.xz .警告:这个 2MB .xz 扩展到 4.9GB 的实际数据......这很好地说明了这个问题，以及为什么到目前为止我还没有找到比 5 倍压缩效果更好的方法令人沮丧:/

Answer 1

我们可以结合三个简单的想法:

1. 对连续集合之间的对称差异进行编码(我认为这就是 Mark 的建议)。

2. 这有利于编码，但很难随机解码。要修复它，请定期发出整个集合。一种启发式方法是，每当我们发射的增量与整个集合差不多时，就执行此操作——理论上，这只会在存储上花费一个常数因子，同时将我们扫描的增量的总大小限制为一个常数因子，超过集合的大小。

3. 使用带有 varint 的增量编码。这是发布列表的通用编码，因此应该有优化的实现。

Python 3 编码器将给定输入压缩到小于 5 MB。我们还需要一个索引，但这不会增加太多。

import fileinput
import re
import sys

output = open("output", "wb")


def emit_varint(n):
    buffer = []
    mask = 127
    while n > mask:
        buffer.append(128 | (n & mask))
        n >>= 7
    buffer.append(n)
    output.write(bytes(buffer))


def emit_indices(delta):
    emit_varint(len(delta))
    prev = 0
    for x in sorted(delta):
        emit_varint(x - prev)
        prev = x


delta_counter = 0
delta_from = 0
previous_indices = set()
for i, line in enumerate(fileinput.input()):
    if i % 1000 == 0:
        print(i, file=sys.stderr)
    m = re.match(r"[^{}]*\{(\d+(,\d+)*)\}", line)
    if not m:
        continue
    indices = set(map(int, re.findall("\d+", m.group(1))))
    delta = indices ^ previous_indices
    delta_counter += len(delta)
    if delta_counter + len(delta) > 2 * len(indices):
        emit_indices(indices)
        delta_counter = 0
        delta_from = i
    else:
        emit_indices(delta)
    previous_indices = indices