22

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

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

相反，我正在尝试使用分区方法。当您查看二维一阶希尔伯特曲线时

1   4
|   |
2---3

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

所以本质上，我想执行一个分而治之的策略（与快速排序密切相关 - 在均匀分布的数据上，这甚至应该是最佳的！），并且只根据需要计算希尔伯特索引的必要“位”。所以假设“1”中只有一个对象，那么就不需要计算它的完整表示；如果对象分布均匀，分区大小将迅速下降。

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

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

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

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

编辑：见下文，了解我如何解决 Z 曲线和皮亚诺曲线。它也适用于 2D Hilbert 曲线。但是我还没有希尔伯特曲线的旋转和反转。

4

3 回答 3

7

使用基数排序。将每个 1 维索引拆分为d .. 32部分，每个大小1 .. 32/d位。然后（从高位到低位）为每个索引块计算其希尔伯特值并将对象洗牌到适当的箱中。

这应该适用于均匀分布和不均匀分布的数据，无论是希尔伯特排序还是 Z 排序。并且不需要多精度计算。

关于将索引片段转换为希尔伯特顺序的一个细节：

  • 首先提取必要的位，
  • 然后交错来自所有维度的位，
  • 然后将一维索引转换为逆格雷码。

如果索引以双精度存储：

  • 如果索引可能为负数，则添加一些值以使所有内容都为正数，从而简化任务。
  • 确定 2 的最小整数幂，大于所有索引，并将所有索引除以该值
  • 将索引乘以 2^（当前排序步骤所需的位数）。截断结果，将其转换为整数，并将其用于希尔伯特排序（交错并计算逆格雷码）
  • 从索引中减去上一步截断的结果：index = index - i

来到您的基数排序变体，我建议使用两个大小的二进制数组d（一个主要用作堆栈，另一个用于反转索引位）和旋转值扩展 zsort （以使 hilbertsort 脱离 zsort）和旋转值（用于重新排列尺寸）。

如果堆栈中的顶部值为 1，则将 pivotize(...升序) 更改为 pivotize(...descending)，然后对于递归的第一部分，将此顶部值压入堆栈，对于第二个 - 压入该值的倒数。此堆栈应在每次递归后恢复。它包含基数排序过程的最后递归的“决策树” d（逆格雷码）。

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

于 2011-12-13T12:12:52.687 回答
2

您可以直接从 f(x)=y 计算希尔伯特曲线，而无需使用递归或 L 系统或分而治之。基本上它是格雷码或汉密尔顿路径遍历。您可以在 Nick 的空间索引希尔伯特曲线四叉树博客中找到很好的描述，或者从这本书黑客的喜悦中找到一个很好的描述。或者看看单调 n 元格雷码。我已经用 php 编写了一个实现，包括一条摩尔曲线。

于 2011-12-13T01:49:49.500 回答
0

我已经回答了这个问题（和其他问题），但我的答案神秘地消失了。来自http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/CompactHilbertCurve.java的紧凑希尔伯特索引实现（方法 index() ) 已经允许限制计算到给定级别的希尔伯特索引位数。来自上述方法的循环的每次迭代都会计算与空间维数相等的位数。您可以轻松地重构 for 循环以一次只计算一个级别（即，等于空间维数的位数），仅根据需要按字典顺序比较两个数字的紧凑希尔伯特索引所需的深度。

于 2012-03-29T12:03:22.737 回答