Finden Byte-Sequenz innerhalb einer Byte-Array

Question

Ich habe ein Byte-Array und möchte die "Vorkommen" einiger Bytes finden.

Zum Beispiel 00 69 73 6F 6D in einem sehr großen Byte-Array (> 50/100 Megabytes)

OR

besser sogar ein Reverse-Betrieb: Suchen des am häufigsten Muster ohne es zu wissen, der Code sollte in der Lage sein zu lesen und finde es aus der Datei.

Answer 1

Sie können den Boyer-Moore-Algorithmus verwenden, um effizient nach einer Bytefolge in einem Bytearray zu suchen.

Hier ist eine C# Version, die ich von der Java-Version von the Wikipedia entry on Boyer-Moore konvertiert habe.

public sealed class BoyerMoore 
{ 
    readonly byte[] needle; 
    readonly int[] charTable; 
    readonly int[] offsetTable; 

    public BoyerMoore(byte[] needle) 
    { 
     this.needle = needle; 
     this.charTable = makeByteTable(needle); 
     this.offsetTable = makeOffsetTable(needle); 
    } 

    public IEnumerable<int> Search(byte[] haystack) 
    { 
     if (needle.Length == 0) 
      yield break; 

     for (int i = needle.Length - 1; i < haystack.Length;) 
     { 
      int j; 

      for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j) 
      { 
       if (j != 0) 
        continue; 

       yield return i; 
       i += needle.Length - 1; 
       break; 
      } 

      i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]); 
     } 
    } 

    static int[] makeByteTable(byte[] needle) 
    { 
     const int ALPHABET_SIZE = 256; 
     int[] table = new int[ALPHABET_SIZE]; 

     for (int i = 0; i < table.Length; ++i) 
      table[i] = needle.Length; 

     for (int i = 0; i < needle.Length - 1; ++i) 
      table[needle[i]] = needle.Length - 1 - i; 

     return table; 
    } 

    static int[] makeOffsetTable(byte[] needle) 
    { 
     int[] table = new int[needle.Length]; 
     int lastPrefixPosition = needle.Length; 

     for (int i = needle.Length - 1; i >= 0; --i) 
     { 
      if (isPrefix(needle, i + 1)) 
       lastPrefixPosition = i + 1; 

      table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1; 
     } 

     for (int i = 0; i < needle.Length - 1; ++i) 
     { 
      int slen = suffixLength(needle, i); 
      table[slen] = needle.Length - 1 - i + slen; 
     } 

     return table; 
    } 

    static bool isPrefix(byte[] needle, int p) 
    { 
     for (int i = p, j = 0; i < needle.Length; ++i, ++j) 
      if (needle[i] != needle[j]) 
       return false; 

     return true; 
    } 

    static int suffixLength(byte[] needle, int p) 
    { 
     int len = 0; 

     for (int i = p, j = needle.Length - 1; i >= 0 && needle[i] == needle[j]; --i, --j) 
      ++len; 

     return len; 
    } 
} 

Hier einige Konsolenanwendung Test-Code für sie:

public static void Main() 
{ 
    byte[] haystack = new byte[10000]; 
    byte[] needle = { 0x00, 0x69, 0x73, 0x6F, 0x6D }; 

    // Put a few copies of the needle into the haystack. 

    for (int i = 1000; i <= 9000; i += 1000) 
     Array.Copy(needle, 0, haystack, i, needle.Length); 

    var searcher = new BoyerMoore(needle); 

    foreach (int index in searcher.Search(haystack)) 
     Console.WriteLine(index); 
} 

Hinweis, wie die Search() Methode die Indizes aller Standorte des Beginns der needle innerhalb haystack zurückgibt.

Wenn Sie nur die Anzahl wollen, könnten Sie gerade tun:

int count = new BoyerMoore(needle).Search(haystack).Count(); 

---

Für Ihre zweite Frage: Ich nehme an, Sie fragen nach der längsten wiederholten Folge von Bytes zu finden?

Das ist eine viel kompliziertere - und sehr unterschiedliche - Frage. Wenn Sie eine Antwort für das wollen, sollten Sie eine separate Frage dafür stellen, aber Sie sollten the Wikipedia entry on the "longest repeated substring problem" lesen.