recherche de motifs dans un tableau d'octets[]

Question

Quelqu'un connaît-il un moyen efficace de rechercher un motif d'octets dans un tableau d'octets[] et de renvoyer les positions ?

Par exemple

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

Puis-je suggérer quelque chose qui n'implique pas la création de chaînes de caractères, la copie de tableaux ou du code non sécurisé ?

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

Modifier (par IAbstract) - en déplaçant le contenu de poste ici puisque ce n'est pas une réponse

Par curiosité, j'ai créé un petit benchmark avec différentes réponses.

Voici les résultats pour un million d'itérations :

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

Utilice Méthodes 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;
        }
    }
}

Très simple !

Answer 3

À l'origine, j'avais posté un vieux code que j'utilisais, mais j'étais curieux de connaître le code de Jb Evain. repères . J'ai trouvé que ma solution était stupidement lente. Il semble que la solution de Bruno Conde SearchBytePattern est le plus rapide. Je n'ai pas pu comprendre pourquoi, surtout qu'il utilise une méthode Array.Copy et une méthode Extension. Mais il y a une preuve dans les tests de Jb, donc bravo à bruno.

J'ai simplifié encore davantage les éléments, en espérant que cette solution sera la plus claire et la plus simple. (Tout le travail dur fait par bruno conde) Les améliorations sont :

• Buffer.BlockCopy
• Array.IndexOf<byte>
• boucle while au lieu d'une boucle for
• paramètre de l'indice de départ

• converti en méthode d'extension

  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 + 1);
     }
     return positions;    
  }

Notez que, la dernière déclaration dans le while Le bloc doit être i = Array.IndexOf<byte>(buffer, pattern[0], i + 1); au lieu de i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length); . Regardez le commentaire de Johan. Un simple test pourrait le prouver :

byte[] pattern = new byte[] {1, 2};
byte[] toBeSearched = new byte[] { 1, 1, 2, 1, 12 };

Avec i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length); rien n'est retourné. i = Array.IndexOf<byte>(buffer, pattern[0], i + 1); renvoie le résultat correct.

Answer 4

Utilisez l'efficacité Algorithme de Boyer-Moore .

Il est conçu pour trouver des chaînes de caractères dans des chaînes de caractères, mais il ne faut pas beaucoup d'imagination pour le projeter dans des tableaux d'octets.

En général, la meilleure réponse est : utilisez n'importe quel algorithme de recherche de chaîne de caractères que vous aimez :).

Answer 5

Ma solution :

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