algorithm - 什么是压缩被阻止文件中记录的好算法？

Question

假设您有一个由一堆固定大小的 block 组成的大文件。这些 block 中的每一个都包含一些可变大小的记录。每个记录必须完全适合一个 block ，然后根据定义，这些记录永远不会大于一个完整的 block 。随着时间的推移，随着记录从这个“数据库”进出，记录会被添加到这些 block 中或从这些 block 中删除。

在某些时候，尤其是在可能有很多记录被添加到数据库中并且有一些被删除之后 - 许多 block 可能最终只被部分填充。

有什么好的算法可以通过更好地填充部分填充 block 来打乱该数据库中的记录以压缩文件末尾不必要的 block ？

算法要求:

• 压缩必须发生在原始文件的位置，而不是暂时将文件从其起始大小最多扩展几个 block
• 算法不应不必要地干扰已经基本满的 block
• 必须一次从文件读取或写入整个 block ，并且应该假设写入操作相对昂贵
• 如果记录从一个 block 移动到另一个 block ，则必须在从起始位置删除它们之前将它们添加到新位置，以便在操作中断的情况下不会因“失败”压缩而丢失记录。 (假设可以在恢复时检测到此类记录的临时复制)。
• 可用于此操作的内存可能只有几个 block 的数量级，占整个文件大小的百分比非常小
• 假设记录大约为 10 字节到 1K 字节，平均大小可能为 100 字节。固定大小的 block 大约为 4K 或 8K，文件大约为 1000 个 block 。

Answer 1

这听起来像是 bin packing problem 的变体，但是您已经有了想要改进的劣质分配。因此，我建议查看对装箱问题成功的方法的变体。

首先，您可能希望通过定义您认为“足够满”( block 足够满以至于您不想触摸它)以及“太空”(其中一个 block 有太多的空白空间，它必须有更多的记录添加到它)。然后，您可以将所有 block 分类为足够满、太空或部分满(那些既不够满也不太空)。然后，您将问题重新定义为如何通过创建尽可能多的足够满的 block 来消除所有太空的 block ，同时尽量减少部分满的 block 的数量。

您还需要弄清楚什么更重要:将记录放入尽可能少的 block 中，或者充分打包它们但读取和写入的 block 数量最少。

我的方法是对所有 block 进行初始传递，将它们全部分类为上面定义的三个类别之一。对于每个 block ，您还需要跟踪其中的可用空间，对于太空的 block ，您需要一个包含所有记录及其大小的列表。然后，从太空的 block 中最大的记录开始，将它们移动到部分满的 block 中。如果你想最小化读取和写入，将它们移动到你当前内存中的任何 block 中。如果您想最大程度地减少浪费的空间，请找到空白空间最少的 block ，该 block 仍将保留记录，必要时读入该 block 。如果没有 block 将保留记录，则创建一个新 block 。如果内存中的 block 达到“足够满”的阈值，则将其写出。重复直到部分填充 block 中的所有记录都已放置。

我跳过了很多细节，但这应该能让您有所了解。注意装箱问题是NP-hard ，这意味着对于实际应用，您需要决定什么对您最重要，因此您可以选择一种能够在合理时间内为您提供近似最佳解决方案的方法。