实现互联网的希尔伯特地图 [英] Implementing a Hilbert map of the Internet

问题描述

在 XKCD漫画195 设计为互联网地址空间的映射使用的Hilbert曲线这样从一个相似的IP不会忽略的项目将被聚集在一起。

In the XKCD comic 195 a design for a map of the Internet address space is suggested using a Hilbert curve so that items from a similar IP adresses will be clustered together.

给定一个IP地址，我将如何计算它的二维坐标（范围在零到一）在这样的地图？

Given an IP address, how would I calculate its 2D coordinates (in the range zero to one) on such a map?

推荐答案

这是pretty的容易，因为希尔伯特曲线是分形，也就是说，它是递归的。它通过水平和垂直平分每个方块，将其划分成四大块。所以你把IP地址的两个位的时间，从左边开始，并使用它们来确定象限，然后继续，使用接下来的两比特，以该象限而不是整个正方形，并​​依此类推，直至有用尽了所有的位地址。

This is pretty easy, since the Hilbert curve is a fractal, that is, it is recursive. It works by bisecting each square horizontally and vertically, dividing it into four pieces. So you take two bits of the IP address at a time, starting from the left, and use those to determine the quadrant, then continue, using the next two bits, with that quadrant instead of the whole square, and so on until you have exhausted all the bits in the address.

在每平方曲线的基本形状是马蹄形状

The basic shape of the curve in each square is horseshoe-like:

 0 3
 1 2

，其中数字对应上面两位，因此决定了遍历顺序。在XKCD地图上，这个广场是最高级别的遍历顺序。可能旋转和/或反射，这种形状是present在每个2×2平方米。

where the numbers correspond to the top two bits and therefore determine the traversal order. In the xkcd map, this square is the traversal order at the highest level. Possibly rotated and/or reflected, this shape is present at each 2x2 square.

如何马蹄定向在由一个规则来确定每个子格的测定：的 0 0 角落code>广场中规模较大的广场一角。因此，对应于 0 上面的subsquare必须遍历的顺序

Determination of how the "horseshoe" is oriented in each of the subsquares is determined by one rule: the 0 corner of the 0 square is in the corner of the larger square. Thus, the subsquare corresponding to 0 above must be traversed in the order

 0 1
 3 2

和，着眼于整个previous广场和展示四位，我们得到如下形状为方形的下一个区分：

and, looking at the whole previous square and showing four bits, we get the following shape for the next division of the square:

 00 01 32 33
 03 02 31 30
 10 13 20 23
 11 12 21 22

这是怎么了方始终得到下一级分。现在，继续进行，只是根据如何那些位的马蹄形定向集中在后两个比特，东方此更详细的形状，并继续进行类似的除法。

This is how the square always gets divided at the next level. Now, to continue, just focus on the latter two bits, orient this more detailed shape according to how the horseshoe shape of those bits is oriented, and continue with a similar division.

要确定实际坐标，每两个位决定在实数坐标的二进制precision一位。因此，在第一个层面上，二点之后的第一位（假设 [0,1] 范围坐标），在 X 坐标 0 如果地址的前两位的值为 0 或 1 和 1 否则。同样，在是协调的第一位是 0 如果前两位的值为 1 或 2 。要确定是否添加 0 或 1 位坐标，您需要检查马蹄的取向这一水平。

To determine the actual coordinates, each two bits determine one bit of binary precision in the real number coordinates. So, on the first level, the first bit after the binary point (assuming coordinates in the [0,1] range) in the x coordinate is 0 if the first two bits of the address have the value 0 or 1, and 1 otherwise. Similarly, the first bit in the y coordinate is 0 if the first two bits have the value 1 or 2. To determine whether to add a 0 or 1 bit to the coordinates, you need to check the orientation of the horseshoe at that level.

编辑：我开始工作了算法和事实证明，它并不难毕竟，所以这里的一些伪-C。这是假，因为我用的是 B 后缀为二进制常量和治疗作为整数位阵列，但其更改为恰当的C应该不会太难。

I started working out the algorithm and it turns out that it's not that hard after all, so here's some pseudo-C. It's pseudo because I use a b suffix for binary constants and treat integers as arrays of bits, but changing it to proper C shouldn't be too hard.

在code， POS 是一个3位整数的方向。前两位是x和 0 在广场y坐标，第三位表示是否 1 的同样的x坐标为 0 。 的 POS初始值为 011B ，这意味着坐标 0 是（0，1）和 1 具有相同的x坐标为 0 。 广告的地址，视为 N 的2位整数k-元数组，从最显著开始位。

In the code, pos is a 3-bit integer for the orientation. The first two bits are the x and y coordinates of 0 in the square and the third bit indicates whether 1 has the same x coordinate as 0. The initial value of pos is 011b, meaning that the coordinates of 0 are (0, 1) and 1 has the same x coordinate as 0. ad is the address, treated as an n-element array of 2-bit integers, and starting from the most significant bits.

double x = 0.0, y = 0.0;
double xinc, yinc;
pos = 011b;
for (int i = 0; i < n; i++) {
    switch (ad[i]) {
        case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break;
        case 1: xinc = pos[0] ^ ~pos[2]; yinc = pos[1] ^ pos[2]; break;
        case 2: xinc = ~pos[0]; yinc = ~pos[1]; break;
        case 3: xinc = pos[0] ^ pos[2]; yinc = pos[1] ^ ~pos[2];
            pos = ~pos; break;
    }
    x += xinc / (1 << (i+1)); y += yinc / (1 << (i+1));
}

我与一对夫妇的8位prefixes测试，它把他们按照XKCD地图正确，所以我有点信心了code是正确的。

I tested it with a couple of 8-bit prefixes and it placed them correctly according to the xkcd map, so I'm somewhat confident the code is correct.

这篇关于实现互联网的希尔伯特地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！