कुशलता से निर्धारित करें कि सूची कैसे "क्रमबद्ध" है, उदाहरण के लिए। Levenshtein दूरी

Question

मैं रैंकिंग एल्गोरिदम पर कुछ शोध कर रहा हूं, और एक क्रमबद्ध सूची और उस सूची के कुछ क्रमपरिवर्तन को देना चाहता हूं, दो क्रमिकताओं के बीच कुछ दूरी की गणना करना चाहता हूं। लेवेनशेटिन दूरी के मामले में, यह एक अनुक्रम और उस अनुक्रम की एक क्रमबद्ध प्रति के बीच की दूरी की गणना करने के अनुरूप है। उदाहरण के लिए, "इनवर्जन दूरी" भी है, जिसमें एक रैखिक-समय एल्गोरिदम विस्तृत है here, जिसे मैं कार्यान्वित करने पर काम कर रहा हूं।

किसी को भी उलट दूरी के एक मौजूदा अजगर कार्यान्वयन पता है, और/या Levenshtein दूरी की एक अनुकूलन? मैं इसे लगभग 50,000 से 200,000 तत्वों के अनुक्रम पर इसकी गणना कर रहा हूं, इसलिए ओ (एन^2) बहुत धीमी है, लेकिन ओ (एन लॉग (एन)) या बेहतर होना चाहिए।

क्रमचय समानता के लिए अन्य मीट्रिक भी सराहना की जाएगी। भविष्य के लोगों के लिए

---

संपादित करें:

Raymond Hettinger's response के आधार पर; पी एक भयानक डेस्कटॉप पर ~ 6 सेकंड में

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

रन: यह "समष्टि पैटर्न मिलान" Levenshtein नहीं या उलट दूरी, बल्कि।

EDIT2: आप [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 के रूप में उपलब्ध हैं, और संबंधित पी-मानों के साथ रैंक वापस कर देंगे।

Answer 1

लेवेनशेटिन दूरी एक ओ (एन ** 2) एल्गोरिदम है, इसलिए यदि आप तेजी से जाना चाहते हैं, तो difflib module में वैकल्पिक तेज़ एल्गोरिदम का उपयोग करें। ratio विधि दो अनुक्रमों के बीच समानता की माप की गणना करता है।

यदि आपको लेवेनशेटिन के साथ रहना है, तो एएसपीएन पायथन कुकबुक पर इसके लिए पाइथन रेसिपी है: http://code.activestate.com/recipes/576874-levenshtein-distance/।

एक और अजगर स्क्रिप्ट में पाया जा सकता: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python