Bayt dizisi içinde bayt dizisi bul

Question

Bayt dizilim var ve bazı baytların "oluşumlarını" bulmak istiyorum. çok büyük bir bayt dizisi örneğin 00 69 73 6F 6D için

(> 50/100 megabayt)

TD

daha iyi bir ters işlem: bilmeden en yaygın model arama kodu okumak mümkün olmalıdır ve onu dosyadan bul.

Answer 1

Bir bayt dizisinde bayt dizisini verimli bir şekilde aramak için Boyer-Moore algoritmasını kullanabilirsiniz.

İşte Java sürümünden dönüştürdüğüm C# sürümü the Wikipedia entry on Boyer-Moore'dan.

public sealed class BoyerMoore 
{ 
    readonly byte[] needle; 
    readonly int[] charTable; 
    readonly int[] offsetTable; 

    public BoyerMoore(byte[] needle) 
    { 
     this.needle = needle; 
     this.charTable = makeByteTable(needle); 
     this.offsetTable = makeOffsetTable(needle); 
    } 

    public IEnumerable<int> Search(byte[] haystack) 
    { 
     if (needle.Length == 0) 
      yield break; 

     for (int i = needle.Length - 1; i < haystack.Length;) 
     { 
      int j; 

      for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j) 
      { 
       if (j != 0) 
        continue; 

       yield return i; 
       i += needle.Length - 1; 
       break; 
      } 

      i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]); 
     } 
    } 

    static int[] makeByteTable(byte[] needle) 
    { 
     const int ALPHABET_SIZE = 256; 
     int[] table = new int[ALPHABET_SIZE]; 

     for (int i = 0; i < table.Length; ++i) 
      table[i] = needle.Length; 

     for (int i = 0; i < needle.Length - 1; ++i) 
      table[needle[i]] = needle.Length - 1 - i; 

     return table; 
    } 

    static int[] makeOffsetTable(byte[] needle) 
    { 
     int[] table = new int[needle.Length]; 
     int lastPrefixPosition = needle.Length; 

     for (int i = needle.Length - 1; i >= 0; --i) 
     { 
      if (isPrefix(needle, i + 1)) 
       lastPrefixPosition = i + 1; 

      table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1; 
     } 

     for (int i = 0; i < needle.Length - 1; ++i) 
     { 
      int slen = suffixLength(needle, i); 
      table[slen] = needle.Length - 1 - i + slen; 
     } 

     return table; 
    } 

    static bool isPrefix(byte[] needle, int p) 
    { 
     for (int i = p, j = 0; i < needle.Length; ++i, ++j) 
      if (needle[i] != needle[j]) 
       return false; 

     return true; 
    } 

    static int suffixLength(byte[] needle, int p) 
    { 
     int len = 0; 

     for (int i = p, j = needle.Length - 1; i >= 0 && needle[i] == needle[j]; --i, --j) 
      ++len; 

     return len; 
    } 
} 

İşte bunun için bazı konsol uygulaması test kod: Search() yöntem haystack içindeki needle başlangıcının tüm konumların endekslerini döndürür nasıl

public static void Main() 
{ 
    byte[] haystack = new byte[10000]; 
    byte[] needle = { 0x00, 0x69, 0x73, 0x6F, 0x6D }; 

    // Put a few copies of the needle into the haystack. 

    for (int i = 1000; i <= 9000; i += 1000) 
     Array.Copy(needle, 0, haystack, i, needle.Length); 

    var searcher = new BoyerMoore(needle); 

    foreach (int index in searcher.Search(haystack)) 
     Console.WriteLine(index); 
} 

Not. Sadece sayımı isteseydim

, tıpkı senin olabilir:

int count = new BoyerMoore(needle).Search(haystack).Count(); 

---

ikinci soru için: Sana bayt en uzun tekrarlanan diziyi bulma konusunda soruyorsunuz varsayıyorum?

Bu çok daha karmaşık ve çok farklı bir soru. Bunun için bir cevap istiyorsanız, bunun için ayrı bir soru sormalısınız, ancak the Wikipedia entry on the "longest repeated substring problem"'u okumalısınız.