C# - Effiziente Suche im kompletten Dateisystem

[gymfan]

Bis hierhin müsste das schonmal die meisten Fälle auskontern denn wie ihr schon alle sagtet normalerweise hat man ja einen Ordner für sowas.

Wenn mir Dateien wichtig sind, dann habe ich einen Ordner, in dem sie liegen und mind. ein Backup davon. Und da ich seit 30 Jahren faul bin (wobei es schon am C64 Backups meiner wichtigsten Dokumente gab), wird das Backup irgendwie automatisiert erstellt, enthält also auch die Verzeichnisstruktur. Damit weiss ich, wo ich das Backup einer ehemals als "korrekt" identifizierten Datei suchen muss.

Das Backup ist bei mir keine irgendwo vertreute und unsortierte Dateiablage (also z.B. der Quellordner, in dem ich konvertiert/bearbeitet habe), sondern ein Backup-Medium.

Klar kannst Du die Suche ohne Dateinamen machen, im Zweifel genügt einzig die Prüfsumme, die Du für die mögliche Ersatzdatei natürlich erst berechnen musst, wenn andere Kriterien passen "könnten".

Wenn es aber um korrekt abspielbare Musikdateien geht, gibt es kein hinreichendes Kriterium. Ein Lied aus zwei Quellen kann sich identisch anhören, aber auf Grund von (fehlenden) Metadaten eine andere Dateigröße haben. Wurde die identische Datei zweimal herunter geladen, ist sie zwar gleich groß., hat aber ein anderes Änderungsdatum.

also könnte ich dann die gesamte festplatte mit dem Vorgeschlagenen MFT Ansatz durchsuchen und erstmal ganz primitiv nach files filtern die eine Dateigröße besitzen die etwa mit meiner Datei übereinstimmt.

Bei dem Suchkriterium kannst Du Dir die Berechnung der MD5 schenken. Die Wahrscheinlichkeit, dass zwei unterschiedliche Dateien eine identische Prüfsumme haben, ist selbst bei MD5 verschwindend gering. Die MD5 Prüfsumme ich u.A. von der Dateigröße abhängig.

Entweder, die Datei hat exakt die Größe der ehemals korrekten Datei (also die in der DB gespeicherte Dateigröße und nicht die der defekten Datei) oder die Datei kann niemals identisch mit dem Original sein. Aber natürlich kann sie die selbe Musik enthalten, sogar bitgenau den selben Bitstream. Dafür wäre aber eine Inhaltsanalyse nötig.

Änderungsdatum - keine Ahnung. Ich weiß gar nicht wird das nicht sogar schon beim verschieben gesetzt? Oder war das das Erstelldatum? naja... in jedem fall, wenn man den dateinamen ändert müsste es spätestens geändert werden.

Der Dateiname ist kein Bestandteil der Datei. Windows ändert das Änderugnsdatum erst, wenn der Dateiinhalt geändert wird.

 

[Kokujou]

Wenn es aber um korrekt abspielbare Musikdateien geht, gibt es kein hinreichendes Kriterium. Ein Lied aus zwei Quellen kann sich identisch anhören, aber auf Grund von (fehlenden) Metadaten eine andere Dateigröße haben. Wurde die identische Datei zweimal herunter geladen, ist sie zwar gleich groß., hat aber ein anderes Änderungsdatum.

da hast du natürlich auch recht... richtigerweise müsste man jetzt nen melodie-verlgeich-algorithmus einbauen aber da wirds jetzt selbst mir zu blöd^^ aber schön wär's ja trotzdem. wenn man aus einem lied einen string generieren könnte wie bei nem midi file der seine melodie wiedergibt... aber ja, das wäre jetzt maximaler overhead und auch nicht korrekt, denn überlegt mal es gibt ja auch Karaoke-Versionen und die wären dann fälschlicherweise identisch

Bei dem Suchkriterium kannst Du Dir die Berechnung der MD5 schenken. Die Wahrscheinlichkeit, dass zwei unterschiedliche Dateien eine identische Prüfsumme haben, ist selbst bei MD5 verschwindend gering. Die MD5 Prüfsumme ich u.A. von der Dateigröße abhängig.

Halt Stop! Ich redete von Dateigröße, nicht von Prüfsumme. der Pre-Check gilt der Dateigröße, die MD5-prüfsumme kommt danach. klar ist die Wahrscheinlichkeit bei identischer Dateigröße relativ gering, aber es ist durchaus möglich. besonders wenn wir verschiedene dateien mit zumindest garantiert ähnlicher Dateigröße haben. Musikstücke sind schließlich alle ähnlich lang, meistens 4-5 Minuten

