一尘不染

Python中的字符串相似性指标

algorithm

我想找到两个字符串之间的字符串相似性。页面包含其中一些示例。Python具有Levenshtein算法的实现。在这些约束下是否有更好的算法(最好是python库)。

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

对于我的情况,除Levenshtein距离(或Levenshtein比率)以外的其他算法是否会更好?


阅读 252

收藏
2020-07-28

共1个答案

一尘不染

谢菲尔德大学有大量的字符串相似性指标资源。它具有各种指标列表(仅包括Levenshtein),并且具有这些指标的开源实现。看起来其中许多应该很容易适应Python。

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

以下是一些清单:

  • 汉明距离
  • 莱文施泰因距离
  • Needleman-Wunch距离或卖方算法
  • 还有很多…
2020-07-28