एडिट डिस्टेंस (लेवेनश्टाइन डिस्टेंस)

आप recieve लिखते हैं और आपका फ़ोन receive सुझाता है। उसे पता है कि आप करीब थे, क्योंकि दोनों शब्दों में बस कुछ एडिट का फ़र्क है। इस नज़दीकी को, यानी एडिट डिस्टेंस को, मापना गतिशील प्रोग्रामिंग का एक क्लासिक काम है।

एक टेबल, जिसकी बाईं ओर ऊपर से नीचे एक शब्द और ऊपर दूसरा शब्द लिखा है, सेलों में संख्याएँ हैं, और ऊपर-बाएँ से नीचे-दाएँ कोने तक एडिट का एक नारंगी रास्ता है
एक टेबल, जिसकी बाईं ओर ऊपर से नीचे एक शब्द और ऊपर दूसरा शब्द लिखा है, सेलों में संख्याएँ हैं, और ऊपर-बाएँ से नीचे-दाएँ कोने तक एडिट का एक नारंगी रास्ता है

समस्या

एक एडिट किसी शब्द में एक अक्षर का बदलाव करता है: एक अक्षर जोड़ना, एक अक्षर हटाना, या एक अक्षर को दूसरे से बदलना। दो शब्दों के बीच एडिट डिस्टेंस एडिट की वह सबसे कम संख्या है जो एक को दूसरे में बदल दे। cat और cut में 1 का अंतर है, cat और cast में 1, और cat और act में 2। इसे लेवेनश्टाइन डिस्टेंस भी कहते हैं, सोवियत गणितज्ञ व्लादिमीर लेवेनश्टाइन के नाम पर, जिन्होंने 1965 में इसका अध्ययन किया।

टेबल

मान लीजिए d[i][j] एक शब्द के पहले i अक्षरों और दूसरे शब्द के पहले j अक्षरों के बीच का एडिट डिस्टेंस है। किसी शब्द को खाली करने में हर अक्षर के लिए एक बार हटाना पड़ता है, इसलिए d[i][0] = i, और शून्य से शब्द बनाने में हर अक्षर के लिए एक बार जोड़ना पड़ता है, इसलिए d[0][j] = j। अगर अक्षर i, अक्षर j के बराबर है, तो d[i][j] = d[i − 1][j − 1]। नहीं तो d[i][j] = 1 + d[i − 1][j − 1] (बदलना), d[i − 1][j] (हटाना) और d[i][j − 1] (जोड़ना) में से सबसे छोटा।

एक उदाहरण

kitten और sitting के लिए टेबल में 7 पंक्तियाँ और 8 कॉलम हैं। नीचे दाएँ वाला सेल 3 है, और वहाँ से उल्टा पढ़ने पर मिलता है: k को s से बदलें, i, t और t रखें, e को i से बदलें, n रखें, और g जोड़ें। Kitten, sitten, sittin, sitting: तीन एडिट, और टेबल साबित करती है कि इससे छोटी कोई सूची नहीं है।

एडिट उल्टे क्रम में पढ़ना

नीचे दाएँ वाले सेल से शुरू करें और पूछें कि उसका मान किस पड़ोसी से आया। अगर अक्षर मिलते हैं और सेल अपने ऊपर-बाएँ पड़ोसी के बराबर है, तो अक्षर रखा गया था: तिरछा जाएँ। अगर वह ऊपर-बाएँ पड़ोसी से एक ज़्यादा है, तो यह बदलना था; ऊपर वाले सेल से एक ज़्यादा, तो हटाना; बाएँ वाले सेल से एक ज़्यादा, तो जोड़ना। कई रास्ते बराबर हो सकते हैं, और हर एक से एडिट की सबसे छोटी सूची मिलती है।

इतिहास और उपयोग

लेवेनश्टाइन ने यह डिस्टेंस 1965 में गलतियाँ सुधारने वाले कोड पर काम करते हुए पेश किया। टेबल वाला तरीका कई लोगों ने प्रकाशित किया, सबसे मशहूर 1974 में रॉबर्ट वैगनर और माइकल फ़िशर ने, इसलिए इसे अक्सर वैगनर–फ़िशर एल्गोरिदम कहा जाता है। आज एडिट डिस्टेंस से स्पेलिंग सुझावों का क्रम तय होता है, डेटाबेस में टाइपो वाले नाम मिलाए जाते हैं, DNA और प्रोटीन अनुक्रमों की तुलना होती है, और स्पीच रिकग्निशन को अंक दिए जाते हैं।

खुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। जिन दो अक्षरों की तुलना हो रही है, वे हेडिंग में चमकते हैं; एक जैसे अक्षर ऊपर-बाएँ वाले नीले सेल की कॉपी करते हैं, और अलग अक्षर तीनों नीले पड़ोसियों को पढ़कर सबसे छोटे में एक जोड़ते हैं। अंत में नारंगी रास्ता कोने से वापस चलता है, और एडिट टेबल के नीचे दिखते हैं।

अक्सर पूछे जाने वाले प्रश्न

क्या एडिट डिस्टेंस एक मेट्रिक है?

हाँ। यह कभी ऋणात्मक नहीं होता, सिर्फ़ एक जैसे शब्दों के लिए 0 होता है, दोनों दिशाओं में बराबर होता है, और किसी तीसरे शब्द से होकर जाने पर यह कभी छोटा नहीं होता: d(a, c) ≤ d(a, b) + d(b, c)। इसी वजह से यह मिलते-जुलते शब्द खोजने में काम आता है।

डैमेरौ–लेवेनश्टाइन डिस्टेंस क्या है?

एक अतिरिक्त एडिट वाला एडिट डिस्टेंस: पास-पास के दो अक्षरों की अदला-बदली। फ़्रेडरिक डैमेरौ ने 1964 में पाया कि जोड़ना, हटाना, बदलना और अदला-बदली मिलकर 80% से ज़्यादा स्पेलिंग गलतियों को कवर करते हैं। अदला-बदली के साथ recieve और receive में 2 की जगह 1 का अंतर है।

क्या एडिट डिस्टेंस O(m·n) से तेज़ निकाला जा सकता है?

बहुत ज़्यादा नहीं। 2015 में आर्टुर्स बैकर्स और पियोत्र इंडिक ने दिखाया कि किसी ε > 0 के लिए O(n^(2 − ε)) समय लेने वाला तरीका स्ट्रॉन्ग एक्सपोनेंशियल टाइम हाइपोथीसिस को तोड़ देगा, जिसे ज़्यादातर शोधकर्ता सही मानते हैं। फिर भी, मिलते-जुलते शब्दों के लिए टेबल के विकर्ण के आसपास की बस एक पतली पट्टी चाहिए।

DNA की तुलना में एडिट डिस्टेंस का उपयोग कैसे होता है?

जीवविज्ञानी इसी टेबल का इस्तेमाल गिनती की जगह अंकों के साथ करते हैं: मेल होने पर अंक मिलते हैं, और बदलने और खाली जगहों (गैप) पर अक्षरों के हिसाब से अंक कटते हैं। पूरे अनुक्रमों के लिए यह 1970 का नीडलमैन–वुन्श एल्गोरिदम है, और सबसे अच्छे मेल वाले हिस्सों के लिए 1981 का स्मिथ–वॉटरमैन एल्गोरिदम।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिट डिस्टेंस आज़माएँ