Entweder, die Datei hat exakt die Größe der ehemals korrekten Datei (also die in der DB gespeicherte Dateigröße und nicht die der defekten Datei) oder die Datei kann niemals identisch mit dem Original sein. Aber natürlich kann sie die selbe Musik enthalten, sogar bitgenau den selben Bitstream. Dafür wäre aber eine Inhaltsanalyse nötig.

stimmt auch wieder... dann lass ich das mit den +- byte... wenn die bits verloren gegangen sind ist ja uach der MD5 nicht mehr identisch

 

[gymfan]

aber ja, das wäre jetzt maximaler overhead und auch nicht korrekt, denn überlegt mal es gibt ja auch Karaoke-Versionen und die wären dann fälschlicherweise identisch

Dann wäre man quasi bei Youtube, nur dass dort niemand die akustische "Qualität" der Musik bewertet (klingt ein modernes 160 KBit/s MP3 wirklich schlechter wie eines mit 192 KBit/s, das aus einer schlechteren Quelle konvertiert wurde).

Ansonsten kannst Du nur auf Bitebene identische Dateien vergleichen/suchen. Und da ist halt eine der Voraussetzung, dass diese auch gleich groß sind.

Deine Idee, bei der Dateigröße eine gewisse Toleranz einzubauen, macht für mich nur an exakt einer Stelle Sinn:

Du musst nach einem Dateirecovery (gelöschte Dateien, die mit irgendeinem Programm wieder hergestellt wurden) ermitteln, ob diese wieder hergestellte Datei diejenige ist, die Du suchst. In dem Szenario kann die gerettete Datei länger sein, relevant sind aber nur die X ersten Byte der Datei, und zwar genau die Länge, welche das Original hatte. Also dürfte man dort nur längere Dateien berücksichtigen, und zwar jene, deren Größe exakt auf 4096 Byte aufgerundet ist (bzw. exakt auf die Blockgröße des genutzen Dateisystems). Zur MD5 Berechnung darf danach nicht die reale Dateilänge sondern nur die angenommene Länge (aus der DB) genutzt werden.

stimmt auch wieder... dann lass ich das mit den +- byte... wenn die bits verloren gegangen sind ist ja uach der MD5 nicht mehr identisch

Ich frage mich immer noch, wo die Bits verloren gehen sollen. Die Dateilänge steht in der FAT, genauso wie der Name und die von der Datei auf der HDD belegten Blöcke. Geht in der FAT nun exakt die Längenangabe kaputt, dann ist die Zieldatei zu kurz.

Falls Du jetzt nicht die Dateistruktur aller Dateien so exakt kennst, dass diese am Ende immer ein paar zusätzliche Byte haben (Metadaten am Ende oder gar Füllbyte), ist die zu kurze Datei defekt. Dann nützt es m.M.n. auch nichts, wenn Du das defekte "Original" durch eine zu kurze Kopie ersetzt. Je nach Dateiformat kann diese nicht abgespielt werde (z.B. MP4, welche nichts fürs Streaming gespeichert wurden) oder das Abspielen endet zu früh.

Selbst wenn man eine solche zu kurze Datei als das kleinere Übel ansieht, müsste man diese im Nachgang bearbeiten um sie wieder im korrekten Format zu speichern. Aber allerspätestens da hätte ich schon lange Backups von solchen, mir extrem wichitgen Dateien angelegt.

 

[Kokujou]

Naja Bitrot würde die datei eben zerstören, aber wie schon ausführlich dargelegt wurde, ist dann sowieso alles im Eimer, also dagegen stabil zu sein ist wohl eine Herkules-Aufgabe. Da müsste ich ja den kompletten Dateiinhalt vergleichen und keinen Hash und dann mit % Identisch arbeiten.
Aber das würde darauf hinauslaufen dass ich meine gesamte Mediensammlung in die Datenbank kopiere. Was möglich sit aber am ende doch nicht sinnvoll. in diesem Fall müsste ich dann einfach gucken welches Lied kaput ist und es selbst finden und neu hochladen.

aber gut ich danke allen für die Super-Tipps! Ich hab reichlich anreize für Features erhalten und ich danke jede für seine Zeit!

 

[Ebrithil]

