दूरी संपादित करें

अभिकलनात्मक भाषाविज्ञान और कंप्यूटर विज्ञान में, संपादन दूरी एक श्रृंखला मापीय है, अर्थात यह मापने का एक तरीका है कि दो श्रंखला (जैसे, शब्द) एक दूसरे से कितने भिन्न हैं, जो एक श्रृंखला को एक अन्य श्रृंखला में बदलने के लिए आवश्यक संचालन की न्यूनतम संख्या की गणना करके मापा जाता है। दूरियों को संपादित करें प्राकृतिक भाषा प्रसंस्करण में अनुप्रयोगों को खोजें, और जहां स्वचालित वर्तनी परीक्षक एक गलत वर्तनी वाले शब्द के लिए एक शब्दकोश से शब्दों का चयन करके उम्मीदवार सुधार निर्धारित कर सकता है, जो प्रश्न में शब्द के लिए कम दूरी रखता है। जैव सूचना विज्ञान में, इसका उपयोग डीएनए अनुक्रमों की समानता को निर्धारित करने के लिए किया जा सकता है, जिसे A, C, G और T अक्षरों की श्रंखला के रूप में देखा जा सकता है।

संपादन दूरी की विभिन्न परिभाषाएँ श्रृंखला संचालन के विभिन्न सम्मुच्चयों का उपयोग करती हैं। लेवेनशेटिन दूरी संचालन श्रृंखला में किसी वर्ण को हटाना, सम्मिलित करना या प्रतिस्थापन करना सम्मिलित है। सबसे सामान्यतः मापीय होने के नाते, 'लेवेनशेटिन दूरी' शब्द का प्रयोग प्रायः 'संपादन दूरी' के साथ एक दूसरे के स्थान पर किया जाता है।

संपादन दूरी के प्रकार

विभिन्न प्रकार की संपादन दूरी श्रृंखला संचालन के विभिन्न सम्मुच्चयों की अनुमति देती है। उदाहरण के लिए:

• लेवेंस्टीन दूरी विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
• सबसे लंबी सामान्य अनुगामी (LCS) दूरी केवल प्रविष्टि और विलोपन की अनुमति देती है, प्रतिस्थापन की नहीं।
• हैमिंग दूरी केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के श्रंखलाओं पर लागू होती है।
• दमेरौ-लेवेनशेटिन दूरी दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और स्थिति अंतरण (गणित) की अनुमति देती है।
• जारो दूरी केवल स्थानान्तरण (गणित) की अनुमति देती है।

कुछ संपादन दूरियों को अनुमत संपादन कार्यों के एक विशिष्ट सम्मुच्चय के साथ परिकलित एक मापदण्ड योग्य मापीय के रूप में परिभाषित किया गया है, और प्रत्येक संचालन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए अनुक्रम संरेखण कलन विधि जैसे स्मिथ-वाटरमैन कलन विधि द्वारा आगे सामान्यीकृत किया गया है, जो एक संचालन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।

औपचारिक परिभाषा और गुण

दो श्रंखला a और b दिए गए वर्णमाला Σ पर (उदाहरण ASCII वर्णों का सम्मुच्चय, बाइट्स का सम्मुच्चय [0..255], आदि), संपादन दूरी d(a, b) संपादन संचालन की न्यूनतम-भार श्रृंखला है जो a को b में बदल देती है। संपादन संचालन के सबसे सरल सम्मुच्चयों में से एक है जिसे 1966 में लेवेनशेटिन द्वारा परिभाषित किया गया था:

एकल प्रतीक का अंतर्वेशन। यदि a = uv, फिर प्रतीक x सम्मिलित करना uxv उत्पन्न करता है। इसे ε →x भी निरूपित किया जा सकता है, खाली श्रृंखला को निरूपित करने के लिए ε का उपयोग किया जा सकता है।

एकल प्रतीक परिवर्तन का विलोपन uxv को uv (x→ε) में परिवर्तित कर देता है।

एकल प्रतीक का प्रतिस्थापन x प्रतीक के लिए y ≠ x uxv को uyv (x→y) में परिवर्तित कर देता है।

