Wie kann ich die Größe eines ISO 9660-Dateisystems vorhersagen?

Question

Ich archiviere Daten auf DVD, und ich möchte die DVDs voll packen. Ich kenne die Namen und Größen aller Dateien, die ich auf der DVD haben möchte, aber ich weiß nicht, wie viel Platz Metadaten beanspruchen. Ich möchte so viele Dateien wie möglich auf jede DVD bekommen, also benutze ich eine Bubblesearch-Heuristik mit gierigem Bin-Packing. Ich versuche 10.000 Alternativen und bekomme die beste. Derzeit kenne ich die Größe aller Dateien und weil ich nicht weiß, wie Dateien in einem ISO 9660-Dateisystem gespeichert sind, füge ich eine Menge Slop für Metadaten hinzu. Ich würde gerne den Slop reduzieren.

Ich könnte genisoimage -print-size verwenden, außer es ist zu langsam --- gegeben 40.000 Dateien besetzt 500MB, dauert es etwa 3 Sekunden. Das Nehmen von 8 Stunden pro DVD ist nicht in den Karten. Ich habe die Quelle genisoimage vorher modifiziert und bin wirklich nicht scharf darauf, zu versuchen, den Algorithmus aus dem Quellcode herauszuquetschen; Ich hoffe, dass jemand einen besseren Weg kennt, um einen Kostenvoranschlag zu erhalten, oder mir eine hilfreiche Spezifikation geben kann.

---

Klärende das Problem und die Frage:

• Ich brauche Archive zu verbrennen, die über mehrere DVDs aufgeteilt, in der Regel um fünf auf einmal. Das Problem, das ich zu lösen versuche, ist zu entscheiden, welche Dateien auf jede DVD gelegt werden sollen, so dass jede DVD (außer der letzten) so voll wie möglich ist. Dieses Problem ist NP-schwer.

• Ich verwende den standard gierigen Packalgorithmus, wo Sie die größte Datei zuerst und Sie legen es in die erste DVD mit ausreichend Platz. Also j_random_hacker, ich bin definitiv nicht beginnend von Random. Ich starte von sortiert und benutze Bubblesearch, um die Reihenfolge zu ändern, in der die Dateien gepackt werden. Dieses Verfahren verbessert meine Verpackung von etwa 80% der geschätzten Kapazität auf über 99,5% der geschätzten Kapazität. Diese Frage ist etwa eine bessere Arbeit der Schätzung der Kapazität; Derzeit ist meine geschätzte Kapazität niedriger als die tatsächliche Kapazität.

• ich ein Programm geschrieben haben, die 10.000 Störungen versucht, beinhaltet jeweils zwei Schritte:

  1. eine Reihe von Dateien Wählen Sie
  2. Schätzung, wie viel Speicherplatz diese Dateien auf DVD
  nehmen

  Schritt 2 ist der Schritt, den ich versuche, zu verbessern. Gegenwärtig bin ich "auf der Seite der Vorsicht", wie Tyler D vorschlägt. Aber ich würde es gerne besser machen. Ich kann es mir nicht leisten, genisomage -print-size zu verwenden, weil es zu langsam ist. Ebenso kann ich die Dateien nicht auf die Festplatte tarieren, da sie nur zu langsam ist, aber eine TAR-Datei nicht die gleiche Größe wie ein ISO 9660-Bild hat. Es ist die Größe des ISO 9660-Bildes, das ich vorhersagen muss. Im Prinzip könnte das mit absoluter Genauigkeit gemacht werden, aber ich weiß nicht, wie es geht. Das ist die Frage.

---

Hinweis: Diese Dateien sind auf einer Maschine mit 3 TB Festplattenspeicher. In allen Fällen beträgt die durchschnittliche Größe der Dateien mindestens 10 MB. manchmal ist es deutlich größer. Also ist es möglich, dass genisomage schließlich doch schnell genug ist, aber ich bezweifle es --- es scheint zu funktionieren, indem ich das ISO-Image nach/dev/null schreibe, und ich kann mir nicht vorstellen, dass das bei der Bildgröße schnell genug sein wird Ansätze 4.7GB. Ich habe momentan keinen Zugriff auf diese Maschine oder habe die ursprüngliche Frage gepostet. Wenn ich abends Zugang habe, werde ich versuchen, bessere Zahlen für die Frage zu bekommen.Aber ich denke nicht genisomage wird eine gute Lösung sein --- obwohl es eine gute Möglichkeit sein könnte, ein Modell des Dateisystems zu lernen, das mir sagt, wie es funktioniert. Zu wissen, dass die Blockgröße 2 KB ist, ist bereits hilfreich.

