7

我正在将数据存档到 DVD，并且我想将 DVD 打包完整。我知道 DVD 上所有我想要的文件的名称和大小，但我不知道元数据占用了多少空间。我想在每张 DVD 上获取尽可能多的文件，所以我使用了带有贪婪装箱的 Bubblesearch 启发式算法。我尝试了 10,000 种替代方法，并获得了最好的一种。目前我知道所有文件的大小，因为我不知道文件是如何存储在 ISO 9660 文件系统中的，所以我为元数据添加了很多内容。我想减少污水。

我可以使用genisoimage -print-size，但它太慢了——假设 40,000 个文件占用 500MB，大约需要 3 秒。每张 DVD 花费 8 小时是不可能的。我之前修改过genisoimage源代码，真的不热衷于尝试将算法从源代码中挤出来；我希望有人知道一种更好的方法来进行估算，或者可以为我指出一个有用的规范。

澄清问题和问题：

  • 我需要刻录分散在多张 DVD 上的档案，通常一次大约五个。我要解决的问题是决定将哪些文件放在每张 DVD 上，以便每张 DVD（最后一张除外）尽可能满。这个问题是 NP 难的。

  • 我正在使用标准贪婪打包算法，您首先放置最大的文件，然后将其放入第一张有足够空间的 DVD 中。所以j_random_hacker，我绝对不是从随机开始的。我从排序开始，并使用 Bubblesearch 来扰乱文件打包的顺序。此程序将我的包装从估计容量的 80% 左右提高到估计容量的 99.5% 以上。这个问题是关于更好地估计容量；目前我的估计容量低于实际容量。

  • 我编写了一个尝试 10,000 次扰动的程序，每个扰动都涉及两个步骤：

    1. 选择一组文件
    2. 估计这些文件将在 DVD 上占用多少空间

    第 2 步是我要改进的步骤。目前，正如 Tyler D 所暗示的那样，我“谨慎行事”。但我想做得更好。我用不起，genisomage -print-size因为它太慢了。同样，我无法将文件 tar 到磁盘，因为它太慢了，但是 tar 文件的大小与 ISO 9660 映像不同。这是我需要预测的 ISO 9660 图像的大小。原则上这可以完全准确地完成，但我不知道该怎么做。这就是问题所在。

注意：这些文件位于具有 3TB 硬盘存储空间的机器上。在所有情况下，文件的平均大小至少为 10MB；有时它明显更大。所以毕竟它可能genisomage会足够快，但我怀疑它 - 它似乎可以通过将 ISO 映像写入 /dev/null 来工作，我无法想象当图像大小接近时它会足够快4.7GB。我现在无法访问那台机器，或者当我发布原始问题时。当我晚上可以访问时，我会尝试为这个问题获得更好的数字。但我认为这不会genisomage是一个好的解决方案——尽管它可能是学习文件系统模型的好方法，它告诉我它是如何工作的。知道块大小为 2KB 已经很有帮助。

知道同一目录中的文件被刻录到 samae DVD 也可能很有用，这简化了搜索。我想直接访问文件，这排除了 tar-before-burning。（大多数文件是音频或视频，这意味着尝试用 . 来打击它们是没有意义的gzip。）

4

5 回答 5

2

我不确定你目前是如何做到这一点的——根据我的谷歌搜索，“Bubblesearch”是指一​​种选择在某种意义上接近贪婪排序的项目排序方式，但在你的情况下，将文件添加到 DVD 不会改变空间要求，因此这种方法会浪费时间考虑多个不同的订单，这些订单相当于同一组文件。

换句话说，如果您正在执行以下操作来生成候选文件列表：

  1. 随机打乱文件列表。
  2. 从列表顶部开始，贪婪地选择所有您认为 DVD 适合的文件，直到不再适合。

然后，您搜索解决方案空间的效率很低——对于任何n 个文件的最终候选集，您可能正在考虑所有n！制作该套装的方法。我的建议：

  1. 按文件大小的降序对所有文件进行排序。
  2. 将顶部（最大）文件标记为“包含”，并将其从列表中删除。（它必须包含在某些 DVD 中，所以我们不妨现在就包含它。）
  3. 列表中最上面的文件是否可以包含在（估计的）ISO 文件系统大小不超过 DVD 容量的情况下？如果是这样的话：
    • 以概率p（例如p = 0.5），将文件标记为“包含”。
  4. 从列表中删除最上面的文件。
  5. 如果列表现在为空，则您有一个候选文件列表。否则，转到 3。

