Trova la sequenza di byte all'interno di un array di byte

Question

Ho un array di byte e desidero trovare le "occorrenze" di alcuni byte.

Ad esempio 00 69 73 6F 6D in un grande array di byte (> 50/100 Megabytes)

O

ancora meglio un'operazione inversa: Ricerca del modello più comune insaputa il codice dovrebbe essere in grado di leggere e trovalo dal file.

Answer 1

È possibile utilizzare l'algoritmo Boyer-Moore per cercare in modo efficiente una sequenza di byte in una matrice di byte.

Ecco una versione C# che ho convertito dalla versione Java da the Wikipedia entry on Boyer-Moore.

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

Ecco alcuni codice di prova console app per esso:

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

Si noti come il metodo Search() restituisce gli indici di tutte le posizioni di partenza dei needle all'interno haystack.

Se si voleva solo il conteggio, si può solo fare:

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

---

Per la seconda domanda: Suppongo che tu stai chiedendo di trovare la sequenza più lunga ripetute di byte?

Questa è una domanda molto più complicata e molto diversa. Se vuoi una risposta per questo, dovresti fare una domanda a parte, ma dovresti leggere the Wikipedia entry on the "longest repeated substring problem".