Es kann auch nützlich sein zu wissen, dass Dateien im selben Verzeichnis auf die DVD samae gebrannt werden, was die Suche vereinfacht. Ich möchte direkt auf die Dateien zugreifen, was das Teer-vor-Brennen ausschließt. (Die meisten Dateien sind Audio oder Video, was bedeutet, dass es keinen Sinn macht, sie mit gzip zu treffen.)

Answer 1

Danke für das detaillierte Update. Ich bin überzeugt, dass Ihre derzeitige bin-Packing-Strategie sehr effizient ist.

In Bezug auf die Frage, "in Höhe von insgesamt b Bytes Genau wie viel Aufwand funktioniert ein ISO 9660-Dateisystem für n Dateien auf einpacken?" es gibt nur 2 mögliche Antworten:

1. Jemand hat bereits ein effizientes Werkzeug geschrieben, um genau das zu messen. Eine schnelle Google-Suche ergab jedoch nichts, was entmutigend ist. Es ist möglich, dass jemand auf SO mit einem Link zu seinem selbst erstellten Tool antwortet, aber wenn du für ein paar Tage keine Antworten mehr bekommst, dann ist das wahrscheinlich auch out.
2. Sie müssen die readily available ISO 9660 specs lesen und ein solches Werkzeug selbst bauen.

Eigentlich ist es eine dritte Antwort:

(3) Sie haben nicht wirklich auf jeder DVD jeden letzten Byte zu verwenden. In diesem Fall, schnappen Sie sich eine kleine repräsentative Handvoll von Dateien unterschiedlicher Größe (sagen wir 5), pad sie, bis sie ein Vielfaches von 2048 Bytes sind, und setzen Sie alle 2^5 möglichen Teilmengen durch genisoimage -print-size. Dann passen die Gleichung nx + y = iso_size - total_input_size auf diesem Datensatz wo n = Anzahl der Dateien in einem bestimmten Lauf, x zu finden, das ist die Anzahl der Bytes von Aufwand pro Datei und y, das ist die konstante Menge an Overhead (die Größe eines ISO 9660-Dateisystems, das keine Dateien enthält). Round x und y und verwenden Sie diese Formel, um Ihre ISO-Dateisystemgrößen für einen bestimmten Satz von Dateien zu schätzen. Stellen Sie aus Sicherheitsgründen sicher, dass Sie die längsten Dateinamen verwenden, die in Ihrer Sammlung für die Testdateinamen angezeigt werden, und stellen Sie sie jeweils in eine separate Verzeichnishierarchie, die so tief wie die tiefste Hierarchie in Ihrer Sammlung ist.

Answer 2

Kann tar nicht zum Speichern der Dateien auf der Festplatte verwenden? Es ist unklar, ob Sie ein Programm dafür schreiben oder einfach nur Backups machen.

Vielleicht etwas experimentieren und irren auf der Seite der Vorsicht - etwas freien Speicherplatz auf einer Festplatte würde nicht schaden.

Irgendwie stelle ich mir vor, Sie haben diese bereits in Betracht gezogen, oder dass meine Antwort fehlt der Punkt.

Answer 3

Ich bin nicht genau sicher, wie Sie gerade tun dies - nach meinem googeln „Bubblesearch“ bezieht sich auf eine Art und Weise eine Anordnung von Elementen zu wählen, die in der Nähe von eine gierigen Ordnung in gewissem Sinne ist, sondern in Ihr Fall, die Reihenfolge des Hinzufügens von Dateien zu einer DVD ändert nicht die Speicherplatzanforderungen, so dass dieser Ansatz Zeit unter Berücksichtigung mehrerer unterschiedlicher Aufträge, die Set von Dateien verschwenden.

Mit anderen Worten, wenn Sie so etwas wie die folgende machen einen Kandidatendateiliste zu generieren:

