Suche nach Byte []

Question

Die Suche nach einem String innerhalb eines Strings wird in .NET sehr gut unterstützt, aber was tun Sie, wenn die zu suchenden Daten keine Zeichenfolge sind?

Ich habe binäre Daten, die über einen NetworkStream in regelmäßigen Chunks ankommen. Pakete sind binär, aber sie beginnen alle mit einer Signaturfolge von Bytes. Ich akkumuliere die Chunks in einen größeren Puffer und suche nach der Signatur des Startpakets.

Was ich wirklich suche ist die byte[] entspricht der String.IndexOf(ss) Methode. Ich habe das unangenehme Gefühl, dass ich das selbst mit einer Schleife und einer Zustandsmaschine implementieren muss.

Irgendwelche Vorschläge? Zu dir hinüber!

---

Wie vorgeschlagen, Array.IndexOf (Byte) wird mir zumindest eine explizite Schleife speichern. Seit der Veröffentlichung kam ich auf die Idee, das erste Signaturbyte zu finden und dann nach einer Übereinstimmung zu suchen, bei der das letzte Signaturbyte sein sollte. Wenn beide übereinstimmen, versuchen Sie einen Brute-Force-Vergleich für den Rest der Zeichenkette. Dieser Ansatz hat den Vorteil, falsche Übereinstimmungen billig abzulehnen und es mir zu erlauben, billig zurückzuweisen, wenn eine Teilsignatur einen anderen Teil ansteht.

Google enthüllt, dass der obige brillante Plan ein entarteter Fall von "KMP" oder Knuth-Morris-Pratt-Algorithmus ist. Auf der hellen Seite, wenn Knuth seinen Namen darauf geschrieben hat, ist es wahrscheinlich gefettete Blitze, auf der Unterseite warum hat Donald Knuth, wenn ich eine gute Idee habe, vor 25 Jahren daran gedacht?

Da ich die Punkte nicht an Donald Knuth vergeben kann, schätze ich, dass sie nach Nelson gehen.

Answer 1

Sie können Array.IndexOf verwenden, um ein einzelnes Byte zu finden.

Allerdings würde ich Sie davor warnen, dass einige gültige Daten versehentlich Ihre Unterschrift sein könnten und Ihre Anwendung vollständig abwerfen. Eine bessere Lösung wäre meiner Meinung nach, immer eine 4-Byte-Ganzzahl zu senden, die die Größe des Pakets enthält. Dann lese so viele Bytes ein, um den Puffer dieses Pakets zu löschen.

Wenn Sie TCP verwenden es völlig akzeptabel ist, eine Client-off zu treten, wenn sie über Paketgröße liegen oder eine dumme Menge an Speicher anfordern :)

Answer 2

Können Sie nicht verwaltete/unsicheren Code verwenden? Wenn dem so ist, würde ich wahrscheinlich vorschlagen, die Zeigerarithmetik zu verwenden, um Ihr Byte-Array zu durchsuchen. So sind Strings effektiv. Sie können ähnliches tun.

eine andere Lösung könnte sein, ein Wörterbuch zu verwenden, um Ihre Paketdaten zu speichern. Lassen Sie den Schlüssel Ihre Unterschrift sein. Dann ist es ziemlich schnell und einfach, es zu finden. Mehrere Möglichkeiten, um das Byte als ein Schlüssel, wie base64string, eine simepl Wrapper zu haben (Verwendung KeyedCollection wenn Sie dies tun) usw.

Answer 3

die schnellsten Algorithmen für Muster in Byte-Arrays und Strings zu finden, die ich verwendet habe, sind Boyer-Moore und einfach Boyer-Moore (nützlich, wenn sich das Muster wesentlich vom gesuchten Text unterscheidet). Damit habe ich einen schnellen Mime-Parser in Java implementiert. Die code könnte leicht zu .Net portiert werden (die Lizenz ist LGPL).