java - thread - jprogressbar color




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

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.

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.


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.


Hier gibt es drei gute Lösungen:

  1. Wenn Sie etwas benötigen, das einfach und relativ schnell ist, gehen Sie ohne Puffer aus und implementieren Sie stattdessen einen einfachen nicht deterministischen endlichen Automaten. Ihr Status wird eine Liste von Indizes in der Zeichenfolge sein, die Sie suchen, und Ihre Logik sieht in etwa so 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
    

    Dies wird die Zeichenfolge finden, wenn sie existiert, und Sie werden niemals einen Puffer benötigen.

  2. Etwas mehr Arbeit, aber auch schneller: Machen Sie eine NFA-zu-DFA-Konvertierung, die im Voraus herausfindet, welche Listen von Indizes möglich sind, und weisen Sie jeder eine kleine ganze Zahl zu. (Wenn Sie von der Zeichenkettensuche in Wikipedia lesen, wird dies die Powerset-Konstruktion genannt .) Dann haben Sie einen einzelnen Zustand und Sie machen einen Übergang von Zustand zu Zustand für jedes eingehende Zeichen. Das gewünschte NFA ist nur das DFA für die Zeichenfolge, der ein Zustand vorangestellt ist, der nichtdeterministisch entweder ein Zeichen löscht oder versucht, das aktuelle Zeichen zu konsumieren. Sie werden auch einen expliziten Fehlerstatus wünschen.

  3. Wenn Sie etwas schneller wollen, erstellen Sie einen Puffer, dessen Größe mindestens zweimal n , und Benutzer Boyer-Moore, um eine Zustandsmaschine von needle zu kompilieren. Sie werden eine Menge Ärger haben, weil Boyer-Moore nicht einfach zu implementieren ist (obwohl Sie Code online finden werden) und weil Sie dafür sorgen müssen, dass die Zeichenfolge durch den Puffer verschoben wird. Sie müssen einen Ringpuffer erstellen oder finden, der ohne Kopieren kopiert werden kann. Andernfalls werden Sie wahrscheinlich Leistungssteigerungen, die Sie von Boyer-Moore erhalten könnten, zurückgeben.


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).


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"));

    }
}

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

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.



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.


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.





stream