webentwicklung-frage-antwort-db.com.de

Effiziente Möglichkeit, einen Stream nach einer Zeichenfolge zu durchsuchen

Nehmen wir an, ich habe einen Textstrom (oder einen Reader in Java), den ich auf eine bestimmte Zeichenfolge überprüfen möchte. Der Textstrom kann sehr groß sein. Sobald der Suchtext gefunden wurde, möchte ich true zurückgeben und auch vermeiden, dass die gesamte Eingabe im Speicher gespeichert wird.

Naiv, ich könnte versuchen, so etwas (in Java) zu tun:

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Natürlich erkennt dies die angegebene Suchzeichenfolge nicht, wenn sie an der Grenze des 1k-Puffers auftritt:

Suchtext: "stackoverflow"
Stream Buffer 1: "abc ......... stack"
Stream Buffer 2: "Überlauf ....... xyz"

Wie kann ich diesen Code so ändern, dass er die angegebene Suchzeichenfolge über die Puffergrenze hinweg richtig findet, ohne den gesamten Stream in den Speicher zu laden?

Edit: Wenn Sie einen Stream nach einer Zeichenfolge durchsuchen, versuchen wir, die Anzahl der Lesevorgänge aus dem Stream zu minimieren (um Latenzen in einem Netzwerk/einer Festplatte zu vermeiden) und Halten Sie die Speicherverwendung konstant. unabhängig von der Datenmenge im Stream. Die tatsächliche Effizienz des String-Matching-Algorithmus ist zweitrangig, aber es wäre natürlich schön, eine Lösung zu finden, die einen der effizienteren Algorithmen verwendet.

48
Alex Spurling

Ich habe ein paar Änderungen am Knuth Morris Pratt-Algorithmus für die Teilsuche vorgenommen. Da die tatsächliche Vergleichsposition immer kleiner oder gleich der nächsten ist, ist kein zusätzlicher Speicher erforderlich. Der Code mit einem Makefile ist auch auf github verfügbar. Er ist in Haxe geschrieben, um auf mehrere Programmiersprachen gleichzeitig zu zielen, einschließlich Java.

Ich schrieb auch einen Artikel dazu: Suche nach Teilstrings in Streams: eine geringfügige Modifikation des Knuth-Morris-Pratt-Algorithmus in Haxe . Der Artikel erwähnt die Jakarta RegExp , die sich nun zurückgezogen hat und im Apache Attic ruht. Die Jakarta-Regexp-Bibliothek „ match “ in der RE-Klasse verwendet einen CharacterIterator als Parameter.

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}
9
sw.

Hier gibt es drei gute Lösungen:

  1. Wenn Sie etwas suchen, das einfach und schnell ist, gehen Sie ohne Puffer aus und implementieren Sie stattdessen eine einfache, nicht deterministische Maschine mit endlichem Status. Ihr Status ist eine Liste von Indizes in der Zeichenfolge, die Sie durchsuchen, und Ihre Logik sieht in etwa wie folgt aus (Pseudocode):

    String needle;
    n = needle.length();
    
    for every input character c do
      add index 0 to the list
      for every index i in the list do
        if c == needle[i] then
          if i + 1 == n then
            return true
          else
            replace i in the list with i + 1
          end
        else
          remove i from the list
        end
      end
    end
    

    Dadurch wird die Zeichenfolge gefunden, wenn sie vorhanden ist, und Sie benötigen niemals einen Puffer

  2. Etwas mehr Arbeit, aber auch schneller: Führen Sie eine NFA-zu-DFA-Konvertierung durch, die im Voraus ermittelt, welche Indexlisten möglich sind, und ordnen Sie jeder eine kleine Ganzzahl zu. (Wenn Sie über die Suche nach Zeichenfolgen in Wikipedia lesen, wird dies als powerset-Konstruktion bezeichnet.) Dann haben Sie einen einzelnen Zustand und führen bei jedem eingehenden Zeichen einen Übergang von Staat zu Staat durch. Der gewünschte NFA ist nur der DFA für die Zeichenfolge, der ein Zustand vorangestellt ist, in dem ein Zeichen nicht deterministisch abgelegt wird oder das aktuelle Zeichen verbraucht werden soll. Sie möchten auch einen expliziten Fehlerstatus.

  3. Wenn Sie etwas schnelleres wollen, erstellen Sie einen Puffer, dessen Größe mindestens zweimal n ist, und Benutzer Boyer-Moore, um aus needle eine Zustandsmaschine zu kompilieren. Sie haben viel zusätzlichen Aufwand, weil Boyer-Moore nicht einfach zu implementieren ist (obwohl Sie Code online finden) und weil Sie die Zeichenfolge durch den Puffer gleiten müssen. Sie müssen einen kreisförmigen Puffer erstellen oder finden, der ohne Kopieren "gleiten" kann. Andernfalls geben Sie wahrscheinlich alle von Boyer-Moore erzielten Leistungsgewinne zurück.

