如何在{0,1,2}^12中反复查找最近的向量

这听起来很像拼写检查器要做的事情。诀窍通常是滥用 tries .

你能做的最基本的事情是在好的向量上建立一个trie,然后在很少不匹配的情况下对分支进行洪水填充优先级排序。当有一个附近的向量时,这将非常快;当最近的向量非常远时,这将退化为蛮力。不错。

但我认为你可以做得更好。共享相同前缀的错误向量将执行相同的初始分支工作,因此我们也可以尝试共享。所以我们也在坏向量上建立了一个trie,sortof同时完成它们。

没有人保证这是正确的,因为算法和代码都是在我的头脑之外:

var goodTrie = new Trie(goodVectors)
var badTrie = new Trie(badVectors)
var result = new Map<Vector, Vector>()
var pq = new PriorityQueue(x => x.error)
pq.add(new {good: goodTrie, bad: badTrie, error: 0})
while pq.Count > 0
  var g,b,e = q.Dequeue()
  if b.Count == 0: 
      //all leafs of this path have been removed
      continue
  if b.IsLeaf:
      //we have found a mapping with minimum error for this bad item
      result[b.Item] = g.Item
      badTrie.remove(b) //prevent redundant results
  else:
      //We are zipping down the tries. Branch to all possibilities.
      q.EnqueueAll(from i in {0,1,2}
                   from j in {0,1,2}
                   select new {good: g[i], bad: b[j], error: e + i==j ? 0 : 1})

return result   

最后一个优化可能是对向量重新排序,使坏向量之间高度一致的位置优先,并共享更多的工作。

为了保持正确的观点,并确保你没有优化不必要的东西,暴力的方法,没有任何优化需要12秒在我的机器。

Mathematica中的代码:

bad = Table[RandomInteger[5, 12], {1000}];
good = Table[RandomInteger[2, 12], {1000}];
distance[a_, b_] := Total[Sign@Abs[a - b]];

bestMatch = #[[2]] & /@ 
   Position[
    Table[Ordering@
      Table[distance[good[[j]], bad[[i]]], {j, Length@good}], {i, 
      Length@bad}], 1] // Timing

如你所料,时间遵循O(n^2)定律:

3^12不是很大的搜索空间。如果速度是必需的,而算法的通用性不是必需的,您可以将每个向量映射到0..531440范围内的一个int,并将其用作“最近的好向量”的预计算表的索引。

如果给表中的每个条目一个32位的单词(这已经足够了),那么您将看到表的大小约为2 MB,这就相当于瞬时的“计算”。

编辑:这与问题所建议的预计算没有太大区别,但我的观点是,根据应用程序的不同,这样做不一定有任何问题,特别是如果在应用程序运行之前进行了所有的预计算。

我的计算几何很粗糙,但似乎你应该能够:

1. 计算 Voronoi diagram 为了你的一组好向量。
2. 计算 BSP tree 对于图表的单元格。

Voronoi图将为每个好向量提供一个12维凸包,其中包含所有最接近该向量的点。

BSP树将为您提供一种快速的方法来确定向量所在的单元格,从而确定它最接近哪个好的向量。

编辑:我刚刚注意到你用的是汉明距离而不是欧几里德距离。我不知道怎么才能适应这种限制。对不起的。

假设向量的压缩表示,一个距离计算(比较一个好向量和一个坏向量以得出距离)可以在大约20个时钟周期或更少的时间内完成。因此,可以在2000万个周期或(假设为2GHz cpu)0.01秒内完成一百万个这样的距离计算。这些数字有帮助吗?

注:20个周期是保守的高估值。