byte busca de padrão de matriz

Qualquer um sabe uma maneira boa e efetiva de pesquisar / combinar por um padrão de byte em um array byte [] e depois retornar as posições.

Por exemplo

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} 

Posso sugerir algo que não envolva criar strings, copiar matrizes ou códigos inseguros:

 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 (); 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 (por IAbstract)movendo o conteúdo do post aqui, já que não é uma resposta

Por curiosidade, criei um pequeno benchmark com as diferentes respostas.

Aqui estão os resultados para um milhão de iterações:

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

Use os methods LINQ.

 public static IEnumerable 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; } } } 

Muito simples!

Use o eficiente algoritmo Boyer-Moore .

Ele foi projetado para encontrar strings com strings, mas você precisa de pouca imaginação para projetar isso em matrizes de bytes.

Em geral, a melhor resposta é: use qualquer algoritmo de busca de strings que você goste :).

Originalmente, postei um código antigo que usei, mas fiquei curioso sobre os benchmarks de Jb Evain. Eu descobri que minha solução era estúpida e lenta. Parece que o SearchBytePattern de bruno conde é o mais rápido. Eu não conseguia entender por que, especialmente, porque ele usa um método Array.Copy e Extension. Mas há provas nos testes de Jb, então parabéns ao bruno.

Eu simplifiquei os bits ainda mais, então espero que esta seja a solução mais clara e simples. (Todo o trabalho duro feito por Bruno Conde) As melhorias são:

  • Buffer.BlockCopy
  • Array.IndexOf
  • while loop em vez de um loop for
  • parâmetro de índice de início
  • convertido em método de extensão

     public static List IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex) { List positions = new List(); int i = Array.IndexOf(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(pattern)) positions.Add(i); i = Array.IndexOf(buffer, pattern[0], i + pattern.Length); } return positions; } 

Minha solução:

 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 positions = SearchBytePattern(pattern, toBeSearched); foreach (var item in positions) { Console.WriteLine("Pattern matched at pos {0}", item); } } static public List SearchBytePattern(byte[] pattern, byte[] bytes) { List positions = new List(); 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(pattern)) { positions.Add(i); i += patternLength - 1; } } } return positions; } } 

Eu estava faltando um método LINQ / resposta 🙂

 ///  /// Searches in the haystack array for the given needle using the default equality operator and returns the index at which the needle starts. ///  /// Type of the arrays. /// Sequence to operate on. /// Sequence to search for. /// Index of the needle within the haystack or -1 if the needle isn't contained. public static IEnumerable IndexOf(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; } } } } 

Esta é minha proposição, mais simples e mais rápida:

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

Minha versão da resposta de Foubar acima, que evita procurar após o final do palheiro, e permite especificar um deslocamento inicial. Assume que a agulha não está vazia ou maior que o palheiro.

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

Estes são os methods mais simples e rápidos que você pode usar, e não haveria nada mais rápido que esses. Não é seguro, mas é para isso que usamos pointers é a velocidade. Então aqui eu ofereço meus methods de extensão que eu uso busca por um único e uma lista de índices das ocorrências. Eu gostaria de dizer que este é o código mais limpo aqui.

  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 IndexesOf(this byte[] Haystack, byte[] Needle) { List Indexes = new List(); 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; } } 

Comparado com o Locate, é 1,2-1,4x mais rápido

A resposta de Jb Evain tem:

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

e, em seguida, a function IsMatch primeiro verifica se o candidate vai além do comprimento da matriz que está sendo pesquisada.

Isso seria mais eficiente se o loop for fosse codificado:

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

Neste ponto, pode-se também eliminar o teste desde o início do IsMatch , desde que você contrate através de pré-condições para nunca chamá-lo com parâmetros "ilegais".

Eu criei uma nova function usando as dicas da minha resposta e a resposta de Alnitak.

 public static List LocateSubset(Byte[] superSet, Byte[] subSet) { if ((superSet == null) || (subSet == null)) { throw new ArgumentNullException(); } if ((superSet.Length < subSet.Length) || (superSet.Length == 0) || (subSet.Length == 0)) { return new List(); } var result = new List(); Int32 currentIndex = 0; Int32 maxIndex = superSet.Length - subSet.Length; while (currentIndex < maxIndex) { Int32 matchCount = CountMatches(superSet, currentIndex, subSet); if (matchCount == subSet.Length) { result.Add(currentIndex); } currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; } } return result; } private static Int32 CountMatches(Byte[] superSet, int startIndex, Byte[] subSet) { Int32 currentOffset = 0; while (currentOffset < subSet.Length) { if (superSet[startIndex + currentOffset] != subSet[currentOffset]) { break; } currentOffset++; } return currentOffset; } 

