Determinare in modo efficiente "come ordinato" un elenco, ad es. Distanza di Levenshtein

Question

Sto facendo qualche ricerca sugli algoritmi di classificazione, e vorrei, data una lista ordinata e alcune permutazioni di quella lista, calcolare una certa distanza tra le due permutazioni. Per il caso della distanza di Levenshtein, ciò corrisponde al calcolo della distanza tra una sequenza e una copia ordinata di quella sequenza. C'è anche, ad esempio, la "distanza di inversione", un algoritmo di tempo lineare di cui è dettagliato here, che sto lavorando per l'implementazione.

Qualcuno sa di un'implementazione Python esistente della distanza di inversione e/o un'ottimizzazione della distanza di Levenshtein? Sto calcolando questo su una sequenza di circa 50.000 a 200.000 elementi, quindi O (n^2) è troppo lento, ma O (n log (n)) o meglio dovrebbe essere sufficiente.

Sarebbero anche apprezzati altri parametri per la similarità della permutazione.

---

Modifica per le persone dal futuro:

Basato su Raymond Hettinger's response; non è Levenshtein o la distanza di inversione, ma piuttosto "modello gestalt matching": P

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

viene eseguito in ~ 6 secondi su un terribile desktop.

Edit2: Se riesci a forzare la sequenza in una permutazione di [1 .. n], una variazione della metrica di Manhattan è estremamente veloce e ha alcuni risultati interessanti.

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 

Il fattore di normalizzazione è tecnicamente un'approssimazione; è corretto per elenchi di dimensioni uguali, ma dovrebbe essere (0.5 * (len(l) ** 2 - 1)) per elenchi di dimensioni dispari.

Edit3: Esistono diversi altri algoritmi per la somiglianza della lista di controllo! Il coefficiente di ranking Kendall Tau e il coefficiente di ranking Spearman. Le implementazioni di questi sono disponibili nella libreria SciPy come scipy.stats.kendalltau e scipy.stats.rspearman e restituiranno i gradi insieme ai valori p associati.

Answer 1

La distanza di Levenshtein è un algoritmo O (n ** 2), quindi se si vuole andare più veloce, utilizzare l'algoritmo veloce alternativo nello difflib module. Il metodo ratio calcola una misura di somiglianza tra due sequenze.

Se si deve stare con Levenshtein, vi è una ricetta Python per questo nell'UCN Python Cookbook: http://code.activestate.com/recipes/576874-levenshtein-distance/.

Un altro script Python possono essere trovati a: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python