5

.NET 非常支持在字符串中搜索字符串，但是当您需要搜索的数据不是字符串时该怎么办？

我有通过 NetworkStream 以常规块形式到达的二进制数据。数据包是二进制的，但它们都以字节的签名序列开头。我将这些块累积到一个更大的缓冲区中并寻找数据包开始签名。

我真正要找的是方法的byte[]等价物String.IndexOf(ss)。我有一种讨厌的感觉，我将不得不自己用一个循环和一个状态机来实现它。

有什么建议么？交给你了！

正如建议的那样， Array.IndexOf(byte) 至少会为我节省一个显式循环。自发布以来，我想到找到第一个签名字节，然后提前探测最后一个签名字节应该在哪里的匹配，然后如果它们都匹配，则尝试对字符串的其余部分进行蛮力比较。这种方法的优点是可以廉价地拒绝错误匹配，并允许我在有部分签名等待另一个块时廉价地拒绝。

谷歌透露，上述绝妙方案是“KMP”或Knuth-Morris-Pratt算法的退化案例。从好的方面来说，如果 Knuth 把他的名字写在上面，那可能是闪电般的润滑，从不好的方面来说，为什么每当我有一个好主意时，Donald Knuth 会在 25 年前想到它？

由于我不能将积分奖励给 Donald Knuth，我猜他们会去 Nelson。

4

3 回答 3

3

您可以使用 Array.IndexOf 来查找单个字节。

但是，我会提醒您，一些有效数据可能会意外成为您的签名并完全退出您的应用程序。我认为更好的解决方案是始终发送一个包含数据包大小的四字节整数。然后读入那么多字节以清除该数据包的缓冲区。

如果您使用 TCP，如果客户端谎报数据包大小或请求愚蠢的内存量，则完全可以将其踢走：)

于 2008-10-10T05:50:58.630 回答
2

我使用过的在字节数组和字符串中查找模式的最快算法是Boyer-Moore和简单的 Boyer-Moore（当模式与正在搜索的文本显着不同时很有用）。我用它在 Java 中实现了一个快速的 mime 解析器。该代码可以很容易地移植到 .Net（许可证是 LGPL）。

于 2008-10-10T09:09:48.557 回答
0

你可以使用非托管/不安全的代码吗？如果是这样，我可能会建议研究使用指针算法来搜索你的字节数组。这就是字符串有效的方式。你可以做类似的事情。

另一种解决方案可能是使用字典来存储您的数据包数据。让钥匙成为你的签名。然后它相当快速和容易找到它。将字节作为键的几种方法，例如 base64string、simepl 包装器（如果这样做，请使用 KeyedCollection）等。

于 2008-10-10T06:35:32.723 回答