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

अभिकलनात्मक भाषाविज्ञान और कंप्यूटर विज्ञान में, संपादन दूरी एक श्रृंखला मापीय है, अर्थात यह मापने का एक तरीका है कि दो श्रंखला (जैसे, शब्द) एक दूसरे से कितने भिन्न हैं, जो एक श्रृंखला को एक अन्य श्रृंखला में बदलने के लिए आवश्यक संचालन की न्यूनतम संख्या की गणना करके मापा जाता है। दूरियों को संपादित करें प्राकृतिक भाषा प्रसंस्करण में अनुप्रयोगों को खोजें, और जहां स्वचालित वर्तनी परीक्षक एक गलत वर्तनी वाले शब्द के लिए एक शब्दकोश से शब्दों का चयन करके उम्मीदवार सुधार निर्धारित कर सकता है, जो प्रश्न में शब्द के लिए कम दूरी रखता है। जैव सूचना विज्ञान में, इसका उपयोग डीएनए अनुक्रमों की समानता को निर्धारित करने के लिए किया जा सकता है, जिसे 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: Wagner–Fischer algorithm

लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (नॉनसिमेट्रिक) से दूरी संपादित करें $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 में अहो और पीटरसन द्वारा प्रस्तावित क्यूबिक टाइम डायनेमिक प्रोग्रामिंग एल्गोरिदम है जो भाषा संपादन दूरी की गणना करता है। व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि नियमित व्याकरण, संपादन दूरी की गणना के लिए तेज़ एल्गोरिदम मौजूद हैं। लैंग्वेज एडिट डिस्टेंस में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए फोल्डिंग, त्रुटि सुधार और इष्टतम स्टैक जनरेशन समस्या का समाधान।

यह भी देखें

• ग्राफ़ संपादन दूरी
• श्रृंखला-टू-श्रृंखला सुधार समस्या
• श्रृंखला मापीय
• समय ताना संपादन दूरी