दूरी संपादित करें: Difference between revisions

Revision as of 12:03, 1 May 2023

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

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

संपादन प्रक्रिया के प्रकार

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

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

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

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

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

एकल प्रतीक का अंतर्वेशन। यदि

a

=

u

v

, फिर प्रतीक

x

सम्मिलित करना

u

x

v

उत्पन्न करता है। इसे ε →

x

भी निरूपित किया जा सकता है, खाली श्रृंखला को निरूपित करने के लिए ε का उपयोग किया जा सकता है।

एकल प्रतीक परिवर्तन का विलोपन

u

x

v

को

u

v

(

x

→ε) में परिवर्तित कर देता है।

एकल प्रतीक का प्रतिस्थापन

x

प्रतीक के लिए

y

≠

x

u

x

v

को

u

y

v

(

x

→

y

) में परिवर्तित कर देता है।

लेवेनशेटिन की मूल परिभाषा में, इनमें से प्रत्येक संचालन की इकाई लागत होती है (सिवाय इसके कि एक चरित्र के प्रतिस्थापन की लागत शून्य होती है), इसलिए लेवेनशेटिन की प्रक्रिया $a$ को $b$ रूपांतरण के लिए आवश्यक संचालन की न्यूनतम संख्या के बराबर होती है। एक अधिक सामान्य परिभाषा गैर-नकारात्मक भार कार्यों $w$ _ins( $x$ ), $w$ _del( $x$ ) और $w$ _sub( $x$ , $y$ ) को संचालन के साथ जोड़ती है।^[2]

अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन प्रक्रिया एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक संचालन द्वारा विशेषता जो $u$ $x$ $y$ $v$ में $u$ $y$ $x$ $v$ को बदलता है। ^[3]^[4] प्रकाशिक संप्रतीक अभिज्ञान निष्पाद को सही करने के कार्य के लिए, विलय और विपाट संचालन का उपयोग किया गया है जो एकल भूमिका को उनमें से एक जोड़ी या इसके विपरीत में बदल देता है।^[4]

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

उदाहरण

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

किटेन → सिटेन (k के लिए स्थानापन्न s)
सिटेन → सिटन (e के लिए i स्थानापन्न)
सिटिन → सिटिंग (अंत में g डालें)

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

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

5 संचालन की कुल लागत/प्रक्रिया के लिए।

गुण

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

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

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

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

).^[5]

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

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

एलसीएस प्रक्रिया श्रंखला की एक जोड़ी की लंबाई के योग से ऊपर है।^[1]^: 37
एलसीएस प्रक्रिया लेवेनशेटिन प्रक्रिया पर ऊपरी सीमा है।
समान लंबाई के श्रंखलाओं के लिए, हैमिंग प्रक्रिया लेवेनशेटिन प्रक्रिया पर एक ऊपरी सीमा होती है।^[1]

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

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

संगणना

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

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

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

{\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}}

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

भाषा संपादन प्रक्रिया

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

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

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Navarro, Gonzalo (1 March 2001). "अनुमानित स्ट्रिंग मिलान के लिए एक निर्देशित दौरा" (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. S2CID 207551224. Retrieved 19 March 2015.
↑ ^2.0 ^2.1 ^2.2 ^2.3 Daniel Jurafsky; James H. Martin. भाषण और भाषा प्रसंस्करण. Pearson Education International. pp. 107–111.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 Esko Ukkonen (1983). अनुमानित स्ट्रिंग मिलान पर. Foundations of Computation Theory. Springer. pp. 487–495. doi:10.1007/3-540-12689-9_129.
↑ ^4.0 ^4.1 ^4.2 ^4.3 Schulz, Klaus U.; Mihov, Stoyan (2002). "लेवेनशेटिन ऑटोमेटा के साथ फास्ट स्ट्रिंग सुधार". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8. S2CID 207046453.
↑ Lei Chen; Raymond Ng (2004). On the marriage of L_p-norms and edit distance (PDF). Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi:10.1016/b978-012088469-8.50070-x.
↑ Kukich, Karen (1992). "पाठ में स्वचालित रूप से शब्दों को ठीक करने की तकनीकें" (PDF). ACM Computing Surveys. 24 (4): 377–439. doi:10.1145/146370.146380. S2CID 5431215. Archived from the original (PDF) on 2016-09-27. Retrieved 2017-11-09.
↑ R. Wagner; M. Fischer (1974). "स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या". J. ACM. 21: 168–178. doi:10.1145/321796.321811. S2CID 13381535.
↑ Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. Bibcode:2008adm..book.....S. ISBN 978-1-849-96720-4.
↑ Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (July 2010). "जैव सूचना विज्ञान के लिए कैश-बेपरवाह गतिशील प्रोग्रामिंग". IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). 7 (3): 495–510. doi:10.1109/TCBB.2008.94. PMID 20671320. S2CID 2532039.
↑ Ukkonen, Esko (1985). "अनुमानित स्ट्रिंग मिलान के लिए एल्गोरिदम" (PDF). Information and Control. 64 (1–3): 100–118. doi:10.1016/S0019-9958(85)80046-2.
↑ Landau; Myers; Schmidt (1998). "वृद्धिशील स्ट्रिंग तुलना". SIAM Journal on Computing. 27 (2): 557–582. CiteSeerX 10.1.1.38.1766. doi:10.1137/S0097539794264810.
↑ Masek, William J.; Paterson, Michael S. (February 1980). "एक तेज़ एल्गोरिथम कंप्यूटिंग स्ट्रिंग संपादन दूरी". Journal of Computer and System Sciences. 20 (1): 18–31. doi:10.1016/0022-0000(80)90002-1. ISSN 0022-0000.
↑ Esko Ukkonen (1985). "तार में अनुमानित पैटर्न ढूँढना". J. Algorithms. 6: 132–137. doi:10.1016/0196-6774(85)90023-9.
↑ ^14.0 ^14.1 Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). "Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product" (PDF). 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 375–384. arXiv:1707.05095. doi:10.1109/focs.2016.48. ISBN 978-1-5090-3933-3. S2CID 17064578.
↑ Aho, A.; Peterson, T. (1972-12-01). "प्रसंग-मुक्त भाषाओं के लिए एक न्यूनतम दूरी त्रुटि-सुधार पार्सर". SIAM Journal on Computing. 1 (4): 305–312. doi:10.1137/0201022. ISSN 0097-5397.
↑ Wagner, Robert A. (1974). "आदेश-एन नियमित भाषाओं के लिए सुधार". Communications of the ACM. 17 (5): 265–268. doi:10.1145/360980.360995. S2CID 11063282.
↑ Saha, B. (2014-10-01). डाइक लैंग्वेज एडिट डिस्टेंस प्रॉब्लम इन नियर-लीनियर टाइम. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 611–620. doi:10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.