1. Randomly die Liste der Dateien mischen.
2. Ausgehend von der Spitze der Liste, gierig wählen Sie alle Dateien, die Sie auf eine DVD passen wird, bis nicht mehr. ineffizienten

Dann Sie den Lösungsraum suchen - für jeden endgültigen Kandidatensatz von n Dateien, die Sie erwägen möglicherweise alle n! Wege, dieses Set zu produzieren. Mein Vorschlag:

1. Alle Dateien in absteigender Reihenfolge der Dateigröße sortieren.
2. Markieren Sie die oberste (größte) Datei als "eingeschlossen" und entfernen Sie sie aus der Liste. (Es muss auf einigen DVDs enthalten sein, daher können wir es jetzt auch hinzufügen.)
3. Kann die oberste Datei in der Liste enthalten sein, ohne dass die (geschätzte) ISO-Dateisystemgröße die DVD-Kapazität übersteigt? Wenn dies der Fall:
   • Mit der Wahrscheinlichkeit p (z.B. p = 0,5), markiert die Datei als "eingeschlossen".
4. Die oberste Datei aus der Liste entfernen.
5. Wenn die Liste jetzt leer ist, haben Sie eine Kandidatenliste mit Dateien. Andernfalls, gehe zu 3.

Wiederholen Sie dies viele Male und wählen Sie die beste Dateiliste.

Tyler D Vorschlag ist auch gut: Wenn Sie ~ 40000 Dateien im Gesamtumfang von ~ 500MB haben, bedeutet dies eine durchschnittliche Dateigröße von 12,5Kb. ISO 9660 verwendet eine Blockgröße von 2 KB, was bedeutet, dass diese Dateien durchschnittlich 1 KB Speicherplatz oder etwa 8% ihrer Größe verschwenden. Wenn man sie mit Teer zusammenpackt, spart man etwa 8% Platz.

Answer 4

Schönes Denken, J. Random. Natürlich brauche ich nicht jedes letzte Byte, das ist hauptsächlich zum Spaß (und prahlen beim Mittagessen). Ich möchte in der Lage sein du auf der CD-ROM zu geben und haben es ganz in der Nähe 4700000000.

ich an der ECMA-Spezifikation sah aber wie die meisten Spezifikationen ist es mittel schmerzhaft und ich habe kein Vertrauen in meine Fähigkeit, es richtig zu machen . Auch scheint es, Rock Ridge Erweiterungen nicht zu diskutieren, oder wenn es so ist, habe ich es verpasst.

Ich mag Ihre Idee # 3 und denke, ich werde es ein bisschen weitertragen: Ich werde versuchen, ein ziemlich reichhaltiges Modell von dem, was los ist, und dann genisoimage -print-size auf einer Reihe von Dateigruppen verwenden, um die Parameter des Modells zu schätzen . Dann kann ich das Modell für meine Schätzung verwenden. Dies ist ein Hobby-Projekt, also wird es eine Weile dauern, aber ich werde es irgendwann schaffen. Ich werde hier eine Antwort schreiben, um zu sagen, wie viel Verschwendung beseitigt ist!

Answer 5

Ich habe vor kurzem ein Experiment durchgeführt, um eine Formel zu finden, um eine ähnliche Füllschätzung auf DVDs zu machen, und fand eine einfache Formel mit einigen Annahmen ...von Ihrem ursprünglichen Beitrag wird diese Formel wahrscheinlich eine niedrige Zahl für Sie sein, es klingt wie Sie mehrere Verzeichnisse und längere Dateinamen haben.

Annahmen:

• alle Dateien sind genau 8,3 Zeichen.
• Alle Dateien befinden sich im Stammverzeichnis.
• keine Erweiterungen wie Joliet.

Die Formel:

174 + floor(count/42) + sum(ceil(file_size/2048)) 

• Anzahl ist die Anzahl der Dateien
• file_size jede Größe der Datei in Bytes ist
• das Ergebnis ist in 2048-Byte-Blöcken.

Ein Beispielskript:

#!/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; 

ich überprüfte diese auf Festplatten mit bis zu 150k-Dateien mit einer Größe von 200 Byte auf 1 MiB reicht.