Using LINQ to search a byte array for all subarray

问题:

I'm dealing with a COM port application and we have a defined variable-length packet structure that I'm talking to a micro-controller with. The packet has delimiters for the start and stop bytes. The trouble is that sometimes the read buffer can contain extraneous characters. It seems like I'll always get the whole packet, just some extra chatter before/after the actual data. So I have a buffer that I append data to whenever new data is received from the COM port. What is the best way to search this buffer for any possible occurrences of my packet? For example:

Say my packet delimiter is 0xFF and I have an array as such

{ 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 }

How can I create a function/LINQ-statment that returns all subarrays that start and end with the delimiter (almost like a sliding-correlator with wildcards)?

The sample would return the following 3 arrays:

{0xFF, 0x02, 0xDA, 0xFF}, {0xFF, 0x55, 0xFF}, and
{0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF}

回答1:

Here's how you can do this using LINQ ...

int[] list = new int[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
int MAXLENGTH = 10;

var windows = list.Select((element, i) => list.Skip(i).Take(MAXLENGTH));
var matched = windows.Where(w => w.First() == 0xFF);
var allcombinations = matched.SelectMany(m => Enumerable.Range(1, m.Count())
          .Select(i => m.Take(i)).Where(x => x.Count() > 2 && x.Last() == 0xFF));

Or using indexes:

int length = list.Count();
var indexes = Enumerable.Range(0, length)
              .SelectMany(i => Enumerable.Range(3, Math.Min(length-i, MAXLENGTH))
              .Select(count => new {i, count}));
var results = indexes.Select(index => list.Skip(index.i).Take(index.count))
              .Where(x => x.First() == 0xFF && x.Last() == 0xFF);

回答2:

While Trystan's answer is technically correct, he's making lots of copies of the original array all at once. If the starting array is large and has a bunch of delimiters, that gets huge quickly. This approach avoids the massive memory consumption by using only the original array and an array for the current segment being evaluated.

public static List<ArraySegment<byte>> GetSubArrays(this byte[] array, byte delimeter)
{
    if (array == null) throw new ArgumentNullException("array");

    List<ArraySegment<byte>> retval = new List<ArraySegment<byte>>();

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == delimeter)
        {
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[j] == delimeter)
                {
                    retval.Add(new ArraySegment<byte>(array, i + 1, j - i - 1));
                }
            }
        }
    }

    return retval;
}

Can be used as such:

static void Main(string[] args)
{
    byte[] arr = new byte[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
    List<ArraySegment<byte>> retval = GetSubArrays(arr, 0xFF);

    // this also works (looks like LINQ):
    //List<ArraySegment<byte>> retval = arr.GetSubArrays(0xFF);

    byte[] buffer = new byte[retval.Select(x => x.Count).Max()];
    foreach (var x in retval)
    {
        Buffer.BlockCopy(x.Array, x.Offset, buffer, 0, x.Count);
        Console.WriteLine(String.Join(", ", buffer.Take(x.Count).Select(b => b.ToString("X2")).ToArray()));
    }


    Console.ReadLine();
}

回答3:

If you really want to use LINQ, this should work quite fast (even if not as fast as a good-old for loop):

public static IEnumerable<T[]> GetPackets<T>(this IList<T> buffer, T delimiter)
{
    // gets delimiters' indexes
    var delimiterIdxs = Enumerable.Range(0, buffer.Count())
                                  .Where(i => buffer[i].Equals(delimiter))
                                  .ToArray();

    // creates a list of delimiters' indexes pair (startIdx,endIdx)
    var dlmtrIndexesPairs = delimiterIdxs.Take(delimiterIdxs.Count() - 1)
                                         .SelectMany(
                                                     (startIdx, idx) => 
                                                     delimiterIdxs.Skip(idx + 1)
                                                                  .Select(endIdx => new { startIdx, endIdx })
                                                    );
    // creates array of packets
    var packets = dlmtrIndexesPairs.Select(p => buffer.Skip(p.startIdx)
                                                      .Take(p.endIdx - p.startIdx + 1)
                                                      .ToArray())
                                   .ToArray();

    return packets;
}

回答4:

I wouldn't try to do this with linq so here's a regular method that returns the same output as you wanted.

public List<byte[]> GetSubArrays(byte[] array, byte delimeter)
{
  if (array == null) throw new ArgumentNullException("array");

  List<byte[]> subArrays = new List<byte[]>();

  for (int i = 0; i < array.Length; i++)
  {
    if (array[i] == delimeter && i != array.Length - 1)
    {
      List<byte> subList = new List<byte>() { delimeter };

      for (int j = i+1; j < array.Length; j++)
      {
        subList.Add(array[j]);
        if (array[j] == delimeter)
        {
          subArrays.Add(subList.ToArray());
        }
      }
    }
  }

  return subArrays;
}

If it must be an in-place lambda expression, then just change the first line to (byte[] array, byte delimeter) => (without the method modifiers and name) and call it that way.

回答5:

Although the delimiter structure seems a bit vague, I would not use linq and do something like below (no extensive tests performed). It will return all subsets (of bytes surrounded by the delimiter), without including the delimiter (it's a given anyway, why include it?). It also does not return the union of the results, but that can always be assembled manually.

public IEnumerable<byte[]> GetArrays(byte[] data, byte delimiter)
{
    List<byte[]> arrays = new List<byte[]>();
    int start = 0;
    while (start >= 0 && (start = Array.IndexOf<byte>(data, delimiter, start)) >= 0)
    {
        start++;
        if (start >= data.Length - 1)
        {
            break;
        }

        int end = Array.IndexOf<byte>(data, delimiter, start);
        if (end < 0)
        {
            break;
        }

        byte[] sub = new byte[end - start];
        Array.Copy(data, start, sub, 0, end - start);
        arrays.Add(sub);
        start = end;
    }

    return arrays;
}

回答6:

You could do this using a Linq aggregator, but it's much less straightforward than the other solutions suggested here, also had to add a special case to cover extending already completed arrays as you suggested above.

byte[] myArray = new byte[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
var arrayList = myArray.Aggregate(
                new { completedLists = new List<List<byte>>(), 
                      activeList = new List<byte>() },
                (seed, s) =>
                {
                    if (s == 0xFF)
                    {
                        if (seed.activeList.Count == 0)
                        {
                            seed.activeList.Add(s);
                        }
                        else
                        {
                            seed.activeList.Add(s);
                            var combinedLists = new List<List<byte>>();

                            foreach (var l in seed.completedLists)
                            {
                                var combinedList = new List<byte>(l);
                                combinedList.AddRange(seed.activeList.Skip(1));
                                combinedLists.Add(combinedList);
                            }
                            seed.completedLists.AddRange(combinedLists);
                            seed.completedLists.Add(new List<byte>(seed.activeList));
                            seed.activeList.Clear();
                            seed.activeList.Add(s);
                        }
                    }
                    else
                    {
                        if (seed.activeList.Count > 0)
                            seed.activeList.Add(s);
                    }
                    return seed;
                }).completedLists;