有效地确定列表是如何排序的，例如。 Levenshtein距离

我正在做排序算法的一些研究，并希望给定一个排序列表和排列该列表的一些排列，计算两个排列之间的距离。对于Levenshtein距离的情况，这对应于计算序列与该序列的分类副本之间的距离。例如，还有“反转距离”，其中的线性时间算法详述于here，我正在努力实施。有效地确定列表是如何排序的，例如。 Levenshtein距离

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

排列相似性的其他度量也值得赞赏。

编辑从未来的人：基于Raymond Hettinger's response

;它不是莱文斯坦或反转的距离，而是“格式塔模式匹配”：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))。

编辑3：还有其他几种算法用于检查列表相似性！排名系数为Kendall Tau，排名系数为Spearman。这些实现可在SciPy库中作为scipy.stats.kendalltau和scipy.stats.rspearman获得，并将返回行列以及相关的p值。

来源

2011-11-21 stefan

Levenshtein距离是一个O（n ** 2）算法，所以如果您想要更快一点，请使用difflib module中的替代快速算法。方法计算两个序列之间的相似性度量。

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

来源

2011-11-21 02:27:10

的规范DP Levenshtein算法是O（n ** 2），但我知道有很多使用情况允许更快的算法，例如使用[VP-树]（http://www.logarithmic.net/pfh/blog/01164790008）。我将O（n ** 2）算法的实现放在一起，看起来与那些配方相似，但不幸的是，对于我正在做的事情来说太慢了。在此期间，我会检查difflib，谢谢！ – stefan

有效地确定列表是如何排序的，例如。 Levenshtein距离

回答

相关问题