Naja Bitrot würde die datei eben zerstören, aber wie schon ausführlich dargelegt wurde, ist dann sowieso alles im Eimer, also dagegen stabil zu sein ist wohl eine Herkules-Aufgabe. Da müsste ich ja den kompletten Dateiinhalt vergleichen und keinen Hash und dann mit % Identisch arbeiten.

Wenn du schon soweit bist würd ich direkt ein Dateisystem wie ZFS nehmen, da hast du Bitrot detection mit Hashes direkt drin und wenn du n Mirror betreibst (quasi RAID 1) repariert der dir das auch automatisch.

 

[gymfan]

Da müsste ich ja den kompletten Dateiinhalt vergleichen und keinen Hash und dann mit % Identisch arbeiten.

Der Sinn von (eindeutigen) Hashes ist genau das nicht zu benötigen. Du erstellst vom Original den Hash, speicherst den Hash in der DB und kannst danach prüfen, ob die Originaldatei noch in Ordnung ist und ob eine andere Datei bitgenau dieser Originaldatei entspricht ohne die Originaldatei zur Hand haben zu müssen.

Eine der Voraussetzungen dafür ist, dass die Dateien eine identische Größe haben.

Eine kleinere Datei kann niemals identisch mit der Originaldatei sein, eine größere kann am Anfang exakt die Originaldatei enthalten (wie das beim Recovery regelmäßig passiert).

Alles andere wäre Inhaltsanalyse, die Du entweder betreiben kannst oder nicht.

also dagegen stabil zu sein ist wohl eine Herkules-Aufgabe.

BTRFS/ZFS mit passenden Recovery-Informationen oder zusätzlich PAR2 nutzen. Wer dafür zahlen will kann auch Backups mit WinRAR machen. Das ist alles keine Hexerei, es kostet aber zusätzlichen Speicherplatz.

 

[sandreas]

Ich hab sowas ähnliches mal gebaut... Genutzt habe ich:

• Filesystem-Abstraktion: https://www.nuget.org/packages/System.IO.Abstractions
• Hashing: https://www.nuget.org/packages/Blake3Core/
  • Man beachte: Hashing ist (egal ob Blake oder Md5) sehr langsam und dazu noch unzuverlässig, da sich der Hash ändert, sobald man auch nur einen Metadata-Wert bzw. MP3-Tag anpasst
  • Ich hab auch drüber nachgedacht, die ffmpeg framehash funktion bzw. chromaprint zu verwenden, hab das dann aber verworfen (damit kann man wohl inhaltsbasierte Hashes erstellen, die die Metadaten ignorieren - habs aber nicht so zum Laufen bekommen, dass es einen sinnvollen Mehrwert gebracht hat)
• Audio-Metadata Library: https://github.com/Zeugma440/atldotnet
• Filesize
  • Auch hier gilt: Unter Umständen ändert sich diese, sobald man nur einen Tag in der MP3-Datei ändert
• Die simplen Iterator-Funktionen von C# mit einer eigenen Implementierung (siehe unten, die fertigen rekursiven Funktionen von C# führten bei mir zu nicht behandelbaren Exceptions bei Berechtigungsproblemen im Dateisystem)
• Sqlite als Datenbank, um den Datei-Index zu speichern

Das "Verschieben" von Dateien zu erkennen, war in meinem Fall völlig unnötig. Ich habe einfach:

• Ein aktuelles DateTime vor dem neuen Indexieren in einer Variable gespeichert (var indexerStart = DateTime.Now)
• Neue Dateien, die nicht im Index waren, mit aktuellem DateTime hinzugefügt
• Unveränderte vorhandene Einträge mit aktuellem DateTime aktualisiert
  • Veränderte vorhandene Einträge mit aktuellem DateTime und neuen Daten überschrieben
• Alle Einträge, die ein DateTime älter als den Zeitpunkt des Indexierens (var indexerStart) hatten gelöscht (das waren dann die nicht mehr auffindbaren Dateien - verschobene oder gelöschte)

Damit war der Index immer aktuell und vollständig.

