小编典典

有什么好的算法可以压缩已阻止文件中的记录?

algorithm

假设您有一个由一堆固定大小的块组成的大文件。这些块中的每个块都包含一些可变大小的记录。每条记录必须完全适合单个块,然后根据定义,此类记录决不能大于整个块。随着时间的流逝,随着记录从该“数据库”进出,记录将添加到这些块中或从中删除。

在某个时候,尤其是在可能将许多记录添加到数据库中并删除了一些记录之后,尤其是在许多块最终只能部分填充的情况下。

有什么好的算法可以对数据库中的记录进行混洗,从而通过更好地填充部分填充的块来压缩文件末尾的不必要块?

算法要求:

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

阅读 208

收藏
2020-07-28

共1个答案

小编典典

这听起来像是装箱问题的一种变体,但是您已经有一个要改善的劣质分配。因此,我建议研究能成功解决垃圾箱包装问题的各种方法。

首先,您可能想通过定义您认为“足够充满”的内容(其中一个块足够充满以至于您不想触摸它)和什么是“太空”(其中一个块具有太多的空白空间,因此必须添加更多的记录)。然后,您可以将所有块分类为足够满,太空或部分满(既不满也不空)。然后,您将问题重新定义为如何通过创建尽可能多的足够多的块,同时最小化部分完全块的数量来消除所有太空的块。

您还需要弄清更重要的事情:将记录放入尽可能少的块中,或者将它们适当地打包,但要读取和写入的块数最少。

我的方法是对所有块进行初始遍历,将它们全部分类为上面定义的三个类之一。对于每个块,您还希望跟踪其中的可用空间,对于太空的块,您将需要具有所有记录及其大小的列表。然后,从太空的块中最大的记录开始,将它们移到部分充满的块中。如果要最大程度地减少读写,请将它们移到当前内存中的任何块中。如果要最小化浪费的空间,请找到仍然保留记录的空白空间最少的块,并在必要时读取该块。如果没有任何块将保留该记录,请创建一个新块。如果内存中的某个块达到“足够多”的阈值,则将其写出。

我已经跳过了许多细节,但这应该可以使您有所了解。请注意,装箱问题是NP-hard的,这意味着对于实际应用,您将要决定对您最重要的事情,因此您可以选择一种在合理的时间内为您提供最佳解决方案的方法。

2020-07-28