поиск шаблона массива byte []

Question

Любой знает хороший и эффективный способ поиска / сопоставления байтового шаблона в массиве byte [] и затем возврата позиций.

Например

byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};

byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}

Answer 1

Могу ли я предложить что-то, что не связано с созданием строк, копированием массивов или небезопасным кодом:

using System;
using System.Collections.Generic;

static class ByteArrayRocks {

    static readonly int [] Empty = new int [0];

    public static int [] Locate (this byte [] self, byte [] candidate)
    {
        if (IsEmptyLocate (self, candidate))
            return Empty;

        var list = new List<int> ();

        for (int i = 0; i < self.Length; i++) {
            if (!IsMatch (self, i, candidate))
                continue;

            list.Add (i);
        }

        return list.Count == 0 ? Empty : list.ToArray ();
    }

    static bool IsMatch (byte [] array, int position, byte [] candidate)
    {
        if (candidate.Length > (array.Length - position))
            return false;

        for (int i = 0; i < candidate.Length; i++)
            if (array [position + i] != candidate [i])
                return false;

        return true;
    }

    static bool IsEmptyLocate (byte [] array, byte [] candidate)
    {
        return array == null
            || candidate == null
            || array.Length == 0
            || candidate.Length == 0
            || candidate.Length > array.Length;
    }

    static void Main ()
    {
        var data = new byte [] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
        var pattern = new byte [] { 12, 3, 5, 76, 8, 0, 6, 125 };

        foreach (var position in data.Locate (pattern))
            Console.WriteLine (position);
    }
}

---

Edit (by IAbstract) - перемещение содержимого post здесь, поскольку это не ответ

Из любопытства я создал небольшой тест с разными ответами.

Вот результаты для миллиона итераций:

solution [Locate]:            00:00:00.7714027
solution [FindAll]:           00:00:03.5404399
solution [SearchBytePattern]: 00:00:01.1105190
solution [MatchBytePattern]:  00:00:03.0658212

---

Answer 2

Использование Методы LINQ.

public static IEnumerable<int> PatternAt(byte[] source, byte[] pattern)
{
    for (int i = 0; i < source.Length; i++)
    {
        if (source.Skip(i).Take(pattern.Length).SequenceEqual(pattern))
        {
            yield return i;
        }
    }
}

Очень просто!

Answer 3

Используйте эффективный алгоритм Бойера-Мура .

Он предназначен для поиска строк внутри строк, но вам не нужно много воображения, чтобы проецировать это в байтовые массивы.

В общем, лучший ответ: используйте любой алгоритм поиска строк, который вам нравится:).

Answer 4

Первоначально я опубликовал какой-то старый код, который использовал, но мне было любопытно узнать о тестах Дж.Б. Я обнаружил, что мое решение было глупо медленным. Похоже, что * bruno conde SearchBytePattern является самым быстрым. Я не мог понять почему, тем более что он использует Array.Copy и метод Extension. Но в тестах Jb есть доказательства, так что слава Бруно.

Я упростил биты еще больше, так что, надеюсь, это будет самое ясное и простое решение. (Вся тяжелая работа, проделанная Бруно Конде). Улучшения:

• Buffer.BlockCopy
• Array.indexOf
• цикл while вместо цикла for
• параметр индекса начала

• преобразован в метод расширения

  public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex)    
  {
     List<int> positions = new List<int>();
     int i = Array.IndexOf<byte>(buffer, pattern[0], startIndex);  
     while (i >= 0 && i <= buffer.Length - pattern.Length)  
     {
        byte[] segment = new byte[pattern.Length];
        Buffer.BlockCopy(buffer, i, segment, 0, pattern.Length);    
        if (segment.SequenceEqual<byte>(pattern))
             positions.Add(i);
        i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length);
     }
     return positions;    
  }
  

Answer 5

Мое решение:

class Program
{
    public static void Main()
    {
        byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};

        byte[] toBeSearched = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125};

        List<int> positions = SearchBytePattern(pattern, toBeSearched);

        foreach (var item in positions)
        {
            Console.WriteLine("Pattern matched at pos {0}", item);
        }

    }

    static public List<int> SearchBytePattern(byte[] pattern, byte[] bytes)
    {
        List<int> positions = new List<int>();
        int patternLength = pattern.Length;
        int totalLength = bytes.Length;
        byte firstMatchByte = pattern[0];
        for (int i = 0; i < totalLength; i++)
        {
            if (firstMatchByte == bytes[i] && totalLength - i >= patternLength)
            {
                byte[] match = new byte[patternLength];
                Array.Copy(bytes, i, match, 0, patternLength);
                if (match.SequenceEqual<byte>(pattern))
                {
                    positions.Add(i);
                    i += patternLength - 1;
                }
            }
        }
        return positions;
    }
}

