Python 计算字符串相似度

Question

我想比较3或4位整数的字符串表示。我想将它们分组成“接近度”对。也就是说，pc_dud [3]应该与dud [0]配对。

dud = ['3433', '3467', '3551', '345', '345', '3613'] 
pc_dud = ['3401', '3402', '3430', '0342', '3584']

有没有好的工具可以用来完成这个任务呢（我在想也许是jellyfish之类的东西）？当然，另一种解决方法是将算术差作为“接近度”的指标。大家有什么想法吗？

- LarsVegas

---

difflib 模块。 - Ashwini Chaudhary

区别会更容易，因为它们只是数字。如果它们是字母数字字符串，那么您将执行等效的Levenshtein距离。 - Marc B

这取决于你想如何最小化差异，比如是否可以舍弃一对使得其他所有的更接近...如果不行的话，我会对列表进行排序并将它们压缩在一起。 - Jblasco

这些列表的长度不相等。 - LarsVegas

哈哈哈，我完全不知道你所说的“rough match”是什么意思 ;) - Jblasco

Answer 1

你可以使用difflib模块：

示例：

>>> import difflib
>>> dud = ['3433', '3467', '3551', '345', '345', '3613'] 
>>> pc_dud = ['3401', '3402', '3430', '0342', '3584']
>>> difflib.get_close_matches(dud[0], pc_dud)
['3430']

- Ashwini Chaudhary

Answer 2

如果您想要算术接近度，那么pc_dud[3]将无法与dud[0]匹配。

如果您只想保留唯一的配对，请使用此代码：

dud_ = dud[:]
pc_dud_ = pc_dud[:]

while dud_:
    d1, d2 = min(itertools.product(dud, pc_dud), key=lambda d1,d2: abs(int(d1) - int(d2)))
    dud_.remove(d1)
    pc_dud_.remove(d2)
    print d1, d2

- Hans Then

Answer 3

你可以采用一种方法，计算dud中每个整数字符串与pc_dud中每个整数字符串之间的Levenshtein Distance。这个算法将为您提供每个数字序列之间的编辑距离。编辑距离数字表示将给定序列转换为另一个序列所需的最小步骤数。它考虑插入、删除和替换。

您需要一个数据结构来存储相对于比较序列的编辑距离结果。然后，您可以调查哪个编辑距离最小，然后将它们分组成一对。

以下是两个数组中的两个数字序列在使用levenshtein进行比较时的可视化示例。我使用了这个工具来生成截图。http://www.let.rug.nl/kleiweg/lev/

http://imgur.com/OTJia7W

右下角的数字是最小编辑距离。

- Paul Renton

---

其实，我最初没有注意到算术差异的重点。这可能不是最好的解决方案，但可以作为一个很好的替代选择。 - Paul Renton

Answer 4

如果您按照Paul的建议选择Levenshtein距离路线，请查看Apache的PyLucene - 我相信lucene的FuzzyQuery是基于此构建的。

- Nehar Arora