C# Array Subset holen

Question

Ich habe ein Array von Bytes und ich möchte feststellen, ob der Inhalt dieses Array von Bytes in einem anderen größeren Array als eine kontinuierliche Sequenz existiert. Was ist der einfachste Weg, dies zu tun?

Answer 1

Der naive Ansatz ist:

public static bool IsSubsetOf(byte[] set, byte[] subset) { 
    for(int i = 0; i < set.Length && i + subset.Length <= set.Length; ++i) 
     if (set.Skip(i).Take(subset.Length).SequenceEqual(subset)) 
      return true; 
    return false; 
} 

Für eine effizientere Ansätze, könnten Sie erweiterte String-Matching-Algorithmen wie KMP betrachten.

Answer 2

Versuchen Sie, einen String-Suchalgorithmus anzupassen. Einer der schnellsten ist Boyer-Moore. Es ist auch ziemlich einfach. Für binäre Daten, Knuth-Morris-Pratt Algorithmus könnte auch sehr effizient arbeiten.

Answer 3

Dieses, das ein 1/1 Anschluss dieser Antwort lautet: Searching for a sequence of Bytes in a Binary File with Java

ist eine sehr effiziente Art und Weise, dies zu tun:

public static class KmpSearch { 

    public static int IndexOf(byte[] data, byte[] pattern) { 
     int[] failure = ComputeFailure(pattern); 

     int j = 0; 
     if (data.Length == 0) return -1; 

     for (int i = 0; i < data.Length; i++) { 
      while (j > 0 && pattern[j] != data[i]) { 
       j = failure[j - 1]; 
      } 
      if (pattern[j] == data[i]) { j++; } 
      if (j == pattern.Length) { 
       return i - pattern.Length + 1; 
      } 
     } 
     return -1; 
    } 


    private static int[] ComputeFailure(byte[] pattern) { 
     int[] failure = new int[pattern.Length]; 

     int j = 0; 
     for (int i = 1; i < pattern.Length; i++) { 
      while (j > 0 && pattern[j] != pattern[i]) { 
       j = failure[j - 1]; 
      } 
      if (pattern[j] == pattern[i]) { 
       j++; 
      } 
      failure[i] = j; 
     } 

     return failure; 
    } 
}