Python中的字符串距离矩阵

Question

如何在Python中计算字符串的Levenshtein距离矩阵？

              str1    str2    str3    str4    ...     strn
      str1    0.8     0.4     0.6     0.1     ...     0.2
      str2    0.4     0.7     0.5     0.1     ...     0.1
      str3    0.6     0.5     0.6     0.1     ...     0.1
      str4    0.1     0.1     0.1     0.5     ...     0.6
      .       .       .       .       .       ...     .
      .       .       .       .       .       ...     .
      .       .       .       .       .       ...     .
      strn    0.2     0.1     0.1     0.6     ...     0.7

利用距离函数，我们可以计算两个单词之间的距离。在我这里，有一个包含N个字符串的列表。希望的结果是计算距离矩阵，然后对单词进行聚类。

- Ajay Jadhav

---

使用NLTK metrics和这篇文章可能对你有帮助。 - Niranj Rajasekaran

@Tanu 这是给出两个单词之间的距离。我想要针对n个单词的矩阵。 - Ajay Jadhav

@AjayJadhav 在任何时候，您都将计算两个单词之间的距离，因此您可以迭代矩阵并一次计算每组两个单词的距离，并填充一个新矩阵。 - Tanu

嘿，Ajay Jadhav和@Tanu，你们能分享一下你们的代码吗？我需要构建相同的矩阵。 - default_settings

这个回答解决了你的问题吗？使用pdist在Python中创建字符串距离矩阵 - evces

Answer 1

只需使用接受自定义度量的版本的

pdist即可。

Y = pdist(X, levensthein)

并且对于 levensthein，您可以使用来自Rosettacode的实现，就像Tanu所建议的那样。

如果您想要一个完整的平方矩阵，只需在结果上使用 squareform 即可。

Y = scipy.spatial.distance.squareform(Y)

- elabard

---

不需要编写算法，有几个PyPI包已经实现了它，例如editdistance、pylev。 - Eli Korvigo

@elabard Pylev适用于2个单词，但我的问题是如何计算矩阵pylev.levenshtein（'kitten'，'sitting'）3。 - Ajay Jadhav

这难道不是我所建议的吗？pdist通过应用levensthein或任何您想要的度量标准来对每对元素进行计算，从而返回一个矩阵... - elabard

只需使用.reshape（-1,1）重新塑形您的输入。 - elabard

如果你有一组不均匀的字符串列表怎么办？像这样的ids 0 [462423-43, 277581-25, 58545-19] 1 [0] 2 [437742-46, 228893-32, 463200-04, 227479-78, 222217-39, 462579-94, 458759-98, 438589-72, 438675-76, 265589-83, 178215-13, 433701-46, 431222-77, 433515-16] 3 [431380-63] - nerdlyfe

Answer 2

这是我的代码

import pandas as pd
from Levenshtein import distance
import numpy as np

Target = ['Tree','Trip','Treasure','Nothingtodo']

List1 = Target
List2 = Target

Matrix = np.zeros((len(List1),len(List2)),dtype=np.int)

for i in range(0,len(List1)):
  for j in range(0,len(List2)):
      Matrix[i,j] = distance(List1[i],List2[j])

print Matrix

[[ 0  2  4 11]
 [ 2  0  6 10]
 [ 4  6  0 11]
 [11 10 11  0]]

- pratiksha

---

就像我在答案中建议的那样，您不必手动处理嵌套的for循环... pdist可以为您完成这项工作，并以更有效的方式进行计算，因为它仅计算上三角距离...（距离始终对称） - elabard

Answer 3

你可以这样做

from Levenshtein import distance
import numpy as np
from time import time

def get_distance_matrix(str_list):
    """ Construct a levenshtein distance matrix for a list of strings"""
    dist_matrix = np.zeros(shape=(len(str_list), len(str_list)))
    t0 = time()
    print "Starting to build distance matrix. This will iterate from 0 till ", len(str_list) 
    for i in range(0, len(str_list)):
        print i
        for j in range(i+1, len(str_list)):
                dist_matrix[i][j] = distance(str_list[i], str_list[j]) 
    for i in range(0, len(str_list)):
        for j in range(0, len(str_list)):
            if i == j:
                dist_matrix[i][j] = 0 
            elif i > j:
                dist_matrix[i][j] = dist_matrix[j][i]
    t1 = time()
    print "took", (t1-t0), "seconds"
    return dist_matrix

str_list = ["analyze", "analyse", "analysis", "analyst"]
get_distance_matrix(str_list)

Starting to build distance matrix. This will iterate from 0 till  4
0
1
2
3
took 0.000197887420654 seconds
>>> array([[ 0.,  1.,  3.,  2.],
   [ 1.,  0.,  2.,  1.],
   [ 3.,  2.,  0.,  2.],
   [ 2.,  1.,  2.,  0.]])

- Zaher Abdul Azeez