파일에서 바이트 시퀀스 찾기 (C#)

Question

바이트 시퀀스에 대해 파일을 검색해야하는 C# 응용 프로그램을 작성하고 있으며 라이브러리를 사용할 수 없습니다. 그렇게해라. 그래서, 나는 바이트 배열을 인자로 받아서 주어진 시퀀스 다음의 바이트 위치를 반환하는 함수가 필요하다. 이 기능은 빠를 필요가 없으며 단순히 작동해야합니다. 어떤 도움을 크게 그것은 빨리하지 않으면

Answer 1

이 사용할 수 있습니다 :) 감사하겠습니다 :

int GetPositionAfterMatch(byte[] data, byte[]pattern) 
{ 
    for (int i = 0; i < data.Length - pattern.Length; i++) 
    { 
    bool match = true; 
    for (int k = 0; k < pattern.Length; k++) 
    { 
     if (data[i + k] != pattern[k]) 
     { 
     match = false; 
     break; 
     } 
    } 
    if (match) 
    { 
     return i + pattern.Length; 
    } 
    } 
} 

을하지만 난 정말 크 누스 - 모리스 - 프랫 알고리즘을 사용하도록 권장합니다, 그것은이다 알고리즘은 주로 IndexOf 메서드의 기반으로 문자열에 사용됩니다. 위의 알고리즘은 작은 배열과 작은 패턴에 대해서는 실제로 느리게 실행됩니다.

Answer 2

Turrau 작품에서 지적한 직선적 인 접근법은 빠르지 않아도되기 때문에 충분히 유용 할 것입니다. 특히 실용적인 목적을 위해서는 알고리즘이 최악의 경우 O (n * m). (귀하의 패턴에 따라 다름).

최적의 솔루션을 찾으려면 O (n + m) 부분 일치를 사용하는 Knuth-Morris-Pratt algorithm을 확인하십시오.

Answer 3

나는 boyer-moore 유형 검색을 수행하는 데 사용한 코드의 일부입니다. 이것은 pcap 파일에서 작업하는 것을 의미하므로 레코드별로 레코드를 처리하지만 긴 바이너리 파일을 검색하는 경우에 맞게 쉽게 수정할 수 있어야합니다. 그것은 일종의 테스트 코드에서 추출한 것입니다. 그래서 당신이 따라야 할 모든 것을 갖기를 바랍니다. 또한 위키 피 디아에서 boyer-moore 검색을 찾는다.

int[] badMatch = new int[256]; 
byte[] pattern; //the pattern we are searching for 

//badMath is an array of every possible byte value (defined as static later). 
//we use this as a jump table to know how many characters we can skip comparison on 
//so first, we prefill every possibility with the length of our search string 
for (int i = 0; i < badMatch.Length; i++) 
{ 
    badMatch[i] = pattern.Length; 
} 

//Now we need to calculate the individual maximum jump length for each byte that appears in my search string 
for (int i = 0; i < pattern.Length - 1; i++) 
{ 
    badMatch[pattern[i] & 0xff] = pattern.Length - i - 1; 
} 

// Place the bytes you want to run the search against in the payload variable 
byte[] payload = <bytes> 

// search the packet starting at offset, and try to match the last character 
// if we loop, we increment by whatever our jump value is 
for (i = offset + pattern.Length - 1; i < end && cont; i += badMatch[payload[i] & 0xff]) 
{ 
    // if our payload character equals our search string character, continue matching counting backwards 
    for (j = pattern.Length - 1, k = i; (j >= 0) && (payload[k] == pattern[j]) && cont; j--) 
    { 
    k--; 
    } 
// if we matched every character, then we have a match, add it to the packet list, and exit the search (cont = false) 
    if (j == -1) 
    { 
    //we MATCHED!!! 
    //i = end; 
    cont = false; 
    } 
}