Лучший способ найти позицию в потоке, где заданная последовательность байт начинается

Question

Как вы думаете, что это лучший способ найти позицию в System.Stream, где начинается данная последовательность байт (первое вхождение):

public static long FindPosition(Stream stream, byte[] byteSequence) 
{ 
    long position = -1; 

    /// ??? 
    return position; 
} 

PS Предлагается самое простое, но самое быстрое решение. :)

Answer 1

Я добрался до является решением.

Я сделал несколько тестов с файлом ASCII, который был 3.050 KB и 38803 lines. С поиском bytearray из 22 bytes в последней строке файла у меня есть результат примерно в 2.28 секунд (на медленной/старой машине).

public static long FindPosition(Stream stream, byte[] byteSequence) 
{ 
    if (byteSequence.Length > stream.Length) 
     return -1; 

    byte[] buffer = new byte[byteSequence.Length]; 

    using (BufferedStream bufStream = new BufferedStream(stream, byteSequence.Length)) 
    { 
     int i; 
     while ((i = bufStream.Read(buffer, 0, byteSequence.Length)) == byteSequence.Length) 
     { 
      if (byteSequence.SequenceEqual(buffer)) 
       return bufStream.Position - byteSequence.Length; 
      else 
       bufStream.Position -= byteSequence.Length - PadLeftSequence(buffer, byteSequence); 
     } 
    } 

    return -1; 
} 

private static int PadLeftSequence(byte[] bytes, byte[] seqBytes) 
{ 
    int i = 1; 
    while (i < bytes.Length) 
    { 
     int n = bytes.Length - i; 
     byte[] aux1 = new byte[n]; 
     byte[] aux2 = new byte[n]; 
     Array.Copy(bytes, i, aux1, 0, n); 
     Array.Copy(seqBytes, aux2, n); 
     if (aux1.SequenceEqual(aux2)) 
      return i; 
     i++; 
    } 
    return i; 
} 

Answer 2

Вам необходимо сохранить буфер того же размера, что и byteSequence, так что, как только вы обнаружите, что «следующий байт» в потоке совпадает, вы можете проверить остальные, но затем вернуться к «следующий, но один» байт, если это не настоящий матч.

Это, вероятно, будет немного неудобным, что вы делаете, если честно :(

Answer 3

Если рассматривать поток как другую последовательность байт, вы можете просто искать его, как вы делали строку поиск. Wikipedia имеет отличная статья о том, что Boyer-Moore - хороший и простой алгоритм для этого.

Вот быстрый хак, который я собрал на Java. Он работает, и это очень близко, если не Бойер-Мур. Надеюсь, это поможет;)

public static final int BUFFER_SIZE = 32; 

public static int [] buildShiftArray(byte [] byteSequence){ 
    int [] shifts = new int[byteSequence.length]; 
    int [] ret; 
    int shiftCount = 0; 
    byte end = byteSequence[byteSequence.length-1]; 
    int index = byteSequence.length-1; 
    int shift = 1; 

    while(--index >= 0){ 
     if(byteSequence[index] == end){ 
      shifts[shiftCount++] = shift; 
      shift = 1; 
     } else { 
      shift++; 
     } 
    } 
    ret = new int[shiftCount]; 
    for(int i = 0;i < shiftCount;i++){ 
     ret[i] = shifts[i]; 
    } 
    return ret; 
} 

public static byte [] flushBuffer(byte [] buffer, int keepSize){ 
    byte [] newBuffer = new byte[buffer.length]; 
    for(int i = 0;i < keepSize;i++){ 
     newBuffer[i] = buffer[buffer.length - keepSize + i]; 
    } 
    return newBuffer; 
} 

public static int findBytes(byte [] haystack, int haystackSize, byte [] needle, int [] shiftArray){ 
    int index = needle.length; 
    int searchIndex, needleIndex, currentShiftIndex = 0, shift; 
    boolean shiftFlag = false; 

    index = needle.length; 
    while(true){ 
     needleIndex = needle.length-1; 
     while(true){ 
      if(index >= haystackSize) 
       return -1; 
      if(haystack[index] == needle[needleIndex]) 
       break; 
      index++; 
     } 
     searchIndex = index; 
     needleIndex = needle.length-1; 
     while(needleIndex >= 0 && haystack[searchIndex] == needle[needleIndex]){ 
      searchIndex--; 
      needleIndex--; 
     } 
     if(needleIndex < 0) 
      return index-needle.length+1; 
     if(shiftFlag){ 
      shiftFlag = false; 
      index += shiftArray[0]; 
      currentShiftIndex = 1; 
     } else if(currentShiftIndex >= shiftArray.length){ 
      shiftFlag = true; 
      index++; 
     } else{ 
      index += shiftArray[currentShiftIndex++]; 
     }   
    } 
} 

public static int findBytes(InputStream stream, byte [] needle){ 
    byte [] buffer = new byte[BUFFER_SIZE]; 
    int [] shiftArray = buildShiftArray(needle); 
    int bufferSize, initBufferSize; 
    int offset = 0, init = needle.length; 
    int val; 

    try{ 
     while(true){ 
      bufferSize = stream.read(buffer, needle.length-init, buffer.length-needle.length+init); 
      if(bufferSize == -1) 
       return -1; 
      if((val = findBytes(buffer, bufferSize+needle.length-init, needle, shiftArray)) != -1) 
       return val+offset; 
      buffer = flushBuffer(buffer, needle.length); 
      offset += bufferSize-init; 
      init = 0; 
     } 
    } catch (IOException e){ 
     e.printStackTrace(); 
    } 
    return -1; 
} 

