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




jprogressbar color (12)

Verwenden Sie eine Abstraktion, die einen Ringpuffer implementiert, anstatt dass Ihr Puffer ein Array ist. Ihre Indexberechnung wird buf[(next+i) % sizeof(buf)] , und Sie müssen vorsichtig sein, um den Puffer zur Hälfte zu buf[(next+i) % sizeof(buf)] . Aber solange der Suchstring in den halben Puffer passt, finden Sie ihn.

Angenommen, Sie haben einen Textfluss (oder Reader in Java), den ich nach einer bestimmten Zeichenfolge durchsuchen möchte. Der Textstream könnte sehr groß sein, also sobald der Suchstring gefunden wird, möchte ich True zurückgeben und auch versuchen, die gesamte Eingabe nicht im Speicher zu speichern.

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

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 kann die angegebene Suchzeichenfolge nicht gefunden werden, wenn sie an der Grenze des 1k-Puffers auftritt:

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

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

Bearbeiten: Hinweis : Wenn Sie einen Stream nach einer Zeichenfolge durchsuchen, versuchen wir , die Anzahl der Lesevorgänge aus dem Stream zu minimieren (um Latenz in einem Netzwerk / Datenträger zu vermeiden) und die Speichernutzung unabhängig von der Datenmenge im Stream konstant zu halten . Die tatsächliche Effizienz des String-Matching-Algorithmus ist sekundär, aber offensichtlich wäre es schön, eine Lösung zu finden, die einen der effizienteren dieser Algorithmen verwendet.


Implementieren Sie ein Schiebefenster. Lassen Sie Ihren Puffer herum, verschieben Sie alle Elemente im Puffer einen vorwärts und geben Sie ein einzelnes neues Zeichen in den Puffer am Ende ein. Wenn der Puffer dem gesuchten Wort entspricht, ist er enthalten.

Wenn Sie dies effizienter machen wollen, können Sie natürlich einen Weg finden, um zu verhindern, dass alle Elemente im Puffer verschoben werden, zum Beispiel durch einen zyklischen Puffer und eine Darstellung der Strings, die auf die gleiche Weise wie der Puffer "zyklisch" laufen tut, so müssen Sie nur auf Inhaltsgleichheit prüfen. Dies erspart das Verschieben aller Elemente im Puffer.


Wenn Sie nach einem konstanten Teilstring und nicht nach einem Regex suchen, würde ich Boyer-Moore empfehlen. Es gibt viel Quellcode im Internet.

Verwenden Sie auch einen Ringpuffer, um zu vermeiden, zu viel über Puffergrenzen nachzudenken.

Mike.


Ich denke, dass Sie eine kleine Menge an der Grenze zwischen Puffern puffern müssen.

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



Der Suchalgorithmus nach Knuth-Morris-Pratt wird niemals gesichert; Dies ist nur die Eigenschaft, die Sie für Ihre Stream-Suche benötigen. Ich habe es zuvor für dieses Problem verwendet, obwohl es möglicherweise leichtere Möglichkeiten gibt, verfügbare Java-Bibliotheken zu verwenden. (Als dies für mich aufkam, arbeitete ich in den 90er Jahren in C).

KMP ist im Wesentlichen eine schnelle Möglichkeit, ein String-passendes DFA zu erstellen, wie Norman Ramseys Vorschlag # 2.


Ich habe einige Änderungen am Knuth Morris Pratt-Algorithmus für Teilsuchen 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 und in Haxe geschrieben, um mehrere Programmiersprachen gleichzeitig zu erreichen, einschließlich Java.

Ich habe auch einen verwandten Artikel geschrieben: Suche nach Teilstrings in Streams: eine leichte Modifikation des Knuth-Morris-Pratt-Algorithmus in Haxe . Der Artikel erwähnt die Jakarta RegExp , die jetzt im Ruhestand ist und im Apache Attic ruht. Die "regexp library" match Methode 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"));

    }
}

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 (ungetestet, sollte aber in Arbeit sein):

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();
}

