Python 中的字符串相似性度量

Question

我想找到两个字符串之间的字符串相似度。 en.wikipedia 有其中一些示例。 code.google 有 Levenshtein distance 的 Python 实现。

在这些约束下，是否有更好的算法（希望是 Python 库）：

1. 我想在字符串之间进行模糊匹配。例如 matches(‘Hello, All you people’, ‘hello, all You peopl’) 应该返回 True
2. 假阴性是可以接受的，假阳性，除非在极少数情况下是不可接受的。
3. 这是在非实时设置中完成的，因此速度不是（太多）关注的问题。
4. [编辑] 我正在比较多字串。

除了 Levenshtein 距离（或 Levenshtein 比率）之外的其他算法对我的情况来说会是更好的算法吗？

原文由 agiliq 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

谢菲尔德大学提供了有关字符串相似性指标的大量资源。它有一个各种指标的列表（不仅仅是 Levenshtein）并且有它们的开源实现。看起来它们中的许多应该很容易适应 Python。

http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

这是列表的一部分：

• 汉明距离
• 编辑距离
• Needleman-Wunch 距离或 Sellers 算法
• 还有很多…

原文由 ariddell 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我意识到这不是一回事，但这已经足够接近了：

 >>> import difflib
>>> a = 'Hello, All you people'
>>> b = 'hello, all You peopl'
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower())
>>> seq.ratio()
0.97560975609756095

你可以把它作为一个函数

def similar(seq1, seq2):
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9

>>> similar(a, b)
True
>>> similar('Hello, world', 'Hi, world')
False

原文由 Nadia Alramli 发布，翻译遵循 CC BY-SA 2.5 许可协议