希尔伯特按分治算法排序？

Question

我试图按照它们的Hilbert顺序对d维数据向量进行排序，以便大容量加载一个空间索引。

但是，我不想显式地计算每个点的Hilbert值，这特别需要设置一个特定的精度。在高维数据中，这涉及到诸如32*d位这样的精度，这样做就会变得非常麻烦。当数据分布不均匀时，这些计算中的一些是不必要的，需要对数据集中的部分进行额外的精度。

相反，我正在尝试一种分区方法。当你看二维一阶希尔伯特曲线

1   4
|   |
2---3

我首先沿着x轴拆分数据，这样第一部分(不一定包含一半的对象！)将由1和2组成(尚未排序)，第二部分只包含来自3和4的对象。接下来，我再次将Y轴上的每半个部分分开，但在3-4中反转顺序。

因此，本质上，我希望在均匀分布的数据上执行分而治之的策略(与QuickSort密切相关--这甚至应该是最优的！)，并且只在需要时计算必要的希尔伯特索引的“位”。因此，假设"1“中有一个对象，那么就不需要计算它的完整表示；如果对象分布均匀，分区大小就会迅速下降。

我知道常用的教科书方法，就是转换成长的、灰色的、尺寸交错的.这不是我要找的东西(有很多可用的例子)。我明确地想要一个懒惰的分而治之的排序。另外，我需要的不仅仅是2D.

有人知道一篇文章或希尔伯特排序算法是这样工作的吗？或者一个关键的想法，如何得到正确的“旋转”，哪一个代表选择这一点？特别是在更高的维度..。在2D中，它是平凡的；1是旋转+y，+x，而4是-y，-x (旋转和翻转)。但我想，在更高的维度上，这会变得更加棘手。

(当然，结果应该与按照它们的hilbert顺序对对象进行排序时的结果相同，并且具有足够大的精度；我只是想在不需要的时候节省计算整个表示的时间，并且必须管理它。许多人保留了一个“反对希尔伯特数字”的hashmap，这是相当昂贵的。

对于Peano曲线和Z-曲线，类似的方法应该是可能的，并且可能更容易实现.我可能应该先试试这些(Z-曲线已经起作用了--实际上，它可以归结为类似于QuickSort的东西，使用适当的平均值/网格值作为虚拟枢轴，并在每次迭代中遍历维度)。

编辑：关于Z曲线和peano曲线的求解方法，请参阅下面的内容。它也适用于二维希尔伯特曲线。但是对于希尔伯特曲线，我还没有旋转和反演的权利。

Answer 1

使用基类。将每个一维索引拆分到d .. 32部件，每个大小为1 .. 32/d位.然后(从高阶位到低阶位)对每个索引段计算它的Hilbert值，并将对象洗牌到适当的回收箱。

这应该适用于均匀和不均匀分布的数据，包括Hilbert排序或Z-order。不需要多精度的计算。

关于将索引片段转换为Hilbert order的详细信息：

• 首先提取必要的比特，
• 然后从所有维度交错位，
• 然后将一维索引转换为逆灰度码.

如果索引以双倍形式存储：

• 如果索引可能为负值，则添加一些值以使所有事情都是正数，从而简化任务。
• 确定最小整数幂为2，它大于所有索引，并将所有索引除以此值。
• 将索引乘以2^(当前排序步骤所需的位数)。截断结果，将其转换为整数，并将其用于Hilbert排序(交织和计算逆灰色代码)
• 从索引：index = index - i中减去前一步截断的结果

关于基排序的变体，我建议使用两个大小为d的二进制数组(一个主要用作堆栈，另一个用于反转索引位)和旋转值(用于重新排列维度)扩展zsort (从zsort中生成hilbert排序)。

如果堆栈中的顶值为1，则更改枢轴(.提升)使(.)，然后对于递归的第一部分，将这个值推到堆栈中，对于第二个部分--推这个值的逆值。在每次递归之后，应该还原这个堆栈。它包含了基排序过程的最后一次d递归的“决策树”(在逆灰色代码中)。

在d递归之后，应该使用这个“决策树”堆栈来重新计算旋转值和反转数组。确切的方法是如何做到这一点是不平凡的。它可以在以下链接中找到：hilbert.c或hilbert.c。

Answer 2

您可以直接从f(x)=y计算hilbert曲线，而无需使用递归或L-系统，也不需要分治。基本上是灰色代码或者哈密顿路径遍历。你可以在Nick的空间索引hilbert曲线四叉树博客上找到一个很好的描述，或者从图书黑客的乐趣中找到一个很好的描述。或者看一看单调的n进制灰色代码。我用php编写了一个实现，包括moore曲线。

Answer 3

我已经回答了这个问题(和其他人)，但我的答案神秘地消失了。从http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/CompactHilbertCurve.java (方法索引())执行的computed已经允许将计算出的希尔伯特索引位数限制在给定的级别上。从上述方法的循环的每一次迭代计算相等于空间维数的位数。您可以很容易地重构for循环，一次只计算一个级别(即等于空间维数的多个位)，只需要深入比较它们的Compact索引在词典上的两个数字。