a única parte que eu não estou tão feliz é o

  currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; } 

parte ... eu gostaria de usar um if else para evitar o -1, mas isso resulta em uma melhor predição de ramificação (embora eu não tenha certeza de que isso importará muito).

Por que tornar o simples difícil? Isso pode ser feito em qualquer idioma usando loops for. Aqui está um em C #:

 usando o sistema;
 using System.Collections.Generic;

 namespace BinarySearch
 {
     Programa de aula
     {
         static void Main (string [] args)
         {
             byte [] pattern = novo byte [] {12,3,5,76,8,0,6,125};
             byte [] toBeSearched = novo 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}; Listar ocorrences = findOccurences (toBeSearched, padrão); foreach (int ocorrência em ocorrências) { Console.WriteLine ("Correspondência encontrada começando no índice baseado em 0:" + ocorrência); } } lista estática findOccurences (byte [] haystack, byte [] agulha) { List occurences = new List (); para (int i = 0; i = palheiro.Comprimento || agulha [j]! = palheiro [k]) { encontrado = falso; pausa; } } se achado) { ocorrências. Adicionar (i - 1); i = k; } } } retornar ocorrências; } } }

obrigado por tomar o tempo …

Este é o código que eu estava usando / testando com antes de fazer minha pergunta … O motivo de eu fazer essa pergunta foi que estou certo de que não estou usando o código ideal para fazer isso … então obrigado novamente por tomar o tempo!

  private static int CountPatternMatches(byte[] pattern, byte[] bytes) { int counter = 0; for (int i = 0; i < bytes.Length; i++) { if (bytes[i] == pattern[0] && (i + pattern.Length) < bytes.Length) { for (int x = 1; x < pattern.Length; x++) { if (pattern[x] != bytes[x+i]) { break; } if (x == pattern.Length -1) { counter++; i = i + pattern.Length; } } } } return counter; } 

Alguém que veja algum erro no meu código? Isto é considerado como uma abordagem hackeada? Eu tentei quase todas as amostras que vocês postaram e parece que eu tenho algumas variações nos resultados da partida. Tenho executado meus testes com uma matriz de bytes de ~ 10 MB como minha matriz toBeSearched.

Eu usaria uma solução que faz correspondência, convertendo para uma string …