लेवेनशेटिन की मूल परिभाषा में, इनमें से प्रत्येक संचालन की इकाई लागत होती है (सिवाय इसके कि एक चरित्र के प्रतिस्थापन की लागत शून्य होती है), इसलिए लेवेनशेटिन की दूरी a को b रूपांतरण के लिए आवश्यक संचालन की न्यूनतम संख्या के बराबर होती है। एक अधिक सामान्य परिभाषा गैर-नकारात्मक भार कार्यों w_ins(x), w_del(x) और w_sub(x, y) को संचालन के साथ जोड़ती है।

अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन दूरी एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक संचालन द्वारा विशेषता जो uxyv में uyxv को बदलता है। प्रकाशिक संप्रतीक अभिज्ञान निष्पाद को सही करने के कार्य के लिए, विलय और विपाट संचालन का उपयोग किया गया है जो एकल भूमिका को उनमें से एक जोड़ी या इसके विपरीत में बदल देता है।

संचालन के सम्मुच्चय को प्रतिबंधित करके संपादन दूरी के अन्य संस्करण प्राप्त किए जाते हैं। सबसे लंबी सामान्य बाद की समस्या | सबसे लंबी सामान्य अनुवर्ती (एलसीएस) दूरी इकाई लागत पर केवल दो संपादन कार्यों के रूप में सम्मिलन और विलोपन के साथ संपादन दूरी है। इसी तरह, केवल प्रतिस्थापन (फिर से इकाई लागत पर) की अनुमति देकर, हैमिंग दूरी प्राप्त की जाती है; यह समान-लंबाई वाले श्रंखलाओं तक ही सीमित होना चाहिए। जारो-विंकलर दूरी को संपादित दूरी से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।

उदाहरण

बिल्ली के बच्चे और बैठने के बीच लेवेनशेटिन की दूरी 3 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:

1. बिल्ली का बच्चा → बैठा हुआ (के के लिए स्थानापन्न s)
2. बैठे → बैठे (ई के लिए i स्थानापन्न)
3. सिटिन → सिटिंग (अंत में g डालें)

LCS दूरी (केवल सम्मिलन और विलोपन) एक अलग दूरी और न्यूनतम संपादन स्क्रिप्ट देता है:

1. बिल्ली का बच्चा → इटेन (0 पर k हटाएं)
2. itten → बैठे (0 पर एस डालें)
3. बैठे → बैठे (4 पर ई हटाएं)
4. सिट्टन → सिट्टिन (4 पर i डालें)
5. सिटिन → सिटिंग (6 पर जी डालें)

5 संचालन की कुल लागत/दूरी के लिए।

गुण

गैर-ऋणात्मक लागत के साथ संपादन दूरी एक मापीय (गणित) के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित परिस्तिथि पूरी होती हैं, तो श्रृंखला के एक मापीय स्थान को उत्पन्न करता है:

• हर संपादन संचालन की सकारात्मक लागत होती है;
• प्रत्येक संचालन के लिए समान लागत के साथ एक व्युत्क्रम संचालन होता है।

इन गुणों के साथ, मापीय स्वयंसिद्ध निम्नानुसार संतुष्ट हैं:

d(a, b) = 0 यदि और केवल यदि a = b, क्योंकि प्रत्येक श्रृंखला को बिल्कुल शून्य संचालन का उपयोग करके तुच्छ रूप से परिवर्तित किया जा सकता है।

d(a, b) > 0 जब a ≠ b, क्योंकि इसके लिए गैर-शून्य लागत पर कम से कम एक संचालन की आवश्यकता होगी।

d(a, b) = d(b, a) प्रत्येक संचालन की लागत और उसके व्युत्क्रम की समानता।

असमानित त्रिकोण: d(a, c) ≤ d(a, b) + d(b, c).

ईकाई लागत के साथ लेवेनशेटिन दूरी और एलसीएस दूरी उपरोक्त परिस्थितियों को पूरा करते हैं, और इसलिए मापीय स्वयंसिद्ध हैं। संपादन दूरी के परिवर्ती जो उचित आव्यूह नहीं हैं, उन पर भी साहित्य में विचार किया गया है।

इकाई-लागत संपादित दूरियों के अन्य उपयोगी गुणों में सम्मिलित हैं:

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

