映射N维值到希尔伯特曲线上的点 [英] Mapping N-dimensional value to a point on Hilbert curve
问题描述
我有一组N维穴巨大（几千万; N是接近100）
I have a huge set of N-dimensional points (tens of millions; N is close to 100).
我需要将这些点映射到，而preserving空间局部性一个维度。我想用 Hilbert空间填充曲线做到这一点。
I need to map these points to a single dimension while preserving spatial locality. I want to use Hilbert space-filling curve to do it.
有关各点我要挑曲线上的最近点。点（从曲线到采摘点开始曲线长度）的希尔伯特值是单一维度的价值我所追求的。
For each point I want to pick the closest point on the curve. The Hilbert value of the point (curve length from the start of curve to the picked point) is the single dimension value I seek.
计算并不一定是即时的，但我希望它不会超过几个小时以上 体面现代家庭PC硬件。
Computation does not have to be instant, but I expect it to be no more than several hours on decent modern home PC hardware.
实施有什么建议？是否有任何库，将帮助我吗？ （语言没有多大关系。）
Any suggestions on implementation? Are there any libraries that would help me? (Language does not matter much.)
推荐答案
我终于崩溃了，花了一些钱。在AIP（美国物理研究所）有一个漂亮的，短的有源$ C $ C的C.由约翰·斯基林的文章编程希尔伯特曲线（从AIP CONF。PROC。707，381（2004））有一个附录与code在两个方向上的映射。它适用于任何数量的尺寸> 1，是不是递归的，不使用吞噬大量的内存，并且大多采用位操作状态转换的查找表。因此，它是相当快的，具有良好的内存占用。
I finally broke down and shelled out some money. The AIP (American Institute of Physics) has a nice, short article with source code in C. "Programming the Hilbert curve" by John Skilling (from the AIP Conf. Proc. 707, 381 (2004)) has an appendix with code for mappings in both directions. It works for any number of dimensions > 1, is not recursive, does not use state-transition lookup tables that gobble up huge amounts of memory, and mostly uses bit operations. Thus it is reasonably fast and has a good memory footprint.
如果您选择购买的物品，我在源$ C $ C发现错误。
If you choose to purchase the article, I discovered an error in the source code.
的code（在函数TransposetoAxes找到）下面这行有错误：
The following line of code (found in the function TransposetoAxes) has the error:
有（ⅰ= n-1个; I> = 0; I--）x [I] ^ = X [I-1];
for( i = n-1; i >= 0; i-- ) X[i] ^= X[i-1];
校正是改变大于或等于（> =），以一个大于（>）。如果没有这种校正，X数组是使用负折射率当变量i为零，导致程序失败访问。
The correction is to change the greater than or equal (>=) to a greater than (>). Without this correction, the X array is accessed using a negative index when the variable "i" becomes zero, causing the program to fail.
我建议你阅读这篇文章（这是七页长，包括code），因为它解释算法如何工作的，这是很不明显的。
I recommend reading the article (which is seven pages long, including the code), as it explains how the algorithm works, which is far from obvious.
我翻译了他的code到C＃为我所用。在code以下。斯基林进行改造到位，覆盖你通过。我选择了把输入向量的一个副本，并返回一个新的副本的载体。另外，我实现的方法为扩展方法。
I translated his code into C# for my own use. The code follows. Skilling performs the transformation in place, overwriting the vector that you pass in. I chose to make a clone of the input vector and return a new copy. Also, I implemented the methods as extension methods.
斯基林的code再presents希尔伯特指数为转置，作为数组存储。我发现它更方便交织比特和形成单个的BigInteger（在词典更加有用，更容易迭代循环中，等），但我优化的操作和它的逆与幻数，位运算等，并code是漫长的，所以我省略了。
Skilling's code represents the Hilbert index as a transpose, stored as an array. I find it more convenient to interleave the bits and form a single BigInteger (more useful in Dictionaries, easier to iterate over in loops, etc), but I optimized that operation and its inverse with magic numbers, bit operations and the like, and the code is lengthy, so I have omitted it.
namespace HilbertExtensions
{
/// <summary>
/// Convert between Hilbert index and N-dimensional points.
///
/// The Hilbert index is expressed as an array of transposed bits.
///
/// Example: 5 bits for each of n=3 coordinates.
/// 15-bit Hilbert integer = A B C D E F G H I J K L M N O is stored
/// as its Transpose ^
/// X[0] = A D G J M X[2]| 7
/// X[1] = B E H K N <-------> | /X[1]
/// X[2] = C F I L O axes |/
/// high low 0------> X[0]
///
/// NOTE: This algorithm is derived from work done by John Skilling and published in "Programming the Hilbert curve".
/// (c) 2004 American Institute of Physics.
///
/// </summary>
public static class HilbertCurveTransform
{
/// <summary>
/// Convert the Hilbert index into an N-dimensional point expressed as a vector of uints.
///
/// Note: In Skilling's paper, this function is named TransposetoAxes.
/// </summary>
/// <param name="transposedIndex">The Hilbert index stored in transposed form.</param>
/// <param name="bits">Number of bits per coordinate.</param>
/// <returns>Coordinate vector.</returns>
public static uint[] HilbertAxes(this uint[] transposedIndex, int bits)
{
var X = (uint[])transposedIndex.Clone();
int n = X.Length; // n: Number of dimensions
uint N = 2U << (bits - 1), P, Q, t;
int i;
// Gray decode by H ^ (H/2)
t = X[n - 1] >> 1;
// Corrected error in Skilling's paper on the following line. The appendix had i >= 0 leading to negative array index.
for (i = n - 1; i > 0; i--)
X[i] ^= X[i - 1];
X[0] ^= t;
// Undo excess work
for (Q = 2; Q != N; Q <<= 1)
{
P = Q - 1;
for (i = n - 1; i >= 0; i--)
if ((X[i] & Q) != 0U)
X[0] ^= P; // invert
else
{
t = (X[0] ^ X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
} // exchange
return X;
}
/// <summary>
/// Given the axes (coordinates) of a point in N-Dimensional space, find the distance to that point along the Hilbert curve.
/// That distance will be transposed; broken into pieces and distributed into an array.
///
/// The number of dimensions is the length of the hilbertAxes array.
///
/// Note: In Skilling's paper, this function is called AxestoTranspose.
/// </summary>
/// <param name="hilbertAxes">Point in N-space.</param>
/// <param name="bits">Depth of the Hilbert curve. If bits is one, this is the top-level Hilbert curve.</param>
/// <returns>The Hilbert distance (or index) as a transposed Hilbert index.</returns>
public static uint[] HilbertIndexTransposed(this uint[] hilbertAxes, int bits)
{
var X = (uint[])hilbertAxes.Clone();
var n = hilbertAxes.Length; // n: Number of dimensions
uint M = 1U << (bits - 1), P, Q, t;
int i;
// Inverse undo
for (Q = M; Q > 1; Q >>= 1)
{
P = Q - 1;
for (i = 0; i < n; i++)
if ((X[i] & Q) != 0)
X[0] ^= P; // invert
else
{
t = (X[0] ^ X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
} // exchange
// Gray encode
for (i = 1; i < n; i++)
X[i] ^= X[i - 1];
t = 0;
for (Q = M; Q > 1; Q >>= 1)
if ((X[n - 1] & Q)!=0)
t ^= Q - 1;
for (i = 0; i < n; i++)
X[i] ^= t;
return X;
}
}
}
这篇关于映射N维值到希尔伯特曲线上的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
