重新排列文本文件中的行以获得更好的压缩比率。

Question

5

我有很多巨大的文本文件，需要以最高比率压缩。压缩速度可以慢一些，只要解压速度合理即可。

这些文件中的每一行都包含一个数据集，并且它们可以以任何顺序存储。

但对我来说，压缩速度不是问题。是否有现成的工具可以将相似的行分组在一起？或者只是一个我可以实现的算法？

仅仅排序就有了一些改进，但我怀疑可以做得更好。

每个文件约有6亿行，每行~40字节，总共24GB。使用xz压缩到约10GB。

- Craden

1

我想，如果相邻字符串之间的编辑距离最小，你的压缩比将足够好...例如，尝试这种方式。当然，还要尝试不同的压缩算法... - Stanislav Kralin

谢谢您提供的这个例子 - 我目前正在尝试使用k-means聚类算法，并取得了相当不错的结果。 - Craden

1

你能重新排列每行中字段的顺序吗？（假设所有行都有相同的顺序） - samgak

每行中的字段可以重新排列，但我认为这样做没有好处，因为它们都非常相似。 - Craden

准备好使用的工具来分组相似的内容。我期望BWT能够捕捉到大部分可能的优势。截至2017年，24 GB对于大多数机器来说已经超出了易处理数据窗口的大小，并且并非所有格式/实用程序/算法都支持大窗口。 - greybeard

尝试使用k-means聚类算法进行实验，结果非常有前途。请在问题中报告这些实验的方法和结果，以指导不必要的建议。 - greybeard

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- samgak · Accepted Answer

这是一个相对幼稚的算法：

这是一种贪心算法，不会全局最优，但在匹配在一起时压缩效果很好。它是O(n²)的，但您说压缩速度不是问题。主要优点是它是经验性的：它不依赖于哪些行顺序能够压缩得好的假设，而是实际测量。

如果您使用zlib，它提供了一个deflateCopy函数来复制压缩流的状态，尽管这显然是非常昂贵的。

编辑：如果您将此问题视为在尝试最小化序列中所有行之间的总编辑距离的情况下输出所有行，则该问题将简化为旅行商问题，其中编辑距离为“距离”，并且所有行都是您必须访问的节点。因此，您可以研究各种方法来解决此问题并将其应用于此问题。即使如此，在编辑距离方面的最佳TSP解决方案也不一定是压缩最小的文件。