modo migliore per trovare la posizione nel torrente dove data sequenza di byte inizia

Question

Come pensi qual è il modo migliore per trovare la posizione in cui inizia System.Stream data sequenza di byte (prima occorrenza):

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

    /// ??? 
    return position; 
} 

PS La soluzione più semplice ma più veloce è preffered. :)

Answer 1

Ho raggiunto th è una soluzione.

Ho eseguito alcuni benchmark con un file ASCII che era 3.050 KB e 38803 lines. Con una ricerca bytearray di 22 bytes nell'ultima riga del file ho ottenuto il risultato in circa 2.28 secondi (in una macchina lenta/vecchia).

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

Fondamentalmente è necessario mantenere un buffer delle stesse dimensioni di byteSequence in modo che, una volta rilevato che il "byte successivo" nello stream corrisponda, è possibile controllare il resto, ma poi tornare al "next but one" byte se non è una corrispondenza effettiva.

E 'probabile che sia un po' laborioso qualunque cosa tu faccia, ad essere onesti :(

Answer 3

Se trattate il flusso come un altro sequenza di byte, si può solo cercare è come se stessi facendo uno stringa di ricerca. Wikipedia ha Boyer-Moore è un buon e semplice algoritmo per questo:

Ecco un rapido trucco che ho messo insieme in Java: funziona ed è piuttosto vicino se non Boyer-Moore. Spero che sia d'aiuto;)

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

Vecchia domanda, ma ecco la mia risposta. Ho scoperto che i blocchi di lettura e la ricerca in esso sono estremamente inefficienti rispetto alla semplice lettura di uno alla volta e passando da lì.

Inoltre, IIRC, la risposta accettata fallirebbe se parte della sequenza fosse in un blocco letto e metà in un altro - ex, dato 12345, cercando 23, si leggerebbe 12, non corrisponde, quindi legge 34, non match, ecc ... non ho provato, però, visto che richiede net 4.0. In ogni caso, è molto più semplice e probabilmente molto più veloce.

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

Avevo bisogno di farlo da solo, avevo già iniziato, e non mi piacevano le soluzioni di cui sopra. In particolare, avevo bisogno di trovare dove finisce la sequenza di byte di ricerca. Nella mia situazione, ho bisogno di fare avanzare velocemente lo stream fino a dopo quella sequenza di byte. Ma è possibile utilizzare la mia soluzione per questa domanda anche:

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

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