重复此多次并选择最佳文件列表。

Tyler D 的建议也很好：如果您有 ~40000 个文件，总计 ~500Mb，这意味着平均文件大小为 12.5Kb。ISO 9660 使用 2Kb 的块大小，这意味着这些文件平均浪费了 1Kb 的磁盘空间，大约是它们大小的 8%。因此，首先将它们与 tar 打包在一起将节省大约 8% 的空间。

于 2009-01-22T07:28:19.620 回答
2

感谢您的详细更新。我很满意您当前的装箱策略非常有效。

至于问题，“对于总共b字节的n 个文件，ISO 9660 文件系统究竟需要多少开销？” 只有两个可能的答案：

  1. 有人已经编写了一个有效的工具来精确测量这一点。然而，快速的谷歌搜索却一无所获，这令人沮丧。SO上的某个人可能会回复他们自制工具的链接，但如果你几天没有收到更多回复，那么这可能也已经结束了。
  2. 您需要阅读现成的 ISO 9660 规范并自己构建这样的工具。

其实还有第三个答案：

(3) 您并不真正关心使用每张 DVD 上的每个最后一个字节。在这种情况下，抓取一小部分具有代表性的不同大小的文件（比如 5 个），填充它们直到它们是 2048 字节的倍数，然后将所有 2^5 个可能的子集放入genisoimage -print-size. 然后在该数据集上拟合方程nx + y = iso_size - total_input_size，其中n = 给定运行中的文件数，找到x，它是每个文件的开销字节数，和y，它是常数开销（不包含文件的 ISO 9660 文件系统的大小）。圆x和yup 并使用该公式来估计给定文件集的 ISO 文件系统大小。为了安全起见，请确保使用集合中出现的最长文件名作为测试文件名，并将每个文件名放在与集合中最深层次结构一样深的单独目录层次结构下。

于 2009-01-22T15:54:18.100 回答
1

不能使用 tar 将文件存储在磁盘上？目前尚不清楚您是在编写程序来执行此操作，还是只是进行一些备份。

也许做一些实验并谨慎行事 - 磁盘上的一些可用空间不会受到伤害。

不知何故，我想你已经考虑过这些，或者我的回答没有抓住重点。

于 2009-01-22T06:39:45.253 回答
1

我最近进行了一项实验，以找到一个公式来对 dvds 进行类似的填充估计，并在给出一些假设的情况下找到了一个简单的公式......从你原来的帖子来看，这个公式对你来说可能是一个很低的数字，听起来你有多个目录和更长的文件名。

假设：

  • 所有文件都是 8.3 个字符。
  • 所有文件都在根目录中。
  • 没有诸如 Joliet 之类的扩展。

公式：

174 + floor(count / 42) + sum( ceil(file_size / 2048) )
  • count 是文件数
  • file_size 是每个文件的大小（以字节为单位）
  • 结果是 2048 字节块。

一个示例脚本：

#!/usr/bin/perl -w
use strict;
use POSIX;

sub sum {
    my $out = 0;
    for(@_) {
        $out += $_;
    }
    return $out;
}

my @sizes = ( 2048 ) x 1000;
my $file_count = @sizes;

my $data_size = sum(map { ceil($_ / 2048) } @sizes);
my $dir_size = floor( $file_count / 42 ) + 1;
my $overhead = 173;

my $size = $overhead + $dir_size + $data_size;

$\ = "\n";
print $size;

我在具有多达 150k 个文件的磁盘上验证了这一点，文件大小从 200 字节到 1 MiB 不等。

于 2009-06-02T17:59:38.910 回答
0

好主意，J. Random。当然我不需要每个最后一个字节，这主要是为了好玩（以及在午餐时吹牛的权利）。我希望能够du在 CD-ROM 上键入并使其非常接近 4700000000。

我查看了 ECMA 规范，但与大多数规范一样，它是中等痛苦的，我对自己能否正确处理它没有信心。此外，它似乎没有讨论 Rock Ridge 扩展，或者如果有，我错过了。

我喜欢你的想法#3，并认为我会更进一步：我将尝试构建一个相当丰富的模型，然后genisoimage -print-size在多个文件集上使用来估计模型的参数。然后我可以使用该模型进行估计。这是一个爱好项目，所以需要一段时间，但我最终会解决它。我将在这里发布一个答案，说明消除了多少浪费！

于 2009-01-23T03:47:50.250 回答