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

algorithm sorting java bulkloader hilbert-curve

2022-09-02 02:00:39

我正在尝试按希尔伯特顺序对 d 维数据向量进行排序，以便批量加载空间索引。

但是，我不想显式计算每个点的希尔伯特值，这尤其需要设置特定的精度。在高维数据中，这涉及诸如位之类的精度，这变得非常混乱，无法有效地完成。当数据分布不均匀时，其中一些计算是不必要的，并且需要对数据集的某些部分进行额外的精度。32*d

相反，我正在尝试执行分区方法。当您查看 2D 一阶希尔伯特曲线时

1   4
|   |
2---3

我首先沿着x轴拆分数据，以便第一部分（不一定包含一半的对象！）将由1和2（尚未排序）组成，第二部分将仅包含3和4中的对象。接下来，我会在Y轴上再次拆分每半部分，但以3-4反转顺序。

因此，从本质上讲，我想执行一种分而治之的策略（与QuickSort密切相关 - 在均匀分布的数据上，这甚至应该是最优的！），并且仅根据需要计算希尔伯特指数的必要“位”。因此，假设“1”中有一个对象，则无需计算它的完整表示;如果对象均匀分布，分区大小将迅速下降。

我确实知道通常的教科书方法，即转换为长，灰色编码，维度交错。这不是我想要的（有很多这样的例子）。我明确地想要一个懒惰的分而治之的排序。另外，我需要的不仅仅是2D。

有没有人知道以这种方式工作的文章或希尔伯特排序算法？或者一个关键的想法是如何获得正确的“旋转”，为此选择哪种表示？特别是在更高维度...在2D中，它是微不足道的;1 旋转 +y， +x，而 4 是 -y，-x（旋转和翻转）。但是在更高的维度中，我想这会变得更加棘手。

（结果当然应该与按希尔伯特顺序对对象进行排序时相同，并且立即具有足够大的精度;我只是试图节省在不需要的时候计算完整表示的时间，并且必须管理它。许多人保留一个哈希图“对象到希尔伯特数”，这是相当昂贵的。

对于皮亚诺曲线和Z曲线，类似的方法应该是可能的，并且可能更容易实现......我可能应该先尝试这些（Z曲线已经在工作了 - 它确实归结为与QuickSort非常相似的东西，使用适当的平均值/网格值作为虚拟枢轴，并在每次迭代的维度中循环）。

编辑：请参阅下文，了解我如何解决Z和peano曲线。它也已经适用于2D希尔伯特曲线。但是我还没有希尔伯特曲线的旋转和反转。

答案 1

使用基数排序。将每个一维索引拆分为多个部分，每个部分的大小位。然后（从高阶位到低阶位）为每个索引段计算其希尔伯特值并将对象随机排列到适当的条柱。d .. 321 .. 32/d

这应该适用于均匀和不均匀分布的数据，包括希尔伯特排序或Z顺序。无需多精度计算。

有关将索引片段转换为希尔伯特顺序的一个详细信息：

如果索引以双精度形式存储：

对于基数排序的变体，我建议使用两个大小（一个主要用于堆栈，另一个用于反转索引位）和旋转值（用于重新排列维度）来扩展zsort（使hilbertsort脱离zsort）。d

如果堆栈中的最高值为 1，则更改透视化（...升序）以透视（...降序），然后对于递归的第一部分，将此最高值推送到堆栈，对于第二部分 - 推送此值的反函数。此堆栈应在每次递归后还原。它包含基数排序过程的最后递归的“决策树”（在逆格雷码中）。d

递归后，应使用此“决策树”堆栈来重新计算旋转值和反转数组。确切的方法不是微不足道的。它可以在以下链接中找到：hilbert.c或hilbert.c。d

答案 2

您可以直接从 f（x）=y 计算希尔伯特曲线，而无需使用递归或 L 系统或分而治之。基本上，它是一个灰色代码或哈密顿路径遍历。你可以在Nick的空间索引希尔伯特曲线四边形博客或来自黑客的喜悦中找到一个很好的描述。或者看看单调的n-ary格雷码。我已经用php写了一个实现，包括摩尔曲线。