Você deve escrever uma function simples implementando o algoritmo de busca Knuth-Morris-Pratt . Esse será o algoritmo mais rápido e simples que você pode usar para encontrar os índices corretos (você pode usar o Boyer-Moore, mas isso exigirá mais configurações.

Depois de otimizar o algoritmo, você pode tentar procurar outro tipo de otimização. Mas você deve começar com o básico.

Por exemplo, a atual “mais rápida” é a solução Locate de Jb Evian.

se você olhar para o núcleo

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

Após uma correspondência do sub-algoritmo, ele começará a encontrar uma correspondência em i + 1, mas você já sabe que a primeira correspondência possível seria i + candidate.Length. Então, se você adicionar

 i += candidate.Length -2; // -2 instead of -1 because the i++ will add the last index 

será muito mais rápido quando você espera muitas ocorrências do subconjunto no superconjunto. (Bruno Conde já faz isso em sua solução)

Mas isso é apenas metade do algoritmo KNP, você também deve adicionar um parâmetro extra ao método IsMatch chamado numberOfValidMatches, que seria um parâmetro out.

isso resolveria o seguinte:

 int validMatches = 0; if (!IsMatch (self, i, candidate, out validMatches)) { i += validMatches - 1; // -1 because the i++ will do the last one continue; } 

e

 static bool IsMatch (byte [] array, int position, byte [] candidate, out int numberOfValidMatches) { numberOfValidMatches = 0; if (candidate.Length > (array.Length - position)) return false; for (i = 0; i < candidate.Length; i++) { if (array [position + i] != candidate [i]) return false; numberOfValidMatches++; } return true; } 

Um pouco de refatoração e você poderia usar o numberOfValidMatches como a variável de loop, e rewrite o loop Locate usando um tempo para evitar o -2 e -1. Mas eu só queria deixar claro como você poderia adicionar o algoritmo KMP.

A velocidade não é tudo. Você verificou a consistência?

Eu não testei todo o código listado aqui. Eu testei meu próprio código (que não era totalmente consistente, eu admito) e IndexOfSequence. Descobri que para muitos testes IndexOfSequence era um pouco mais rápido que meu código, mas com testes repetidos, descobri que era menos consistente. Em particular, parece ter mais problemas em encontrar padrões no final do array, mas também vai sentir falta deles no meio do array.

Meu código de teste não é projetado para eficiência, eu só queria ter um monte de dados randoms com algumas seqüências conhecidas dentro. Esse padrão de teste é mais ou menos como um marcador de limite em um stream de upload de formulário http. Isso é o que eu estava procurando quando eu encontrei esse código, então pensei em testá-lo com o tipo de dados que eu procuraria. Parece que quanto mais longo o padrão, mais frequentemente IndexOfSequence perderá um valor.

 private static void TestMethod() { Random rnd = new Random(DateTime.Now.Millisecond); string Pattern = "-------------------------------65498495198498"; byte[] pattern = Encoding.ASCII.GetBytes(Pattern); byte[] testBytes; int count = 3; for (int i = 0; i < 100; i++) { StringBuilder TestString = new StringBuilder(2500); TestString.Append(Pattern); byte[] buf = new byte[1000]; rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); testBytes = Encoding.ASCII.GetBytes(TestString.ToString()); List idx = IndexOfSequence(ref testBytes, pattern, 0); if (idx.Count != count) { Console.Write("change from {0} to {1} on iteration {2}: ", count, idx.Count, i); foreach (int ix in idx) { Console.Write("{0}, ", ix); } Console.WriteLine(); count = idx.Count; } } Console.WriteLine("Press ENTER to exit"); Console.ReadLine(); } 

(obviamente eu converti IndexOfSequence de uma extensão de volta para um método normal para este teste)

Aqui está uma amostra de minha saída:

 change from 3 to 2 on iteration 1: 0, 2090, change from 2 to 3 on iteration 2: 0, 1045, 2090, change from 3 to 2 on iteration 3: 0, 1045, change from 2 to 3 on iteration 4: 0, 1045, 2090, change from 3 to 2 on iteration 6: 0, 2090, change from 2 to 3 on iteration 7: 0, 1045, 2090, change from 3 to 2 on iteration 11: 0, 2090, change from 2 to 3 on iteration 12: 0, 1045, 2090, change from 3 to 2 on iteration 14: 0, 2090, change from 2 to 3 on iteration 16: 0, 1045, 2090, change from 3 to 2 on iteration 17: 0, 1045, change from 2 to 3 on iteration 18: 0, 1045, 2090, change from 3 to 1 on iteration 20: 0, change from 1 to 3 on iteration 21: 0, 1045, 2090, change from 3 to 2 on iteration 22: 0, 2090, change from 2 to 3 on iteration 23: 0, 1045, 2090, change from 3 to 2 on iteration 24: 0, 2090, change from 2 to 3 on iteration 25: 0, 1045, 2090, change from 3 to 2 on iteration 26: 0, 2090, change from 2 to 3 on iteration 27: 0, 1045, 2090, change from 3 to 2 on iteration 43: 0, 1045, change from 2 to 3 on iteration 44: 0, 1045, 2090, change from 3 to 2 on iteration 48: 0, 1045, change from 2 to 3 on iteration 49: 0, 1045, 2090, change from 3 to 2 on iteration 50: 0, 2090, change from 2 to 3 on iteration 52: 0, 1045, 2090, change from 3 to 2 on iteration 54: 0, 1045, change from 2 to 3 on iteration 57: 0, 1045, 2090, change from 3 to 2 on iteration 62: 0, 1045, change from 2 to 3 on iteration 63: 0, 1045, 2090, change from 3 to 2 on iteration 72: 0, 2090, change from 2 to 3 on iteration 73: 0, 1045, 2090, change from 3 to 2 on iteration 75: 0, 2090, change from 2 to 3 on iteration 76: 0, 1045, 2090, change from 3 to 2 on iteration 78: 0, 1045, change from 2 to 3 on iteration 79: 0, 1045, 2090, change from 3 to 2 on iteration 81: 0, 2090, change from 2 to 3 on iteration 82: 0, 1045, 2090, change from 3 to 2 on iteration 85: 0, 2090, change from 2 to 3 on iteration 86: 0, 1045, 2090, change from 3 to 2 on iteration 89: 0, 2090, change from 2 to 3 on iteration 90: 0, 1045, 2090, change from 3 to 2 on iteration 91: 0, 2090, change from 2 to 1 on iteration 92: 0, change from 1 to 3 on iteration 93: 0, 1045, 2090, change from 3 to 1 on iteration 99: 0, 

Eu não quero pegar no IndexOfSequence, aconteceu de ser o que eu comecei a trabalhar hoje. Percebi no final do dia que parecia que faltavam padrões nos dados, então escrevi meu próprio padrão de correspondência hoje à noite. Não é tão rápido embora. Vou ajustá-lo um pouco mais para ver se posso obtê-lo 100% consistente antes de publicá-lo.

Eu só queria lembrar a todos que eles deveriam testar coisas como essa para garantir que eles fornecessem bons resultados repetíveis antes de você confiar neles no código de produção.

Eu tentei várias soluções e acabei modificando o SearchBytePattern. Eu testei em uma sequência de 30k e é rápido 🙂

  static public int SearchBytePattern(byte[] pattern, byte[] bytes) { int matches = 0; for (int i = 0; i < bytes.Length; i++) { if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length) { bool ismatch = true; for (int j = 1; j < pattern.Length && ismatch == true; j++) { if (bytes[i + j] != pattern[j]) ismatch = false; } if (ismatch) { matches++; i += pattern.Length - 1; } } } return matches; } 

