我正在对排名算法进行一些研究，并希望给定一个排序列表和该列表的一些排列，计算两个排列之间的一些距离。对于 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 秒。
Edit2：如果您可以将您的序列强制转换为 [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：还有其他几种检查列表相似性的算法！Kendall Tau排名系数和Spearman排名系数。这些的实现在SciPy库中作为scipy.stats.kendalltau和可用scipy.stats.rspearman，并将返回排名以及相关的 p 值。