假设您有一个由一堆固定大小的块组成的大文件。每个块都包含一定数量的可变大小的记录。每条记录必须完全适合单个块，并且根据定义，此类记录永远不会大于整个块。随着时间的推移，随着记录从这个“数据库”中移入和移出，记录会被添加到这些块中或从这些块中删除。
在某些时候，尤其是在许多记录添加到数据库并删除一些记录之后，许多块最终可能只被部分填充。
有什么好的算法可以打乱数据库中的记录，通过更好地填充部分填充的块来压缩文件末尾不必要的块？
算法要求：
- 压缩必须发生在原始文件的位置，而不会暂时将文件从其起始大小扩展到最多几个块
- 该算法不应不必要地干扰已经基本满的块
- 必须一次从文件中读取或写入整个块，并且应该假设写入操作相对昂贵
- 如果记录从一个块移动到另一个块，则必须将它们添加到新位置，然后再将其从起始位置删除，以便万一操作中断，不会因“失败”压缩而丢失任何记录。 （假设可以在恢复时检测到此类记录的临时重复）。
- 可用于此操作的内存可能只能是几个块的数量级，这仅占整个文件大小的很小一部分
- 假设记录大小约为 10 字节到 1K 字节，平均大小可能为 100 字节。固定大小的块约为 4K 或 8K，文件约为 1000 个块。
这听起来像是一个变体装箱问题，但是您已经有了想要改进的较差分配。因此，我建议研究一些成功解决装箱问题的方法的变体。
首先，您可能想通过定义您认为“足够满”（块足够满以至于您不想碰它）和“太空”（块有如此多的空白空间以至于必须添加更多记录）。然后，您可以将所有块分类为足够满、太空或部分满（那些既不够满也不太空的块）。然后，您将问题重新定义为如何通过创建尽可能多的足够满的块，同时最小化部分满的块的数量来消除所有太空的块。
您还需要弄清楚什么更重要：将记录放入尽可能少的块中，或者将它们充分打包，但读取和写入的块数量最少。
我的方法是对所有块进行初始遍历，将它们全部分类到上面定义的三个类别之一。对于每个块，您还希望跟踪其中的可用空间，对于太空的块，您需要获得所有记录及其大小的列表。然后，从太空的块中最大的记录开始，将它们移动到部分满的块中。如果您想最大程度地减少读取和写入，请将它们移动到内存中当前拥有的任何块中。如果您想最大程度地减少浪费的空间，请找到仍可保存记录的空白空间最少的块，并在必要时读取该块。如果没有块可以保存记录，则创建一个新块。如果内存中的块达到“足够满”阈值，请将其写出。重复此操作，直到部分填充的块中的所有记录都已放置完毕。
我跳过了很多细节，但这应该可以让您有所了解。请注意，装箱问题是NP-hard，这意味着对于实际应用，您需要决定什么对您最重要，因此您可以选择一种方法，在合理的时间内为您提供近似最佳的解决方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
