Znajdź sekwencję bajtów w tablicy bajtów.

Question

Mam tablicę bajtów i chcę znaleźć "wystąpienia" niektórych bajtów.

Na przykład 00 69 73 6F 6D w bardzo dużej tablicy bajtów (> 50/100 megabajtów)

LUB

nawet lepiej odwrotna operacja: Wyszukiwanie wzorca najczęściej nieświadomie kod powinien być w stanie odczytać i znajdź go z pliku.

Answer 1

Możesz użyć algorytmu Boyer-Moore do efektywnego wyszukiwania sekwencji bajtów w tablicy bajtów.

Oto wersja C#, którą przekonwertowałem z wersji Java z 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; 
    } 
} 

Oto niektóre kodu testu konsola app dla niego:

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

Uwaga jaki sposób Search() zwraca indeksy wszystkich lokalizacjach początku needle wewnątrz haystack.

Jeśli tylko chciał liczyć, można po prostu zrobić:

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

---

Na drugie pytanie: Zakładam, że jesteś z prośbą o znalezienie najdłuższy powtarzającego sekwencję bajtów?

To o wiele bardziej skomplikowane - i bardzo różne - pytanie. Jeśli chcesz na to odpowiedzieć, powinieneś zadać mu osobne pytanie, ale powinieneś przeczytać the Wikipedia entry on the "longest repeated substring problem".