가장 좋은 방법은

Question

가 어떻게 주어진 바이트 순서가 시작되는 (를 선두)를 System.Stream의 위치를 ​​찾을 수있는 가장 좋은 방법은 어떻게 생각하십니까 시작 추신 가장 간단하면서도 빠른 솔루션이 선호됩니다. :)

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으로 유지해야 스트림의 '다음 바이트'가 일치하는 것을 확인한 후에는 나머지를 확인한 다음 다시 "다음하지만 1"바이트는 실제 일치가 아닌 경우입니다.

그것은 조금 서투른 당신이 무엇이든 될 가능성이 높습니다

, 솔직히 말해서 :(

Answer 3

당신이 바이트의 또 다른 시퀀스와 같은 스트림을 치료하는 경우 문자열 검색을 수행 것처럼, 당신은 그냥 검색 할 수 있습니다. Wikipedia가있다 Boyer-Moore는 이것에 대한 좋은 간단한 알고리즘입니다.

여기에 Java로 정리 한 간단한 해킹이 있습니다. Boyer-Moore가 아니라면 꽤 가까워요.)

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의 경우 시퀀스의 일부가 한 블록에 읽혀지고 나머지 블록이 절반 인 경우 대답이 실패합니다. 예를 들어 12345를 입력하고 23을 검색하면 12가 읽히고 일치하지 않으면 34가 읽히고 match, etc ... net 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; 
     } 
    } 
}