Brauche Rat beim Durchsuchen von großen Binärdateien nach bestimmten Strings

Hallo Zusammen,

Würde gerne euren Rat hören zu folgender Sache:

Ich muss mehrere Pcap Dateien durchsuchen (Gesamtgröße geht in die Terrabyte) nach User-Agent Strings (z.B. "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:7.0.1) Gecko/20100101 Firefox/7.0.1"). Diese Strings werden in den Dateien immer mit \r\n abgeschlossen. Ich möchte alle vorkommenden User-Agents sichern
, jedoch Duplikate verhindern.

Ich verfolge dabei den Ansatz die Pcap-Datei jeweils komplett einzulesen, in einer String-Variable zu speichern und anschliessend zu nach "\r\n" zu splitten.

// List for User Agents
        private List<String> userAgents = new List<String>();
...

string[] stringSeparators = new String[] { "\r\n" };
            string data;
            using (StreamReader sr = new StreamReader(dataFile))
                data = sr.ReadToEnd();
            dataStrings = data.Split(stringSeparators, StringSplitOptions.RemoveEmptyEntries);

            foreach (string s in dataStrings)
            {
                // found user-agent string?
                if (s.StartsWith("User-Agent:"))
                {
                    if (!userAgents.Contains(s.Substring(12)))
                        userAgents.Add(s.Substring(12));
                }

                if (GlobalVariables.StopThread)
                    return;
            }

Hier gibt es bestimmt einen eleganteren Ansatz. 🤔
Kann mir jemand einen nennen? 🙂

Funktioniert deine Lösung nicht, ist sie zu langsam?

Was ist Elegant? Schneller, speicher-effizienter?

Dein Frage ist zu unkonkret.

Mögliche Ansätze:
Du brauchst nicht die ganze Datei auf einmal einlesen sondern kannst es zeilenweise machen.

Desweiteren könntest du ein Dictionary<string,int> benutzen, dann müsstest du dich nicht über das contains kümmern und könntest z.B. zählen, wie oft der jeweilige User-Agent drin war

Hallo Seikilos,

vielen Dank für deine Antwort. Mir geht es darum die Schnelligkeit des Programmes zu erhöhen, es werden Datenmengen im Terrabytebereich verarbeitet.

Der Ansatz Dictionary<string,int> ist auf jeden Fall eine sehr gute Idee! Werde mich gleich mal an die Umsetzung wagen 🙂
Vielen Dank hierfür!

Zum lesen: Ich würde es Zeilenweise machen, so hast Du z.B. die Möglichkeit eine Statusanzeige zu implementieren XX.XXX Zeilen Durchsucht oder sowas.

Zum suchen: Schreib die Methode lieber selbst. Boyer-Moore-Algorithmus dürfte passen. Hier ein Beispiel: Boyer-Moore DotNetPerls

Der Ansatz Dictionary<string,int> ist auf jeden Fall eine sehr gute Idee! Werde mich gleich mal an die Umsetzung wagen 😃

Instinktiv würd ich das nicht on the fly machen sondern erstmal alle wegschreiben und nachher ein group by nachsetzen. Edit: Das ist blödsinn.

Hallo Tanari,

bei Terrabytes würde File.ReadAllLines vermutlich genauso wie StreamReader.ReadToEnd den Hauptspeicher sprengen. Aber ich wüsste nicht, was gegen StreamReader.ReadLine spricht. Splitten muss und sollte man jedenfalls nicht.

Ich gehe davon aus, dass das Einlesen der Daten von der Platte der Flaschenhals ist. Daher stände der Programmieraufwand für Boyer-Moore wohl nicht im Verhältnis zum Nutzen.

List<String> userAgents solltest du allerdings besser durch HashSet<String> ersetzen. Und natürlich geht es damit genauso wie mit dem Dictionary<> gut "on the fly". Erstmal alles wegzuschreiben halte ich nicht nur für unnötig, sondern auch für unnötig aufwändig.

herbivore

Uuuh, HashSet, wo warst du mein Leben lang! 😄

@Mathias Lauth: Was spricht gegen eine implizite Filterung von redundanten Einträgen durch Dictionary oder HashSet?

Ich stimme überein, dass man ein Problem nach dem anderen lösen sollte, aber hier fällt die Filterung ja quasi "kostenlos" nebenbei heraus.