Hier noch der Code-Baustein für meinen File-Iterator. Man beachte das yield return, damit war der viel schneller als Standardimplementierungen, die man so im Netz findet.

        private IEnumerable<string> WalkRecursive(string currentPath)
        {
            var pending = new Stack<string>();
            pending.Push(currentPath);
   
            while (pending.Count != 0)
            {
                currentPath = pending.Pop();
                yield return currentPath;
                IEnumerable<string> tmp;
                try
                {
                    tmp = _fs.Directory.EnumerateFiles(currentPath);
                }
                catch (Exception e)
                {
                    if (!_exceptionHandler(currentPath, e))
                    {
                        break;
                    }
                    continue;
                }
                foreach (var item in tmp)
                {
                    yield return item;
                }
           
                _fs.Directory.EnumerateDirectories(currentPath).AsParallel().ForAll(pending.Push);
            }
        }

 

[cfHxqA]

Man beachte: Hashing ist (egal ob Blake oder Md5) sehr langsam und dazu noch unzuverlässig, da sich der Hash ändert, sobald man auch nur einen Metadata-Wert bzw. MP3-Tag anpasst

Das erklärt sich doch von alleine, dass wenn Du etwas änderst - innerhalb der Datei - das auch der Hash geändert wird. Das ist doch der Sinn einer Hash-Funktion? Somit sehr zuverlässig.

Andernfalls hinterlege zur entsprechenden Datei weitere META-Daten, separat.

 

[sandreas]

Das ist doch der Sinn einer Hash-Funktion? Somit sehr zuverlässig.

Gut "unzuverlässig" war in dem Fall nicht das richtige Wort. Für das Erkennen von Datei-Änderungen bzw. Duplikaten ist das sehr zuverlässig, das ist richtig. Für die Erkennung von verschobenen oder doppelten Audio-Dateien ist es aber nicht so gut geeignet, weil eine Audio-Datei den selben Audio-Inhalt haben kann, obwohl der Hash unterschiedlich ist. Hat man also in der MP3-Sammlung mal eine Datei kopiert und dort dann Tags geändert (z.B. die Bewertung), kann man das "Duplikat" nicht mehr ohne Weiteres als solches erkennen.

 

[tollertyp]

Dafür kann die Hash-Funktion nicht, daran ist halt das Dateiformat schuld. Wer möchte, kann ja nur die Nutzdaten hashen... aber ob das zum gewünschen Ergebnis führt?

Neu codiert, mit abweichender Bitrate z.B., ist das Musik-Stück doch immer noch dasselbe.

 

[Yuuri]

Hat man also in der MP3-Sammlung mal eine Datei kopiert und dort dann Tags geändert (z.B. die Bewertung), kann man das "Duplikat" nicht mehr ohne Weiteres als solches erkennen.

So schwer ist das auch nicht. Wenns wirklich um den Inhalt geht, gibts hunderte Libs und Tools, die die verschiedensten Formate parsen und dir den reinen Stream zurückgeben können. Den kannst du problemlos hashen und jegliche Metadaten dabei ignorieren.

Zur Not einfach den PCM Stream mit ffmpeg extrahieren und diese hashen.

ffmpeg -i "$input" -acodec pcm_s16le -f s16le - 2>/dev/null | md5sum

Problematisch wirds natürlich, wenn man den Stream selbst anfässt.

 

[sandreas]

Dafür kann die Hash-Funktion nicht, daran ist halt das Dateiformat schuld. Wer möchte, kann ja nur die Nutzdaten hashen... aber ob das zum gewünschen Ergebnis führt?

Ich weiß nicht mal genau, was das "gewünschte" Ergebnis ist. Fakt ist, dass es kein ganz so triviales Problem ist, doppelte oder verschobene Audio-Dateien zu erkennen, sofern es auch um den Inhalt / Stream geht, verglichen mit einem einfachen Byte-Abgleich. Bei Bildern und Videos wäre das aber genau so.

So schwer ist das auch nicht.

Es ist tatsächich nicht so schwierig. Oben habe ich ja bereits erwähnt, dass ich darüber nachgedacht hatte, ffmpeg framehash oder chromaprint zu verwenden.

Das Problem ist die Performance. Um einen Datei-Hash zu bilden, muss ich die Datei ganz einlesen (zumindest den Teil, den ich hashen will). Wenn ich jetzt noch ffmpeg den Stream normalisieren lasse, wird es elend langsam. Bei mir war es um ein vielfaches schneller, NEUE und GEÄNDERTE Dateien zu re-indexieren und dann alle NICHT-MEHR-VORHANDENEN aus dem Index zu entfernen. Dateien via Hash vergleichen ist bei mir deutlich langsamer - den Dateisystem-Scan musste ich ohnehin machen, um eine Index-Aktualisierung vorzunehmen.