Darf ich etwas vorschlagen, bei dem keine Zeichenfolgen erstellt, Arrays kopiert oder unsicherer Code verwendet wird:
using System;
using System.Collections.Generic;
static class ByteArrayRocks
{
static readonly int[] Empty = new int[0];
public static int[] Locate (this byte[] self, byte[] candidate)
{
if (IsEmptyLocate(self, candidate))
return Empty;
var list = new List<int>();
for (int i = 0; i < self.Length; i++)
{
if (!IsMatch(self, i, candidate))
continue;
list.Add(i);
}
return list.Count == 0 ? Empty : list.ToArray();
}
static bool IsMatch (byte[] array, int position, byte[] candidate)
{
if (candidate.Length > (array.Length - position))
return false;
for (int i = 0; i < candidate.Length; i++)
if (array[position + i] != candidate[i])
return false;
return true;
}
static bool IsEmptyLocate (byte[] array, byte[] candidate)
{
return array == null
|| candidate == null
|| array.Length == 0
|| candidate.Length == 0
|| candidate.Length > array.Length;
}
static void Main()
{
var data = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
var pattern = new byte[] { 12, 3, 5, 76, 8, 0, 6, 125 };
foreach (var position in data.Locate(pattern))
Console.WriteLine(position);
}
}
Edit (von iAbstract) - Inhalt des Bewegens Post hier , da es nicht eine Antwort
Aus Neugier habe ich einen kleinen Benchmark mit unterschiedlichen Antworten erstellt.
Hier sind die Ergebnisse für eine Million Iterationen:
solution [Locate]: 00:00:00.7714027
solution [FindAll]: 00:00:03.5404399
solution [SearchBytePattern]: 00:00:01.1105190
solution [MatchBytePattern]: 00:00:03.0658212
Verwenden Sie LINQ-Methoden.
public static IEnumerable<int> PatternAt(byte[] source, byte[] pattern) { for (int i = 0; i < source.Length; i++) { if (source.Skip(i).Take(pattern.Length).SequenceEqual(pattern)) { yield return i; } } }Sehr einfach!
quelle
Verwenden Sie den effizienten Boyer-Moore-Algorithmus .
Es wurde entwickelt, um Zeichenfolgen mit Zeichenfolgen zu finden, aber Sie benötigen wenig Vorstellungskraft, um diese auf Byte-Arrays zu projizieren.
Im Allgemeinen lautet die beste Antwort: Verwenden Sie einen beliebigen Algorithmus für die Zeichenfolgensuche :).
quelle
Ursprünglich habe ich einen alten Code gepostet, den ich verwendet habe, war aber neugierig auf die Benchmarks von Jb Evain . Ich fand, dass meine Lösung langsam dumm war. Es scheint , dass Brüno Condes SearchBytePattern die schnellste ist. Ich konnte mir nicht vorstellen warum, zumal er eine Array.Copy- und eine Extension-Methode verwendet. Aber es gibt Beweise in Jbs Tests, also ein großes Lob an Bruno.
Ich habe die Bits noch weiter vereinfacht, also ist dies hoffentlich die klarste und einfachste Lösung. (All die harte Arbeit von bruno conde) Die Verbesserungen sind:
in Erweiterungsmethode konvertiert
public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex) { List<int> positions = new List<int>(); int i = Array.IndexOf<byte>(buffer, pattern[0], startIndex); while (i >= 0 && i <= buffer.Length - pattern.Length) { byte[] segment = new byte[pattern.Length]; Buffer.BlockCopy(buffer, i, segment, 0, pattern.Length); if (segment.SequenceEqual<byte>(pattern)) positions.Add(i); i = Array.IndexOf<byte>(buffer, pattern[0], i + 1); } return positions; }Beachten Sie, dass die letzte Anweisung im
whileBlocki = Array.IndexOf<byte>(buffer, pattern[0], i + 1);anstelle von sein solltei = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length);. Schauen Sie sich den Kommentar von Johan an. Ein einfacher Test könnte beweisen, dass:byte[] pattern = new byte[] {1, 2}; byte[] toBeSearched = new byte[] { 1, 1, 2, 1, 12 };Mit
i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length);kehrte nichts zurück.i = Array.IndexOf<byte>(buffer, pattern[0], i + 1);gibt das richtige Ergebnis zurück.quelle
Dies ist mein Vorschlag, einfacher und schneller:
int Search(byte[] src, byte[] pattern) { int c = src.Length - pattern.Length + 1; int j; for (int i = 0; i < c; i++) { if (src[i] != pattern[0]) continue; for (j = pattern.Length - 1; j >= 1 && src[i + j] == pattern[j]; j--) ; if (j == 0) return i; } return -1; }quelle
Meine Lösung:
class Program { public static void Main() { byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; byte[] toBeSearched = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125}; List<int> positions = SearchBytePattern(pattern, toBeSearched); foreach (var item in positions) { Console.WriteLine("Pattern matched at pos {0}", item); } } static public List<int> SearchBytePattern(byte[] pattern, byte[] bytes) { List<int> positions = new List<int>(); int patternLength = pattern.Length; int totalLength = bytes.Length; byte firstMatchByte = pattern[0]; for (int i = 0; i < totalLength; i++) { if (firstMatchByte == bytes[i] && totalLength - i >= patternLength) { byte[] match = new byte[patternLength]; Array.Copy(bytes, i, match, 0, patternLength); if (match.SequenceEqual<byte>(pattern)) { positions.Add(i); i += patternLength - 1; } } } return positions; } }quelle
Mir fehlte eine LINQ-Methode / Antwort :-)
/// <summary> /// Searches in the haystack array for the given needle using the default equality operator and returns the index at which the needle starts. /// </summary> /// <typeparam name="T">Type of the arrays.</typeparam> /// <param name="haystack">Sequence to operate on.</param> /// <param name="needle">Sequence to search for.</param> /// <returns>Index of the needle within the haystack or -1 if the needle isn't contained.</returns> public static IEnumerable<int> IndexOf<T>(this T[] haystack, T[] needle) { if ((needle != null) && (haystack.Length >= needle.Length)) { for (int l = 0; l < haystack.Length - needle.Length + 1; l++) { if (!needle.Where((data, index) => !haystack[l + index].Equals(data)).Any()) { yield return l; } } } }quelle
Meine Version von Foubars Antwort oben, die es vermeidet, über das Ende des Heuhaufens hinaus zu suchen, und die Angabe eines Startversatzes ermöglicht. Angenommen, die Nadel ist nicht leer oder länger als der Heuhaufen.
public static unsafe long IndexOf(this byte[] haystack, byte[] needle, long startOffset = 0) { fixed (byte* h = haystack) fixed (byte* n = needle) { for (byte* hNext = h + startOffset, hEnd = h + haystack.LongLength + 1 - needle.LongLength, nEnd = n + needle.LongLength; hNext < hEnd; hNext++) for (byte* hInc = hNext, nInc = n; *nInc == *hInc; hInc++) if (++nInc == nEnd) return hNext - h; return -1; } }quelle
Wenn Sie .NET Core 2.1 oder höher (oder eine .NET Standard 2.1 oder höher-Plattform) verwenden, können Sie die
MemoryExtensions.IndexOfErweiterungsmethode mit dem neuenSpanTyp verwenden :int matchIndex = toBeSearched.AsSpan().IndexOf(pattern);Um alle Vorkommen zu finden, können Sie Folgendes verwenden:
public static IEnumerable<int> IndexesOf(this byte[] haystack, byte[] needle, int startIndex = 0, bool includeOverlapping = false) { int matchIndex = haystack.AsSpan(startIndex).IndexOf(needle); while (matchIndex >= 0) { yield return startIndex + matchIndex; startIndex += matchIndex + (includeOverlapping ? 1 : needle.Length); matchIndex = haystack.AsSpan(startIndex).IndexOf(needle); } }Leider verwendet die Implementierung in .NET Core 2.1 - 3.0 einen iterierten Ansatz "Optimierte Einzelbyte-Suche im ersten Byte, dann Rest prüfen" anstelle eines schnellen String-Suchalgorithmus. Dies könnte sich jedoch in einer zukünftigen Version ändern.
quelle
Jb Evains Antwort lautet:
for (int i = 0; i < self.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); }und dann prüft die IsMatch-Funktion zuerst, ob
candidatedie Länge des durchsuchten Arrays überschritten wird.Dies wäre effizienter, wenn die
forSchleife codiert würde:for (int i = 0, n = self.Length - candidate.Length + 1; i < n; ++i) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); }Zu diesem Zeitpunkt könnte man den Test auch von Anfang an eliminieren
IsMatch, solange man sich über Vorbedingungen zusammenschließt, um ihn niemals mit "illegalen" Parametern aufzurufen. Hinweis: Ein Fehler wurde 2019 behoben.quelle
Dies sind die einfachsten und schnellsten Methoden, die Sie verwenden können, und es gibt nichts Schnelleres als diese. Es ist unsicher, aber dafür verwenden wir Zeiger für die Geschwindigkeit. Hier biete ich Ihnen meine Erweiterungsmethoden an, mit denen ich nach einer einzelnen suche, und eine Liste von Indizes der Vorkommen. Ich möchte sagen, dass dies hier der sauberste Code ist.
public static unsafe long IndexOf(this byte[] Haystack, byte[] Needle) { fixed (byte* H = Haystack) fixed (byte* N = Needle) { long i = 0; for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++) { bool Found = true; for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ; if (Found) return i; } return -1; } } public static unsafe List<long> IndexesOf(this byte[] Haystack, byte[] Needle) { List<long> Indexes = new List<long>(); fixed (byte* H = Haystack) fixed (byte* N = Needle) { long i = 0; for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++) { bool Found = true; for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ; if (Found) Indexes.Add(i); } return Indexes; } }Mit Locate verglichen, ist es 1,2-1,4x schneller
quelle
Hier ist meine (nicht die performanteste) Lösung. Es beruht auf der Tatsache, dass die Bytes / Latin-1-Konvertierung verlustfrei ist, was für Bytes / ASCII- oder Bytes / UTF8-Konvertierungen nicht gilt.
Die Vorteile sind, dass It Works (tm) für alle Bytewerte funktioniert (einige andere Lösungen funktionieren nicht korrekt mit den Bytes 0x80-0xff) und erweitert werden kann, um eine erweiterte Regex-Anpassung durchzuführen.
using System; using System.Collections.Generic; using System.Text; using System.Text.RegularExpressions; class C { public static void Main() { byte[] data = {0, 100, 0, 255, 100, 0, 100, 0, 255}; byte[] pattern = {0, 255}; foreach (int i in FindAll(data, pattern)) { Console.WriteLine(i); } } public static IEnumerable<int> FindAll( byte[] haystack, byte[] needle ) { // bytes <-> latin-1 conversion is lossless Encoding latin1 = Encoding.GetEncoding("iso-8859-1"); string sHaystack = latin1.GetString(haystack); string sNeedle = latin1.GetString(needle); for (Match m = Regex.Match(sHaystack, Regex.Escape(sNeedle)); m.Success; m = m.NextMatch()) { yield return m.Index; } } }quelle
Ich habe eine neue Funktion mit den Tipps aus meiner Antwort und der Antwort von Alnitak erstellt.
public static List<Int32> LocateSubset(Byte[] superSet, Byte[] subSet) { if ((superSet == null) || (subSet == null)) { throw new ArgumentNullException(); } if ((superSet.Length < subSet.Length) || (superSet.Length == 0) || (subSet.Length == 0)) { return new List<Int32>(); } var result = new List<Int32>(); Int32 currentIndex = 0; Int32 maxIndex = superSet.Length - subSet.Length; while (currentIndex < maxIndex) { Int32 matchCount = CountMatches(superSet, currentIndex, subSet); if (matchCount == subSet.Length) { result.Add(currentIndex); } currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; } } return result; } private static Int32 CountMatches(Byte[] superSet, int startIndex, Byte[] subSet) { Int32 currentOffset = 0; while (currentOffset < subSet.Length) { if (superSet[startIndex + currentOffset] != subSet[currentOffset]) { break; } currentOffset++; } return currentOffset; }Der einzige Teil, über den ich nicht so glücklich bin, ist der
currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; }Teil ... Ich hätte gerne ein if else verwendet, um das -1 zu vermeiden, aber dies führt zu einer besseren Verzweigungsvorhersage (obwohl ich nicht sicher bin, ob es so wichtig ist).
quelle
Warum das Einfache schwierig machen? Dies kann in jeder Sprache mit for-Schleifen erfolgen. Hier ist eine in C #:
using System; using System.Collections.Generic; Namespace BinarySearch { Klassenprogramm { statische Leere Main (string [] args) { Byte [] Muster = neues Byte [] {12,3,5,76,8,0,6,125}; Byte [] toBeSearched = neues Byte [] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76, 64,12,3,5,76,8,0,6,125}; List <int> occences = findOccurences (toBeSearched, pattern); foreach (int Vorkommen in Vorkommen) { Console.WriteLine ("Übereinstimmung gefunden ab 0-basiertem Index:" + Vorkommen); }} }} statische Liste <int> findOccurences (Byte [] Heuhaufen, Byte [] Nadel) { List <int> Vorkommen = new List <int> (); für (int i = 0; i <haystack.Length; i ++) { if (Nadel [0] == Heuhaufen [i]) { bool found = true; int j, k; für (j = 0, k = i; j <Nadellänge; j ++, k ++) { if (k> = Heuhaufen.Länge || Nadel [j]! = Heuhaufen [k]) { gefunden = falsch; brechen; }} }} wenn gefunden) { Vorkommen.Add (i - 1); i = k; }} }} }} Vorkommen zurückgeben; }} }} }}
quelle
O(needle.Length * haystack.Length), ein optimierter Algorithmus hat LaufzeitO(needle.Length + haystack.Length).Danke, dass du dir die Zeit genommen hast ...
Dies ist der Code, den ich verwendet / getestet habe, bevor ich meine Frage gestellt habe ... Der Grund, warum ich diese Frage gestellt habe, war, dass ich sicher bin, dass ich nicht den optimalen Code verwende, um dies zu tun ... also nochmals vielen Dank dafür, dass du dir die Zeit genommen hast!
private static int CountPatternMatches(byte[] pattern, byte[] bytes) { int counter = 0; for (int i = 0; i < bytes.Length; i++) { if (bytes[i] == pattern[0] && (i + pattern.Length) < bytes.Length) { for (int x = 1; x < pattern.Length; x++) { if (pattern[x] != bytes[x+i]) { break; } if (x == pattern.Length -1) { counter++; i = i + pattern.Length; } } } } return counter; }Hat jemand Fehler in meinem Code gesehen? Wird dies als hackiger Ansatz angesehen? Ich habe fast jede Probe ausprobiert, die ihr gepostet habt, und ich scheine einige Variationen in den Spielergebnissen zu bekommen. Ich habe meine Tests mit einem ~ 10-MB-Byte-Array als toBeSearched-Array ausgeführt.
quelle
Ich würde eine Lösung verwenden, die Matching durch Konvertieren in einen String ausführt ...
Sie sollten eine einfache Funktion schreiben, die den Knuth-Morris-Pratt-Suchalgorithmus implementiert . Dies ist der schnellste einfache Algorithmus, mit dem Sie die richtigen Indizes finden können. (Sie könnten Boyer-Moore verwenden , erfordern jedoch mehr Einstellungen.
Nachdem Sie den Algorithmus optimiert haben, können Sie versuchen, nach anderen Optimierungen zu suchen. Aber Sie sollten mit den Grundlagen beginnen.
Das derzeit "schnellste" ist beispielsweise die Locate-Lösung von Jb Evian.
wenn Sie sich den Kern ansehen
for (int i = 0; i < self.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); }Nach einer Übereinstimmung des Subalgorithmus wird bei i + 1 eine Übereinstimmung gefunden, aber Sie wissen bereits, dass die erste mögliche Übereinstimmung i + Kandidat ist. Länge. Also, wenn Sie hinzufügen,
i += candidate.Length -2; // -2 instead of -1 because the i++ will add the last indexEs wird viel schneller sein, wenn Sie viele Vorkommen der Teilmenge in der Obermenge erwarten. (Bruno Conde macht das schon in seiner Lösung)
Dies ist jedoch nur die Hälfte des KNP-Algorithmus. Sie sollten der IsMatch-Methode namens numberOfValidMatches auch einen zusätzlichen Parameter hinzufügen, der ein out-Parameter wäre.
Dies würde sich wie folgt auflösen:
int validMatches = 0; if (!IsMatch (self, i, candidate, out validMatches)) { i += validMatches - 1; // -1 because the i++ will do the last one continue; }und
static bool IsMatch (byte [] array, int position, byte [] candidate, out int numberOfValidMatches) { numberOfValidMatches = 0; if (candidate.Length > (array.Length - position)) return false; for (i = 0; i < candidate.Length; i++) { if (array [position + i] != candidate [i]) return false; numberOfValidMatches++; } return true; }Ein wenig Refactoring und Sie könnten die numberOfValidMatches als Schleifenvariable verwenden und die Locate-Schleife mit einer Weile neu schreiben, um die -2 und -1 zu vermeiden. Aber ich wollte nur klarstellen, wie Sie den KMP-Algorithmus hinzufügen können.
quelle
Geschwindigkeit ist nicht alles. Haben Sie sie auf Konsistenz überprüft?
Ich habe nicht den gesamten hier aufgeführten Code getestet. Ich habe meinen eigenen Code (der zugegebenermaßen nicht vollständig konsistent war) und IndexOfSequence getestet. Ich stellte fest, dass IndexOfSequence für viele Tests viel schneller war als mein Code, aber bei wiederholten Tests stellte ich fest, dass es weniger konsistent war. Insbesondere scheint es am schwierigsten zu sein, Muster am Ende des Arrays zu finden, aber manchmal werden sie auch in der Mitte des Arrays übersehen.
Mein Testcode ist nicht auf Effizienz ausgelegt, ich wollte nur eine Reihe zufälliger Daten mit einigen bekannten Zeichenfolgen enthalten. Dieses Testmuster ähnelt in etwa einer Grenzmarkierung in einem Upload-Stream für http-Formulare. Das war es, wonach ich gesucht habe, als ich auf diesen Code gestoßen bin, also dachte ich mir, ich würde ihn mit den Daten testen, nach denen ich suchen werde. Je länger das Muster ist, desto häufiger verfehlt IndexOfSequence einen Wert.
private static void TestMethod() { Random rnd = new Random(DateTime.Now.Millisecond); string Pattern = "-------------------------------65498495198498"; byte[] pattern = Encoding.ASCII.GetBytes(Pattern); byte[] testBytes; int count = 3; for (int i = 0; i < 100; i++) { StringBuilder TestString = new StringBuilder(2500); TestString.Append(Pattern); byte[] buf = new byte[1000]; rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); testBytes = Encoding.ASCII.GetBytes(TestString.ToString()); List<int> idx = IndexOfSequence(ref testBytes, pattern, 0); if (idx.Count != count) { Console.Write("change from {0} to {1} on iteration {2}: ", count, idx.Count, i); foreach (int ix in idx) { Console.Write("{0}, ", ix); } Console.WriteLine(); count = idx.Count; } } Console.WriteLine("Press ENTER to exit"); Console.ReadLine(); }(Offensichtlich habe ich IndexOfSequence von einer Erweiterung wieder in eine normale Methode für diesen Test konvertiert.)
Hier ist ein Beispiellauf meiner Ausgabe:
change from 3 to 2 on iteration 1: 0, 2090, change from 2 to 3 on iteration 2: 0, 1045, 2090, change from 3 to 2 on iteration 3: 0, 1045, change from 2 to 3 on iteration 4: 0, 1045, 2090, change from 3 to 2 on iteration 6: 0, 2090, change from 2 to 3 on iteration 7: 0, 1045, 2090, change from 3 to 2 on iteration 11: 0, 2090, change from 2 to 3 on iteration 12: 0, 1045, 2090, change from 3 to 2 on iteration 14: 0, 2090, change from 2 to 3 on iteration 16: 0, 1045, 2090, change from 3 to 2 on iteration 17: 0, 1045, change from 2 to 3 on iteration 18: 0, 1045, 2090, change from 3 to 1 on iteration 20: 0, change from 1 to 3 on iteration 21: 0, 1045, 2090, change from 3 to 2 on iteration 22: 0, 2090, change from 2 to 3 on iteration 23: 0, 1045, 2090, change from 3 to 2 on iteration 24: 0, 2090, change from 2 to 3 on iteration 25: 0, 1045, 2090, change from 3 to 2 on iteration 26: 0, 2090, change from 2 to 3 on iteration 27: 0, 1045, 2090, change from 3 to 2 on iteration 43: 0, 1045, change from 2 to 3 on iteration 44: 0, 1045, 2090, change from 3 to 2 on iteration 48: 0, 1045, change from 2 to 3 on iteration 49: 0, 1045, 2090, change from 3 to 2 on iteration 50: 0, 2090, change from 2 to 3 on iteration 52: 0, 1045, 2090, change from 3 to 2 on iteration 54: 0, 1045, change from 2 to 3 on iteration 57: 0, 1045, 2090, change from 3 to 2 on iteration 62: 0, 1045, change from 2 to 3 on iteration 63: 0, 1045, 2090, change from 3 to 2 on iteration 72: 0, 2090, change from 2 to 3 on iteration 73: 0, 1045, 2090, change from 3 to 2 on iteration 75: 0, 2090, change from 2 to 3 on iteration 76: 0, 1045, 2090, change from 3 to 2 on iteration 78: 0, 1045, change from 2 to 3 on iteration 79: 0, 1045, 2090, change from 3 to 2 on iteration 81: 0, 2090, change from 2 to 3 on iteration 82: 0, 1045, 2090, change from 3 to 2 on iteration 85: 0, 2090, change from 2 to 3 on iteration 86: 0, 1045, 2090, change from 3 to 2 on iteration 89: 0, 2090, change from 2 to 3 on iteration 90: 0, 1045, 2090, change from 3 to 2 on iteration 91: 0, 2090, change from 2 to 1 on iteration 92: 0, change from 1 to 3 on iteration 93: 0, 1045, 2090, change from 3 to 1 on iteration 99: 0,Ich möchte mich nicht für IndexOfSequence entscheiden, es war einfach das, mit dem ich heute angefangen habe zu arbeiten. Am Ende des Tages bemerkte ich, dass Muster in den Daten fehlten, also schrieb ich heute Abend meinen eigenen Mustervergleicher. Es ist allerdings nicht so schnell. Ich werde es ein bisschen weiter optimieren, um zu sehen, ob ich es 100% konsistent machen kann, bevor ich es poste.
Ich wollte nur alle daran erinnern, dass sie solche Dinge testen sollten, um sicherzustellen, dass sie gute, wiederholbare Ergebnisse liefern, bevor Sie ihnen im Produktionscode vertrauen.
quelle
Ich habe verschiedene Lösungen ausprobiert und am Ende das SearchBytePattern geändert. Ich habe auf einer 30k Sequenz getestet und es ist schnell :)
static public int SearchBytePattern(byte[] pattern, byte[] bytes) { int matches = 0; for (int i = 0; i < bytes.Length; i++) { if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length) { bool ismatch = true; for (int j = 1; j < pattern.Length && ismatch == true; j++) { if (bytes[i + j] != pattern[j]) ismatch = false; } if (ismatch) { matches++; i += pattern.Length - 1; } } } return matches; }Lass mich wissen was du denkst.
quelle
Hier ist eine Lösung, die ich gefunden habe. Ich habe Notizen beigefügt, die ich auf dem Weg zur Implementierung gefunden habe. Es kann vorwärts, rückwärts und mit unterschiedlichen (in / dec) Remementbeträgen übereinstimmen, z. B. Richtung; beginnend mit einem beliebigen Versatz im Heuhaufen.
Jede Eingabe wäre fantastisch!
/// <summary> /// Matches a byte array to another byte array /// forwards or reverse /// </summary> /// <param name="a">byte array</param> /// <param name="offset">start offset</param> /// <param name="len">max length</param> /// <param name="b">byte array</param> /// <param name="direction">to move each iteration</param> /// <returns>true if all bytes match, otherwise false</returns> internal static bool Matches(ref byte[] a, int offset, int len, ref byte[] b, int direction = 1) { #region Only Matched from offset Within a and b, could not differ, e.g. if you wanted to mach in reverse for only part of a in some of b that would not work //if (direction == 0) throw new ArgumentException("direction"); //for (; offset < len; offset += direction) if (a[offset] != b[offset]) return false; //return true; #endregion //Will match if b contains len of a and return a a index of positive value return IndexOfBytes(ref a, ref offset, len, ref b, len) != -1; } ///Here is the Implementation code /// <summary> /// Swaps two integers without using a temporary variable /// </summary> /// <param name="a"></param> /// <param name="b"></param> internal static void Swap(ref int a, ref int b) { a ^= b; b ^= a; a ^= b; } /// <summary> /// Swaps two bytes without using a temporary variable /// </summary> /// <param name="a"></param> /// <param name="b"></param> internal static void Swap(ref byte a, ref byte b) { a ^= b; b ^= a; a ^= b; } /// <summary> /// Can be used to find if a array starts, ends spot Matches or compltely contains a sub byte array /// Set checkLength to the amount of bytes from the needle you want to match, start at 0 for forward searches start at hayStack.Lenght -1 for reverse matches /// </summary> /// <param name="a">Needle</param> /// <param name="offset">Start in Haystack</param> /// <param name="len">Length of required match</param> /// <param name="b">Haystack</param> /// <param name="direction">Which way to move the iterator</param> /// <returns>Index if found, otherwise -1</returns> internal static int IndexOfBytes(ref byte[] needle, ref int offset, int checkLength, ref byte[] haystack, int direction = 1) { //If the direction is == 0 we would spin forever making no progress if (direction == 0) throw new ArgumentException("direction"); //Cache the length of the needle and the haystack, setup the endIndex for a reverse search int needleLength = needle.Length, haystackLength = haystack.Length, endIndex = 0, workingOffset = offset; //Allocate a value for the endIndex and workingOffset //If we are going forward then the bound is the haystackLength if (direction >= 1) endIndex = haystackLength; #region [Optomization - Not Required] //{ //I though this was required for partial matching but it seems it is not needed in this form //workingOffset = needleLength - checkLength; //} #endregion else Swap(ref workingOffset, ref endIndex); #region [Optomization - Not Required] //{ //Otherwise we are going in reverse and the endIndex is the needleLength - checkLength //I though the length had to be adjusted but it seems it is not needed in this form //endIndex = needleLength - checkLength; //} #endregion #region [Optomized to above] //Allocate a value for the endIndex //endIndex = direction >= 1 ? haystackLength : needleLength - checkLength, //Determine the workingOffset //workingOffset = offset > needleLength ? offset : needleLength; //If we are doing in reverse swap the two //if (workingOffset > endIndex) Swap(ref workingOffset, ref endIndex); //Else we are going in forward direction do the offset is adjusted by the length of the check //else workingOffset -= checkLength; //Start at the checkIndex (workingOffset) every search attempt #endregion //Save the checkIndex (used after the for loop is done with it to determine if the match was checkLength long) int checkIndex = workingOffset; #region [For Loop Version] ///Optomized with while (single op) ///for (int checkIndex = workingOffset; checkIndex < endIndex; offset += direction, checkIndex = workingOffset) ///{ ///Start at the checkIndex /// While the checkIndex < checkLength move forward /// If NOT (the needle at the checkIndex matched the haystack at the offset + checkIndex) BREAK ELSE we have a match continue the search /// for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; /// If the match was the length of the check /// if (checkIndex == checkLength) return offset; //We are done matching ///} #endregion //While the checkIndex < endIndex while (checkIndex < endIndex) { for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; //If the match was the length of the check if (checkIndex == checkLength) return offset; //We are done matching //Move the offset by the direction, reset the checkIndex to the workingOffset offset += direction; checkIndex = workingOffset; } //We did not have a match with the given options return -1; }quelle
Ich bin etwas spät zur Party. Wie wäre es mit dem Boyer Moore-Algorithmus, aber der Suche nach Bytes anstelle von Strings. c # Code unten.
EyeCode Inc.
class Program { static void Main(string[] args) { byte[] text = new byte[] {12,3,5,76,8,0,6,125,23,36,43,76,125,56,34,234,12,4,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,123}; byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; BoyerMoore tmpSearch = new BoyerMoore(pattern,text); Console.WriteLine(tmpSearch.Match()); Console.ReadKey(); } public class BoyerMoore { private static int ALPHABET_SIZE = 256; private byte[] text; private byte[] pattern; private int[] last; private int[] match; private int[] suffix; public BoyerMoore(byte[] pattern, byte[] text) { this.text = text; this.pattern = pattern; last = new int[ALPHABET_SIZE]; match = new int[pattern.Length]; suffix = new int[pattern.Length]; } /** * Searches the pattern in the text. * returns the position of the first occurrence, if found and -1 otherwise. */ public int Match() { // Preprocessing ComputeLast(); ComputeMatch(); // Searching int i = pattern.Length - 1; int j = pattern.Length - 1; while (i < text.Length) { if (pattern[j] == text[i]) { if (j == 0) { return i; } j--; i--; } else { i += pattern.Length - j - 1 + Math.Max(j - last[text[i]], match[j]); j = pattern.Length - 1; } } return -1; } /** * Computes the function last and stores its values in the array last. * last(Char ch) = the index of the right-most occurrence of the character ch * in the pattern; * -1 if ch does not occur in the pattern. */ private void ComputeLast() { for (int k = 0; k < last.Length; k++) { last[k] = -1; } for (int j = pattern.Length-1; j >= 0; j--) { if (last[pattern[j]] < 0) { last[pattern[j]] = j; } } } /** * Computes the function match and stores its values in the array match. * match(j) = min{ s | 0 < s <= j && p[j-s]!=p[j] * && p[j-s+1]..p[m-s-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, else * min{ s | j+1 <= s <= m * && p[0]..p[m-s-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, * m, otherwise, * where p is the pattern and m is its length. */ private void ComputeMatch() { /* Phase 1 */ for (int j = 0; j < match.Length; j++) { match[j] = match.Length; } //O(m) ComputeSuffix(); //O(m) /* Phase 2 */ //Uses an auxiliary array, backwards version of the KMP failure function. //suffix[i] = the smallest j > i s.t. p[j..m-1] is a prefix of p[i..m-1], //if there is no such j, suffix[i] = m //Compute the smallest shift s, such that 0 < s <= j and //p[j-s]!=p[j] and p[j-s+1..m-s-1] is suffix of p[j+1..m-1] or j == m-1}, // if such s exists, for (int i = 0; i < match.Length - 1; i++) { int j = suffix[i + 1] - 1; // suffix[i+1] <= suffix[i] + 1 if (suffix[i] > j) { // therefore pattern[i] != pattern[j] match[j] = j - i; } else {// j == suffix[i] match[j] = Math.Min(j - i + match[i], match[j]); } } /* Phase 3 */ //Uses the suffix array to compute each shift s such that //p[0..m-s-1] is a suffix of p[j+1..m-1] with j < s < m //and stores the minimum of this shift and the previously computed one. if (suffix[0] < pattern.Length) { for (int j = suffix[0] - 1; j >= 0; j--) { if (suffix[0] < match[j]) { match[j] = suffix[0]; } } { int j = suffix[0]; for (int k = suffix[j]; k < pattern.Length; k = suffix[k]) { while (j < k) { if (match[j] > k) { match[j] = k; } j++; } } } } } /** * Computes the values of suffix, which is an auxiliary array, * backwards version of the KMP failure function. * * suffix[i] = the smallest j > i s.t. p[j..m-1] is a prefix of p[i..m-1], * if there is no such j, suffix[i] = m, i.e. * p[suffix[i]..m-1] is the longest prefix of p[i..m-1], if suffix[i] < m. */ private void ComputeSuffix() { suffix[suffix.Length-1] = suffix.Length; int j = suffix.Length - 1; for (int i = suffix.Length - 2; i >= 0; i--) { while (j < suffix.Length - 1 && !pattern[j].Equals(pattern[i])) { j = suffix[j + 1] - 1; } if (pattern[j] == pattern[i]) { j--; } suffix[i] = j + 1; } } } }quelle
Sie können ORegex verwenden:
var oregex = new ORegex<byte>("{0}{1}{2}", x=> x==12, x=> x==3, x=> x==5); var toSearch = new byte[]{1,1,12,3,5,1,12,3,5,5,5,5}; var found = oregex.Matches(toSearch);Wird zwei Übereinstimmungen gefunden:
i:2;l:3 i:6;l:3Komplexität: O (n * m) im schlimmsten Fall, im wirklichen Leben ist es O (n) aufgrund der internen Zustandsmaschine. In einigen Fällen ist es schneller als .NET Regex. Es ist kompakt, schnell und speziell für den Array-Mustervergleich konzipiert.
quelle
Hier ist ein einfacher Code, den ich nur mit grundlegenden Datentypen geschrieben habe: (Er gibt den Index des ersten Auftretens zurück.)
private static int findMatch(byte[] data, byte[] pattern) { if(pattern.length > data.length){ return -1; } for(int i = 0; i<data.length ;){ int j; for(j=0;j<pattern.length;j++){ if(pattern[j]!=data[i]) break; i++; } if(j==pattern.length){ System.out.println("Pattern found at : "+(i - pattern.length )); return i - pattern.length ; } if(j!=0)continue; i++; } return -1; }quelle
Here's a little code I wrote, you might want to see it node for node, don't worry, be happyNur eine weitere Antwort, die einfach zu befolgen und für eine Operation vom Typ O (n) ziemlich effizient ist, ohne unsicheren Code zu verwenden oder Teile der Quell-Arrays zu kopieren.
Stellen Sie sicher, dass Sie testen. Einige der Vorschläge zu diesem Thema sind anfällig für Situationen.
static void Main(string[] args) { // 1 1 1 1 1 1 1 1 1 1 2 2 2 // 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 byte[] buffer = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 5, 5, 0, 5, 5, 1, 2 }; byte[] beginPattern = new byte[] { 1, 0, 2 }; byte[] middlePattern = new byte[] { 8, 9, 10 }; byte[] endPattern = new byte[] { 9, 10, 11 }; byte[] wholePattern = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; byte[] noMatchPattern = new byte[] { 7, 7, 7 }; int beginIndex = ByteArrayPatternIndex(buffer, beginPattern); int middleIndex = ByteArrayPatternIndex(buffer, middlePattern); int endIndex = ByteArrayPatternIndex(buffer, endPattern); int wholeIndex = ByteArrayPatternIndex(buffer, wholePattern); int noMatchIndex = ByteArrayPatternIndex(buffer, noMatchPattern); } /// <summary> /// Returns the index of the first occurrence of a byte array within another byte array /// </summary> /// <param name="buffer">The byte array to be searched</param> /// <param name="pattern">The byte array that contains the pattern to be found</param> /// <returns>If buffer contains pattern then the index of the first occurrence of pattern within buffer; otherwise, -1</returns> public static int ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern return i; else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } } return -1; } /// <summary> /// Returns the indexes of each occurrence of a byte array within another byte array /// </summary> /// <param name="buffer">The byte array to be searched</param> /// <param name="pattern">The byte array that contains the pattern to be found</param> /// <returns>If buffer contains pattern then the indexes of the occurrences of pattern within buffer; otherwise, null</returns> /// <remarks>A single byte in the buffer array can only be part of one match. For example, if searching for 1,2,1 in 1,2,1,2,1 only zero would be returned.</remarks> public static int[] ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { List<int> indexes = new List<int>(); int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern indexes.Add(i); else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } if (indexes.Count > 0) return indexes.ToArray(); } return null; }quelle
Ich habe versucht, Sanchez 'Vorschlag zu verstehen und schneller zu suchen. Die Leistung des folgenden Codes ist nahezu gleich. Aber der Code ist verständlicher.
public int Search3(byte[] src, byte[] pattern) { int index = -1; for (int i = 0; i < src.Length; i++) { if (src[i] != pattern[0]) { continue; } else { bool isContinoue = true; for (int j = 1; j < pattern.Length; j++) { if (src[++i] != pattern[j]) { isContinoue = true; break; } if(j == pattern.Length - 1) { isContinoue = false; } } if ( ! isContinoue) { index = i-( pattern.Length-1) ; break; } } } return index; }quelle
Dies ist mein eigener Ansatz zu diesem Thema. Ich habe Zeiger verwendet, um sicherzustellen, dass es auf größeren Arrays schneller ist. Diese Funktion gibt das erste Auftreten der Sequenz zurück (was ich in meinem Fall benötigt habe).
Ich bin sicher, Sie können es ein wenig ändern, um eine Liste mit allen Vorkommen zurückzugeben.
Was ich mache, ist ziemlich einfach. Ich durchlaufe das Quellarray (Heuhaufen), bis ich das erste Byte des Musters (Nadel) finde. Wenn das erste Byte gefunden wird, überprüfe ich separat weiter, ob die nächsten Bytes mit den nächsten Bytes des Musters übereinstimmen. Wenn nicht, suche ich wie gewohnt weiter anhand des Index (im Heuhaufen), auf dem ich zuvor war, bevor ich versuche, die Nadel zu finden.
Also hier ist der Code:
public unsafe int IndexOfPattern(byte[] src, byte[] pattern) { fixed(byte *srcPtr = &src[0]) fixed (byte* patternPtr = &pattern[0]) { for (int x = 0; x < src.Length; x++) { byte currentValue = *(srcPtr + x); if (currentValue != *patternPtr) continue; bool match = false; for (int y = 0; y < pattern.Length; y++) { byte tempValue = *(srcPtr + x + y); if (tempValue != *(patternPtr + y)) { match = false; break; } match = true; } if (match) return x; } } return -1; }Sicherer Code unten:
public int IndexOfPatternSafe(byte[] src, byte[] pattern) { for (int x = 0; x < src.Length; x++) { byte currentValue = src[x]; if (currentValue != pattern[0]) continue; bool match = false; for (int y = 0; y < pattern.Length; y++) { byte tempValue = src[x + y]; if (tempValue != pattern[y]) { match = false; break; } match = true; } if (match) return x; } return -1; }quelle
Ich bin neulich auf dieses Problem gestoßen. Versuchen Sie Folgendes:
public static long FindBinaryPattern(byte[] data, byte[] pattern) { using (MemoryStream stream = new MemoryStream(data)) { return FindBinaryPattern(stream, pattern); } } public static long FindBinaryPattern(string filename, byte[] pattern) { using (FileStream stream = new FileStream(filename, FileMode.Open)) { return FindBinaryPattern(stream, pattern); } } public static long FindBinaryPattern(Stream stream, byte[] pattern) { byte[] buffer = new byte[1024 * 1024]; int patternIndex = 0; int read; while ((read = stream.Read(buffer, 0, buffer.Length)) > 0) { for (int bufferIndex = 0; bufferIndex < read; ++bufferIndex) { if (buffer[bufferIndex] == pattern[patternIndex]) { ++patternIndex; if (patternIndex == pattern.Length) return stream.Position - (read - bufferIndex) - pattern.Length + 1; } else { patternIndex = 0; } } } return -1; }Es macht nichts kluges, hält es einfach.
quelle
Sie können das Byte-Array in String einfügen und die Übereinstimmung mit IndexOf ausführen. Oder Sie können zumindest vorhandene Algorithmen für den String-Abgleich wiederverwenden .
[STAThread] static void Main(string[] args) { byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}; string needle, haystack; unsafe { fixed(byte * p = pattern) { needle = new string((SByte *) p, 0, pattern.Length); } // fixed fixed (byte * p2 = toBeSearched) { haystack = new string((SByte *) p2, 0, toBeSearched.Length); } // fixed int i = haystack.IndexOf(needle, 0); System.Console.Out.WriteLine(i); } }quelle
toBeSearched.Except (Muster) gibt Ihnen Unterschiede zurück zu BeSearched.Intersect (Muster) erzeugt eine Reihe von Schnittpunkten. Im Allgemeinen sollten Sie erweiterte Methoden in Linq-Erweiterungen untersuchen
quelle