Tìm chuỗi byte trong một mảng byte

Question

Tôi có một mảng byte và muốn tìm "các lần xuất hiện" của một số byte.

Ví dụ 00 69 73 6F 6D trong một mảng byte rất lớn (> 50/100 MB)

HOẶC

thậm chí tốt hơn một hoạt động ngược lại: Tìm kiếm mô hình phổ biến nhất mà không biết mã sẽ có thể đọc và tìm nó từ tập tin.

Answer 1

Bạn có thể sử dụng thuật toán Boyer-Moore để tìm kiếm một chuỗi có hiệu quả trong một mảng byte.

Đây là phiên bản C# tôi đã chuyển đổi từ phiên bản Java từ 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; 
    } 
} 

Dưới đây là một số giao diện điều khiển mã kiểm tra ứng dụng cho nó:

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

Lưu ý cách phương pháp Search() trả về chỉ số của tất cả các địa điểm của sự bắt đầu của needle bên haystack.

Nếu bạn chỉ muốn đếm, bạn chỉ có thể làm:

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

---

Đối với câu hỏi thứ hai của bạn: Tôi giả sử bạn đang yêu cầu về việc tìm kiếm trình tự lặp đi lặp lại dài nhất của byte?

Đó là một câu hỏi phức tạp hơn - và rất khác. Nếu bạn muốn có câu trả lời cho điều đó, bạn nên đặt một câu hỏi riêng cho nó, nhưng bạn nên đọc the Wikipedia entry on the "longest repeated substring problem".