字節數組模式匹配

Question

比方說，我有兩個字節數組，每個包含像一系列的值：

byte[] b = {50,60,70,80,90,10,20,1,2,3,4,5,50,2,3,1,2,3,4,5}; 
byte[] b2 = {1,2,3,4,5} 

我可以比較這兩個數組，並查找使用LINQ方法相同的值。這樣，如果我在這兩個數組之間進行比較，結果將是b數組的索引，其中b2數組的索引中的值是匹配的。

我一直在試圖精確地找到b數組在b數組中循環的範圍。我的意思是

if (TheLenghtOfSearch==5) {Now the indexes of two regions must be return } 
Result ->(7, 11), (15, 19) 

if (TheLenghtOfSearch==2) {Now the indexes of around 9 regions where the two consecutive values in b2 recurred in b must be returned} 
Result ->(7, 8), (15, 16), (8, 9), (13, 14), (16, 17), (9, 10), (17, 18), (10, 11), (18, 19) 

我想解決方案更數學。

Answer 1

我決定用列表，而不是數組，因爲它有更多的幫手對於這種操作。 據我所知深度=每個數組中必須等於的項目數量。這一個工程，檢查了這一點：

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<byte> b = new List<byte>() { 50, 60, 70, 80, 90, 10, 20, 1, 2, 3, 4, 5, 50, 2, 3, 1, 2, 3, 4, 5 }; 
     List<byte> b2 = new List<byte>() { 1, 2, 3, 4, 5 }; 
     SmartComparer comparer = new SmartComparer(); 
     //Setting the depth here, now the depth is = 5 
     var result = comparer.CompareArraysWithDepth(b, b2, 5); 
     foreach (var keyValuePair in result) 
     { 
      Console.WriteLine(String.Format("b[{0}]->b[{1}] are equal to b2[{2}]->b2[{3}]", keyValuePair.Key.Key, 
              keyValuePair.Key.Value, keyValuePair.Value.Key, keyValuePair.Value.Value)); 
     } 
    } 
} 

public class SmartComparer 
{ 
    public Boolean CompareRange(List<byte> a, List<byte> b) 
    { 
     for (int i = 0; i < a.Count; i++) 
     { 
      if (a[i] != b[i]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 

    /// <summary> 
    /// | 
    /// </summary> 
    /// <param name="a"></param> 
    /// <param name="b"></param> 
    /// <param name="depth"></param> 
    /// <returns>Key->range in 'a', Value->range in 'b'</returns> 
    public List<KeyValuePair<KeyValuePair<int, int>, KeyValuePair<int, int>>> CompareArraysWithDepth(
     List<byte> a, List<byte> b, int depth) 
    { 
     var result = new List<KeyValuePair<KeyValuePair<int, int>, KeyValuePair<int, int>>>(); 
     if (depth > b.Count) 
      throw new ArgumentException("Array 'b' item count should be more then depth"); 
     if(a.Count<b.Count) 
      throw new ArgumentException("Array 'a' item count should be more then Array 'b' item count"); 
     for (int i = 0; i <= a.Count - depth; i++) 
     { 
      for (int j = 0; j <= b.Count - depth; j++) 
      { 
       if (CompareRange(a.GetRange(i, depth), b.GetRange(j, depth))) 
       { 
        result.Add(new KeyValuePair<KeyValuePair<int, int>, KeyValuePair<int, int>>(new KeyValuePair<int, int>(i, i + depth-1), new KeyValuePair<int, int>(j, j + depth-1))); 
       } 
      } 
     } 
     return result; 
    } 
} 

ADDED

該操作用於深度的結果= 3：

b[7]->b[9] are equal to b2[0]->b2[2] 
b[8]->b[10] are equal to b2[1]->b2[3] 
b[9]->b[11] are equal to b2[2]->b2[4] 
b[15]->b[17] are equal to b2[0]->b2[2] 
b[16]->b[18] are equal to b2[1]->b2[3] 
b[17]->b[19] are equal to b2[2]->b2[4] 

該操作用於深度= 2的結果是：

b[7]->b[8] are equal to b2[0]->b2[1] 
b[8]->b[9] are equal to b2[1]->b2[2] 
b[9]->b[10] are equal to b2[2]->b2[3] 
b[10]->b[11] are equal to b2[3]->b2[4] 
b[13]->b[14] are equal to b2[1]->b2[2] 
b[15]->b[16] are equal to b2[0]->b2[1] 
b[16]->b[17] are equal to b2[1]->b2[2] 
b[17]->b[18] are equal to b2[2]->b2[3] 
b[18]->b[19] are equal to b2[3]->b2[4] 

該操作的結果爲depth = 5：

b[7]->b[11] are equal to b2[0]->b2[4] 
b[15]->b[19] are equal to b2[0]->b2[4] 

Answer 2

如果LINQ的不是你是絕對必需的選項，您可以獲得由循環的結果：

public static IList<Tuple<int, int>> RecurringIndexes(Byte[] master, Byte[] toFind, int length) { 
    List<Tuple<int, int>> result = new List<Tuple<int, int>>(); 

    // Let's return empty list ... Or throw appropriate exception 
    if (Object.ReferenceEquals(null, master)) 
    return result; 
    else if (Object.ReferenceEquals(null, toFind)) 
    return result; 
    else if (length < 0) 
    return result; 
    else if (length > toFind.Length) 
    return result; 

    Byte[] subRegion = new Byte[length]; 

    for (int i = 0; i <= toFind.Length - length; ++i) { 
    for (int j = 0; j < length; ++j) 
     subRegion[j] = toFind[j + i]; 

    for (int j = 0; j < master.Length - length + 1; ++j) { 
     Boolean counterExample = false; 

     for (int k = 0; k < length; ++k) 
     if (master[j + k] != subRegion[k]) { 
      counterExample = true; 

      break; 
     } 

     if (counterExample) 
     continue; 

     result.Add(new Tuple<int, int>(j, j + length - 1)); 
    } 
    } 

    return result; 
} 

.... 

byte[] b = {50,60,70,80,90,10,20,1,2,3,4,5,50,2,3,1,2,3,4,5}; 
byte[] b2 = { 1, 2, 3, 4, 5 }; 

// Returns 2 patterns: {(7, 11), (15, 19)} 
IList<Tuple<int, int>> indice5 = RecurringIndexes(b, b2, 5); 
// Return 9 patterns: {(7, 8), (15, 16), (8, 9), (13, 14), (16, 17), (9, 10), (17, 18), (10, 11), (18, 19)} 
IList<Tuple<int, int>> indice2 = RecurringIndexes(b, b2, 2);