Answer 6

Это моё предложение, более простое и быстрое:

int Search(byte[] src, byte[] pattern)
{
    int c = src.Length - pattern.Length + 1;
    int j;
    for (int i = 0; i < c; i++)
    {
        if (src[i] != pattern[0]) continue;
        for (j = pattern.Length - 1; j >= 1 && src[i + j] == pattern[j]; j--) ;
        if (j == 0) return i;
    }
    return -1;
}

Answer 7

Мне не хватало метода / ответа LINQ: -)

/// <summary>
/// Searches in the haystack array for the given needle using the default equality operator and returns the index at which the needle starts.
/// </summary>
/// <typeparam name="T">Type of the arrays.</typeparam>
/// <param name="haystack">Sequence to operate on.</param>
/// <param name="needle">Sequence to search for.</param>
/// <returns>Index of the needle within the haystack or -1 if the needle isn't contained.</returns>
public static IEnumerable<int> IndexOf<T>(this T[] haystack, T[] needle)
{
    if ((needle != null) && (haystack.Length >= needle.Length))
    {
        for (int l = 0; l < haystack.Length - needle.Length + 1; l++)
        {
            if (!needle.Where((data, index) => !haystack[l + index].Equals(data)).Any())
            {
                yield return l;
            }
        }
    }
}

Answer 8

Моя версия ответа Фубара выше, которая позволяет избежать поиска за концом стога сена и позволяет указать начальное смещение. Предполагается, что игла не пуста и не длиннее стога сена.

public static unsafe long IndexOf(this byte[] haystack, byte[] needle, long startOffset = 0)
{ 
    fixed (byte* h = haystack) fixed (byte* n = needle)
    {
        for (byte* hNext = h + startOffset, hEnd = h + haystack.LongLength + 1 - needle.LongLength, nEnd = n + needle.LongLength; hNext < hEnd; hNext++)
            for (byte* hInc = hNext, nInc = n; *nInc == *hInc; hInc++)
                if (++nInc == nEnd)
                    return hNext - h;
        return -1;
    }
}

Answer 9

Это самые простые и быстрые методы, которые вы можете использовать, и не было бы ничего быстрее, чем эти. Это небезопасно, но для этого мы используем указатели скорости. Поэтому здесь я предлагаю вам свои методы расширения, которые я использую для поиска одного, и список индексов происшествий. Я хотел бы сказать, что это самый чистый код здесь.

    public static unsafe long IndexOf(this byte[] Haystack, byte[] Needle)
    {
        fixed (byte* H = Haystack) fixed (byte* N = Needle)
        {
            long i = 0;
            for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
            {
                bool Found = true;
                for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
                if (Found) return i;
            }
            return -1;
        }
    }
    public static unsafe List<long> IndexesOf(this byte[] Haystack, byte[] Needle)
    {
        List<long> Indexes = new List<long>();
        fixed (byte* H = Haystack) fixed (byte* N = Needle)
        {
            long i = 0;
            for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
            {
                bool Found = true;
                for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
                if (Found) Indexes.Add(i);
            }
            return Indexes;
        }
    }

В сравнении с Locate, он в 1,2-1,4 раза быстрее

Answer 10

Jb Evain ответ имеет:

 for (int i = 0; i < self.Length; i++) {
      if (!IsMatch (self, i, candidate))
           continue;
      list.Add (i);
 }

, а затем функция IsMatch сначала проверяет, превышает ли candidate длину искомого массива.

Это было бы более эффективно, если бы кодировался цикл for:

     for (int i = 0, n = self.Length - candidate.Length + 1; i < n; ++i) {
          if (!IsMatch (self, i, candidate))
               continue;
          list.Add (i);
     }

в этот момент один может также исключить тест с начала IsMatch, если вы заключаете контракт с предварительными условиями, чтобы никогда не вызывать его с «недопустимыми» параметрами. Примечание. В 2019 году исправлена ​​ошибка, связанная с ошибкой.