भरे गए सेल
एडिट डिस्टेंस
रखे गए अक्षर

  • भरा जा रहा है
  • यहाँ से पढ़ा
  • उत्तर

एडिट डिस्टेंस के बारे में और

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

kitten को sitting में बदलने के लिए एक-एक अक्षर के कितने बदलाव चाहिए? तीन: k को s से बदलें, e को i से बदलें, और एक g जोड़ें। यही संख्या एडिट डिस्टेंस है; स्पेल चेकर इसी से सुझावों का क्रम तय करते हैं और जीवविज्ञानी इसी से जीन की तुलना करते हैं। दो शब्द लिखें और देखें कि एक टेबल इसे कैसे ढूँढ़ती है। टेबल को भरते हुए देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। दो शब्द लिखें: पहला टेबल की बाईं ओर ऊपर से नीचे लिखा जाता है, दूसरा ऊपर की ओर बाएँ से दाएँ। हर सेल में एडिट की वह सबसे कम संख्या होती है जो उसकी पंक्ति तक के अक्षरों को उसके कॉलम तक के अक्षरों में बदल देती है। अंत में एडिट नीचे दाएँ सेल से उल्टे क्रम में पढ़े जाते हैं। “नया उदाहरण” शब्दों की कोई दूसरी जोड़ी चुनता है। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. दो शब्द लिखें: पहला टेबल की बाईं ओर ऊपर से नीचे, दूसरा ऊपर की ओर बाएँ से दाएँ लिखा जाता है।
  2. “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
  3. देखें कि हर सेल अपने तीन पड़ोसियों में से सबसे सस्ता कैसे लेता है, फिर एडिट को नारंगी रंग में उल्टे क्रम में पढ़ा जाता देखें।

टेबल कैसे काम करती है

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

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

नीचे दाएँ वाला सेल एडिट डिस्टेंस है। वहाँ से शुरू करके ऐप पता लगाता है कि सेल का मान किस पड़ोसी से आया, और उस पर जाता है: रखे गए या बदले गए अक्षर के लिए तिरछा, हटाए गए अक्षर के लिए ऊपर, जोड़े गए अक्षर के लिए बाएँ। ऊपर-बाएँ से पढ़ने पर ये चरण एडिट की सबसे छोटी सूची बनाते हैं, जो टेबल के नीचे दिखती है: सादा अक्षर रखा गया है, k→s बदलना है, −e हटाना है और +g जोड़ना है।

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

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

यह इसी एडिट डिस्टेंस का दूसरा नाम है: किसी स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के लिए एक-एक अक्षर को जोड़ने, हटाने और बदलने की सबसे कम संख्या। इसका नाम व्लादिमीर लेवेनश्टाइन के नाम पर है, जिन्होंने 1965 में इसका वर्णन किया।

kitten और sitting के बीच एडिट डिस्टेंस कितना है?

3: k को s से बदलें, e को i से बदलें, और अंत में g जोड़ें। टेबल दिखाती है कि इससे छोटी एडिट सूची नहीं हो सकती।

एडिट डिस्टेंस एल्गोरिदम कितना तेज़ है?

m और n लंबाई वाले शब्दों के लिए टेबल में (m + 1)·(n + 1) सेल होते हैं, और हर सेल एक चरण में भरता है, इसलिए इसमें O(m·n) समय लगता है। अगर सिर्फ़ डिस्टेंस चाहिए, तो टेबल की दो पंक्तियाँ काफ़ी हैं।

और कौन-से एडिट डिस्टेंस होते हैं?

डैमेरौ–लेवेनश्टाइन डिस्टेंस पास-पास के दो अक्षरों की अदला-बदली को भी एक एडिट गिनता है, जो टाइपिंग की गलतियों के लिए ठीक बैठता है। हैमिंग डिस्टेंस सिर्फ़ बदलने की अनुमति देता है और बराबर लंबाई की स्ट्रिंग पर काम करता है। LCS डिस्टेंस सिर्फ़ जोड़ने और हटाने की अनुमति देता है।

क्या कुछ कहीं भेजा जाता है?

नहीं। सारी गणना आपके ब्राउज़र में होती है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

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

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

एडिटर पर जाएँ