반응형
byte [] 배열 패턴 검색
누구나 byte [] 배열에서 바이트 패턴을 검색 / 일치 한 다음 위치를 반환하는 좋고 효과적인 방법을 알고 있습니다.
예를 들면
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}
문자열 생성, 배열 복사 또는 안전하지 않은 코드를 포함하지 않는 것을 제안 할 수 있습니다.
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<int> ();
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);
}
}
편집 (IAbstract에 의해) - 답변이 아니므 로 게시물 내용을 여기로 이동
호기심으로 저는 다른 답변으로 작은 벤치 마크를 만들었습니다.
다음은 백만 번 반복 한 결과입니다.
solution [Locate]: 00:00:00.7714027
solution [FindAll]: 00:00:03.5404399
solution [SearchBytePattern]: 00:00:01.1105190
solution [MatchBytePattern]: 00:00:03.0658212
LINQ 메서드를 사용합니다 .
public static IEnumerable<int> 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;
}
}
}
아주 간단합니다!
효율적인 Boyer-Moore 알고리즘을 사용합니다 .
문자열이있는 문자열을 찾도록 설계되었지만이를 바이트 배열에 투영하려면 상상력이 거의 필요하지 않습니다.
일반적으로 가장 좋은 대답은 다음과 같습니다. 원하는 문자열 검색 알고리즘을 사용하십시오. :).
원래 내가 사용한 오래된 코드를 게시했지만 Jb Evain의 벤치 마크 에 대해 궁금했습니다 . 내 솔루션이 어리석은 느리다는 것을 알았습니다. bruno conde의 SearchBytePattern 이 가장 빠른 것 같습니다. 특히 그가 Array.Copy 및 Extension 메서드를 사용하기 때문에 이유를 알 수 없습니다. 그러나 Jb의 테스트에는 증거가 있으므로 브루노에게 찬사를 보냅니다.
비트를 더 단순화했기 때문에 이것이 가장 명확하고 간단한 솔루션이되기를 바랍니다. (bruno conde의 모든 노력) 개선 사항은 다음과 같습니다.
- Buffer.BlockCopy
- Array.IndexOf <바이트>
- for 루프 대신 while 루프
- 시작 색인 매개 변수
확장 방법으로 변환
public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex) { List<int> positions = new List<int>(); int i = Array.IndexOf<byte>(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<byte>(pattern)) positions.Add(i); i = Array.IndexOf<byte>(buffer, pattern[0], i + 1); } return positions; }
while블록 의 마지막 문 i = Array.IndexOf<byte>(buffer, pattern[0], i + 1);은 i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length);. Johan의 의견을보십시오. 간단한 테스트로 다음을 증명할 수 있습니다.
byte[] pattern = new byte[] {1, 2};
byte[] toBeSearched = new byte[] { 1, 1, 2, 1, 12 };
을 사용 i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length);하면 아무것도 반환되지 않습니다. i = Array.IndexOf<byte>(buffer, pattern[0], i + 1);올바른 결과를 반환합니다.
내 솔루션 :
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<int> positions = SearchBytePattern(pattern, toBeSearched);
foreach (var item in positions)
{
Console.WriteLine("Pattern matched at pos {0}", item);
}
}
static public List<int> SearchBytePattern(byte[] pattern, byte[] bytes)
{
List<int> positions = new List<int>();
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<byte>(pattern))
{
positions.Add(i);
i += patternLength - 1;
}
}
}
return positions;
}
}
이것은 더 간단하고 빠른 내 제안입니다.
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;
}
LINQ 방법 / 답변이 누락되었습니다. :-)
/// <summary>
/// Searches in the haystack array for the given needle using the default equality operator and returns the index at which the needle starts.
/// </summary>
/// <typeparam name="T">Type of the arrays.</typeparam>
/// <param name="haystack">Sequence to operate on.</param>
/// <param name="needle">Sequence to search for.</param>
/// <returns>Index of the needle within the haystack or -1 if the needle isn't contained.</returns>
public static IEnumerable<int> IndexOf<T>(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;
}
}
}
}
위의 Foubar 답변의 내 버전은 건초 더미의 끝을지나 검색하지 않고 시작 오프셋을 지정할 수 있습니다. 바늘이 비어 있지 않거나 건초 더미보다 길지 않다고 가정합니다.
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;
}
}
이것들은 당신이 사용할 수있는 가장 간단하고 빠른 방법이며, 이것보다 더 빠른 방법은 없을 것입니다. 안전하지 않지만 우리가 포인터를 사용하는 이유는 속도입니다. 그래서 여기에서는 단일 검색을 사용하는 확장 방법과 발생 색인 목록을 제공합니다. 여기에서 가장 깨끗한 코드라고 말하고 싶습니다.
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<long> IndexesOf(this byte[] Haystack, byte[] Needle)
{
List<long> Indexes = new List<long>();
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;
}
}
Locate로 벤치마킹, 1.2-1.4 배 더 빠름
Jb Evain의 대답은 다음과 같습니다.
for (int i = 0; i < self.Length; i++) {
if (!IsMatch (self, i, candidate))
continue;
list.Add (i);
}
그런 다음 IsMatch 함수는 먼저 candidate검색되는 배열의 길이를 초과 하는지 여부를 확인합니다 .
for루프가 코딩 된 경우 더 효율적입니다 .
for (int i = 0, n = self.Length - candidate.Length + 1; i < n; ++i) {
if (!IsMatch (self, i, candidate))
continue;
list.Add (i);
}
이 시점 에서 '불법'매개 변수로 절대 호출하지 않도록 사전 조건을 통해 계약 하는 한 , 시작부터 테스트를 제거 할 수도 있습니다 IsMatch. 참고 : 2019 년에 개별 버그가 수정되었습니다.
내 답변의 팁과 Alnitak의 답변을 사용하여 새로운 함수를 만들었습니다.
public static List<Int32> 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<Int32>();
}
var result = new List<Int32>();
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;
}
내가 그렇게 행복하지 않은 유일한 부분은
currentIndex++;
if (matchCount > 0)
{
currentIndex += matchCount - 1;
}
부분 ... -1을 피하기 위해 if else를 사용하고 싶지만 더 나은 분기 예측이 가능합니다 (그게 중요할지는 모르겠지만) ..
단순함을 왜 어렵게 만들까요? 이는 for 루프를 사용하여 모든 언어로 수행 할 수 있습니다. 다음은 C #에서 하나입니다.
시스템 사용;
System.Collections.Generic 사용;
네임 스페이스 BinarySearch
{
수업 프로그램
{
static void Main (string [] args)
{
byte [] 패턴 = 새로운 byte [] {12,3,5,76,8,0,6,125};
byte [] toBeSearched = 새 바이트 [] {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 <int> 발생 = findOccurences (toBeSearched, pattern);
foreach (int 발생) {
Console.WriteLine ( "0 기반 인덱스에서 시작하는 일치 항목 발견 :"+ 발생);
}
}
static List <int> findOccurences (byte [] haystack, byte [] needle)
{
List <int> 발생 = new List <int> ();
for (int i = 0; i <haystack.Length; i ++)
{
if (needle [0] == haystack [i])
{
bool found = true;
int j, k;
for (j = 0, k = i; j <needle. Length; j ++, k ++)
{
if (k> = haystack.Length || needle [j]! = haystack [k])
{
발견 = 거짓;
단절;
}
}
만약 (발견)
{
발생 .Add (i-1);
나는 = k;
}
}
}
반환 발생;
}
}
}
시간을 내 주셔서 감사합니다 ...
이것은 제가 질문하기 전에 사용 / 테스트하고 있던 코드입니다 ...이 질문을 한 이유는 제가이 작업을 수행하는 데 최적의 코드를 사용하고 있지 않다는 것을 확신하기 때문입니다. 다시 한 번 감사드립니다. 시간을내어!
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;
}
내 코드에 오류가있는 사람이 있습니까? 이것은 해킹 접근으로 간주됩니까? 나는 너희들이 게시 한 거의 모든 샘플을 시도했고 경기 결과에 약간의 변형이있는 것 같다. toBeSearched 배열로 ~ 10Mb 바이트 배열로 테스트를 실행했습니다.
문자열로 변환하여 일치하는 솔루션을 사용합니다.
Knuth-Morris-Pratt 검색 알고리즘을 구현하는 간단한 함수를 작성해야 합니다 . 이것은 올바른 인덱스를 찾는 데 사용할 수있는 가장 빠르고 간단한 알고리즘입니다 ( Boyer-Moore를 사용할 수 있지만 더 많은 설정이 필요합니다.
알고리즘을 최적화 한 후 다른 종류의 최적화를 찾아 볼 수 있습니다. 하지만 기본부터 시작해야합니다.
예를 들어, 현재 "가장 빠른"것은 Jb Evian의 Locate 솔루션입니다.
핵심을 보면
for (int i = 0; i < self.Length; i++) {
if (!IsMatch (self, i, candidate))
continue;
list.Add (i);
}
하위 알고리즘의 일치 후 i + 1에서 일치하는 항목을 찾기 시작하지만 가능한 첫 번째 일치 항목이 i + 후보라는 것을 이미 알고 있습니다. 따라서 추가하면
i += candidate.Length -2; // -2 instead of -1 because the i++ will add the last index
상위 집합에서 하위 집합의 많은 발생을 예상 할 때 훨씬 빠릅니다. (Bruno Conde는 이미 그의 솔루션에서이 작업을 수행합니다.)
그러나 이것은 KNP 알고리즘의 절반에 불과하므로 out 매개 변수가 될 numberOfValidMatches라는 IsMatch 메서드에 추가 매개 변수도 추가해야합니다.
이것은 다음으로 해결됩니다.
int validMatches = 0;
if (!IsMatch (self, i, candidate, out validMatches))
{
i += validMatches - 1; // -1 because the i++ will do the last one
continue;
}
과
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;
}
약간의 리팩토링과 numberOfValidMatches를 루프 변수로 사용하고 -2와 -1을 피하기 위해 while을 사용하여 Locate 루프를 다시 작성할 수 있습니다. 하지만 KMP 알고리즘을 추가 할 수있는 방법을 명확히하고 싶었습니다.
속도가 전부는 아닙니다. 일관성을 확인 했습니까?
여기에 나열된 모든 코드를 테스트하지는 않았습니다. 나는 내 자신의 코드 (완전히 일관성이 없었던 것은 인정한다)와 IndexOfSequence를 테스트했다. 많은 테스트에서 IndexOfSequence가 내 코드보다 훨씬 빠르지 만 반복 테스트를 통해 일관성이 떨어지는 것을 발견했습니다. 특히 배열의 끝에서 패턴을 찾는 데 가장 어려움을 겪는 것처럼 보이지만 배열 중간에서 너무 가끔 놓칠 것입니다.
내 테스트 코드는 효율성을 고려하여 설계되지 않았으며 내부에 알려진 문자열이 포함 된 임의의 데이터를 갖고 싶었습니다. 이 테스트 패턴은 대략 http 양식 업로드 스트림의 경계 마커와 비슷합니다. 이것이 제가이 코드를 살펴 보았을 때 찾고 있던 것이기 때문에 검색 할 데이터의 종류로 테스트 할 것이라고 생각했습니다. 패턴이 길수록 IndexOfSequence가 값을 놓치는 경우가 더 많습니다.
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<int> 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();
}
(분명히 IndexOfSequence를 확장에서 다시이 테스트를위한 일반적인 방법으로 변환했습니다)
다음은 내 출력의 샘플 실행입니다.
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,
IndexOfSequence를 선택하려는 것이 아닙니다. 오늘부터 작업을 시작했습니다. 하루가 끝날 무렵 데이터에서 패턴이 누락 된 것 같았 기 때문에 오늘 밤 나만의 패턴 매처를 작성했습니다. 그래도 빠르지는 않습니다. 게시하기 전에 100 % 일관성을 유지할 수 있는지 확인하기 위해 조금 더 조정하겠습니다.
나는 모든 사람들에게 프로덕션 코드에서 신뢰하기 전에 좋은 반복 가능한 결과를 제공하는지 확인하기 위해 이와 같은 것을 테스트해야한다는 것을 상기시키고 싶었습니다.
나는 다양한 솔루션을 시도하고 SearchBytePattern 하나를 수정했습니다. 30k 시퀀스에서 테스트했으며 빠릅니다 :)
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;
}
네 생각을 말해봐.
여기 내가 생각해 낸 해결책이 있습니다. 구현 과정에서 찾은 메모를 포함했습니다. 앞으로, 뒤로 그리고 다른 (in / dec) 보정량 (예 : 방향)과 일치시킬 수 있습니다. 건초 더미의 오프셋에서 시작합니다.
모든 입력은 굉장 할 것입니다!
/// <summary>
/// Matches a byte array to another byte array
/// forwards or reverse
/// </summary>
/// <param name="a">byte array</param>
/// <param name="offset">start offset</param>
/// <param name="len">max length</param>
/// <param name="b">byte array</param>
/// <param name="direction">to move each iteration</param>
/// <returns>true if all bytes match, otherwise false</returns>
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, e.g. 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 a a index of positive value
return IndexOfBytes(ref a, ref offset, len, ref b, len) != -1;
}
///Here is the Implementation code
/// <summary>
/// Swaps two integers without using a temporary variable
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
internal static void Swap(ref int a, ref int b)
{
a ^= b;
b ^= a;
a ^= b;
}
/// <summary>
/// Swaps two bytes without using a temporary variable
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
internal static void Swap(ref byte a, ref byte b)
{
a ^= b;
b ^= a;
a ^= b;
}
/// <summary>
/// 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
/// </summary>
/// <param name="a">Needle</param>
/// <param name="offset">Start in Haystack</param>
/// <param name="len">Length of required match</param>
/// <param name="b">Haystack</param>
/// <param name="direction">Which way to move the iterator</param>
/// <returns>Index if found, otherwise -1</returns>
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;
}
ORegex를 사용할 수 있습니다.
var oregex = new ORegex<byte>("{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);
두 가지 일치 항목이 있습니다.
i:2;l:3
i:6;l:3
복잡성 : 최악의 경우 O (n * m), 실생활에서는 내부 상태 머신 때문에 O (n)입니다. 경우에 따라 .NET Regex보다 빠릅니다. 작고 빠르며 특히 어레이 패턴 매칭을 위해 설계되었습니다.
여기 내 (가장 성능이 좋은) 솔루션이 있습니다. 이는 bytes / latin-1 변환이 무손실이라는 사실에 의존하며 이는 bytes / ASCII 또는 bytes / UTF8 변환에 해당 되지 않습니다 .
장점은 모든 바이트 값에 대해 It Works (tm) (일부 다른 솔루션이 바이트 0x80-0xff로 잘못 작동 함)하고 확장하여 고급 정규식 일치를 수행 할 수 있다는 것입니다.
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<int> 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;
}
}
}
나는 파티에 조금 늦었 어 Boyer Moore 알고리즘을 사용하는 것은 어떻습니까? 그러나 문자열 대신 바이트를 검색하십시오. 아래의 C # 코드.
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[j-s]!=p[j]
* && p[j-s+1]..p[m-s-1] is suffix of p[j+1]..p[m-1] },
* if such s exists, else
* min{ s | j+1 <= s <= m
* && p[0]..p[m-s-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 s.t. 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[j-s]!=p[j] and p[j-s+1..m-s-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..m-s-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 s.t. p[j..m-1] is a prefix of p[i..m-1],
* if there is no such j, suffix[i] = m, i.e.
* 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;
}
}
}
}
다음은 기본 데이터 유형 만 사용하여 작성한 간단한 코드입니다. (첫 번째 발생 인덱스를 반환합니다.)
private static int findMatch(byte[] data, byte[] pattern) {
if(pattern.length > data.length){
return -1;
}
for(int i = 0; i<data.length ;){
int j;
for(j=0;j<pattern.length;j++){
if(pattern[j]!=data[i])
break;
i++;
}
if(j==pattern.length){
System.out.println("Pattern found at : "+(i - pattern.length ));
return i - pattern.length ;
}
if(j!=0)continue;
i++;
}
return -1;
}
따르기 쉽고 안전하지 않은 코드를 사용하거나 소스 배열의 일부를 복사하지 않고도 O (n) 유형의 작업에 대해 매우 효율적인 또 다른 답변입니다.
테스트하십시오. 이 주제에서 찾은 제안 중 일부는 상황에 취약합니다.
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);
}
/// <summary>
/// Returns the index of the first occurrence of a byte array within another byte array
/// </summary>
/// <param name="buffer">The byte array to be searched</param>
/// <param name="pattern">The byte array that contains the pattern to be found</param>
/// <returns>If buffer contains pattern then the index of the first occurrence of pattern within buffer; otherwise, -1</returns>
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;
}
/// <summary>
/// Returns the indexes of each occurrence of a byte array within another byte array
/// </summary>
/// <param name="buffer">The byte array to be searched</param>
/// <param name="pattern">The byte array that contains the pattern to be found</param>
/// <returns>If buffer contains pattern then the indexes of the occurrences of pattern within buffer; otherwise, null</returns>
/// <remarks>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.</remarks>
public static int[] ByteArrayPatternIndex(byte[] buffer, byte[] pattern)
{
if (buffer != null && pattern != null && pattern.Length <= buffer.Length)
{
List<int> indexes = new List<int>();
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;
}
나는 산체스의 제안을 이해하고 더 빠른 검색을하려고 노력했지만 코드의 성능은 거의 같지만 코드는 더 이해하기 쉽습니다.
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;
}
이것은 주제에 대한 내 자신의 접근 방식입니다. 나는 더 큰 배열에서 더 빠른지 확인하기 위해 포인터를 사용했습니다. 이 함수는 시퀀스의 첫 번째 발생을 반환합니다 (내 경우에 필요함).
모든 항목이 포함 된 목록을 반환하기 위해 약간 수정할 수 있다고 확신합니다.
내가하는 일은 매우 간단합니다. 패턴의 첫 번째 바이트 (바늘)를 찾을 때까지 소스 배열 (haystack)을 반복합니다. 첫 번째 바이트가 발견되면 다음 바이트가 패턴의 다음 바이트와 일치하는지 개별적으로 계속 확인합니다. 그렇지 않은 경우 바늘을 맞추기 전에 이전에 있던 색인 (건초 더미에서)에서 정상적으로 검색을 계속합니다.
그래서 여기에 코드가 있습니다 :
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;
}
아래의 안전한 코드 :
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;
}
지난번에이 문제가 발생했습니다.
public static long FindBinaryPattern(byte[] data, byte[] pattern)
{
using (MemoryStream stream = new MemoryStream(data))
{
return FindBinaryPattern(stream, pattern);
}
}
public static long FindBinaryPattern(string filename, byte[] pattern)
{
using (FileStream stream = new FileStream(filename, FileMode.Open))
{
return FindBinaryPattern(stream, pattern);
}
}
public static long FindBinaryPattern(Stream stream, byte[] pattern)
{
byte[] buffer = new byte[1024 * 1024];
int patternIndex = 0;
int read;
while ((read = stream.Read(buffer, 0, buffer.Length)) > 0)
{
for (int bufferIndex = 0; bufferIndex < read; ++bufferIndex)
{
if (buffer[bufferIndex] == pattern[patternIndex])
{
++patternIndex;
if (patternIndex == pattern.Length)
return stream.Position - (read - bufferIndex) - pattern.Length + 1;
}
else
{
patternIndex = 0;
}
}
}
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
참고URL : https://stackoverflow.com/questions/283456/byte-array-pattern-search
반응형
'Programing' 카테고리의 다른 글
| 데스크탑 앱의 Slack 채널에서 기록의 특정 날짜 또는 가장 오래된 메시지로 이동하려면 어떻게합니까? (0) | 2020.11.11 |
|---|---|
| setTimeout보다 Javascript 타이머를 만드는 더 정확한 방법이 있습니까? (0) | 2020.11.11 |
| 자바 스크립트에서 유형 검사 (0) | 2020.11.11 |
| jQuery는 다른 클래스가없는 특정 클래스가있는 div를 선택합니다. (0) | 2020.11.11 |
| 자바 스크립트에서 이미지를 캐시하는 방법 (0) | 2020.11.11 |