C＃模式搜索

Question

我有一组我想搜索一个文件的十六进制数字，每个时间这符合它存储在从文本文件中的模式找到的最后一个字节的最后偏移地址。

因此，例如，模式是'04 00 03 00 00 00 04 00 04 00 00 00 08 00'，那么每当在文件中找到这个时候，那么模式中'00'的最后一个字节是偏移量被读入并存储在一个数组中。

任何帮助，在此请，这已经现在把我逼疯了几个月。

感谢

---

感谢Svick它做的工作确实是......它返回哪个是我需要找到偏移的所有比赛。

然而，由于我加一点一点我的代码，它停止在第一场比赛和不循环......可能有人请指出什么是错误的，为什么它是在第一场比赛中停止

非常感谢

Answer 1

好像你有几个步骤：

1. 从文本文件
2. 读取模式（针）从十六进制ASCII字符模式转换到一个数组字节
3. 读你的二进制文件（大海捞针）到内存
4. 寻找大海捞针

如果整个草垛装入内存一次，这是非常简单的。 std::find和 memcmp可以照顾第4步（哎呀，这些都是C++）C＃字符串可以包含NUL字节，所以你应该可以在这里使用的字符串 IndexOf功能。您将获得模式开始的偏移量，只需添加模式长度（减1）即可获得结束字节的偏移量。或者只是用几个 for循环自己写搜索。 请参阅@ svick对第4步讨论的出色答案。

处理更大的文件草垛，处理的模块在同一时间，确保由模式减一的长度重叠，否则你可能会错过一场比赛跨越块边界。

Answer 2

我的想法是使用队列来通过输入“寻找”。

static void Main(string[] args) 
{ 
    byte[] pattern = new byte[] { 3, 2, 1 }; 
    byte[] data = new byte[] { 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1 }; 
    foreach (long offset in FindPattern(pattern, data)) 
    { 
     Console.WriteLine(offset); 
    } 

    Console.ReadLine(); 
} 

public static IEnumerable<long> FindPattern(byte[] pattern, byte[] data) 
{ 
    Queue<byte> queue = new Queue<byte>(pattern.Length); 
    using (MemoryStream input = new MemoryStream(data)) 
    using (BinaryReader reader = new BinaryReader(input)) 
    { 
     byte[] buffer = new byte[1]; 
     while (1 == reader.Read(buffer, 0, 1)) 
     { 
      if (queue.Count == pattern.Length) 
      { 
       queue.Dequeue(); 
      } 

      queue.Enqueue(buffer[0]); 
      if (Matches(queue, pattern)) 
      { 
       // The input is positioned after the last read byte, which 
       // completed the pattern. 
       yield return input.Position; 
      } 
     } 
    } 
} 

private static bool Matches(Queue<byte> data, byte[] pattern) 
{ 
    return data.SequenceEqual(pattern); 
} 

我确定使用自定义的“队列”比SequenceEquals（）执行更好的比较，但你明白了。

Answer 3

我假设你得到了一个字符串模式。你应该做的是把它转换成一个字节数组。

如果搜索的文件比较小，效率是不是你能做到这一点非常重要只需在文件中开始从每个字节的搜索和与字节模式字节进行比较。如果遍历整个模式并且所有字节匹配，则将该位置存储在结果数组中。在代码中，它会去是这样的：

byte[] pattern = …; 
byte[] file = …; 

var result = Enumerable.Range(0, file.Length - pattern.Length + 1) 
         .Where(i => pattern.Select((b, j) => new { j, b }) 
              .All(p => file[i + p.j] == p.b)) 
         .Select(i => i + pattern.Length - 1); 

这种解决方案的时间复杂度是O（HN），其中H是文件（“干草堆”）的长度，而N是所述图案的长度（“针”）。

如果文件很大或者您需要的速度很快，则应该使用复杂度为O（H   +   N）的KMP algorithm。