c++ - 寻找用于计算 IP 地址的算法/类(直方图)

Question

我需要一个简单的类来计算来自网络监控系统的 IP 地址分布(直方图)。可能有 1 到 10¹⁰ 个数据包，有 1 到 2 个³² 地址(或者更多，如果我们有 IPv6 接口(interface))。我理想中寻找的是一个 C++ 类，它会自动创建直方图，然后在达到限制时，开始通过某种前缀路由组合不太受欢迎的节点。

有没有人知道这样的东西，或者我需要写它吗？

谢谢!

Answer 1

您所描述的听起来像是 Count-Min sketch 的完美用例 数据结构。该数据结构用于近似数据流中各种元素的频率，并且可以进行调整以精确地使用一定数量的内存。此外，给定一个固定的内存限制，您可以调整它的准确性以及与您想要的确切答案的接近程度。我的理解是，Google 使用此数据结构来识别频繁搜索，而无需使用大量磁盘空间。

作为一个额外的好处，数据结构永远不会低估给定值的真实频率。也就是说，如果您想查询您看到给定 IP 地址的频率，Count-Min sketch 将始终为您提供一个不小于真实数字的值。

Count-Min 草图非常容易实现——您只需要一堆不同的哈希函数和一个二维数组。您还可以找到 Count-Min 草图的各种不同实现 at Google's page on the data structure.

希望这对您有所帮助!