Szukaj tablicą lub listy na liście

Question

Czy

List<byte> lbyte 

Czy

byte[] searchBytes 

Jak mogę przeszukiwać lbyte na nie tylko jeden bajt, ale dla indeksu z searchBytes?
E.G.

Int32 index = lbyte.FirstIndexOf(searchBytes); 

Oto brutalna siła, którą wymyśliłem.
Nie ten spektakl, którego szukam.

public static Int32 ListIndexOfArray(List<byte> lb, byte[] sbs) 
{ 
    if (sbs == null) return -1; 
    if (sbs.Length == 0) return -1; 
    if (sbs.Length > 8) return -1; 
    if (sbs.Length == 1) return lb.FirstOrDefault(x => x == sbs[0]); 
    Int32 sbsLen = sbs.Length; 
    Int32 sbsCurMatch = 0; 
    for (int i = 0; i < lb.Count; i++) 
    { 
     if (lb[i] == sbs[sbsCurMatch]) 
     { 
      sbsCurMatch++; 
      if (sbsCurMatch == sbsLen) 
      { 
       //int index = lb.FindIndex(e => sbs.All(f => f.Equals(e))); // fails to find a match 
       IndexOfArray = i - sbsLen + 1; 
       return; 
      } 
     } 
     else 
     { 
      sbsCurMatch = 0; 
     } 
    } 
    return -1; 
} 

Answer 1

Może Ci się przydać przydatna Boyer-Moore algorithm. Konwertuj listę do tablicy i wyszukiwania. Kod algorytmu jest pobierany z this post.

static int SimpleBoyerMooreSearch(byte[] haystack, byte[] needle) 
{ 
    int[] lookup = new int[256]; 
    for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; } 

    for (int i = 0; i < needle.Length; i++) 
    { 
     lookup[needle[i]] = needle.Length - i - 1; 
    } 

    int index = needle.Length - 1; 
    var lastByte = needle.Last(); 
    while (index < haystack.Length) 
    { 
     var checkByte = haystack[index]; 
     if (haystack[index] == lastByte) 
     { 
      bool found = true; 
      for (int j = needle.Length - 2; j >= 0; j--) 
      { 
       if (haystack[index - needle.Length + j + 1] != needle[j]) 
       { 
        found = false; 
        break; 
       } 
      } 

      if (found) 
       return index - needle.Length + 1; 
      else 
       index++; 
     } 
     else 
     { 
      index += lookup[checkByte]; 
     } 
    } 
    return -1; 
} 

Możesz następnie wyszukiwać w ten sposób. Jeśli lbyte pozostanie stały po określonym czasie, możesz po prostu przekształcić go w tablicę i przekazać ją.

//index is returned, or -1 if 'searchBytes' is not found 
int startIndex = SimpleBoyerMooreSearch(lbyte.ToArray(), searchBytes); 

Aktualizacja oparta na komentarzu. Oto, co oznacza, że ​​realizacja macierze i listy (i cokolwiek innego, który implementuje IList mogą być przekazywane) IList

static int SimpleBoyerMooreSearch(IList<byte> haystack, IList<byte> needle) 
{ 
    int[] lookup = new int[256]; 
    for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Count; } 

    for (int i = 0; i < needle.Count; i++) 
    { 
     lookup[needle[i]] = needle.Count - i - 1; 
    } 

    int index = needle.Count - 1; 
    var lastByte = needle[index]; 
    while (index < haystack.Count) 
    { 
     var checkByte = haystack[index]; 
     if (haystack[index] == lastByte) 
     { 
      bool found = true; 
      for (int j = needle.Count - 2; j >= 0; j--) 
      { 
       if (haystack[index - needle.Count + j + 1] != needle[j]) 
       { 
        found = false; 
        break; 
       } 
      } 

      if (found) 
       return index - needle.Count + 1; 
      else 
       index++; 
     } 
     else 
     { 
      index += lookup[checkByte]; 
     } 
    } 
    return -1; 
} 

Ponieważ macierze i listy wdrożyć IList, nie ma potrzeby konwersji podczas wywoływania go w Twoim przypadku.

int startIndex = SimpleBoyerMooreSearch(lbyte, searchBytes); 

Answer 2

Brutalna siła jest zawsze opcją. Choć powolny w porównaniu do innych metod, w praktyce zwykle nie jest tak źle. Jest łatwy do wdrożenia i całkiem do przyjęcia, jeśli lbyte nie jest ogromny i nie ma danych patologicznych.

To ta sama koncepcja, co brute force string searching.

Answer 3

Innym sposobem można zrobić z lambda wyrażenia

int index = lbyte.FindIndex(e => searchBytes.All(i => i.Equals(e));