[navarro-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Navarro, Gonzalo (1 March 2001). "अनुमानित स्ट्रिंग मिलान के लिए एक निर्देशित दौरा" (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. S2CID 207551224. Retrieved 19 March 2015.

[slp-2] 2.0 ^2.1 ^2.2 ^2.3 Daniel Jurafsky; James H. Martin. भाषण और भाषा प्रसंस्करण. Pearson Education International. pp. 107–111.

[ukkonen83-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 Esko Ukkonen (1983). अनुमानित स्ट्रिंग मिलान पर. Foundations of Computation Theory. Springer. pp. 487–495. doi:10.1007/3-540-12689-9_129.

[ssm-4] 4.0 ^4.1 ^4.2 ^4.3 Schulz, Klaus U.; Mihov, Stoyan (2002). "लेवेनशेटिन ऑटोमेटा के साथ फास्ट स्ट्रिंग सुधार". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8. S2CID 207046453.

[5] Lei Chen; Raymond Ng (2004). On the marriage of L_p-norms and edit distance (PDF). Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi:10.1016/b978-012088469-8.50070-x.

[6] Kukich, Karen (1992). "पाठ में स्वचालित रूप से शब्दों को ठीक करने की तकनीकें" (PDF). ACM Computing Surveys. 24 (4): 377–439. doi:10.1145/146370.146380. S2CID 5431215. Archived from the original (PDF) on 2016-09-27. Retrieved 2017-11-09.

[7] R. Wagner; M. Fischer (1974). "स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या". J. ACM. 21: 168–178. doi:10.1145/321796.321811. S2CID 13381535.

[8] Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. Bibcode:2008adm..book.....S. ISBN 978-1-849-96720-4.

[CLR-08-9] Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (July 2010). "जैव सूचना विज्ञान के लिए कैश-बेपरवाह गतिशील प्रोग्रामिंग". IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). 7 (3): 495–510. doi:10.1109/TCBB.2008.94. PMID 20671320. S2CID 2532039.

[10] Ukkonen, Esko (1985). "अनुमानित स्ट्रिंग मिलान के लिए एल्गोरिदम" (PDF). Information and Control. 64 (1–3): 100–118. doi:10.1016/S0019-9958(85)80046-2.

[11] Landau; Myers; Schmidt (1998). "वृद्धिशील स्ट्रिंग तुलना". SIAM Journal on Computing. 27 (2): 557–582. CiteSeerX 10.1.1.38.1766. doi:10.1137/S0097539794264810.

[12] Masek, William J.; Paterson, Michael S. (February 1980). "एक तेज़ एल्गोरिथम कंप्यूटिंग स्ट्रिंग संपादन दूरी". Journal of Computer and System Sciences. 20 (1): 18–31. doi:10.1016/0022-0000(80)90002-1. ISSN 0022-0000.

[13] Esko Ukkonen (1985). "तार में अनुमानित पैटर्न ढूँढना". J. Algorithms. 6: 132–137. doi:10.1016/0196-6774(85)90023-9.

[:0-14] 14.0 ^14.1 Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). "Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product" (PDF). 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 375–384. arXiv:1707.05095. doi:10.1109/focs.2016.48. ISBN 978-1-5090-3933-3. S2CID 17064578.

[15] Aho, A.; Peterson, T. (1972-12-01). "प्रसंग-मुक्त भाषाओं के लिए एक न्यूनतम दूरी त्रुटि-सुधार पार्सर". SIAM Journal on Computing. 1 (4): 305–312. doi:10.1137/0201022. ISSN 0097-5397.

[16] Wagner, Robert A. (1974). "आदेश-एन नियमित भाषाओं के लिए सुधार". Communications of the ACM. 17 (5): 265–268. doi:10.1145/360980.360995. S2CID 11063282.

[17] Saha, B. (2014-10-01). डाइक लैंग्वेज एडिट डिस्टेंस प्रॉब्लम इन नियर-लीनियर टाइम. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 611–620. doi:10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

@@ Line 1: / Line 1: @@
 {{short description|Computer science metric of string similarity}}
-अभिकलनात्मक भाषाविज्ञान और कंप्यूटर विज्ञान में, संपादन दूरी एक श्रृंखला मापीय है, अर्थात यह मापने का एक तरीका है कि दो श्रंखला (जैसे, शब्द) एक दूसरे से कितने भिन्न हैं, जो एक श्रृंखला को एक अन्य श्रृंखला में बदलने के लिए आवश्यक संचालन की न्यूनतम संख्या की गणना करके मापा जाता है। दूरियों को संपादित करें [[प्राकृतिक भाषा प्रसंस्करण]] में अनुप्रयोगों को खोजें, और जहां स्वचालित वर्तनी परीक्षक एक गलत वर्तनी वाले शब्द के लिए एक शब्दकोश से शब्दों का चयन करके उम्मीदवार सुधार निर्धारित कर सकता है, जो प्रश्न में शब्द के लिए कम दूरी रखता है। जैव सूचना विज्ञान में, इसका उपयोग [[डीएनए]] अनुक्रमों की समानता को निर्धारित करने के लिए किया जा सकता है, जिसे A, C, G और T अक्षरों की श्रंखला के रूप में देखा जा सकता है।
+अभिकलनात्मक भाषाविज्ञान और कंप्यूटर विज्ञान में, संपादन प्रक्रिया एक श्रृंखला मापीय है, अर्थात यह मापने का एक तरीका है कि दो श्रंखला (जैसे, शब्द) एक दूसरे से कितने भिन्न हैं, जो एक श्रृंखला को एक अन्य श्रृंखला में बदलने के लिए आवश्यक संचालन की न्यूनतम संख्या की गणना करके मापा जाता है। संपादन प्रक्रिया [[प्राकृतिक भाषा प्रसंस्करण]] में अनुप्रयोगों को खोजना, और जहां स्वचालित वर्तनी परीक्षक एक गलत वर्तनी वाले शब्द के लिए एक शब्दकोश से शब्दों का चयन करके उम्मीदवार सुधार निर्धारित कर सकता है, जो प्रश्न में शब्द के लिए कम प्रक्रिया रखता है। जैव सूचना विज्ञान में, इसका उपयोग [[डीएनए]] अनुक्रमों की समानता को निर्धारित करने के लिए किया जा सकता है, जिसे A, C, G और T अक्षरों की श्रंखला के रूप में देखा जा सकता है।
-संपादन दूरी की विभिन्न परिभाषाएँ श्रृंखला संचालन के विभिन्न सम्मुच्चयों का उपयोग करती हैं। लेवेनशेटिन दूरी संचालन श्रृंखला में किसी वर्ण को हटाना, सम्मिलित करना या प्रतिस्थापन करना सम्मिलित है। सबसे सामान्यतः मापीय होने के नाते, '[[लेवेनशेटिन दूरी]]' शब्द का प्रयोग प्रायः 'संपादन दूरी' के साथ एक दूसरे के स्थान पर किया जाता है।<ref name="navarro">{{cite journal|last1=Navarro|first1=Gonzalo|title=अनुमानित स्ट्रिंग मिलान के लिए एक निर्देशित दौरा|journal=ACM Computing Surveys|date=1 March 2001|volume=33|issue=1|pages=31–88|doi=10.1145/375360.375365|url=http://users.csc.calpoly.edu/~dekhtyar/570-Fall2011/papers/navarro-approximate.pdf|access-date=19 March 2015|citeseerx=10.1.1.452.6317|s2cid=207551224 }}</ref>
+संपादन प्रक्रिया की विभिन्न परिभाषाएँ श्रृंखला संचालन के विभिन्न सम्मुच्चयों का उपयोग करती हैं। लेवेनशेटिन प्रक्रिया संचालन श्रृंखला में किसी वर्ण को हटाना, सम्मिलित करना या प्रतिस्थापन करना सम्मिलित है। सबसे सामान्यतः मापीय होने के नाते, '[[लेवेनशेटिन दूरी|लेवेनशेटिन प्रक्रिया]]' शब्द का प्रयोग प्रायः 'संपादन प्रक्रिया' के साथ एक दूसरे के स्थान पर किया जाता है।<ref name="navarro">{{cite journal|last1=Navarro|first1=Gonzalo|title=अनुमानित स्ट्रिंग मिलान के लिए एक निर्देशित दौरा|journal=ACM Computing Surveys|date=1 March 2001|volume=33|issue=1|pages=31–88|doi=10.1145/375360.375365|url=http://users.csc.calpoly.edu/~dekhtyar/570-Fall2011/papers/navarro-approximate.pdf|access-date=19 March 2015|citeseerx=10.1.1.452.6317|s2cid=207551224 }}</ref>
-== संपादन दूरी के प्रकार ==
+== संपादन प्रक्रिया के प्रकार ==
-विभिन्न प्रकार की संपादन दूरी श्रृंखला संचालन के विभिन्न सम्मुच्चयों की अनुमति देती है। उदाहरण के लिए:
+विभिन्न प्रकार की संपादन प्रक्रिया श्रृंखला संचालन के विभिन्न सम्मुच्चयों की अनुमति देती है। उदाहरण के लिए:
-* लेवेंस्टीन दूरी विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
+* लेवेंस्टीन प्रक्रिया विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
-* सबसे लंबी सामान्य अनुगामी (LCS) दूरी केवल प्रविष्टि और विलोपन की अनुमति देती है, प्रतिस्थापन की नहीं।
+* सबसे लंबी सामान्य अनुगामी (LCS) प्रक्रिया केवल प्रविष्टि और विलोपन की अनुमति देती है, परन्तु प्रतिस्थापन की अनुमति नहींदेती है।
-* [[हैमिंग दूरी]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के श्रंखलाओं पर लागू होती है।
+* [[हैमिंग दूरी|हैमिंग प्रक्रिया]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के श्रंखलाओं पर लागू होती है।
-* दमेरौ-लेवेनशेटिन दूरी दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और स्थिति अंतरण (गणित) की अनुमति देती है।
+* दमेरौ-लेवेनशेटिन प्रक्रिया दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और स्थिति अंतरण (गणित) की अनुमति देती है।
-* जारो दूरी केवल [[स्थानान्तरण (गणित)]] की अनुमति देती है।
+* जारो प्रक्रिया केवल [[स्थानान्तरण (गणित)]] की अनुमति देती है।
-कुछ संपादन दूरियों को अनुमत संपादन कार्यों के एक विशिष्ट सम्मुच्चय के साथ परिकलित एक मापदण्ड योग्य मापीय के रूप में परिभाषित किया गया है, और प्रत्येक संचालन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] कलन विधि जैसे स्मिथ-वाटरमैन कलन विधि द्वारा आगे सामान्यीकृत किया गया है, जो एक संचालन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
+कुछ संपादन प्रक्रियाओं को अनुमत संपादन कार्यों के एक विशिष्ट सम्मुच्चय के साथ परिकलित एक मापदण्ड योग्य मापीय के रूप में परिभाषित किया गया है, और प्रत्येक संचालन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] कलन विधि जैसे स्मिथ-वाटरमैन कलन विधि द्वारा आगे सामान्यीकृत किया गया है, जो एक संचालन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
 == औपचारिक परिभाषा और गुण ==
-दो श्रंखला {{mvar|a}} और {{mvar|b}} दिए गए वर्णमाला {{math|Σ}} पर (उदाहरण [[ASCII]] वर्णों का सम्मुच्चय, [[बाइट]]्स का सम्मुच्चय [0..255], आदि), संपादन दूरी {{nowrap|d({{mvar|a}}, {{mvar|b}})}} संपादन संचालन की न्यूनतम-भार श्रृंखला है जो a को b में बदल देती है। संपादन संचालन के सबसे सरल सम्मुच्चयों में से एक है जिसे 1966 में लेवेनशेटिन द्वारा परिभाषित किया गया था:<ref name="slp"/>
+दो श्रंखला {{mvar|a}} और {{mvar|b}} दिए गए वर्णमाला {{math|Σ}} पर (उदाहरण [[ASCII]] वर्णों का सम्मुच्चय, [[बाइट]]्स का सम्मुच्चय [0..255], आदि), संपादन प्रक्रिया {{nowrap|d({{mvar|a}}, {{mvar|b}})}} संपादन संचालन की न्यूनतम-भार श्रृंखला है जो a को b में बदल देती है। संपादन संचालन के सबसे सरल सम्मुच्चयों में से एक है जिसे 1966 में लेवेनशेटिन द्वारा परिभाषित किया गया था:<ref name="slp"/>
-: एकल प्रतीक का '''अंतर्वेशन'''। यदि {{mvar|a}} = {{mvar|u}}{{mvar|v}}, फिर प्रतीक {{mvar|x}} सम्मिलित करना {{mvar|u}}{{mvar|x}}{{mvar|v}} उत्पन्न करता है। इसे ε →{{mvar|x}} भी निरूपित किया जा सकता है, खाली श्रृंखला को निरूपित करने के लिए ε का उपयोग किया जा सकता है।
+: एकल प्रतीक का अंतर्वेशन। यदि {{mvar|a}} = {{mvar|u}}{{mvar|v}}, फिर प्रतीक {{mvar|x}} सम्मिलित करना {{mvar|u}}{{mvar|x}}{{mvar|v}} उत्पन्न करता है। इसे ε →{{mvar|x}} भी निरूपित किया जा सकता है, खाली श्रृंखला को निरूपित करने के लिए ε का उपयोग किया जा सकता है।
 : एकल प्रतीक परिवर्तन का विलोपन {{mvar|u}}{{mvar|x}}{{mvar|v}} को {{mvar|u}}{{mvar|v}} ({{mvar|x}}→ε) में परिवर्तित कर देता है।
 : एकल प्रतीक का प्रतिस्थापन {{mvar|x}} प्रतीक के लिए {{mvar|y}} ≠ {{mvar|x}} {{mvar|u}}{{mvar|x}}{{mvar|v}} को {{mvar|u}}{{mvar|y}}{{mvar|v}} ({{mvar|x}}→{{mvar|y}}) में परिवर्तित कर देता है।
-लेवेनशेटिन की मूल परिभाषा में, इनमें से प्रत्येक संचालन की इकाई लागत होती है (सिवाय इसके कि एक चरित्र के प्रतिस्थापन की लागत शून्य होती है), इसलिए लेवेनशेटिन की दूरी {{mvar|a}} को {{mvar|b}} रूपांतरण के लिए आवश्यक संचालन की न्यूनतम संख्या के बराबर होती है। एक अधिक सामान्य परिभाषा गैर-नकारात्मक भार कार्यों  {{mvar|w}}<sub>ins</sub>({{mvar|x}}), {{mvar|w}}<sub>del</sub>({{mvar|x}}) और {{mvar|w}}<sub>sub</sub>({{mvar|x}}, {{mvar|y}}) को संचालन के साथ जोड़ती है।<ref name="slp">{{cite book |author1=Daniel Jurafsky |author2=James H. Martin |title=भाषण और भाषा प्रसंस्करण|publisher=Pearson Education International |pages=107–111}}</ref>
+लेवेनशेटिन की मूल परिभाषा में, इनमें से प्रत्येक संचालन की इकाई लागत होती है (सिवाय इसके कि एक चरित्र के प्रतिस्थापन की लागत शून्य होती है), इसलिए लेवेनशेटिन की प्रक्रिया {{mvar|a}} को {{mvar|b}} रूपांतरण के लिए आवश्यक संचालन की न्यूनतम संख्या के बराबर होती है। एक अधिक सामान्य परिभाषा गैर-नकारात्मक भार कार्यों  {{mvar|w}}<sub>ins</sub>({{mvar|x}}), {{mvar|w}}<sub>del</sub>({{mvar|x}}) और {{mvar|w}}<sub>sub</sub>({{mvar|x}}, {{mvar|y}}) को संचालन के साथ जोड़ती है।<ref name="slp">{{cite book |author1=Daniel Jurafsky |author2=James H. Martin |title=भाषण और भाषा प्रसंस्करण|publisher=Pearson Education International |pages=107–111}}</ref>
-अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन दूरी एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक संचालन द्वारा विशेषता जो  {{mvar|u}}{{mvar|x}}{{mvar|y}}{{mvar|v}} में {{mvar|u}}{{mvar|y}}{{mvar|x}}{{mvar|v}} को बदलता है। <ref name="ukkonen83">{{cite conference |author=Esko Ukkonen |title=अनुमानित स्ट्रिंग मिलान पर|conference=Foundations of Computation Theory |year=1983 |pages=487–495 |publisher=Springer|doi=10.1007/3-540-12689-9_129 }}</ref><ref name="ssm" /> [[ऑप्टिकल कैरेक्टर मान्यता|प्रकाशिक संप्रतीक अभिज्ञान]] निष्पाद को सही करने के कार्य के लिए, विलय और विपाट संचालन का उपयोग किया गया है जो एकल भूमिका को उनमें से एक जोड़ी या इसके विपरीत में बदल देता है।<ref name="ssm">{{cite journal |first1=Klaus U. |last1=Schulz |first2=Stoyan |last2=Mihov |year=2002 |citeseerx=10.1.1.16.652 |title=लेवेनशेटिन ऑटोमेटा के साथ फास्ट स्ट्रिंग सुधार|journal=International Journal of Document Analysis and Recognition |volume=5 |issue=1 |pages=67–85 |doi=10.1007/s10032-002-0082-8|s2cid=207046453 |url=https://www.semanticscholar.org/paper/f3e52f82393d70ec2d68962ea4542d919e2b1ab1 }}</ref>
+अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन प्रक्रिया एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक संचालन द्वारा विशेषता जो  {{mvar|u}}{{mvar|x}}{{mvar|y}}{{mvar|v}} में {{mvar|u}}{{mvar|y}}{{mvar|x}}{{mvar|v}} को बदलता है। <ref name="ukkonen83">{{cite conference |author=Esko Ukkonen |title=अनुमानित स्ट्रिंग मिलान पर|conference=Foundations of Computation Theory |year=1983 |pages=487–495 |publisher=Springer|doi=10.1007/3-540-12689-9_129 }}</ref><ref name="ssm" /> [[ऑप्टिकल कैरेक्टर मान्यता|प्रकाशिक संप्रतीक अभिज्ञान]] निष्पाद को सही करने के कार्य के लिए, विलय और विपाट संचालन का उपयोग किया गया है जो एकल भूमिका को उनमें से एक जोड़ी या इसके विपरीत में बदल देता है।<ref name="ssm">{{cite journal |first1=Klaus U. |last1=Schulz |first2=Stoyan |last2=Mihov |year=2002 |citeseerx=10.1.1.16.652 |title=लेवेनशेटिन ऑटोमेटा के साथ फास्ट स्ट्रिंग सुधार|journal=International Journal of Document Analysis and Recognition |volume=5 |issue=1 |pages=67–85 |doi=10.1007/s10032-002-0082-8|s2cid=207046453 |url=https://www.semanticscholar.org/paper/f3e52f82393d70ec2d68962ea4542d919e2b1ab1 }}</ref>
-संचालन के सम्मुच्चय को प्रतिबंधित करके संपादन दूरी के अन्य संस्करण प्राप्त किए जाते हैं। सबसे लंबी सामान्य बाद की समस्या | सबसे लंबी सामान्य अनुवर्ती (एलसीएस) दूरी इकाई लागत पर केवल दो संपादन कार्यों के रूप में सम्मिलन और विलोपन के साथ संपादन दूरी है। <ref name="navarro" />{{rp|37}} इसी तरह, केवल प्रतिस्थापन (फिर से इकाई लागत पर) की अनुमति देकर, हैमिंग दूरी प्राप्त की जाती है; यह समान-लंबाई वाले श्रंखलाओं तक ही सीमित होना चाहिए।<ref name="navarro" /> जारो-विंकलर दूरी को संपादित दूरी से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।
+संचालन के सम्मुच्चय को प्रतिबंधित करके संपादन प्रक्रिया के अन्य संस्करण प्राप्त किए जाते हैं। सबसे लंबी सामान्य बाद की समस्या | सबसे लंबी सामान्य अनुवर्ती (एलसीएस) प्रक्रिया इकाई लागत पर केवल दो संपादन कार्यों के रूप में सम्मिलन और विलोपन के साथ संपादन प्रक्रिया है। <ref name="navarro" />{{rp|37}} इसी तरह, केवल प्रतिस्थापन (फिर से इकाई लागत पर) की अनुमति देकर, हैमिंग प्रक्रिया प्राप्त की जाती है; यह समान-लंबाई वाले श्रंखलाओं तक ही सीमित होना चाहिए।<ref name="navarro" /> जारो-विंकलर प्रक्रिया को संपादित प्रक्रिया से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।
 === उदाहरण ===
-'''किटेन और सिटेन के बीच लेवेनशेटिन की दूरी 3 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:'''
+'''किटेन और सिटेन के बीच लेवेनशेटिन की प्रक्रिया 3 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:'''
 # किटेन → सिटेन (k के लिए स्थानापन्न s)
@@ Line 35: / Line 35: @@
 # सिटिन → सिटिंग (अंत में g डालें)
-LCS दूरी (केवल सम्मिलन और विलोपन) एक अलग दूरी और न्यूनतम संपादन स्क्रिप्ट देता है:
+LCS प्रक्रिया (केवल सम्मिलन और विलोपन) एक अलग प्रक्रिया और न्यूनतम संपादन स्क्रिप्ट देता है:
 # किटेन → इटेन (0 पर k हटाएं)
@@ Line 43: / Line 43: @@
 # सिटिन → सिटिंग (6 पर g डालें)
-संचालन की कुल लागत/दूरी के लिए।
+संचालन की कुल लागत/प्रक्रिया के लिए।
 === गुण ===
-गैर-ऋणात्मक लागत के साथ संपादन दूरी एक [[मीट्रिक (गणित)|मापीय (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित परिस्तिथि पूरी होती हैं, तो श्रृंखला के एक [[मीट्रिक स्थान|मापीय स्थान]] को उत्पन्न करता है:<ref name="navarro"/>{{rp|37}}
+गैर-ऋणात्मक लागत के साथ संपादन प्रक्रिया एक [[मीट्रिक (गणित)|मापीय (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित परिस्तिथि पूरी होती हैं, तो श्रृंखला के एक [[मीट्रिक स्थान|मापीय स्थान]] को उत्पन्न करता है:<ref name="navarro"/>{{rp|37}}
 * हर संपादन संचालन की सकारात्मक लागत होती है;
@@ Line 55: / Line 55: @@
 :{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = 0 यदि और केवल यदि a = b, क्योंकि प्रत्येक श्रृंखला को बिल्कुल शून्य संचालन का उपयोग करके तुच्छ रूप से परिवर्तित किया जा सकता है।
 :{{mvar|d}}({{mvar|a}}, {{mvar|b}}) > 0 जब {{mvar|a}} ≠ {{mvar|b}}, क्योंकि इसके लिए गैर-शून्य लागत पर कम से कम एक संचालन की आवश्यकता होगी।
-:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|b}}, {{mvar|a}}) प्रत्येक संचालन की लागत और उसके व्युत्क्रम की समानता।
+:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|b}}, {{mvar|a}}) प्रत्येक संचालन की लागत और उसके व्युत्क्रम की समानता होती है।
 :असमानित त्रिकोण: {{mvar|d}}({{mvar|a}}, {{mvar|c}}) ≤ {{mvar|d}}({{mvar|a}}, {{mvar|b}}) + {{mvar|d}}({{mvar|b}}, {{mvar|c}}).<ref>{{cite conference |author1=Lei Chen |author2=Raymond Ng |title=On the marriage of L<sub>p</sub>-norms and edit distance |conference=Proc. 30th Int'l Conf. on Very Large Databases (VLDB) |url=http://www.cs.ust.hk/~leichen/pub/04/vldb04.pdf |volume=30 |year=2004 |doi=10.1016/b978-012088469-8.50070-x}}</ref>
-ईकाई लागत के साथ लेवेनशेटिन दूरी और एलसीएस दूरी उपरोक्त परिस्थितियों को पूरा करते हैं, और इसलिए मापीय स्वयंसिद्ध हैं। संपादन दूरी के परिवर्ती जो उचित आव्यूह नहीं हैं, उन पर भी साहित्य में विचार किया गया है।<ref name="navarro"/>
+ईकाई लागत के साथ लेवेनशेटिन प्रक्रिया और एलसीएस प्रक्रिया उपरोक्त परिस्थितियों को पूरा करते हैं, और इसलिए मापीय स्वयंसिद्ध हैं। संपादन प्रक्रिया के परिवर्ती जो उचित आव्यूह नहीं हैं, उन पर भी साहित्य में विचार किया गया है।<ref name="navarro"/>
-इकाई-लागत संपादित दूरियों के अन्य उपयोगी गुणों में सम्मिलित हैं:
+इकाई-लागत संपादित प्रक्रियाओं के अन्य उपयोगी गुणों में सम्मिलित हैं:
-* एलसीएस दूरी श्रंखला की एक जोड़ी की लंबाई के योग से ऊपर है।<ref name="navarro"/>{{rp|37}}
+* एलसीएस प्रक्रिया श्रंखला की एक जोड़ी की लंबाई के योग से ऊपर है।<ref name="navarro"/>{{rp|37}}
-* एलसीएस दूरी लेवेनशेटिन दूरी पर ऊपरी सीमा है।
+* एलसीएस प्रक्रिया लेवेनशेटिन प्रक्रिया पर ऊपरी सीमा है।
-* समान लंबाई के श्रंखलाओं के लिए, हैमिंग दूरी लेवेनशेटिन दूरी पर एक ऊपरी सीमा होती है।<ref name="navarro"/>
+* समान लंबाई के श्रंखलाओं के लिए, हैमिंग प्रक्रिया लेवेनशेटिन प्रक्रिया पर एक ऊपरी सीमा होती है।<ref name="navarro"/>
-लागत/भार पर ध्यान दिए बिना, निम्नलिखित संपत्ति सभी संपादन दूरी रखती है:
+लागत/भार पर ध्यान दिए बिना, निम्नलिखित संपत्ति सभी संपादन प्रक्रिया रखती है:
-* जब {{mvar|a}} और {{mvar|b}} एक सामान्य उपसर्ग साझा करें, इस उपसर्ग का दूरी पर कोई प्रभाव नहीं पड़ता है। औपचारिक रूप से, जब {{mvar|a}} = {{mvar|uv}} और {{mvar|b}} = {{mvar|uw}}, तब {{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|v}}, {{mvar|w}}).<ref name="ssm"/> यह संपादन दूरी और संपादन आलेख से जुड़ी कई संगणनाओं को तेज करने की अनुमति देता है, क्योंकि सामान्यतः उपसर्गों और प्रत्ययों को रैखिक समय में छोड़ दिया जा सकता है।
+* जब {{mvar|a}} और {{mvar|b}} एक सामान्य उपसर्ग साझा करें, इस उपसर्ग का प्रक्रिया पर कोई प्रभाव नहीं पड़ता है। औपचारिक रूप से, जब {{mvar|a}} = {{mvar|uv}} और {{mvar|b}} = {{mvar|uw}}, तब {{mvar|d}}({{mvar|a}}, {{mvar|b}}) = {{mvar|d}}({{mvar|v}}, {{mvar|w}}).<ref name="ssm"/> यह संपादन प्रक्रिया और संपादन आलेख से जुड़ी कई संगणनाओं को तेज करने की अनुमति देता है, क्योंकि सामान्यतः उपसर्गों और प्रत्ययों को रैखिक समय में छोड़ दिया जा सकता है।
 == संगणना ==
-श्रंखलाओं की एक जोड़ी के बीच न्यूनतम संपादन दूरी की गणना के लिए पहला कलन विधि 1964 में फ्रेडरिक जे डमेराउ द्वारा प्रकाशित किया गया था।<ref>{{Cite journal |title=पाठ में स्वचालित रूप से शब्दों को ठीक करने की तकनीकें|first=Karen |last=Kukich |journal=ACM Computing Surveys |volume=24 |issue=4 |year=1992 |url=http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |doi=10.1145/146370.146380 |pages=377–439 |s2cid=5431215 |access-date=2017-11-09 |archive-url=https://web.archive.org/web/20160927030713/http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |archive-date=2016-09-27 |url-status=dead }}</ref>
+श्रंखलाओं की एक जोड़ी के बीच न्यूनतम संपादन प्रक्रिया की गणना के लिए पहला कलन विधि 1964 में फ्रेडरिक जे डमेराउ द्वारा प्रकाशित किया गया था।<ref>{{Cite journal |title=पाठ में स्वचालित रूप से शब्दों को ठीक करने की तकनीकें|first=Karen |last=Kukich |journal=ACM Computing Surveys |volume=24 |issue=4 |year=1992 |url=http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |doi=10.1145/146370.146380 |pages=377–439 |s2cid=5431215 |access-date=2017-11-09 |archive-url=https://web.archive.org/web/20160927030713/http://dc-pubs.dbs.uni-leipzig.de/files/Kukich1992Techniqueforautomatically.pdf |archive-date=2016-09-27 |url-status=dead }}</ref>
@@ Line 77: / Line 77: @@
 {{main|वैगनर-फिशर कलन विधि}}
-लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (असममितीय) से दूरी <math>a = a_1\ldots a_m</math> को <math>b = b_1\ldots b_n</math> संपादन <math>d_{mn}</math> द्वारा दिया गया है, [[पुनरावर्ती परिभाषा]] द्वारा निम्न परिभाषित<ref name="slp"/>
+लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (असममितीय) से प्रक्रिया <math>a = a_1\ldots a_m</math> को <math>b = b_1\ldots b_n</math> संपादन <math>d_{mn}</math> द्वारा दिया गया है, [[पुनरावर्ती परिभाषा]] द्वारा निम्न परिभाषित<ref name="slp"/>
 :<math>\begin{align}d_{i0} &= \sum_{k=1}^{i} w_\mathrm{del}(a_{k}), & & \quad  \text{for}\; 1 \leq i \leq m \\
@@ Line 86: / Line 86: @@
 इस पुनरावृत्ति का मूल्यांकन करने का सीधा, पुनरावर्तन (कंप्यूटर विज्ञान) तरीका [[घातीय समय]] लेता है। इसलिए, यह सामान्यतः एक [[गतिशील प्रोग्रामिंग|गतिशील क्रमादेशन]] कलन विधि का उपयोग करके गणना की जाती है जिसे सामान्यतः वैगनर-फिशर कलन विधि को श्रेय दिया जाता है।<ref>{{cite journal |author1=R. Wagner |author2=M. Fischer |s2cid=13381535 |title=स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|journal=J. ACM |volume=21 |year=1974 |pages=168–178 |doi=10.1145/321796.321811}}</ref> हालांकि इसका कई आविष्कारों का इतिहास है।<ref name="slp"/><ref name="ukkonen83"/> वैगनर-फिशर कलन विधि के पूरा होने के बाद, गतिशील क्रमादेशन कलन विधि के उपरान्त उपयोग किए जाने वाले संचालन के पश्व-अनुरेखन के रूप में संपादन संचालन का एक न्यूनतम अनुक्रम <math>d_{mn}</math> पढ़ा जा सकता है।
-इस कलन विधि में Θ की [[समय जटिलता]] ({{mvar|m}}{{mvar|n}}) है जहाँ {{mvar|m}} और {{mvar|n}} श्रंखला की लंबाई हैं। जब पूर्ण गतिशील क्रमादेशन तालिका का निर्माण किया जाता है, तो इसकी [[अंतरिक्ष जटिलता]] {{nowrap|Θ({{mvar|m}}{{mvar|n}})}} भी होती है; इसमें {{nowrap|Θ(min({{mvar|m}},{{mvar|n}}))}} सुधार किया जा सकता है  यह देखते हुए कि किसी भी समय, कलन विधि को स्मृति में केवल दो पंक्तियों (या दो स्तंभ) की आवश्यकता होती है। हालाँकि, यह अनुकूलन संपादन कार्यों की न्यूनतम श्रृंखला को पढ़ना असंभव बनाता है।<ref name="ukkonen83"/> इस समस्या का एक रैखिक-अंतरिक्ष समाधान हिर्शबर्ग के कलन विधि द्वारा प्रस्तुत किया गया है।<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = एल्गोरिथ्म डिजाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4|bibcode=2008adm..book.....S }}</ref>{{rp|634}} इस तरह की पुनरावृत्ति को हल करने के लिए एक सामान्य पुनरावर्ती विभाजन-और-जीत रूपरेखा, निविष्ट के आकार में अंतरिक्ष रैखिक में कुशलता से संचालन के एक इष्टतम अनुक्रम को निकालने के लिए चौधरी, ले और रामचंद्रन द्वारा दिया गया है।<ref name="CLR-08">{{cite journal |last1=Chowdhury |first1=Rezaul |last2=Le |first2=Hai-Son |last3=Ramachandran |first3=Vijaya |title=जैव सूचना विज्ञान के लिए कैश-बेपरवाह गतिशील प्रोग्रामिंग|journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) |date=July 2010 |volume=7 |issue=3 |pages=495–510 |doi=10.1109/TCBB.2008.94 |pmid=20671320 |s2cid=2532039 |url=https://ieeexplore.ieee.org/document/4609376}}</ref>
+इस कलन विधि में Θ की [[समय जटिलता]] ({{mvar|m}}{{mvar|n}}) है जहाँ {{mvar|m}} और {{mvar|n}} श्रंखला की लंबाई हैं। जब पूर्ण गतिशील क्रमादेशन तालिका का निर्माण किया जाता है, तो इसकी [[अंतरिक्ष जटिलता]] {{nowrap|Θ({{mvar|m}}{{mvar|n}})}} भी होती है; इसमें {{nowrap|Θ(min({{mvar|m}},{{mvar|n}}))}} सुधार किया जा सकता है  यह देखते हुए कि किसी भी समय, कलन विधि को स्मृति में केवल दो पंक्तियों (या दो स्तंभ) की आवश्यकता होती है। हालाँकि, यह अनुकूलन संपादन कार्यों की न्यूनतम श्रृंखला को पढ़ना असंभव बनाता है।<ref name="ukkonen83"/> इस समस्या का एक रैखिक-अंतरिक्ष समाधान हिर्शबर्ग के कलन विधि द्वारा प्रस्तुत किया गया है।<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = एल्गोरिथ्म डिजाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4|bibcode=2008adm..book.....S }}</ref>{{rp|634}} इस तरह की पुनरावृत्ति को हल करने के लिए एक सामान्य पुनरावर्ती विभाजन-और-जीत रूपरेखा, निविष्ट के आकार में अंतरिक्ष रैखिक में कुशलता से संचालन के एक इष्टतम अनुक्रम को निकालने के लिए चौधरी, लेह और रामचंद्रन द्वारा दिया गया है।<ref name="CLR-08">{{cite journal |last1=Chowdhury |first1=Rezaul |last2=Le |first2=Hai-Son |last3=Ramachandran |first3=Vijaya |title=जैव सूचना विज्ञान के लिए कैश-बेपरवाह गतिशील प्रोग्रामिंग|journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) |date=July 2010 |volume=7 |issue=3 |pages=495–510 |doi=10.1109/TCBB.2008.94 |pmid=20671320 |s2cid=2532039 |url=https://ieeexplore.ieee.org/document/4609376}}</ref>
 === बेहतर कलन विधि ===
-ऊपर वर्णित वैगनर-फिशर कलन विधि में सुधार करते हुए, [[एस्को उकोनेन]] कई रूपों का वर्णन करता है,<ref>{{cite journal |title=अनुमानित स्ट्रिंग मिलान के लिए एल्गोरिदम|journal=Information and Control |volume=64 |issue=1–3 |year=1985 |doi=10.1016/S0019-9958(85)80046-2|url=http://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF |pages=100–118|last1=Ukkonen |first1=Esko |doi-access=free }}</ref> जिनमें से एक में दो श्रंखला और अधिकतम संपादन दूरी {{mvar|s}}, और प्रतिलाभ {{nowrap|min({{mvar|s}}, {{mvar|d}})}} होती है। यह केवल अपने विकर्ण के चारों ओर गतिशील क्रमादेशन तालिका के एक भाग की गणना और भंडारण करके इसे प्राप्त करता है। इस कलन विधि {{nowrap|O({{mvar|s}}×min({{mvar|m}},{{mvar|n}}))}} में समय लगता है, जहाँ {{mvar|m}} और {{mvar|n}} श्रंखला की लंबाई हैं। अंतरिक्ष जटिलता {{nowrap|O({{mvar|s}}<sup>2</sup>)}} या {{nowrap|O({{mvar|s}})}} है, इस पर निर्भर करता है कि संपादन अनुक्रम को पढ़ने की आवश्यकता है या नहीं।<ref name="ukkonen83"/>
+ऊपर वर्णित वैगनर-फिशर कलन विधि में सुधार करते हुए, [[एस्को उकोनेन]] कई रूपों का वर्णन करता है,<ref>{{cite journal |title=अनुमानित स्ट्रिंग मिलान के लिए एल्गोरिदम|journal=Information and Control |volume=64 |issue=1–3 |year=1985 |doi=10.1016/S0019-9958(85)80046-2|url=http://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF |pages=100–118|last1=Ukkonen |first1=Esko |doi-access=free }}</ref> जिनमें से एक में दो श्रंखला और अधिकतम संपादन प्रक्रिया {{mvar|s}}, और प्रतिलाभ {{nowrap|min({{mvar|s}}, {{mvar|d}})}} होती है। यह केवल अपने विकर्ण के चारों ओर गतिशील क्रमादेशन तालिका के एक भाग की गणना और भंडारण करके इसे प्राप्त करता है। इस कलन विधि {{nowrap|O({{mvar|s}}×min({{mvar|m}},{{mvar|n}}))}} में समय लगता है, जहाँ {{mvar|m}} और {{mvar|n}} श्रंखला की लंबाई हैं। अंतरिक्ष जटिलता {{nowrap|O({{mvar|s}}<sup>2</sup>)}} या {{nowrap|O({{mvar|s}})}} है, इस पर निर्भर करता है कि संपादन अनुक्रम को पढ़ने की आवश्यकता है या नहीं।<ref name="ukkonen83"/>
 लैंडौ, मायर्स और श्मिट [https://dblp.org/pers/hd/s/Schmidt:Jeanette_P=] द्वारा किए गए और सुधार एक {{nowrap|O({{mvar|s}}{{sup|2}} + max({{mvar|m}},{{mvar|n}}))}} समय कलन विधि देते हैं।<ref>{{cite journal |year=1998 |last1=Landau |last2=Myers |last3=Schmidt |citeseerx=10.1.1.38.1766 |title=वृद्धिशील स्ट्रिंग तुलना|journal=SIAM Journal on Computing |volume=27 |issue=2 |pages=557–582 |doi=10.1137/S0097539794264810}}</ref>
@@ Line 97: / Line 97: @@
 == अनुप्रयोग ==
-संपादन दूरी [[कम्प्यूटेशनल बायोलॉजी|अभिकलनात्मक जीवविज्ञान]] और प्रकृत भाषा संसाधन में अनुप्रयोग ढूंढता है, उदा. वर्तनी की त्रुटियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान|अनुमानित श्रृंखला मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी श्रृंखला के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की अपेक्षा की जाती है।
+संपादन प्रक्रिया [[कम्प्यूटेशनल बायोलॉजी|अभिकलनात्मक जीवविज्ञान]] और प्रकृत भाषा संसाधन में अनुप्रयोग ढूंढता है, उदा. वर्तनी की त्रुटियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान|अनुमानित श्रृंखला मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी श्रृंखला के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की अपेक्षा की जाती है।
-विभिन्न कलन विधि उपस्थित हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए श्रंखलाओं की एक जोड़ी के बीच की दूरी की गणना के साथ-साथ समस्याओं को हल करते हैं।
+विभिन्न कलन विधि उपस्थित हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए श्रंखलाओं की एक जोड़ी के बीच की प्रक्रिया की गणना के साथ-साथ समस्याओं को हल करते हैं।
-* हिर्शबर्ग का कलन विधि दो श्रृंखला के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन दूरी को कम करने के रूप में परिभाषित किया गया है।
+* हिर्शबर्ग का कलन विधि दो श्रृंखला के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन प्रक्रिया को कम करने के रूप में परिभाषित किया गया है।
-* अनुमानित श्रृंखला मिलान संपादन दूरी के संदर्भ में तैयार किया जा सकता है। उकोनेन का 1985 का कलन विधि एक श्रृंखला {{mvar|p}} लेता है, जिसे पतिरूप और स्थिर {{mvar|k}} कहा जाता है; यह तब एक नियतात्मक परिमित अवस्था यंत्र मानव बनाता है जो एक मनमाने ढंग से श्रृंखला में {{mvar|s}} पाता है, एक उपरज्जु जिसकी संपादन दूरी {{mvar|p}} ज्यादा से ज्यादा {{mvar|k}} है <ref>{{cite journal |author=Esko Ukkonen |title=तार में अनुमानित पैटर्न ढूँढना|journal=J. Algorithms |volume=6 |pages=132–137 |year=1985 |doi=10.1016/0196-6774(85)90023-9}}</ref> (cf. अहो-कोरासिक कलन विधि, जो समान रूप से किसी भी पतिरूप को खोजने के लिए एक यंत्र मानव का निर्माण करता है, लेकिन संपादन कार्यों की अनुमति के बिना)। अनुमानित श्रृंखला मिलान के लिए एक समान कलन विधि [[थकना|बिटप]] है, जिसे संपादन दूरी के संदर्भ में भी परिभाषित किया गया है।
+* अनुमानित श्रृंखला मिलान संपादन प्रक्रिया के संदर्भ में तैयार किया जा सकता है। उकोनेन का 1985 का कलन विधि एक श्रृंखला {{mvar|p}} लेता है, जिसे पतिरूप और स्थिर {{mvar|k}} कहा जाता है; यह तब एक नियतात्मक परिमित अवस्था यंत्र मानव बनाता है जो एक मनमाने ढंग से श्रृंखला में {{mvar|s}} पाता है, एक उपरज्जु जिसकी संपादन प्रक्रिया {{mvar|p}} ज्यादा से ज्यादा {{mvar|k}} है <ref>{{cite journal |author=Esko Ukkonen |title=तार में अनुमानित पैटर्न ढूँढना|journal=J. Algorithms |volume=6 |pages=132–137 |year=1985 |doi=10.1016/0196-6774(85)90023-9}}</ref> (cf. अहो-कोरासिक कलन विधि, जो समान रूप से किसी भी पतिरूप को खोजने के लिए एक यंत्र मानव का निर्माण करता है, लेकिन संपादन कार्यों की अनुमति के बिना)। अनुमानित श्रृंखला मिलान के लिए एक समान कलन विधि [[थकना|बिटप]] है, जिसे संपादन प्रक्रिया के संदर्भ में भी परिभाषित किया गया है।
-* [[लेवेनशेटिन ऑटोमेटन|लेवेनशेटिन रोबोट]] परिमित-अवस्था वाली मशीनें हैं जो एक निश्चित संदर्भ श्रृंखला की सीमित संपादन दूरी के भीतर श्रृंखला के एक सम्मुच्चय को पहचानती हैं।<ref name="ssm"/>
+* [[लेवेनशेटिन ऑटोमेटन|लेवेनशेटिन रोबोट]] परिमित-अवस्था वाली मशीनें हैं जो एक निश्चित संदर्भ श्रृंखला की सीमित संपादन प्रक्रिया के भीतर श्रृंखला के एक सम्मुच्चय को पहचानती हैं।<ref name="ssm"/>
-== भाषा संपादन दूरी ==
+== भाषा संपादन प्रक्रिया ==
-श्रृंखला के बीच संपादन दूरी का एक सामान्यीकरण श्रृंखला और भाषा के बीच भाषा संपादन दूरी है, सामान्यतः एक [[औपचारिक भाषा]] है। एक श्रृंखला और दूसरे के बीच संपादन दूरी पर विचार करने के स्थान पर, भाषा संपादन दूरी न्यूनतम संपादन दूरी है जिसे एक निश्चित श्रृंखला और श्रृंखला के सम्मुच्चय से ली गई किसी भी श्रृंखला के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा L और श्रृंखला x के लिए एक वर्णमाला {{math|Σ}} के ऊपर, भाषा संपादन दूरी d(L, x) <math>d(L,x) = \min_{y \in L} d(x,y)
+श्रृंखला के बीच संपादन प्रक्रिया का एक सामान्यीकरण श्रृंखला और भाषा के बीच भाषा संपादन प्रक्रिया है, सामान्यतः एक [[औपचारिक भाषा]] है। एक श्रृंखला और दूसरे के बीच संपादन प्रक्रिया पर विचार करने के स्थान पर, भाषा संपादन प्रक्रिया न्यूनतम संपादन प्रक्रिया है जिसे एक निश्चित श्रृंखला और श्रृंखला के सम्मुच्चय से ली गई किसी भी श्रृंखला के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा L और श्रृंखला x के लिए एक वर्णमाला {{math|Σ}} के ऊपर, भाषा संपादन प्रक्रिया d(L, x) <math>d(L,x) = \min_{y \in L} d(x,y)
-</math> द्वारा दी गई है<ref name=":0">{{cite book|doi=10.1109/focs.2016.48|chapter=Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product|chapter-url=https://theory.stanford.edu/~virgi/RNAfold.pdf|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|pages=375–384|year=2016|last1=Bringmann|first1=Karl|last2=Grandoni|first2=Fabrizio|last3=Saha|first3=Barna|author3-link=Barna Saha|last4=Williams|first4=Virginia Vassilevska|author-link4=Virginia Vassilevska Williams|isbn=978-1-5090-3933-3|arxiv=1707.05095|s2cid=17064578 }}</ref>, जहाँ <math>d(x,y)</math> श्रृंखला संपादन दूरी है। जब भाषा एल [[प्रसंग-मुक्त भाषा]] है, तो 1972 में अहो और पीटरसन द्वारा प्रस्तावित त्रिविमीय काल गतिशील क्रमादेशन कलन विधि है जो भाषा संपादन दूरी की गणना करता है।<ref>{{Cite journal|last1=Aho|first1=A.|last2=Peterson|first2=T.|date=1972-12-01|title=प्रसंग-मुक्त भाषाओं के लिए एक न्यूनतम दूरी त्रुटि-सुधार पार्सर|journal=SIAM Journal on Computing|volume=1|issue=4|pages=305–312|doi=10.1137/0201022|issn=0097-5397}}</ref> व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि [[नियमित व्याकरण]], संपादन दूरी की गणना के लिए तीव्र कलन विधि उपस्थित हैं।<ref>{{cite journal|doi=10.1145/360980.360995|title=आदेश-एन नियमित भाषाओं के लिए सुधार|journal=Communications of the ACM|volume=17|issue=5|pages=265–268|year=1974|last1=Wagner|first1=Robert A.|s2cid=11063282}}</ref>
+</math> द्वारा दी गई है<ref name=":0">{{cite book|doi=10.1109/focs.2016.48|chapter=Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product|chapter-url=https://theory.stanford.edu/~virgi/RNAfold.pdf|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|pages=375–384|year=2016|last1=Bringmann|first1=Karl|last2=Grandoni|first2=Fabrizio|last3=Saha|first3=Barna|author3-link=Barna Saha|last4=Williams|first4=Virginia Vassilevska|author-link4=Virginia Vassilevska Williams|isbn=978-1-5090-3933-3|arxiv=1707.05095|s2cid=17064578 }}</ref>, जहाँ <math>d(x,y)</math> श्रृंखला संपादन प्रक्रिया है। जब भाषा एल [[प्रसंग-मुक्त भाषा]] है, तो 1972 में अहो और पीटरसन द्वारा प्रस्तावित त्रिविमीय काल गतिशील क्रमादेशन कलन विधि है जो भाषा संपादन प्रक्रिया की गणना करता है।<ref>{{Cite journal|last1=Aho|first1=A.|last2=Peterson|first2=T.|date=1972-12-01|title=प्रसंग-मुक्त भाषाओं के लिए एक न्यूनतम दूरी त्रुटि-सुधार पार्सर|journal=SIAM Journal on Computing|volume=1|issue=4|pages=305–312|doi=10.1137/0201022|issn=0097-5397}}</ref> व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि [[नियमित व्याकरण]], संपादन प्रक्रिया की गणना के लिए तीव्र कलन विधि उपस्थित हैं।<ref>{{cite journal|doi=10.1145/360980.360995|title=आदेश-एन नियमित भाषाओं के लिए सुधार|journal=Communications of the ACM|volume=17|issue=5|pages=265–268|year=1974|last1=Wagner|first1=Robert A.|s2cid=11063282}}</ref>
-लैंग्वेज संपादन दूरी में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए वलन, त्रुटि सुधार और इष्टतम स्तंभ जनन समस्या का समाधान।<ref name=":0" /><ref>{{Cite conference|last=Saha|first=B.|author-link=Barna Saha|s2cid=14806359|date=2014-10-01|title=डाइक लैंग्वेज एडिट डिस्टेंस प्रॉब्लम इन नियर-लीनियर टाइम|conference=2014 IEEE 55th Annual Symposium on Foundations of Computer Science|pages=611–620|doi=10.1109/FOCS.2014.71|isbn=978-1-4799-6517-5}}</ref>
+लैंग्वेज संपादन प्रक्रिया में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए वलन, त्रुटि सुधार और इष्टतम स्तंभ जनन समस्या का समाधान।<ref name=":0" /><ref>{{Cite conference|last=Saha|first=B.|author-link=Barna Saha|s2cid=14806359|date=2014-10-01|title=डाइक लैंग्वेज एडिट डिस्टेंस प्रॉब्लम इन नियर-लीनियर टाइम|conference=2014 IEEE 55th Annual Symposium on Foundations of Computer Science|pages=611–620|doi=10.1109/FOCS.2014.71|isbn=978-1-4799-6517-5}}</ref>
 == यह भी देखें ==
-* आलेख संपादन दूरी
+* आलेख संपादन प्रक्रिया
 * [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|श्रृंखला-से-श्रृंखला सुधार समस्या]]
 * श्रृंखला मापीय
-* [[समय ताना संपादन दूरी|समय आधार संपादन दूरी]]
+* [[समय ताना संपादन दूरी|समय आधार संपादन प्रक्रिया]]
 ==संदर्भ==

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

दूरी संपादित करें: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:03, 1 May 2023

Contents

संपादन प्रक्रिया के प्रकार