随着标题的推进，我们希望获得一些关于可用于具有以下约束的模式匹配的最快算法的建议:
长字典:256
短但不固定长度的规则(最多从 1 到 3 或 4 字节深度)
少量 (150) 条规则(如果 3 个字节)或中等(~1K)如果 4 个
比 Snort 中使用的当前 AC-DFA 或 Snort 再次使用的 AC-DFA-Split 性能更好
基于软件(最近的 COTS 系统，如 E5 的 E3) 理想情况下希望使用一些 SIMD/SSE 的东西，因为目前它们是 128 位宽，在不久的将来它们将是 256 位，而不是 CPU 的 64 位
我们通过使用 Sigmatch 论文中显示的算法对 Snort AC 进行预过滤来开始这个项目，但遗憾的是结果并没有那么令人印象深刻(使用 GCC 编译时提高了约 12%，但使用 ICC 则没有)
之后，我们尝试通过 IPP 库利用 SSE 4.2 中的新模式匹配功能，但根本没有提高性能(猜测直接在机器代码中执行会更好，但肯定更复杂)
所以回到最初的想法。现在我们正在沿着 Head Body Segmentation AC 的方向工作，但我们知道除非我们为头部替换提议的 AC-DFA 将很难获得改进的性能，但至少可以支持更多的规则而无需显着的性能下降
我们知道使用位并行思想会为长模式使用大量内存，但准确地说，问题范围已减少到最多 3 或 4 个字节长，因此使它们成为可行的替代方案
我们特别找到了 Nedtries，但想知道你们有什么想法，或者是否有更好的选择
理想情况下，源代码应使用 C 语言并在开源许可下。
恕我直言，我们的想法是搜索一次移动 1 个字节的内容以应对不同的大小，但是通过使用 SIMD/SSE 尽可能地利用大多数并行性并尝试尽可能减少分支来非常有效地做到这一点可能的
我不知道这样做是有点明智还是字节明智
回到正确的键盘 :D
本质上，大多数算法都没有正确利用当前的硬件功能或限制。它们的缓存非常低效，非常分支并不是说它们不利用 COTS CPU 中现在存在的功能，这些功能允许您具有一定程度的并行性(SIMD、SSE 等)
这正是我们所寻求的，一种算法(或一种已经存在的算法的实现)适本地考虑了所有这些，具有不试图覆盖所有规则长度的优势，只是较短的规则
例如，我看到一些关于 NFA 的论文声称，由于适当的缓存效率、增强的并行性等，如今它们的性能可以与内存需求少得多的 DFA 配对
最佳答案
请看: http://www.slideshare.net/bouma2 1 和 2 字节的支持与 Baxter 上面写的类似。尽管如此，如果您可以提供您希望在数据库中的单字节和双字节字符串的数量，以及您希望处理的流量类型(互联网、公司等)，这将会有所帮助——毕竟，也是许多单字节字符串可能最终匹配每个字节。 Bouma2的思想是允许将出现统计纳入预处理阶段，从而降低误报率。
关于algorithm - 多短规则模式匹配算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10455717/