14
Norman Ramsey

Der Knuth-Morris-Pratt-Suchalgorithmus sichert niemals; Dies ist genau die Eigenschaft, die Sie für Ihre Stream-Suche wünschen. Ich habe es zuvor für dieses Problem verwendet, obwohl es möglicherweise einfachere Wege gibt, verfügbare Java-Bibliotheken zu verwenden. (Als dies für mich aufkam, arbeitete ich in den 90ern in C.)

KMP ist im Wesentlichen ein schneller Weg, um einen String-passenden DFA zu erstellen, wie Norman Ramseys Vorschlag # 2.

9
Darius Bacon

Diese Antwort wurde auf die ursprüngliche Version der Frage angewendet, bei der der Schlüssel den Stream nur so weit lesen musste, dass er mit einem String übereinstimmt, sofern dieser String vorhanden war. Diese Lösung erfüllt nicht die Anforderung, eine feste Speicherauslastung zu gewährleisten, kann jedoch eine Überlegung wert sein, wenn Sie diese Frage gefunden haben und nicht an diese Einschränkung gebunden sind.

Wenn Sie an die Einschränkung der konstanten Speichernutzung gebunden sind, speichert Java Arrays eines beliebigen Typs auf dem Heapspeicher. Durch die Nullung der Referenz wird der Speicher daher in keiner Weise freigegeben. Ich denke, dass jede Lösung, die Arrays in einer Schleife beinhaltet, Speicherplatz auf dem Heap verbraucht und GC erfordert. 


Für eine einfache Implementierung ist es vielleicht möglich, dass Java 5 Scanner einen InputStream akzeptiert und ein Java.util.regex.Pattern verwendet, um die Eingabe zu durchsuchen, wodurch Sie sich um die Implementierungsdetails kümmern müssen.

Hier ist ein Beispiel für eine mögliche Implementierung:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

Ich denke an Regex, weil es sich nach einem Job für einen Finite-State-Automaton anhört, etwas, das in einem Anfangszustand beginnt und den Status Zeichen für Zeichen ändert, bis entweder die Zeichenfolge abgelehnt wird (keine Übereinstimmung) oder ein akzeptabler Zustand erreicht wird.

Ich denke, dies ist wahrscheinlich die effizienteste Übereinstimmungslogik, die Sie verwenden könnten, und wie Sie das Lesen der Informationen organisieren, kann für die Leistungsoptimierung von der Übereinstimmungslogik getrennt werden.

Auf diese Weise funktionieren auch Regexen.

5
brabster

Anstelle, dass Ihr Puffer ein Array ist, verwenden Sie eine Abstraktion, die einen Ringpuffer implementiert. Ihre Indexberechnung lautet buf[(next+i) % sizeof(buf)], und Sie müssen darauf achten, den Puffer jeweils zur Hälfte zu füllen. Solange der Suchstring jedoch in die Hälfte des Puffers passt, werden Sie ihn finden. 

4
Norman Ramsey

Ich glaube, die beste Lösung für dieses Problem ist der Versuch, es einfach zu halten. Denken Sie daran, denn ich lese aus einem Stream. Ich möchte die Anzahl der Lesevorgänge aus dem Stream so gering wie möglich halten (da Netzwerk- oder Festplattenlatenz ein Problem sein kann), während die Menge des verwendeten Speichers konstant bleibt (wie der Stream dies kann) sehr groß in der Größe). Die tatsächliche Effizienz des String-Abgleichs ist nicht das Ziel Nummer eins (da dies bereits zu Tode studiert war.

Basierend auf AlbertoPLs Vorschlag, folgt hier eine einfache Lösung, die den Puffer zeichenweise mit dem Suchstring vergleicht. Der Schlüssel ist, dass, weil die Suche nur jeweils ein Zeichen ausführt, keine Rückverfolgung erforderlich ist und daher keine kreisförmigen Puffer oder Puffer einer bestimmten Größe erforderlich sind.

Wenn nun jemand mit einer ähnlichen Implementierung auf der Basis von Knuth-Morris-Pratt-Suchalgorithmus aufkommt, dann hätten wir eine effiziente Lösung von Nice;)

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}
4
Alex Spurling

In der RingBuffer-Klasse wird vom Ujorm-Framework aus sehr schnell ein Stream gesucht. Siehe das Muster:

 Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");

 String Word1 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("abc", Word1);

 String Word2 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("def", Word2);

 String Word3 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("", Word3);

Die Einzelklassenimplementierung ist unter SourceForge : .__ verfügbar. Weitere Informationen finden Sie unter link .

1
pop

Implementieren Sie ein Schiebefenster. Halten Sie Ihren Puffer bereit, verschieben Sie alle Elemente im Puffer um einen Schritt nach vorne und geben Sie am Ende ein einzelnes neues Zeichen in den Puffer ein. Wenn der Puffer Ihrem gesuchten Wort entspricht, ist es enthalten. 

