分治算法实现的希尔伯特排序？

Question

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

但是，我不想显式计算每个点的希尔伯特值，这需要设置特定的精度。在高维数据中，这涉及到像32*d位这样的精度，这样做效率会变得非常混乱。当数据不均匀分布时，一些计算是不必要的，部分数据集需要额外的精度。

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

1   4
|   |
2---3

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

因此，本质上，我想执行一种分治策略（与QuickSort密切相关 - 在均匀分布的数据上，这甚至应该是最优的！），并且仅在需要时计算必要的hilbert索引“位”。因此，假设“1”中有单个对象，则无需计算其完整表示形式；如果对象均匀分布，则分区大小将迅速减小。

我知道通常的教科书方法是将其转换为长整型、格雷编码、维度交错。这不是我要找的（这方面有很多例子可供参考）。我明确需要一种懒惰的分治排序。此外，我需要比2D更高的维数。

是否有人知道按此方式工作的hilbert排序算法或文章？或者有一个关键的想法如何正确获取“旋转”，选择哪种表示形式？特别是在更高的维数中...在2D中，这很简单；1被旋转+y，+x，而4被旋转和翻转-y，-x。但在更高的维数中，这变得更加棘手。

（当然，结果应该与立即按其hilbert顺序对对象进行排序时相同并具有足够大的精度；我只是尝试在不需要计算完整表示形式并且必须管理它时节省时间。许多人保留一个相当昂贵的哈希映射“对象到hilbert编号”。）

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

编辑：请参见下面的内容，了解我如何解决Z和peano曲线的问题。它在2D Hilbert曲线上也有效。但是，我尚未正确获取Hilbert曲线的旋转和反转。

- Has QUIT--Anony-Mousse

---

你能否使用八叉树代替？ - Mikeb

不，八叉树在不平衡和高维数据上不易扩展。它们适用于空间分布相对均匀的3D游戏。 - Has QUIT--Anony-Mousse

这听起来像是一个动态希尔伯特R树，http://en.wikipedia.org/wiki/Hilbert_R-tree - John L

是的，我打算使用这个工具来通过对对象按照希尔伯特顺序（“希尔伯特打包”）进行预排序来进行R树的批量加载。但我不打算存储入口和/或出口点，因此它不会成为完整的“动态希尔伯特R树”。 - Has QUIT--Anony-Mousse

这个链接可能会有用：http://code.google.com/p/uzaygezen/downloads/detail?name=uzaygezen-0.1.zip - Evgeny Kluev

Answer 1

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

这对于均匀和不均匀分布的数据以及希尔伯特顺序或Z顺序都很有效。而且不需要多精度计算。

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

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

如果索引存储在双精度浮点数中：

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

针对您的基数排序变体，我建议扩展zsort（将hilbertsort转换为zsort），并使用两个大小为d的二进制数组（一个主要用作堆栈，另一个用于反转索引位）和旋转值（用于重新排列维度）。

如果堆栈中的顶部值为1，则将pivotize（... ascending）更改为pivotize（... descending），然后对于递归的第一部分，将此顶部值推送到堆栈中，对于第二部分-推送此值的反向值。每次递归后应恢复此堆栈。它包含基数排序过程的最后d次递归的“决策树”（反格雷码）。

在进行了 d 次递归之后，应使用此“决策树”堆栈重新计算旋转值和反演数组。如何准确地执行此操作是非常复杂的，可以在以下链接中找到详细信息：hilbert.c 或 hilbert.c。

- Evgeny Kluev

---

环形缓冲区如何确定下一个分割轴？ - Has QUIT--Anony-Mousse

第一个轴在一级分割后因模式而异。在初始设置中（即在分割“x，y”之后），必须将1和4分割为y，x，而2和3必须分割为“x，y”。这对应于旋转使用希尔伯特基本模式。 - Has QUIT--Anony-Mousse

是的，这个算法有漏洞。我需要思考一下。 - Evgeny Kluev

唉，我所有尝试寻找 d>2 可行算法的尝试都失败了。我想我应该将此答案移除。 - Evgeny Kluev

据我所知，对于 3+d，您至少需要 d 个标志，这些标志需要以某种非平凡的方式“重新排序”维度。 - Evgeny Kluev

Answer 2

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

- Micromega

---

好吧，我并不想计算希尔伯特曲线。我想根据物体沿着它的位置对它们进行排序，而不是计算完整的希尔伯特曲线，只需懒惰地计算我需要的那些分隔符即可。 - Has QUIT--Anony-Mousse

@Anonymouse：我认为你无法计算一条曲线的一半，但你可以使用表格，即预先计算好的曲线。 - Micromega

嗯，我根本不在看曲线。我只是在看单个的排序位。视觉效果并不是我感兴趣的。 - Has QUIT--Anony-Mousse

@Anonymouse：不幸的是，它被称为希尔伯特曲线，而你所建议的是不同的东西。我知道你所说的排序方式。我自己使用它。我已经用莫尔曲线编写了一个PHP版本。此外，希尔伯特曲线不会刺激眼睛。 - Micromega

Answer 3

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

- Daniel

---

但代码仍然是按级别而不是按位运算的。对于高维设置，比如128维，这似乎比必要的工作还要多一些，因为少于128维的数据已经足以区分所有我的数据了（至少除非非常密集聚类）。 - Has QUIT--Anony-Mousse