algorithm - 使用哈希进行高效的深度数据包检测

Question

为了提高深度数据包检测的性能，我们通过对规则集执行哈希算法对规则集进行预处理，然后将规则分成更小的子规则 block ，从而使检测速度更快。

散列是在最初的 104 位的前 17 位上完成的。预处理完成后，每当数据包到达时，我们都会对其前 17 位进行散列，并根据结果根据更小的规则集对其进行检查。

(该算法使用了两次，在对前 17 位进行哈希处理后，它对接下来的 16 位进行哈希处理并存储结果，但是对于这个特定问题，我们可以假设我们只对固定数量的位)

该算法确实有效，但是，我们似乎无法找到一种方法将其应用于具有无关位的条目 - 我们得到了很多。

我们在许多地方搜索了解决方案，并尝试了例如使用无关位复制规则的建议。然而，它不起作用，因为它需要大量的内存(对于众多规则中的 17 条中的每个无关位，可以选择它是 1 或零 - 这将需要指数数量的空格)。

我们非常感谢任何建议或见解，即使是部分解决方案也很好。

注意:预处理时间或额外空间没有限制，只要它不是指数或任何不切实际的。

Answer 1

如果您使用哈希表作为缓存并在找不到当前值的条目时恢复到较慢的状态，那么您不需要完全填充它。您可以根据对以前流量的分析提前构建它，创建尽可能多的条目，或者您可以动态填充它，在找不到条目时处理数据包后创建新条目，并删除旧条目一段时间未使用的条目以回收存储。