在一个分块文件中，什么是一种好的压缩记录算法？

Question

假设您有一个由许多固定大小块组成的大文件。每个块包含一些变量大小的记录。每条记录必须完全适合单个块中，因此这样的记录定义上永远不会比完整块更大。随着时间的推移，“数据库”中的记录被添加到这些块中并从中删除。

在某些时候，特别是在向数据库添加了许多记录并删除了几个记录之后，许多块可能仅部分填充。

什么是一种好的算法来重新排列这个数据库中的记录，以通过更好地填充部分填充的块来压缩文件末尾的不必要块？

算法的要求：

- 压缩必须在原始文件中进行，而不是通过暂时将文件扩展超过其起始大小的几个块。 - 算法不应不必要地干扰已经主要充满的块。 - 整个块必须一次从/写入文件，并且应该假定写操作相对昂贵。 - 如果将记录从一个块移动到另一个块，则必须在将其从起始位置删除之前将其添加到新位置，以便在操作中断时不会因“失败”的压缩而丢失记录。（假设可以在恢复时检测到这些记录的临时复制）。 - 可以用于此操作的内存可能只有几个块的数量，这是整个文件大小的非常小的百分比。 - 假设记录的数量为10字节到1K字节，平均大小可能为100字节。固定大小的块大约为4K或8K，文件大约为数千个块。

- InSciTek Jeff

Answer 1

这听起来像是装箱问题的变种，但你已经有了一个较差的分配方案，想要改进它。因此，我建议看一下对于装箱问题成功的方法的变化。

首先，你可能想通过定义什么是“足够满”（即一个块已经足够满了，你不想再动它），以及什么是“太空虚”（即一个块有太多的空间需要添加更多的记录），来参数化你的问题。然后，你可以将所有块分类为足够满、太空虚或部分满（既不足够满也不太空虚）。接下来，你将重新定义问题，即如何通过创建尽可能多的足够满的块来消除所有太空虚的块，同时最小化部分满块的数量。

你还需要确定哪个更重要：将记录放入尽可能少的块中，还是充分地打包记录但读写的块数最少。

我的方法是首先对所有块进行一次分类，将它们分类为上述三类中的一类。对于每个块，您还需要跟踪其中可用的空闲空间，并对于太空置的块，您需要有一个记录所有记录及其大小的列表。然后，从太空置块中最大的记录开始，将它们移动到部分填充的块中。如果您想要最小化读写操作，请将它们移动到当前已经在内存中的任何块中。如果您想要最小化浪费的空间，请找到剩余空间最少但仍能容纳记录的块，必要时读取该块。如果没有块可以容纳该记录，则创建一个新块。如果内存中的块达到“足够满”的阈值，请将其写出。重复此过程，直到所有部分填充的块中的记录都被放置。

我省略了很多细节，但这应该可以给您一些思路。请注意，装箱问题是NP-hard问题，这意味着对于实际应用程序，您需要决定哪些方面最重要，以便选择一种方法，在合理的时间内给您提供近似最佳解决方案。

- TimB

---

感谢指出了二进制装箱问题的比较。这很有帮助。解决方案中棘手的部分是第一遍扫描和保留统计信息的记录数量庞大，这是不可行的。此外，由于写入操作很昂贵，在某种意义上，您只有一两次机会重新编写给定块。 - Tall Jeff

理想情况下，我考虑使用一些遍数来针对特定的块和记录进行合并。例如：在每次遍历中找到最容易优化的部分进行处理，并在时间过长或没有显著优化时停止。再次感谢！ - Tall Jeff

Answer 2

一种在线（一次性碎片整理）有界空间（内存需求）装箱算法的修改可能在这里起作用。请参阅Coffman等人的《装箱近似算法：组合分析》。"Bin Packing Approximation Algorithms: Combinatorial Analysis"。

- Rafał Dowgird

---

谢谢您提供关于装箱问题比较和这篇关于各种方法分析的论文的参考！ - Tall Jeff

Answer 3

如果这些记录没有排序，我会从前面开始使用从最后一个块中提取的记录来填充块。这将最小化数据移动，相当简单，并且应该可以很好地紧密打包数据。

例如：

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

更新：我忽略了保持仅在内存中使用非块的规则。我已更新伪代码以修复此问题。还修复了循环条件中的故障。

- Derek Park

---

这种方法基本上是我们开始的地方，但事实证明记录大小的不规则性经常会留下未经优化的紧凑块。如果愿意再多搜索一些，可以找到更好的匹配，但这样就变成了NP难问题，现在正在寻找更多的启发式方法。 - Tall Jeff

不客气。我认为调整一次在内存中保留的块数会有所帮助。如果你在内存中保留了十个块的记录，我预计你可以填满大多数部分块。 - Derek Park

你也可以只在内存中保存较小的记录，然后在之后压缩剩余的大记录（这样你就不会随着时间的推移填满整个内存）。 - Derek Park

Answer 4

这里有一个算法，你可能可以利用它，尽管你的记录在固定大小的块内可能需要更多的工作。

有界时间堆碎片整理

- Richard

---

谢谢。然而，正如你所提到的那样，那篇论文没有解决问题的两个动态因素。1）固定大小块的箱式特性和（2）记录大小的线性字节变异性。即：堆中“记录”的2^N特性是其解决方案的关键因素。 - Tall Jeff