Determina de manera eficiente "cómo está ordenada" una lista, p. Ej. Distancia de Levenshtein

Question

Estoy investigando algoritmos de clasificación, y me gustaría, dada una lista ordenada y alguna permutación de esa lista, calcular la distancia entre las dos permutaciones. Para el caso de la distancia de Levenshtein, esto corresponde al cálculo de la distancia entre una secuencia y una copia ordenada de esa secuencia. También existe, por ejemplo, la "distancia de inversión", cuyo algoritmo de tiempo lineal se detalla en here, y estoy trabajando en su implementación.

¿Alguien sabe de una implementación de python existente de la distancia de inversión, y/o una optimización de la distancia de Levenshtein? Estoy calculando esto en una secuencia de alrededor de 50,000 a 200,000 elementos, por lo que O (n^2) es demasiado lento, pero O (n log (n)) o mejor debería ser suficiente.

Otras métricas para la similitud de permutación también se apreciarían.

---

Editar para la gente del futuro:

Basado en Raymond Hettinger's response; no es levenshtein o la distancia de inversión, sino más bien "coincidencia de patrones gestalt": P

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

carreras en ~ 6 segundos en un terrible escritorio.

Edit2: Si puede forzar su secuencia en una permutación de [1 .. n], entonces una variación de la métrica de Manhattan es extremadamente rápida y tiene algunos resultados interesantes.

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 

El factor de normalización es técnicamente una aproximación; es correcto para listas de tamaño par, pero debe ser (0.5 * (len(l) ** 2 - 1)) para listas de tamaños impares.

Edit3: ¡Hay varios otros algoritmos para verificar la similitud de la lista! El coeficiente de clasificación Kendall Tau y el coeficiente de clasificación Spearman. Las implementaciones de estos están disponibles en la biblioteca SciPy como scipy.stats.kendalltau y scipy.stats.rspearman, y devolverán los rangos junto con los valores p asociados.

Answer 1

Levenshtein distance es un algoritmo O (n ** 2), por lo que si desea ir más rápido, utilice el algoritmo alternativo rápido en el difflib module. El método ratio calcula una medida de similitud entre dos secuencias.

Si tiene que seguir con Levenshtein, hay una receta de Python para él en el Cookbook de ASPN Python: http://code.activestate.com/recipes/576874-levenshtein-distance/.

otro script Python se puede encontrar en: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python