从一组元素

Question

我正在与一个想法，其中我具有以下子问题的尝试检索最接近元素：

我有固定长度n的含元组大小m的列表。

[(e11, e12, .., e1n), (e21, e22, .., e2n), ..., (em1, em2, .., emn)] 

现在，由于一些随机元组(t1, t2, .., tn)，这不属于名单，我想找到最接近的元组（S），属于列表。

我用下面的距离函数（汉明距离）：

def distance(A, B): 
    total = 0 
    for e1, e2 in zip(A, B): 
     total += e1 == e2 
    return total 

一种选择是使用穷举搜索，但是这还不够我的问题的列表是相当大的。其他的想法，我想出了，是先用kmedoids集群的列表，并检索K中心点划分（聚类中心）。对于查询，我可以使用K调用距离函数来确定距离最近的簇。然后，我可以从该特定群集中搜索最接近的元组。我认为它应该可以工作，但我不完全确定，如果在查询元组位于集群边缘的情况下很好。

不过，我想知道，如果你有更好的想法来解决问题，因为我的心在那一刻完全空白。但是，我有强烈的感觉，可能有一个聪明的方法来做到这一点。

的解决方案，需要预先计算的东西，只要他们打倒查询的复杂性都很好。

Answer 1

可以将哈希表（字典/地图），其从一个元素映射（在元组）存储它出现在tupples：hash:element->list<tupple>。

现在，当您有一个新的“查询”时，您需要为新的“查询”的每个元素迭代每个hash(element)，并查找最大匹配数。

伪代码：

findMax(tuple): 
    histogram <- empty map 
    for each element in tuple: 
    #assuming hash_table is the described DS from above 
    for each x in hash_table[element]: 
     histogram[x]++ #assuming lazy initialization to 0 
    return key with highest value in histogram 

---

的替代，这并不完全遵循你想要的度量是k-d tree。不同之处在于k-d树也考虑了元素之间的“距离”（而不仅仅是平等/不平等）。
K-d树木也要求元素相媲美。

Answer 2

如果数据足够大，你可能想在它创建一些inverted indexes。

随着的Ñ元件米矢量的数据。

数据：

0: 1, 2, 3, 4, 5, ... 
1: 2, 3, 1, 5, 3, ... 
2: 5, 3, 2, 1, 3, ... 
3: 1, 2, 1, 5, 3, ... 
... 
m: m0, ... mn 

然后你想获得ň指标如下：

索引0

1: 0, 3 
2: 1 
5: 2 

指数1

2: 0, 3 
3: 3, 3 

索引2

3: 0 
1: 1, 3 
2: 2 

...

那么你就只能搜索你的索引，以获取包含任何查询元组的值，并找到内的那些最接近的元组的元组。

def search(query) 
    candidates = [] 
    for i in range(len(query)) 
    value = query[i] 
    candidates.append(indexes[i][value]) 

    # find candidates with min distance 
    for candidate in candidates 
    distance = distance(candidate, query) 
    ... 

沉重的过程是创建索引，一旦你建立索引，搜索将会非常快。