Wenn Sie dies effizienter gestalten möchten, können Sie natürlich nach Möglichkeiten suchen, um das Verschieben aller Elemente im Puffer zu verhindern, z. B. durch einen zyklischen Puffer und eine Darstellung der Zeichenfolgen, die den Puffer auf dieselbe Weise "zyklisch" durchlaufen Wenn Sie dies tun, müssen Sie nur die Inhaltsgleichheit prüfen. Dies erspart das Verschieben aller Elemente im Puffer. 

1
Tetha

Ich denke, Sie müssen einen kleinen Betrag an der Grenze zwischen den Puffern puffern.

Wenn Ihre Puffergröße beispielsweise 1024 ist und die Länge des SearchString 10 beträgt, müssen Sie neben jedem 1024-Byte-Puffer auch jeden 18-Byte-Übergang zwischen zwei Puffern (9 Byte vom Ende des vorherigen Puffers) suchen verkettet mit 9 Bytes ab dem Start des nächsten Puffers).

1
ChrisW

Ich würde sagen, dass Sie zu einer Zeichen-für-Zeichen-Lösung wechseln. In diesem Fall würden Sie nach dem ersten Zeichen in Ihrem Zieltext suchen. Wenn Sie dieses Zeichen gefunden haben, erhöhen Sie einen Zähler und suchen nach dem nächsten Zeichen. Starten Sie den Zähler jedes Mal neu, wenn Sie den nächsten aufeinanderfolgenden Charakter nicht finden. Es würde so funktionieren:

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
    if (buffer[numCharsRead -1] == searchString.charAt(count))
        count++;
    else
        count = 0;

    if (count == searchString.size())    
     return true;
}
return false; 
}

Das einzige Problem ist, wenn Sie gerade durch die Charaktere blättern. In diesem Fall muss es eine Möglichkeit geben, sich an Ihre count-Variable zu erinnern. Ich sehe keinen einfachen Weg, außer als private Variable für die gesamte Klasse. In diesem Fall würden Sie die Zählung in dieser Methode nicht instanziieren.

1
AlbertoPL

Wenn Sie nicht an einen Reader gebunden sind, können Sie die NIO-API von Java verwenden, um die Datei effizient zu laden. Zum Beispiel (ungeprüft, sollte aber fast funktionieren):

public boolean streamContainsString(File input, String searchString) throws IOException {
    Pattern pattern = Pattern.compile(Pattern.quote(searchString));

    FileInputStream fis = new FileInputStream(input);
    FileChannel fc = fis.getChannel();

    int sz = (int) fc.size();
    MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);

    CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
    CharBuffer cb = decoder.decode(bb);

    Matcher matcher = pattern.matcher(cb);

    return matcher.matches();
}

Im Grunde ist dies die Datei, die gesucht werden muss, und das Betriebssystem hängt davon ab, was in Bezug auf Cache und Speicher richtig ist. Beachten Sie jedoch, dass map () das Lesen der Datei in einen großen Puffer für Dateien mit weniger als 10 KiB teurer ist.

1
deverton

Wenn Sie nach einem konstanten Teilstring anstatt nach einem Regex suchen, würde ich Boyer-Moore empfehlen. Es gibt eine Menge Quellcode im Internet.

Verwenden Sie außerdem einen Ringpuffer, um nicht zu stark über Puffergrenzen nachzudenken.

Mike.

0
Mike

Sie können die Suchgeschwindigkeit für sehr große Zeichenfolgen erhöhen, indem Sie einen Zeichenfolgen-Suchalgorithmus verwenden.

0
Alex

Ich hatte auch ein ähnliches Problem: Überspringe Bytes aus dem InputStream, bis der angegebene String (oder Byte-Array) angegeben ist. Dies ist der einfache Code, der auf dem Umlaufpuffer basiert. Es ist nicht sehr effizient, funktioniert aber für meine Bedürfnisse:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }
0
dmitriykovalev

Sie können möglicherweise eine sehr schnelle Lösung implementieren, indem Sie schnelle Fourier-Transformationen verwenden. Wenn dies ordnungsgemäß implementiert ist, können Sie den String-Abgleich in den Zeiten O (nlog (m)) durchführen, wobei n die Länge des zu vergleichenden längeren Strings ist und m ist die Länge der kürzeren Zeichenfolge. Sie können beispielsweise eine FFT durchführen, sobald Sie eine Stream-Eingabe der Länge m erhalten. Wenn sie übereinstimmt, können Sie zurückkehren. Wenn sie nicht passt, können Sie den ersten Buchstaben in der Stream-Eingabe wegwerfen. Warten Sie Damit ein neuer Buchstabe durch den Stream angezeigt wird, und führen Sie dann erneut die FFT durch. 

0
rboling