压缩文件中记录的压缩算法是什么？

Question

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

在某些情况下，尤其是在将许多记录添加到数据库并删除多个记录之后 - 许多块最终只能部分填充。

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

算法的要求：

• 压实必须到位原始文件的发生没有暂时超过几个街区最多从其起始大小
• 算法应避免不必要地延长了文件干扰已经主要完成的块
• 必须从文件中一次读取或写入整个块，并且应该假定写入操作相对昂贵
• 如果将记录从一个块移动到另一个他们必须被添加到他们的新位置，然后再从他们的起始位置移除，以便在操作中断的情况下，由于“失败”压缩而没有记录丢失。 （假设这种记录的临时重复可以在恢复时检测到）。
• 可以使用该操作的内存只能是也许还有好几个块的顺序是整个文件的大小
• 的比例很小就假设记录的10个字节的顺序与1K字节平均大小可能为100字节。固定大小的块大小为4K或8K，文件大小为1000块。

Answer 1

这听起来像是bin packing problem的一种变体，但是您已经有了一个您想要改进的低劣分配。所以我建议看一下对于装箱问题成功的方法的变化。

首先，您可能希望通过定义您认为“足够”（其中一个块足够完整以至于不想触摸它）来参数化您的问题，以及什么是“太空”（一个块有很多空的空间，它必须添加更多的记录）。然后，您可以将所有块分为足够空，空或部分空间（那些既不够饱满也不空）。然后您将问题重新定义为如何通过尽可能多地创建足够多的块来消除所有太空块，同时尽量减少部分满块的数量。

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

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

我已经跳过了几个细节，但是这应该会给你一些想法。请注意，bin装箱问题是NP-hard，这意味着在实际应用中，您需要决定哪些对您最重要，因此您可以选择一种方法，在合理的时间内为您提供近似最佳的解决方案。

Answer 2

如果没有这些记录的排序，我只需从前面的块中填充从最后一个块提取的记录。这将最大限度地减少数据的移动，相当简单，并且应该做好包装数据的体面工作。

例如为：

// 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(); 
     } 
    } 
} 

更新：我忘了保持无块，仅-内存规则。我更新了伪代码来解决这个问题。还修复了我的循环条件中的小故障。

Answer 3

以下是您可以利用的算法，尽管您在固定大小块中的记录可能需要更多的工作。

Heap Defragmentation in Bounded Time

Answer 4

的上线（在一个通整理）的修改界空间（内存要求）装箱算法很可能在这里工作。

参见Coffman等人的"Bin Packing Approximation Algorithms: Combinatorial Analysis"。