Schnellere Suche eines Strings in Textdateien

Question

Ich muss mit C# in einer Gruppe von Textdateien nach einer Zeichenfolge (ungefähr 13 Zeichen) suchen. Die Anzahl der Textdateien ändert sich und kann zwischen 100-1000 liegen. Die Größe der Dateien kann zwischen 1 KB und 10 MB liegen.

Ich versuchte die naive Art, jede Datei zu öffnen, Zeile für Zeile zu lesen und zu sehen, ob die Zeichenfolge existiert (mit index.of), aber das ist zu langsam. Ich habe auch versucht, den Boyer-Moore-Algorithmus zu verwenden, der das Timing um 5 Sekunden verbessert hat, aber das fühlt sich immer noch langsam an.

Haben Sie eine Idee, wie Sie die Suche beschleunigen können?

Answer 1

Sie sollten die Betriebssystem-Dateisuche mit Inhalten in Betracht ziehen. Werfen Sie einen Blick auf Microsoft Windows Search 3.x SDK

Oder Sie können PLINQ für die Suche in einem Array von Dateien verwenden. Siehe diesen Link:

File Content and Directory Search using Directory.GetFiles and PLINQ

Answer 2

zwei Möglichkeiten in den Sinn kommen:

Lesen der Textdatei im Speicher und suchen Sie einfach die gesamte Zeichenfolge auf einmal.

Wenn sich herausstellt, dass es zu langsam oder zu speicherhungrig ist, verwenden Sie einen Indexer wie Apache Lucene. Es gibt eine schöne und einfache SDK für die für .NET zur Verfügung, die so genannte Lucene.net

Hier ist eine kleine Einführung für sie: http://www.codeproject.com/Articles/29755/Introducing-Lucene-Net

Answer 3

Wenn Ihr Computer verarbeiten kann es versuchen, alle Textdateien in den Speicher zu laden (Verwenden Sie die technique shown here und dann den Text im Speicher auszuwerten.

Wenn Sie nicht alle Dateien gleichzeitig verarbeiten können, dann tun Sie dies für die kleinsten Dateien.File I/O wird hier Ihre größten Kosten sein, so wollen Sie um das so weit wie möglich zu minimieren

Answer 4

Abhängig von ho Wenn Sie oft die Suche durchführen möchten, möchten Sie eine Suchmaschine verwenden oder nicht. Wenn Sie häufig suchen möchten, verwenden Sie eine Suchmaschine, andernfalls nicht. Ich werde beschreiben, wie Sie beide Szenarien hier implementieren.

Wenn Sie eine Suchmaschine verwenden: Es klingt wie Sie nach Teilstrings suchen, was bedeutet, dass Sie Ihre Dateien als solche mit Ihrer bevorzugten Suchmaschine indizieren sollten, vorzugsweise eine, die Sie anpassen können (Lucene, Terrier, etc.). Die Technik, die Sie hier brauchen, ist das Indizieren von Trigrammen, dh alle 3-stelligen Kombinationen müssen indiziert werden. ZB: 'foobar' erzeugt 'foo', 'oob', 'oba' und 'bar'. Bei der Suche möchten Sie dasselbe mit Ihrer Abfrage durchführen und eine Suchmaschinenkombination mit dem UND aller dieser Trigramme ausgeben. (Das führt einen Merge-Join auf den Buchungslisten aus den Dokumenten aus, die ihre IDs zurückgeben oder was auch immer Sie in die Buchungslisten setzen).

Alternativ können Sie Suffix-Arrays implementieren und Ihre Dateien einmal indizieren. Dies gibt ein wenig mehr Flexibilität, wenn Sie nach kurzen (1-2 Zeichen) Teilzeichenfolgen suchen, aber in Bezug auf Indizes ist es schwieriger zu verwalten. (Es gibt einige Forschung bei CWI/Amsterdam für schnelle Indizierung Suffix-Arrays)

Wenn Sie nur ein paar Mal suchen möchten, ist der Algorithmus entweder Boyer-Moore (ich benutze normalerweise Boyer-Moore-Sonntag wie in beschrieben) [Graham A. Stephen, Zeichenkettensuche]) oder ein kompiliertes DFA (Sie können sie aus einem NFA konstruieren, was einfacher zu machen ist). Dies führt jedoch nur zu einer kleinen Geschwindigkeitssteigerung, da Disk-IO wahrscheinlich der Flaschenhals ist und ein paar Bytes, die Sie sowieso dekodieren müssen, ziemlich schnell sind.

Die größte Verbesserung, die Sie machen können, ist das Lesen Ihrer Datei Zeile für Zeile, aber in Blöcken. Sie sollten NTFS so konfigurieren, dass Sie eine Blockgröße von 64 KB verwenden, wenn Sie können, und die Dateien in Multiplizierungen von 64 KB lesen - denken Sie an 4 MB oder mehr in einem einzelnen Lesevorgang. Ich würde sogar vorschlagen, asynchrone IO zu verwenden, so dass Sie gleichzeitig lesen und verarbeiten können (zuvor gelesene Daten). Wenn Sie es richtig machen, sollte Ihnen das bereits eine Implementierung in Sekundenbruchteilen für 10 MB auf der modernsten Hardware geben.

Last but not least, ist ein netter Trick beim Informationsabruf auch, Ihre Daten mit einem schnellen Komprimierungsalgorithmus zu komprimieren. Da Disk-IO langsamer als Speicher/CPU-Operationen ist, wird dies wahrscheinlich auch helfen. Der Snappy-Komprimierer von Google ist ein gutes Beispiel für einen schnellen Komprimierungsalgorithmus.

Answer 5

Sie können den Indexdienst von Microsoft verwenden, um nach Dokumenten in den Ordnern zu suchen, die Sie im Katalog hinzufügen würden. Here ist ein sehr schöner Artikel, mit dem Sie Ihre Textdateien durchsuchen können.