Dies ist im Grunde genommen die Datei mmap (), die zu durchsuchen ist, und hängt vom Betriebssystem ab, um das Richtige bezüglich der Cache- und Speichernutzung zu tun. Beachten Sie jedoch, dass map () teurer ist, wenn Sie die Datei nur für Dateien mit weniger als 10 KiB in einen großen Puffer einlesen.


Ich hatte auch ein ähnliches Problem: Überspringen von Bytes aus dem InputStream bis zur angegebenen Zeichenfolge (oder Byte-Array). Dies ist der einfache Code, der auf Ringpuffer basiert. Es ist nicht sehr effizient, aber funktioniert 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;
    }
  }

Diese Antwort wurde auf die erste Version der Frage angewendet, bei der der Schlüssel den Stream nur so weit lesen sollte, wie es für eine Übereinstimmung in einem String erforderlich ist, wenn dieser String vorhanden ist. Diese Lösung würde nicht die Anforderung erfüllen, eine feste Speichernutzung zu garantieren, aber es könnte eine Überlegung wert sein, wenn Sie diese Frage gefunden haben und nicht an diese Einschränkung gebunden sind.

Wenn Sie an die Konstante für die Speicherbelegung gebunden sind, speichert Java Arrays jedes Typs auf dem Heapspeicher. Daher hebt die Nullung der Referenz den Speicher in keiner Weise auf. Ich denke, jede Lösung mit Arrays in einer Schleife wird Speicher auf dem Heap verbrauchen und GC erfordern.

Für eine einfache Implementierung könnte der Java 5- Scanner der einen InputStream akzeptieren und ein java.util.regex.Pattern , um die Eingabe zu suchen, möglicherweise weniger über die Implementierungsdetails besorgt sein.

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 Regex, weil es sich wie ein Job für einen Finite-State-Automaten anhört, etwas, das in einem Anfangszustand beginnt und den Status Zeichen für Zeichen ändert, bis es entweder die Zeichenfolge (keine Übereinstimmung) ablehnt oder in einen akzeptierten Zustand übergeht.

Ich denke, dies ist wahrscheinlich die effizienteste Matching-Logik, die Sie verwenden könnten, und wie Sie das Lesen der Informationen organisieren, kann von der passenden Logik für Performance-Tuning getrennt werden.

Es ist auch, wie Regexes funktionieren.


Ich glaube, die beste Lösung für dieses Problem ist es, es einfach zu halten. Denken Sie daran, weil ich aus einem Stream lese, möchte ich die Anzahl der Lesevorgänge aus dem Stream auf ein Minimum beschränken (da Netzwerk- oder Festplattenlatenz ein Problem sein kann), während die verwendete Speichermenge konstant bleibt (so wie der Stream sein mag) sehr groß). Die tatsächliche Effizienz der String-Übereinstimmung ist nicht das Hauptziel (da dies bereits zu Tode untersucht wurde ).

Basierend auf dem Vorschlag von AlbertoPL gibt es hier eine einfache Lösung, die den Puffer Zeichen für Zeichen mit dem Suchstring vergleicht. Der Schlüssel besteht darin, dass, da die Suche nur jeweils ein Zeichen durchgeführt wird, keine Rückverfolgung erforderlich ist und daher keine Ringpuffer oder Puffer einer bestimmten Größe benötigt werden.

Nun, wenn jemand eine ähnliche Implementierung basierend auf dem Knuth-Morris-Pratt Suchalgorithmus entwickeln könnte, hätten wir eine schöne, effiziente Lösung;)

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;
}

Sie können möglicherweise eine sehr schnelle Lösung mit Fast Fourier Transformationen implementieren, die, wenn sie richtig implementiert sind, Ihnen erlauben, Zeichenfolgenabgleich in Zeiten O (nlog (m)) durchzuführen, wobei n die Länge der längeren zu vergleichenden Zeichenfolge ist. und m ist die Länge der kürzeren Saite. Sie könnten zum Beispiel FFT ausführen, sobald Sie eine Stream-Eingabe der Länge m erhalten, und wenn es übereinstimmt, können Sie zurückkehren, und wenn es nicht übereinstimmt, können Sie das erste Zeichen in der Stream-Eingabe wegwerfen, warten Damit ein neues Zeichen im Stream angezeigt wird, führen Sie die FFT erneut aus.





stream