Deixe-me saber a sua opinião.

Aqui está uma solução que eu criei. Incluí notas que encontrei ao longo do caminho com a implementação. Pode combinar para a frente, para trás e com quantidades de remessa diferentes (em / dec), por exemplo, direção; começando em qualquer deslocamento no palheiro.

Qualquer input seria incrível!

  ///  /// Matches a byte array to another byte array /// forwards or reverse ///  /// byte array /// start offset /// max length /// byte array /// to move each iteration /// true if all bytes match, otherwise false internal static bool Matches(ref byte[] a, int offset, int len, ref byte[] b, int direction = 1) { #region Only Matched from offset Within a and b, could not differ, eg if you wanted to mach in reverse for only part of a in some of b that would not work //if (direction == 0) throw new ArgumentException("direction"); //for (; offset < len; offset += direction) if (a[offset] != b[offset]) return false; //return true; #endregion //Will match if b contains len of a and return aa index of positive value return IndexOfBytes(ref a, ref offset, len, ref b, len) != -1; } ///Here is the Implementation code ///  /// Swaps two integers without using a temporary variable ///  ///  ///  internal static void Swap(ref int a, ref int b) { a ^= b; b ^= a; a ^= b; } ///  /// Swaps two bytes without using a temporary variable ///  ///  ///  internal static void Swap(ref byte a, ref byte b) { a ^= b; b ^= a; a ^= b; } ///  /// Can be used to find if a array starts, ends spot Matches or compltely contains a sub byte array /// Set checkLength to the amount of bytes from the needle you want to match, start at 0 for forward searches start at hayStack.Lenght -1 for reverse matches ///  /// Needle /// Start in Haystack /// Length of required match /// Haystack /// Which way to move the iterator /// Index if found, otherwise -1 internal static int IndexOfBytes(ref byte[] needle, ref int offset, int checkLength, ref byte[] haystack, int direction = 1) { //If the direction is == 0 we would spin forever making no progress if (direction == 0) throw new ArgumentException("direction"); //Cache the length of the needle and the haystack, setup the endIndex for a reverse search int needleLength = needle.Length, haystackLength = haystack.Length, endIndex = 0, workingOffset = offset; //Allocate a value for the endIndex and workingOffset //If we are going forward then the bound is the haystackLength if (direction >= 1) endIndex = haystackLength; #region [Optomization - Not Required] //{ //I though this was required for partial matching but it seems it is not needed in this form //workingOffset = needleLength - checkLength; //} #endregion else Swap(ref workingOffset, ref endIndex); #region [Optomization - Not Required] //{ //Otherwise we are going in reverse and the endIndex is the needleLength - checkLength //I though the length had to be adjusted but it seems it is not needed in this form //endIndex = needleLength - checkLength; //} #endregion #region [Optomized to above] //Allocate a value for the endIndex //endIndex = direction >= 1 ? haystackLength : needleLength - checkLength, //Determine the workingOffset //workingOffset = offset > needleLength ? offset : needleLength; //If we are doing in reverse swap the two //if (workingOffset > endIndex) Swap(ref workingOffset, ref endIndex); //Else we are going in forward direction do the offset is adjusted by the length of the check //else workingOffset -= checkLength; //Start at the checkIndex (workingOffset) every search attempt #endregion //Save the checkIndex (used after the for loop is done with it to determine if the match was checkLength long) int checkIndex = workingOffset; #region [For Loop Version] ///Optomized with while (single op) ///for (int checkIndex = workingOffset; checkIndex < endIndex; offset += direction, checkIndex = workingOffset) ///{ ///Start at the checkIndex /// While the checkIndex < checkLength move forward /// If NOT (the needle at the checkIndex matched the haystack at the offset + checkIndex) BREAK ELSE we have a match continue the search /// for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; /// If the match was the length of the check /// if (checkIndex == checkLength) return offset; //We are done matching ///} #endregion //While the checkIndex < endIndex while (checkIndex < endIndex) { for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; //If the match was the length of the check if (checkIndex == checkLength) return offset; //We are done matching //Move the offset by the direction, reset the checkIndex to the workingOffset offset += direction; checkIndex = workingOffset; } //We did not have a match with the given options return -1; } 