लागत/भार पर ध्यान दिए बिना, निम्नलिखित संपत्ति सभी संपादन दूरी रखती है:

• जब a और b एक सामान्य उपसर्ग साझा करें, इस उपसर्ग का दूरी पर कोई प्रभाव नहीं पड़ता है। औपचारिक रूप से, जब a = uv और b = uw, तब d(a, b) = d(v, w). यह संपादन दूरी और संपादन आलेख से जुड़ी कई संगणनाओं को तेज करने की अनुमति देता है, क्योंकि सामान्यतः उपसर्गों और प्रत्ययों को रैखिक समय में छोड़ दिया जा सकता है।

संगणना

श्रंखलाओं की एक जोड़ी के बीच न्यूनतम संपादन दूरी की गणना के लिए पहला कलन विधि 1964 में फ्रेडरिक जे डमेराउ द्वारा प्रकाशित किया गया था।

सामान्य कलन विधि

Main article: वैगनर-फिशर कलन विधि

लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (असममितीय) से दूरी $a=a_{1}\ldots a_{m}$ को $b=b_{1}\ldots b_{n}$ संपादन $d_{mn}$ द्वारा दिया गया है, पुनरावर्ती परिभाषा द्वारा निम्न परिभाषित

${\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}$

पुनरावर्ती खंड के न्यूनीकरण में एक और शब्द जोड़कर पारदर्शिता को संभालने के लिए इस कलन विधि को सामान्यीकृत किया जा सकता है।

इस पुनरावृत्ति का मूल्यांकन करने का सीधा, पुनरावर्तन (कंप्यूटर विज्ञान) तरीका घातीय समय लेता है। इसलिए, यह सामान्यतः एक गतिशील क्रमादेशन कलन विधि का उपयोग करके गणना की जाती है जिसे सामान्यतः वैगनर-फिशर कलन विधि को श्रेय दिया जाता है। हालांकि इसका कई आविष्कारों का इतिहास है। वैगनर-फिशर कलन विधि के पूरा होने के बाद, गतिशील क्रमादेशन कलन विधि के उपरान्त उपयोग किए जाने वाले संचालन के पश्व-अनुरेखन के रूप में संपादन संचालन का एक न्यूनतम अनुक्रम $d_{mn}$ पढ़ा जा सकता है।

इस कलन विधि में Θ की समय जटिलता (mn) है जहाँ m और n श्रंखला की लंबाई हैं। जब पूर्ण गतिशील क्रमादेशन तालिका का निर्माण किया जाता है, तो इसकी अंतरिक्ष जटिलता Θ(mn) भी होती है; इसमें Θ(min(m,n)) सुधार किया जा सकता है यह देखते हुए कि किसी भी समय, कलन विधि को स्मृति में केवल दो पंक्तियों (या दो स्तंभ) की आवश्यकता होती है। हालाँकि, यह अनुकूलन संपादन कार्यों की न्यूनतम श्रृंखला को पढ़ना असंभव बनाता है। इस समस्या का एक रैखिक-अंतरिक्ष समाधान हिर्शबर्ग के कलन विधि द्वारा प्रस्तुत किया गया है। इस तरह की पुनरावृत्ति को हल करने के लिए एक सामान्य पुनरावर्ती विभाजन-और-जीत रूपरेखा, निविष्ट के आकार में अंतरिक्ष रैखिक में कुशलता से संचालन के एक इष्टतम अनुक्रम को निकालने के लिए चौधरी, ले और रामचंद्रन द्वारा दिया गया है।

बेहतर कलन विधि

ऊपर वर्णित वैगनर-फिशर कलन विधि में सुधार करते हुए, एस्को उकोनेन कई रूपों का वर्णन करता है, जिनमें से एक में दो श्रंखला और अधिकतम संपादन दूरी s, और प्रतिलाभ min(s, d) होती है। यह केवल अपने विकर्ण के चारों ओर गतिशील क्रमादेशन तालिका के एक भाग की गणना और भंडारण करके इसे प्राप्त करता है। इस कलन विधि O(s×min(m,n)) में समय लगता है, जहाँ m और n श्रंखला की लंबाई हैं। अंतरिक्ष जटिलता O(s²) या O(s) है, इस पर निर्भर करता है कि संपादन अनुक्रम को पढ़ने की आवश्यकता है या नहीं।

