如何检查是否字节数组包含另一个数组

Question

我有一个很长的字节数组，例如：

Byte[] bytes = {90, 80, 63, 65, 70 ...}; 

这几乎是20-30 MB（理论上）。有没有一种快速的方法，来检查这个数组包含另一个数组例如：

Byte[] small = {63, 80, 75, 77}; 

首先，我需要找到他们在小阵定义的顺序字节。其次，我需要在另一个数组中找到数组，而不是任何小数组的字节。 谢谢大家前进。

Answer 1

如果你以字节为单位得到了数以百万计的元素，我建议：

1. 排序字节的小
2. 的foreach如果找不到元素返回false

因此

bytes.Sort(); // only need to do this once. 
bool smallContained = ContainsAll(bytes, small); 

and

static bool ContainsAll(int[] src, int [] subset) 
{ 
    foreach(var i in subset) 
     if (src.BinarySearch(i) < 0) 
       return false; 
    return true; 
} 

Answer 2

static int search(byte[] haystack, byte[] needle) 
{ 
    for (int i = 0; i <= haystack.Length - needle.Length; i++) 
    { 
     if (match(haystack, needle, i)) 
     { 
      return i; 
     } 
    } 
    return -1; 
} 

static bool match(byte[] haystack, byte[] needle, int start) 
{ 
    if (needle.Length + start > haystack.Length) 
    { 
     return false; 
    } 
    else 
    { 
     for (int i = 0; i < needle.Length; i++) 
     { 
      if (needle[i] != haystack[i + start]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

Answer 3

使用此：

bool isSubset = !t2.Except(t1).Any(); 

这是一个从@Farhad Jabiyev的链接： Check whether an array is a subset of another

Answer 4

对于性能你想要的东西，如Boyer-Moore string search algorithm。虽然它是为字符串设计的，但它在字节数组上应该也能工作，并且比蛮力解决方案更具性能。

维基百科文章提供了几个实现，其中包括Java中的一个和C中的一个，因此创建C＃实现应该相当轻松。

---

事实证明，翻译维基百科的文章的Java实现博耶 - 穆尔的为C＃（和char到byte）是无痛确实如此。这里是：

public static class BoyerMoore 
{ 
    public static int IndexOf(byte[] haystack, byte[] needle) 
    { 
     if (needle.Length == 0) 
     { 
      return 0; 
     } 

     int[] charTable = MakeCharTable(needle); 
     int[] offsetTable = MakeOffsetTable(needle); 
     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) 
       { 
        return i; 
       } 
      } 

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

     return -1; 
    } 

    private static int[] MakeCharTable(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; 
    } 

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

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

    private 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 += 1; 
     } 

     return len; 
    } 
} 

该算法花费了一个线性位的时间在开始，建立它的表;从那以后它的速度非常快。

Answer 5

如果我理解正确，你想说如果small是bytes的子序列。你可以在字节上找到循环。由于处理器缓存，它应该运行得非常快。

for (int i = 0, index = 0; i < bytes.Length; ++i) 
    if (bytes[i] == small[index]) { 
     if (++index >= small.Length) { 
     return true; 
     } 
    } 
    return false;