0

我有一个大约 100 万个唯一的 16 个字符的字符串列表（一个称为 VEC 的数组），我想计算 Python 中每个字符串的最小成对汉明距离（一个称为 RES 的数组）。基本上，我一次计算一行完整的成对距离矩阵，但只将每行的最小值存储在 RES 中。

VEC= ['AAAAAAAAAAAAAAAA','AAAAAAAAAAAAAAAT','AAAAGAAAAAATAAAA'...]

因此 dist(VEC[1],VEC[2])=1, dist(VEC[1],VEC[3])=2 等等...并且 RES[1]=1。使用这些页面中的提示和技巧，我想出了：

#METHOD#1:
import Levenshtein
import numpy
RES=99*numpy.ones(len(VEC))
i=0
for a in VEC:
    dist=numpy.array([Levenshtein.hamming(a,b) for b in VEC] ) #array of distances
    RES[i]=numpy.amin(dist[dist>0])  #pick min distance greater than zero
    i+=1

一个只有 10,000 的缩短 VEC 大约需要 70 秒，但如果我将其推断为整百万，则需要 8 天。我的方法似乎很浪费，因为我正在重新计算距离矩阵的对称部分，所以我尝试计算矩阵的一半，同时更新每一行的 RES：

#METHOD #2:
import Levenshtein
import numpy
RES=99*numpy.ones(len(VEC))
for i in range(len(VEC)-1):
    dist=[Levenshtein.hamming(VEC[i],VEC[j]) for j in range(i+1, len(VEC))]
    RES[i]=min(numpy.amin(dist),RES[i])
    #update RES as you go along:
    k=0
    for j in range(i+1,len(VEC)):
        if dist[k]<RES[j]:
             RES[j]=dist[k]
        k+=1

可能并不奇怪，第二种方法需要几乎两倍的时间（117 秒），所以它不是很好。无论如何，任何人都可以推荐改进/更改以使其更快吗？

4

2 回答 2

1

如果您只需要每个二进制文件的最近邻居（忽略自身），并且您可能只获得一个近似最近邻居的可能性很小，那么您可以考虑为汉明距离实施“位采样”局部敏感哈希。简而言之，创建三个哈希表。从每个 128 位输入中，使用这 16 位样本作为键，对 16 位进行 3 次采样。哈希表的值应该是具有该采样键的所有 128 位输入的列表。将所有数百万个输入放入 LSH 索引后，只需：

  • 迭代超过百万点
  • 对于每个输入，执行上述 3 次采样
  • 在三个列表的每一个中找到最近的邻居（距离> 0），保持最好的整体

加载和测试都快得离谱。我可能会推荐优秀的bitarray库来支持这一点。

于 2015-03-19T21:22:50.027 回答
0

我尝试使用 numpy。这是我的代码：

#!/usr/bin/env python

import numpy as np
import time

def gen_data(n):
    arr = np.empty(shape=(n, 16))
    for i in range(n):
        arr[i] = np.random.randint(ord('A'), ord('Z')+1, 16)
    return arr

def distance_from_array(i, arr):
    r = arr[i] != arr
    r[i,:] = True
    min_i = np.argmin(np.sum(r, axis=1))
    return min_i

data = gen_data(1000000)
distances = []
start = time.time()
for i in range(200):
    distances.append(distance_from_array(i, data))
end = time.time()
print end - start

您可以将字符串列表转换为数字数组。然后您可以使用 numpy 函数来处理数组，例如 sum 和 argmin。如果一个字符串可能出现两次，我认为你不想只找到大于 1 的距离。

我在我的电脑上测试了一下，处理 200 个字符串大约需要 10 秒。对于每一个，您必须遍历所有 1 000 000 个其他字符串，因此我们可以相当容易地计算出处理所有这些字符串所需的时间。应该是13小时左右。但是，不要忘记我们目前只使用一个核心。如果您拆分索引并使用http://docs.python.org/2/library/multiprocessing.html#module-multiprocessing.pool，您可以很快得到结果。

于 2013-05-30T20:16:08.807 回答