Python Numpy中的配对编辑距离

Question

所以，我有一个由字符串组成的numpy数组，我想使用这个函数计算每对元素之间的成对编辑距离：scipy.spatial.distance.pdist，链接在http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.spatial.distance.pdist.html。

我的数组样本如下：

 >>> d[0:10]
 array(['TTTTT', 'ATTTT', 'CTTTT', 'GTTTT', 'TATTT', 'AATTT', 'CATTT',
   'GATTT', 'TCTTT', 'ACTTT'], 
  dtype='|S5')

然而，由于它没有“editdistance”选项，因此我想提供一个自定义距离函数。 我尝试了这个并遇到了以下错误：

 >>> import editdist
 >>> import scipy
 >>> import scipy.spatial
 >>> scipy.spatial.distance.pdist(d[0:10], lambda u,v: editdist.distance(u,v))

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/epd-7.3.2/lib/python2.7/site-packages/scipy/spatial/distance.py", line 1150, in pdist
    [X] = _copy_arrays_if_base_present([_convert_to_double(X)])
  File "/usr/local/epd-7.3.2/lib/python2.7/site-packages/scipy/spatial/distance.py", line 153, in _convert_to_double
    X = np.double(X)
ValueError: could not convert string to float: TTTTT

- Vahid Mirjalili

---

看起来它并不适用于字符串。你可能想要查看 https://docs.python.org/2/library/difflib.html - Pavel

那个错误行是pdist中的第二行。因此，在将字符串传递给pdist之前，您需要将其转换为某种数字。另外，pdist需要一个二维数组。 - hpaulj

Answer 1

如果您确实需要使用 pdist，则需要先将字符串转换为数字格式。如果您知道所有字符串的长度都相同，那么这可以很容易地完成：

numeric_d = d.view(np.uint8).reshape((len(d),-1))

这只是将您的字符串数组视为一长串uint8字节，然后重新整形使得每个原始字符串在自己的一行上。在你的例子中，看起来是这样的：

In [18]: d.view(np.uint8).reshape((len(d),-1))
Out[18]:
array([[84, 84, 84, 84, 84],
       [65, 84, 84, 84, 84],
       [67, 84, 84, 84, 84],
       [71, 84, 84, 84, 84],
       [84, 65, 84, 84, 84],
       [65, 65, 84, 84, 84],
       [67, 65, 84, 84, 84],
       [71, 65, 84, 84, 84],
       [84, 67, 84, 84, 84],
       [65, 67, 84, 84, 84]], dtype=uint8)

然后，您可以像往常一样使用 pdist。只需确保您的 editdist 函数期望整数数组而不是字符串。您可以通过调用 .tostring() 快速转换新输入：

def editdist(x, y):
  s1 = x.tostring()
  s2 = y.tostring()
  ... rest of function as before ...

- perimosocordiae

---

或者直接在 uint8 上执行编辑距离。 - eickenberg

Answer 2

def my_pdist(data,f):
    N=len(data)
    matrix=np.empty([N*(N-1)/2])
    ind=0
    for i in range(N):
        for j in range(i+1,N):
            matrix[ind]=f(data[i],data[j])
            ind+=1
    return matrix

- Fenglou Mao

---

提供一些背景信息和额外的说明，以阐明这个答案是如何回答这个问题的，对于原始提问者和未来访问此解决方案的人都有帮助和益处。一个仅包含代码的简短片段并不是一个最佳的回答形式。 - gravity