python - 有效地确定 "how sorted"列表是，例如。编辑距离

Question

我正在对排名算法进行一些研究，并且想在给定一个排序列表和该列表的一些排列的情况下，计算两个排列之间的一些距离。对于 Levenshtein 距离的情况，这对应于计算序列和该序列的排序副本之间的距离。还有，例如，“反演距离”，一种线性时间算法，详细说明 here ，我正在努力实现。

有谁知道反演距离的现有 python 实现和/或 Levenshtein 距离的优化？我在大约 50,000 到 200,000 个元素的序列上计算这个，所以 O(n^2) 太慢了，但 O(n log(n)) 或更好应该足够了。

排列相似性的其他指标也将受到赞赏。

---

为 future 的人编辑:

基于 Raymond Hettinger's response ;这不是 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: 还有其他几种检查列表相似性的算法! Kendall Tau排名系数和Spearman排名系数。这些的实现在 SciPy 中可用。库作为 scipy.stats.kendalltau 和 scipy.stats.rspearman，并将返回排名以及相关的 p 值。

Answer 1

Levenshtein 距离是一种 O(n**2) 算法，所以如果你想走得更快，请使用 difflib module 中的替代快速算法。 . ratio 方法计算两个序列之间的相似性度量。

如果您必须坚持使用 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