Mich würde jedoch interessieren, wie sich Boyer-Moore zum StartsWith verhält

Hallo Seikilos,

StartsWith ist - gerade bei langen Strings - natürlich deutlich schneller als Boyer-Moore, weil StartWith nur am Anfang sucht. Aber wenn man Boyer-Moore verwenden würde, dann würde man gar nicht zeilenweise arbeiten, sondern könnte im Gesamt-String oder in größeren Blöcken davon möglicht schnell die Stellen finden, die mit User-Agent beginnen. Dabei arbeitet Boyer-Moore um so schneller, je länger der zu suchende String ist, weil dann gar nicht jedes Zeichen geprüft werden muss, sondern immer wieder Teile des zu durchsuchenden Strings übersprungen werden, weil klar ist, dass in diesem Teilen der gesuchte String nicht vorkommen kann. Genaueres in Boyer-Moore-Algorithmus.

herbivore

@Mathias Lauth: Was spricht gegen eine implizite Filterung von redundanten Einträgen durch Dictionary oder HashSet?

Offenbar nichts. Ich hatte vermutet (deswegen das Wort instinktiv), dass die ContainsKey Methode eine Laufzeit von mehr als O(1) hat, dass trifft aber nicht zu.

Wenn er jedoch wirklich große Mengen an Daten liest, müsste er nicht zeilenweise, sondern in Chunks die Daten lesen.

Wäre interessant, bei welcher Chunk Größe Boyer-Moore StartsWith überholen würde

Hallo Matthias Lauth,

beim HashSet muss man nicht mal Contains abfragen, sondern kann einfach ungeprüft Add verwenden. Ist der Eintrag schon vorhanden, wird er - automatisch - nicht neu hinzugefügt. Auch Add hat O(1).

Hallo Seikilos,

wie schon gesagt, wird der Flaschenhals das Einlesen sein. Spätestens wenn man das Durchsuchen auf einem Multicore-System in einen anderen Thread packt als das Einlesen, wird es von der Gesamtlaufzeit keinen Unterschied machen, ob man den String linear durchsucht oder mit Boyer-Moore. Selbst wenn man Einlesen und Durchsuchen in einem einzigen Thread durchführt, werden die Laufzeitunterschiede vermutlich minimal sein. Oder mit anderen Worten: "premature optimization is the root of all evil".

herbivore

Hallo Zusammen!

viele Dank für die rege Teilnahme! Ich habe jetzt alle List<String> auf HashSet<String> umgestellt und mal die Performance verglichen.

für die Verarbeitung von 52 Pcap-Dateien (insg. 2 GB) benötigt das Programm (inkl. parsen der User-Agents) auf einem i5 Prozessor mit 8GB Ram ziemlich genau 2 Minuten. Durch die Nutzung von HashSet<String> habe ich wie es scheint insg. ca 5 Sekunden gewonnen.

Wie setze ich es jetzt aber um das ich zu dem jeweiligen User-Agent String auch eine Anzahl speichere? Kann mir da jemand weiterhelfen?

Hallo Tanari,

das wurde doch schon beantwortet: Mit einem Dictionary<String, int>.

Wir sollten aufpassen, dass der Thread nicht vollends nach [Hinweis] Wie poste ich richtig? Punkt 1.1.1 abgleitet.

herbivore

Hallo herbivore,

sorry für meine Unkenntnis, aber kann ich Dictonary mit HashSet anstatt String kombinieren?

Danke!

Dictionary ist eine Art HashSet, bei dem zu jedem Hash Key ein Value zugewiesen wird.
Du brauchst also nur Dictionary<string, int>

Konkrete Antwort auf die Frage: Ja, da es generisch ist, kannst du auch Dictionary<HashSet<string>, int> schreiben, macht aber keinen Sinn.

Durch die Nutzung von HashSet<String> habe ich wie es scheint insg. ca 5 Sekunden gewonnen.

Da das Lesen von der Platte der Flaschenhals sein sollte, ist es sinnvoll, anstatt StreamReader einen BufferedReader (edit: heißt korrekt BufferedStream) oder einen FileStream mit Puffer zu verwenden.

Was Dictionary/HashSet angeht - schau einfach mal in die Doku!