找出多组数之间交集的最有效方法

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，我尝试从一组公共子集中构建每个子集--即分解出最常见的数据循环子集，一个层次深度(即不递归)。

为了确定要分解的公共子集，我尝试逐行考虑这些集合，并查看添加了哪些项和删除了哪些项。这些新的子集被认为是新的子集，随着时间的推移，等大小的子集成对合并成新的子集。例如，对于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}),

然后...which合并成..。

({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)对于大型数据集来说是痛苦的，在比较交叉点以找出潜在的公共子集时，如何排除噪声并不明显。

TL;DR:在大量集合之间识别结构相似性的最佳方法是什么，以便筛选出重复的子集？

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

Answer 1

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

1. 编码连续集合之间的对称差异(我认为这就是马克的意思)。

1. --这对编码很好，但很难随机解码。要修复它，定期发出整个集合。一种启发式方法是，每当我们在三角点中发出的量与整个集合发出的量大致相同时，就可以做到这一点--理论上，这只需要在存储中增加一个常数因子，同时将我们扫描的三角洲的总大小限制在一个大于集合大小的常数因子上。

1. 对varint使用增量编码。这是发布列表的常见编码，因此应该有优化的实现在周围浮动。

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

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