0

给定一个数字向量：V=(v1, v2, ..., vn)。这 n 个数字不需要区分或排序。

假设我们有几个向量 V1, V2, ..., Vm。可以用一个数（整数或浮点数）来唯一地表示每个向量，这样对于任何一个不等于 Vj 的 Vi，对应的数 f(Vi) 和 f（Vj) 也不相等。

一个简单的解决方案是用一个从 0 到 m-1 范围内的数字作为 ID 来表示一个向量，但是我们假设这种解决方案在每个向量存储在几个分布式机器中的情况下是行不通的。也就是说，两台机器中的向量部分可能会重叠，并且算法不知道全局向量的分布。

4

2 回答 2

1

当然，如果你有 n 个数字，你不能在不丢失信息的情况下将它们压缩成一个相同长度的数字（例如，如果你从向量计算某种散列，就会出现散列冲突）。

如果您有无限空间（如 Java 中的 BigInteger），则可以对向量进行编码。假设向量长度是固定的，您可以简单地使用一些“互锁”模式：

vector = [12345,4711,42]

1  2  3  4  5
 0  4  7  1  1
  0  0  0  4  2
100240370414512 <-- your unique number

对向量大小进行编码也不应该太难，因此这也适用于不同大小的向量（例如，您使用八进制的长度和 8 作为“前缀”）。

于 2013-05-09T13:37:33.050 回答
0

我假设输入原则上是无界的，输出数也是如此，否则它是微不足道的。一个简单的方法就是将 n 和 v1, v2, .. vn 的表示连接到某个基数 b 中。用 k 位数字表示它们，然后用一个连续位注释每个 k 位数字（如果下一个 k 位组开始一个新数字，则为 0，如果它属于同一数字，则为 1）。除了平等测试之外，这对任何事情都没有多大用处，但您没有提及其他任何事情。

如果您还关心保留局部性（即附近的点 p、q 经常具有附近的值 f(p)、f(q)），则可以使用一些空间填充曲线来实现此目的。希尔伯特曲线推广到更高维度有点复杂，而且计算很复杂。Z 阶曲线在保留局部性方面没有那么好，但对于任意数量的维度实现它几乎是微不足道的——只需交错二进制表示的位即可。

于 2013-05-09T13:49:27.317 回答