Answer 4

Бит старый вопрос, но вот мой ответ. Я обнаружил, что блоки чтения, а затем поиск в них крайне неэффективны, чем просто чтение по одному и оттуда.

Также, IIRC, принятый ответ завершился неудачно, если часть последовательности была в одном блоке, а половина - в другом - ex, учитывая 12345, ища 23, он будет читать 12, не соответствует, а затем читать 34, а не матч и т. д., однако, не пробовали, видя, что для этого требуется чистая версия 4.0. Во всяком случае, это намного проще и, вероятно, намного быстрее.

static long ReadOneSrch(Stream haystack, byte[] needle) 
{ 
    int b; 
    long i = 0; 
    while ((b = haystack.ReadByte()) != -1) 
    { 
     if (b == needle[i++]) 
     { 
      if (i == needle.Length) 
       return haystack.Position - needle.Length; 
     } 
     else 
      i = b == needle[0] ? 1 : 0; 
    } 

    return -1; 
} 

Answer 5

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

var afterSequence = stream.ScanUntilFound(byteSequence); 
var beforeSequence = afterSequence - byteSequence.Length; 

Вот StreamExtensions.cs

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace System 
{ 

    static class StreamExtensions 
    { 
     /// <summary> 
     /// Advances the supplied stream until the given searchBytes are found, without advancing too far (consuming any bytes from the stream after the searchBytes are found). 
     /// Regarding efficiency, if the stream is network or file, then MEMORY/CPU optimisations will be of little consequence here. 
     /// </summary> 
     /// <param name="stream">The stream to search in</param> 
     /// <param name="searchBytes">The byte sequence to search for</param> 
     /// <returns></returns> 
     public static int ScanUntilFound(this Stream stream, byte[] searchBytes) 
     { 
      // For this class code comments, a common example is assumed: 
      // searchBytes are {1,2,3,4} or 1234 for short 
      // # means value that is outside of search byte sequence 

      byte[] streamBuffer = new byte[searchBytes.Length]; 
      int nextRead = searchBytes.Length; 
      int totalScannedBytes = 0; 

      while (true) 
      { 
       FillBuffer(stream, streamBuffer, nextRead); 
       totalScannedBytes += nextRead; //this is only used for final reporting of where it was found in the stream 

       if (ArraysMatch(searchBytes, streamBuffer, 0)) 
        return totalScannedBytes; //found it 

       nextRead = FindPartialMatch(searchBytes, streamBuffer); 
      } 
     } 

     /// <summary> 
     /// Check all offsets, for partial match. 
     /// </summary> 
     /// <param name="searchBytes"></param> 
     /// <param name="streamBuffer"></param> 
     /// <returns>The amount of bytes which need to be read in, next round</returns> 
     static int FindPartialMatch(byte[] searchBytes, byte[] streamBuffer) 
     { 
      // 1234 = 0 - found it. this special case is already catered directly in ScanUntilFound    
      // #123 = 1 - partially matched, only missing 1 value 
      // ##12 = 2 - partially matched, only missing 2 values 
      // ###1 = 3 - partially matched, only missing 3 values 
      // #### = 4 - not matched at all 

      for (int i = 1; i < searchBytes.Length; i++) 
      { 
       if (ArraysMatch(searchBytes, streamBuffer, i)) 
       { 
        // EG. Searching for 1234, have #123 in the streamBuffer, and [i] is 1 
        // Output: 123#, where # will be read using FillBuffer next. 
        Array.Copy(streamBuffer, i, streamBuffer, 0, searchBytes.Length - i); 
        return i; //if an offset of [i], makes a match then only [i] bytes need to be read from the stream to check if there's a match 
       } 
      } 

      return 4; 
     } 

     /// <summary> 
     /// Reads bytes from the stream, making sure the requested amount of bytes are read (streams don't always fulfill the full request first time) 
     /// </summary> 
     /// <param name="stream">The stream to read from</param> 
     /// <param name="streamBuffer">The buffer to read into</param> 
     /// <param name="bytesNeeded">How many bytes are needed. If less than the full size of the buffer, it fills the tail end of the streamBuffer</param> 
     static void FillBuffer(Stream stream, byte[] streamBuffer, int bytesNeeded) 
     { 
      // EG1. [123#] - bytesNeeded is 1, when the streamBuffer contains first three matching values, but now we need to read in the next value at the end 
      // EG2. [####] - bytesNeeded is 4 

      var bytesAlreadyRead = streamBuffer.Length - bytesNeeded; //invert 
      while (bytesAlreadyRead < streamBuffer.Length) 
      { 
       bytesAlreadyRead += stream.Read(streamBuffer, bytesAlreadyRead, streamBuffer.Length - bytesAlreadyRead); 
      } 
     } 

     /// <summary> 
     /// Checks if arrays match exactly, or with offset. 
     /// </summary> 
     /// <param name="searchBytes">Bytes to search for. Eg. [1234]</param> 
     /// <param name="streamBuffer">Buffer to match in. Eg. [#123] </param> 
     /// <param name="startAt">When this is zero, all bytes are checked. Eg. If this value 1, and it matches, this means the next byte in the stream to read may mean a match</param> 
     /// <returns></returns> 
     static bool ArraysMatch(byte[] searchBytes, byte[] streamBuffer, int startAt) 
     { 
      for (int i = 0; i < searchBytes.Length - startAt; i++) 
      { 
       if (searchBytes[i] != streamBuffer[i + startAt]) 
        return false; 
      } 
      return true; 
     } 
    } 
}