Это очень похоже на то, что должны делать проверщики орфографии.Хитрость, как правило, состоит в том, чтобы злоупотреблять попытки .
Самое основное, что вы можете сделать, это построить три на основе хороших векторов, а затем выполнить приоритетную ветвь с флуд-заливкой с небольшими несовпадениями.Это будет очень быстро, когда есть соседний вектор, и выродится в грубую силу, когда ближайший вектор будет очень далеко.Неплохо.
Но я думаю, вы можете добиться большего.Плохие векторы, которые имеют один и тот же префикс, будут выполнять ту же самую начальную работу ветвления, поэтому мы можем попытаться поделиться этим.Таким образом, мы также строим три на основе плохих векторов и сортируем их все сразу.
Нет гарантий, что это правильно, так как и алгоритм, и код не в моей голове:
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
Окончательная оптимизация может состоять в том, чтобы переупорядочить векторы, чтобы позиции с высоким соглашением среди плохих векторов были на первом месте и разделили больше работы.