लैंडौ, मायर्स और श्मिट [1] द्वारा किए गए और सुधार एक O(s² + max(m,n)) समय कलन विधि देते हैं।

एक परिमित वर्णमाला और संपादन लागत के लिए जो एक दूसरे के गुणक हैं, सबसे तेज़ ज्ञात सटीक एल्गोरिदम मासेक और पैटरसन का है जिसमें O(nm/logn) का सबसे खराब वस्तुस्थिति कार्यावधि है।।

अनुप्रयोग

संपादन दूरी अभिकलनात्मक जीवविज्ञान और प्रकृत भाषा संसाधन में अनुप्रयोग ढूंढता है, उदा. वर्तनी की त्रुटियों या ओसीआर त्रुटियों का सुधार, और अनुमानित श्रृंखला मिलान, जहां उद्देश्य कई लंबे पाठों में छोटी श्रृंखला के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की अपेक्षा की जाती है।

विभिन्न कलन विधि उपस्थित हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए श्रंखलाओं की एक जोड़ी के बीच की दूरी की गणना के साथ-साथ समस्याओं को हल करते हैं।

• हिर्शबर्ग का कलन विधि दो श्रृंखला के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन दूरी को कम करने के रूप में परिभाषित किया गया है।
• अनुमानित श्रृंखला मिलान संपादन दूरी के संदर्भ में तैयार किया जा सकता है। उकोनेन का 1985 का कलन विधि एक श्रृंखला p लेता है, जिसे पतिरूप और स्थिर k कहा जाता है; यह तब एक नियतात्मक परिमित अवस्था यंत्र मानव बनाता है जो एक मनमाने ढंग से श्रृंखला में s पाता है, एक उपरज्जु जिसकी संपादन दूरी p ज्यादा से ज्यादा k है (cf. अहो-कोरासिक कलन विधि, जो समान रूप से किसी भी पतिरूप को खोजने के लिए एक यंत्र मानव का निर्माण करता है, लेकिन संपादन कार्यों की अनुमति के बिना)। अनुमानित श्रृंखला मिलान के लिए एक समान कलन विधि बिटप है, जिसे संपादन दूरी के संदर्भ में भी परिभाषित किया गया है।
• लेवेनशेटिन रोबोट परिमित-अवस्था वाली मशीनें हैं जो एक निश्चित संदर्भ श्रृंखला की सीमित संपादन दूरी के भीतर श्रृंखला के एक सम्मुच्चय को पहचानती हैं।

भाषा संपादन दूरी

श्रृंखला के बीच संपादन दूरी का एक सामान्यीकरण श्रृंखला और भाषा के बीच भाषा संपादन दूरी है, सामान्यतः एक औपचारिक भाषा है। एक श्रृंखला और दूसरे के बीच संपादन दूरी पर विचार करने के स्थान पर, भाषा संपादन दूरी न्यूनतम संपादन दूरी है जिसे एक निश्चित श्रृंखला और श्रृंखला के सम्मुच्चय से ली गई किसी भी श्रृंखला के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा L और श्रृंखला x के लिए एक वर्णमाला Σ के ऊपर, भाषा संपादन दूरी d(L, x) $d(L,x)=\min _{y\in L}d(x,y)$ द्वारा दी गई है, जहाँ $d(x,y)$ श्रृंखला संपादन दूरी है। जब भाषा एल प्रसंग-मुक्त भाषा है, तो 1972 में अहो और पीटरसन द्वारा प्रस्तावित त्रिविमीय काल गतिशील क्रमादेशन कलन विधि है जो भाषा संपादन दूरी की गणना करता है। व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि नियमित व्याकरण, संपादन दूरी की गणना के लिए तीव्र कलन विधि उपस्थित हैं।

लैंग्वेज संपादन दूरी में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए वलन, त्रुटि सुधार और इष्टतम स्तंभ जनन समस्या का समाधान।

यह भी देखें

• आलेख संपादन दूरी
• श्रृंखला-से-श्रृंखला सुधार समस्या
• श्रृंखला मापीय
• समय आधार संपादन दूरी