问题标签 [hilbert-curve]

我有一组巨大（但有限）的自然语言字符串。

我需要一种将每个字符串转换为数值的方法。对于任何给定的字符串，每次的值都必须相同。

两个给定的字符串越“不同”，两个对应的值应该越不同。它们越“相似”，不同的值应该越少。

我还不知道我需要的字符串之间差异的确切定义。反正没有自然语言解析。它可能应该类似于 Levenstein（但 Levenstein 是相对的，我需要绝对度量）。让我们从简单的事情开始。

尺寸更新

我很乐意接受多维（最好是 3d）向量而不是单个数值。

更新预期结果的正确性

正如在此处和此处正确指出的那样，从一个字符串到另一个字符串的距离是一个具有MAX(firstStringLength, secondStringLength)维度的向量。一般来说，在不丢失一些信息的情况下减少维数是不可能的。

但是我不需要一个绝对的解决方案。我会满足于从 N 维字符串空间到我的 3D 空间的任何“足够好”的转换。

另请注意，我有有限数量的有限长度的字符串。（虽然字符串的数量相当大，大约 8000 万（10 GB），所以我最好选择一些单通道无状态算法。）

从扫描参考资料来看，我的印象是希尔伯特空间填充曲线可能对我有所帮助。看起来希尔伯特空间填充曲线的聚类特性分析文章讨论了一些接近我的问题的东西......

希尔伯特曲线方法的更新

1. 我们将每个字符串映射到 N 维空间中的一个点，其中 N 是集合中字符串的最大长度。顺便说一句，字符串中的第 i 个字符代码可以用作这里的第 i 个坐标值吗？
2. 我们通过该 N 维空间绘制一条希尔伯特曲线。
3. 对于每个字符串，我们在曲线上取点，最接近字符串的坐标。该点的希尔伯特值（从曲线开始的长度）是我寻求的一维值。
4. 如果我们需要 3D 值，我们在 3D 中绘制 Hilbert 曲线并选择匹配 Hilbert 值的点，如上所述。

这看起来对吗？这里的计算费用是多少？

我有大量的 N 维点（数千万；N 接近 100）。

我需要将这些点映射到一个维度，同时保留空间局部性。我想用希尔伯特空间填充曲线来做。

对于每个点，我想选择曲线上最近的点。点的希尔伯特值（从曲线起点到选取点的曲线长度）是我寻求的单维值。

计算不必是即时的，但我希望在体面的现代家用 PC 硬件上不会超过几个小时。

对实施有何建议？有什么图书馆可以帮助我吗？（语言并不重要。）

我有一组希尔伯特值（从希尔伯特曲线起点到给定点的长度）。

将这些值转换为 3D 点的最佳方法是什么？原始希尔伯特曲线不是 3D 的，所以我想我必须自己选择我需要的希尔伯特曲线等级。我确实有总曲线长度（即集合中的最大值）。

也许有一个现有的实现？一些允许我使用希尔伯特曲线/值的库？语言无关紧要。

在XKCD 漫画 195中，建议使用希尔伯特曲线设计 Internet 地址空间图，以便将来自相似 IP 地址的项目聚集在一起。

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

我在 MySQL 中存储了 ax,y,z 3D 点，我想询问区域、切片或点邻居。有没有办法使用 Peano-Hilbert 曲线来索引点以加速查询？还是有更有效的方法将 3D 数据存储在 MySQL 中？

谢谢阿曼。

我正在研究使用类似 geohash 的索引存储地理空间信息，也许使用希尔伯特曲线。我的问题是关于如何最好地拆分此类索引上的区域查询。

例如，本文展示了如何将一个区域查询拆分为多个查询，以避免查询表现出较差局部性的范围（参见此图）。如果您想使用 Z 曲线（如普通 geohash）通过单个查询来搜索圆形区域，您将不得不查询整个左下象限，它只有我们关注的区域的一小部分。

在这种情况下，最好将搜索拆分为几个查询，但是我无法找到有关如何最好地执行此操作的任何信息。是否有将这样的范围查询拆分为覆盖原始区域的较小范围的算法？

我有一个包含稀疏几何的非立方边界框的 3d 数组。

如果 (x,y,z) 是计算域的一部分，则数组 geometry[x][y][z] 包含值 0，否则为 1。

为了重新排序计算，我想使用希尔伯特曲线遍历这个空间。

上下文是优化内存绑定 GPU 程序中的全局内存访问。

我该如何实施？

更新：我只想遍历非空单元格，因为我只会将这些单元格（在数组中）与一个跟踪元素的 19 个相邻节点的邻接列表一起存储。

计算只是在两个数组之间复制：

这是稀疏格子玻尔兹曼方法的传播阶段，其中物理解释是从相邻站点流式传输“流体粒子”。

adjacency_map 中的值越连续；我们希望得到的合并内存访问越多。

OpenCL 内核：

我有大量数据希望能够使用 PHP 的 GD 库逐个像素地读出到希尔伯特曲线中。

目的是创建一个任意大小的查找表，将地址映射到像素网格上的点。例如。

本例中的第八个连续地址是 2,2。最终结果查找表将仅包含可以引用的点。

我意识到肯定有一种有效的方法来生成它，只是我还没有想到它。

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

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

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

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

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

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

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

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

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

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

我有一个多维点，它可能具有以下 3 种类型 INT(4) 的键，即 Short 或 INT(8) 或 varchar(512)。

出于这个原因，我不能使用正常的希尔伯特曲线变换。我找到了一个非常好的资源来计算紧凑的希尔伯特指数。链接在这里。

http://web.cs.dal.ca/~chamilto/hilbert/index.html

我理解他论文中的要点和动机，但我无法破译代码。我不知道要调用哪些函数来计算紧凑希尔伯特指数及其倒数。