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

अभिकलनात्मक भाषाविज्ञान और कंप्यूटर विज्ञान में, संपादन प्रक्रिया एक श्रृंखला मापीय है, अर्थात यह मापने का एक तरीका है कि दो श्रंखला (जैसे, शब्द) एक दूसरे से कितने भिन्न हैं, जो एक श्रृंखला को एक अन्य श्रृंखला में बदलने के लिए आवश्यक संचालन की न्यूनतम संख्या की गणना करके मापा जाता है। संपादन प्रक्रिया प्राकृतिक भाषा प्रसंस्करण में अनुप्रयोगों को खोजना, और जहां स्वचालित वर्तनी परीक्षक एक गलत वर्तनी वाले शब्द के लिए एक शब्दकोश से शब्दों का चयन करके उम्मीदवार सुधार निर्धारित कर सकता है, जो प्रश्न में शब्द के लिए कम प्रक्रिया रखता है। जैव सूचना विज्ञान में, इसका उपयोग डीएनए अनुक्रमों की समानता को निर्धारित करने के लिए किया जा सकता है, जिसे 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. किटेन → सिटेन (k के लिए स्थानापन्न s)
2. सिटेन → सिटन (e के लिए i स्थानापन्न)
3. सिटिन → सिटिंग (अंत में g डालें)

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

1. किटेन → इटेन (0 पर k हटाएं)
2. इटेन → सिटेन (0 पर s डालें)
3. सिटेन → सिटेन (4 पर e हटाएं)
4. सिट्टन → सिट्टिन (4 पर i डालें)
5. सिटिन → सिटिंग (6 पर g डालें)

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 में अहो और पीटरसन द्वारा प्रस्तावित त्रिविमीय काल गतिशील क्रमादेशन कलन विधि है जो भाषा संपादन प्रक्रिया की गणना करता है। व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि नियमित व्याकरण, संपादन प्रक्रिया की गणना के लिए तीव्र कलन विधि उपस्थित हैं।

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

यह भी देखें

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