Skutecznie określa "sortowanie" listy, np. Levenshtein odległość

Question

Robię pewne badania na temat algorytmów rankingowych, i chciałbym, biorąc pod uwagę posortowaną listę i pewną permutację tej listy, obliczyć odległość między dwoma permutacjami. W przypadku odległości Levenshteina odpowiada to obliczeniu odległości między sekwencją a posortowaną kopią tej sekwencji. Istnieje również na przykład "odległość inwersji", której algorytm liniowy jest szczegółowy here, nad którym pracuję.

Czy ktoś wie o istniejącej implementacji Pythona odległości inwersji i/lub optymalizacji odległości Levenshtein? Obliczam to na sekwencji około 50 000 do 200 000 elementów, więc O (n^2) jest o wiele za wolne, ale O (n log (n)) lub lepsze powinny wystarczyć.

Inne parametry dotyczące podobieństwa permutacji również zostałyby docenione.

---

Edycja dla ludzi z przyszłości:

oparciu o Raymond Hettinger's response; to nie Levenshteina lub odległość inwersja, ale raczej „dopasowanie” gestalt wzór: P

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

działa w ~ 6 sekund na strasznym pulpicie.

Edit2: Jeśli można zmusić swoją sekwencję w permutacji [1 .. n], a następnie odmianą metryką Manhattan jest bardzo szybki i ma kilka ciekawych wyników.

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 

Współczynnik normalizacji jest technicznie aproksymacją; jest poprawny dla list o wyrównanych rozmiarach, ale powinien mieć wartość (0.5 * (len(l) ** 2 - 1)) dla list o nietypowych rozmiarach.

Edycja3: Istnieje kilka innych algorytmów do sprawdzania podobieństwa listy! Współczynnik rankingowy Kendall Tau i współczynnik rankingowy Spearman. Implementacje tych są dostępne w bibliotece SciPy jako scipy.stats.kendalltau i scipy.stats.rspearman i zwrócą szeregi wraz z powiązanymi wartościami p.

Answer 1

Odległość odstępu to algorytm O (n ** 2), więc jeśli chcesz jechać szybciej, użyj alternatywnego szybkiego algorytmu w difflib module. Metoda oblicza miarę podobieństwa między dwiema sekwencjami.

Jeśli musisz trzymać się Levenshteina, istnieje przepis Pythona na ten temat w podręczniku ASPN Python Cookbook: http://code.activestate.com/recipes/576874-levenshtein-distance/.

Inny skrypt Pythona można znaleźć w: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python