有效地确定列表的"排序方式",例如.Levenshtein距离

Question

我正在对排名算法进行一些研究,并且想要给出排序列表和该列表的一些排列,计算两个排列之间的一些距离.对于Levenshtein距离的情况,这对应于计算序列与该序列的分类副本之间的距离.例如,还有"反转距离",这里详细描述了线性时间算法,我正在努力实现.

有没有人知道反演距离的现有python实现,和/或Levenshtein距离的优化？我在大约50,000到200,000个元素的序列上计算它,因此O(n ^ 2)太慢,但O(n log(n))或更好应该足够.

还可以理解排列相似性的其他度量.

---

为未来的人们编辑:

基于Raymond Hettinger的回应 ; 它不是Levenshtein或反转距离,而是"格式塔模式匹配":P

from difflib import SequenceMatcher
import random
ratings = [random.gauss(1200, 200) for i in range(100000)]
SequenceMatcher(None, ratings, sorted(ratings)).ratio()

在可怕的桌面上运行约6秒钟.

编辑2:如果你可以将你的序列强制转换为[1 .. n]的排列,那么曼哈顿度量的变化非常快并且有一些有趣的结果.

manhattan = lambda l: sum(abs(a - i) for i, a in enumerate(l)) / (0.5 * len(l) ** 2)
rankings = list(range(100000))
random.shuffle(rankings)
manhattan(rankings) # ~ 0.6665, < 1 second

归一化因子在技术上是近似值; 它对于偶数大小的列表是正确的,但应该(0.5 * (len(l) ** 2 - 1))用于奇数大小的列表.

Edit3:还有其他几种算法可用于检查列表相似度!的肯德尔头排名系数和斯皮尔曼等级系数.这些实现的可SciPy的库如scipy.stats.kendalltau和scipy.stats.rspearman,并返回队伍与相关的p值一起.

Answer 1

编辑距离是一个 O(n**2) 算法，因此如果您想更快，请使用difflib 模块中的替代快速算法。比率方法计算两个序列之间的相似性度量。

如果您必须坚持使用 Levenshtein，ASPN Python Cookbook 上有一个 Python 配方： http: //code.activestate.com/recipes/576874-levenshtein-distance/。

另一个 Python 脚本可以在以下位置找到： http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python