Aqui está a minha solução (não a mais eficaz). Ele se baseia no fato de que a conversão de bytes / latin-1 é sem perdas, o que não é verdadeiro para conversões de bytes / ASCII ou bytes / UTF8.

Suas vantagens são o It Works ™ para qualquer valor de byte (algumas outras soluções funcionam incorretamente com bytes 0x80-0xff) e podem ser estendidas para executar uma correspondência de regex mais avançada.

 using System; using System.Collections.Generic; using System.Text; using System.Text.RegularExpressions; class C { public static void Main() { byte[] data = {0, 100, 0, 255, 100, 0, 100, 0, 255}; byte[] pattern = {0, 255}; foreach (int i in FindAll(data, pattern)) { Console.WriteLine(i); } } public static IEnumerable FindAll( byte[] haystack, byte[] needle ) { // bytes <-> latin-1 conversion is lossless Encoding latin1 = Encoding.GetEncoding("iso-8859-1"); string sHaystack = latin1.GetString(haystack); string sNeedle = latin1.GetString(needle); for (Match m = Regex.Match(sHaystack, Regex.Escape(sNeedle)); m.Success; m = m.NextMatch()) { yield return m.Index; } } } 

Estou um pouco atrasado para a festa Que tal usar o algoritmo Boyer Moore, mas procure por bytes em vez de seqüências de caracteres. c # código abaixo.

EyeCode Inc.

 class Program { static void Main(string[] args) { byte[] text = new byte[] {12,3,5,76,8,0,6,125,23,36,43,76,125,56,34,234,12,4,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,123}; byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; BoyerMoore tmpSearch = new BoyerMoore(pattern,text); Console.WriteLine(tmpSearch.Match()); Console.ReadKey(); } public class BoyerMoore { private static int ALPHABET_SIZE = 256; private byte[] text; private byte[] pattern; private int[] last; private int[] match; private int[] suffix; public BoyerMoore(byte[] pattern, byte[] text) { this.text = text; this.pattern = pattern; last = new int[ALPHABET_SIZE]; match = new int[pattern.Length]; suffix = new int[pattern.Length]; } /** * Searches the pattern in the text. * returns the position of the first occurrence, if found and -1 otherwise. */ public int Match() { // Preprocessing ComputeLast(); ComputeMatch(); // Searching int i = pattern.Length - 1; int j = pattern.Length - 1; while (i < text.Length) { if (pattern[j] == text[i]) { if (j == 0) { return i; } j--; i--; } else { i += pattern.Length - j - 1 + Math.Max(j - last[text[i]], match[j]); j = pattern.Length - 1; } } return -1; } /** * Computes the function last and stores its values in the array last. * last(Char ch) = the index of the right-most occurrence of the character ch * in the pattern; * -1 if ch does not occur in the pattern. */ private void ComputeLast() { for (int k = 0; k < last.Length; k++) { last[k] = -1; } for (int j = pattern.Length-1; j >= 0; j--) { if (last[pattern[j]] < 0) { last[pattern[j]] = j; } } } /** * Computes the function match and stores its values in the array match. * match(j) = min{ s | 0 < s <= j && p[js]!=p[j] * && p[j-s+1]..p[ms-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, else * min{ s | j+1 <= s <= m * && p[0]..p[ms-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, * m, otherwise, * where p is the pattern and m is its length. */ private void ComputeMatch() { /* Phase 1 */ for (int j = 0; j < match.Length; j++) { match[j] = match.Length; } //O(m) ComputeSuffix(); //O(m) /* Phase 2 */ //Uses an auxiliary array, backwards version of the KMP failure function. //suffix[i] = the smallest j > i st p[j..m-1] is a prefix of p[i..m-1], //if there is no such j, suffix[i] = m //Compute the smallest shift s, such that 0 < s <= j and //p[js]!=p[j] and p[j-s+1..ms-1] is suffix of p[j+1..m-1] or j == m-1}, // if such s exists, for (int i = 0; i < match.Length - 1; i++) { int j = suffix[i + 1] - 1; // suffix[i+1] <= suffix[i] + 1 if (suffix[i] > j) { // therefore pattern[i] != pattern[j] match[j] = j - i; } else {// j == suffix[i] match[j] = Math.Min(j - i + match[i], match[j]); } } /* Phase 3 */ //Uses the suffix array to compute each shift s such that //p[0..ms-1] is a suffix of p[j+1..m-1] with j < s < m //and stores the minimum of this shift and the previously computed one. if (suffix[0] < pattern.Length) { for (int j = suffix[0] - 1; j >= 0; j--) { if (suffix[0] < match[j]) { match[j] = suffix[0]; } } { int j = suffix[0]; for (int k = suffix[j]; k < pattern.Length; k = suffix[k]) { while (j < k) { if (match[j] > k) { match[j] = k; } j++; } } } } } /** * Computes the values of suffix, which is an auxiliary array, * backwards version of the KMP failure function. * * suffix[i] = the smallest j > i st p[j..m-1] is a prefix of p[i..m-1], * if there is no such j, suffix[i] = m, ie * p[suffix[i]..m-1] is the longest prefix of p[i..m-1], if suffix[i] < m. */ private void ComputeSuffix() { suffix[suffix.Length-1] = suffix.Length; int j = suffix.Length - 1; for (int i = suffix.Length - 2; i >= 0; i--) { while (j < suffix.Length - 1 && !pattern[j].Equals(pattern[i])) { j = suffix[j + 1] - 1; } if (pattern[j] == pattern[i]) { j--; } suffix[i] = j + 1; } } } } 

Here’s a simple code i wrote using only basic data types: (It returns the index of first occurance)

 private static int findMatch(byte[] data, byte[] pattern) { if(pattern.length > data.length){ return -1; } for(int i = 0; i 

Just another answer that is easy to follow and pretty efficient for a O(n) type of operation without using unsafe code or copying parts of the source arrays.

Be sure to test. Some of the suggestions found on this topic are susceptible to gotta situations.

  static void Main(string[] args) { // 1 1 1 1 1 1 1 1 1 1 2 2 2 // 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 byte[] buffer = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 5, 5, 0, 5, 5, 1, 2 }; byte[] beginPattern = new byte[] { 1, 0, 2 }; byte[] middlePattern = new byte[] { 8, 9, 10 }; byte[] endPattern = new byte[] { 9, 10, 11 }; byte[] wholePattern = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; byte[] noMatchPattern = new byte[] { 7, 7, 7 }; int beginIndex = ByteArrayPatternIndex(buffer, beginPattern); int middleIndex = ByteArrayPatternIndex(buffer, middlePattern); int endIndex = ByteArrayPatternIndex(buffer, endPattern); int wholeIndex = ByteArrayPatternIndex(buffer, wholePattern); int noMatchIndex = ByteArrayPatternIndex(buffer, noMatchPattern); } ///  /// Returns the index of the first occurrence of a byte array within another byte array ///  /// The byte array to be searched /// The byte array that contains the pattern to be found /// If buffer contains pattern then the index of the first occurrence of pattern within buffer; otherwise, -1 public static int ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern return i; else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } } return -1; } ///  /// Returns the indexes of each occurrence of a byte array within another byte array ///  /// The byte array to be searched /// The byte array that contains the pattern to be found /// If buffer contains pattern then the indexes of the occurrences of pattern within buffer; otherwise, null /// A single byte in the buffer array can only be part of one match. For example, if searching for 1,2,1 in 1,2,1,2,1 only zero would be returned. public static int[] ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { List indexes = new List(); int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern indexes.Add(i); else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } if (indexes.Count > 0) return indexes.ToArray(); } return null; } 

You can use ORegex:

 var oregex = new ORegex("{0}{1}{2}", x=> x==12, x=> x==3, x=> x==5); var toSearch = new byte[]{1,1,12,3,5,1,12,3,5,5,5,5}; var found = oregex.Matches(toSearch); 

Will be found two matches:

 i:2;l:3 i:6;l:3 

Complexity: O(n*m) in worst case, in real life it is O(n) because of internal state machine. It is faster than .NET Regex in some cases. It is compact, fast and designed especialy for array pattern matching.

I tried to understand Sanchez’s proposal and make faster search.Below code’s performance nearly equal.But code is more understandable.

 public int Search3(byte[] src, byte[] pattern) { int index = -1; for (int i = 0; i < src.Length; i++) { if (src[i] != pattern[0]) { continue; } else { bool isContinoue = true; for (int j = 1; j < pattern.Length; j++) { if (src[++i] != pattern[j]) { isContinoue = true; break; } if(j == pattern.Length - 1) { isContinoue = false; } } if ( ! isContinoue) { index = i-( pattern.Length-1) ; break; } } } return index; } 

This is my own approach on the topic. I used pointers to ensure that it is faster on larger arrays. This function will return the first occurence of the sequence (which is what I needed in my own case).

I am sure you can modify it a little bit in order to return a list with all occurences.

What I do is fairly simple. I loop through the source array (haystack) until I find the first byte of the pattern (needle). When the first byte is found, I continue checking separately if the next bytes match the next bytes of the pattern. If not, I continue searching as normal, from the index (in the haystack) I was previously on, before trying to match the needle.

So here’s the code:

  public unsafe int IndexOfPattern(byte[] src, byte[] pattern) { fixed(byte *srcPtr = &src[0]) fixed (byte* patternPtr = &pattern[0]) { for (int x = 0; x < src.Length; x++) { byte currentValue = *(srcPtr + x); if (currentValue != *patternPtr) continue; bool match = false; for (int y = 0; y < pattern.Length; y++) { byte tempValue = *(srcPtr + x + y); if (tempValue != *(patternPtr + y)) { match = false; break; } match = true; } if (match) return x; } } return -1; } 

Safe code below:

  public int IndexOfPatternSafe(byte[] src, byte[] pattern) { for (int x = 0; x < src.Length; x++) { byte currentValue = src[x]; if (currentValue != pattern[0]) continue; bool match = false; for (int y = 0; y < pattern.Length; y++) { byte tempValue = src[x + y]; if (tempValue != pattern[y]) { match = false; break; } match = true; } if (match) return x; } return -1; } 

You can put the byte array into String and run match by IndexOf. Or you can at least reuse existing algorithms on string matching.

  [STAThread] static void Main(string[] args) { 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}; string needle, haystack; unsafe { fixed(byte * p = pattern) { needle = new string((SByte *) p, 0, pattern.Length); } // fixed fixed (byte * p2 = toBeSearched) { haystack = new string((SByte *) p2, 0, toBeSearched.Length); } // fixed int i = haystack.IndexOf(needle, 0); System.Console.Out.WriteLine(i); } } 

toBeSearched.Except(pattern) will return you differences toBeSearched.Intersect(pattern) will produce set of intersections Generally, you should look into extended methods within Linq extensions