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

Latest revision as of 10:11, 4 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 अक्षरों की श्रंखला के रूप में देखा जा सकता है।
-संपादन दूरी की विभिन्न परिभाषाएँ स्ट्रिंग संचालन के विभिन्न सेटों का उपयोग करती हैं। लेवेनशेटिन डिस्टेंस ऑपरेशंस स्ट्रिंग में किसी वर्ण को हटाना, सम्मिलित करना या प्रतिस्थापन करना है। सबसे आम मीट्रिक होने के नाते, '[[लेवेनशेटिन दूरी]]' शब्द का प्रयोग अक्सर 'संपादन दूरी' के साथ एक दूसरे के स्थान पर किया जाता है।<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>
-== संपादन दूरी के प्रकार ==
+== संपादन प्रक्रिया के प्रकार ==
-विभिन्न प्रकार की संपादन दूरी स्ट्रिंग संचालन के विभिन्न सेटों की अनुमति देती है। उदाहरण के लिए:
+विभिन्न प्रकार की संपादन प्रक्रिया श्रृंखला संचालन के विभिन्न सम्मुच्चयों की अनुमति देती है। उदाहरण के लिए:
-* Levenshtein दूरी विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
+* लेवेंस्टीन प्रक्रिया विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
-* सबसे लंबी सामान्य अनुगामी (LCS) दूरी केवल प्रविष्टि और विलोपन की अनुमति देती है, प्रतिस्थापन की नहीं।
+* सबसे लंबी सामान्य अनुगामी (LCS) प्रक्रिया केवल प्रविष्टि और विलोपन की अनुमति देती है, परन्तु प्रतिस्थापन की अनुमति नहींदेती है।
-* [[हैमिंग दूरी]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के तारों पर लागू होती है।
+* [[हैमिंग दूरी|हैमिंग प्रक्रिया]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के श्रंखलाओं पर लागू होती है।
-* दमेरौ-लेवेनशेटिन दूरी दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और ट्रांसपोजिशन (गणित) की अनुमति देती है।
+* दमेरौ-लेवेनशेटिन प्रक्रिया दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और स्थिति अंतरण (गणित) की अनुमति देती है।
-* जारो दूरी केवल [[स्थानान्तरण (गणित)]] की अनुमति देती है।
+* जारो प्रक्रिया केवल [[स्थानान्तरण (गणित)]] की अनुमति देती है।
-कुछ संपादन दूरियों को अनुमत संपादन कार्यों के एक विशिष्ट सेट के साथ परिकलित एक पैरामीटर योग्य मीट्रिक के रूप में परिभाषित किया गया है, और प्रत्येक ऑपरेशन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] एल्गोरिदम जैसे स्मिथ-वाटरमैन एल्गोरिदम द्वारा आगे सामान्यीकृत किया गया है, जो एक ऑपरेशन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
+कुछ संपादन प्रक्रियाओं को अनुमत संपादन कार्यों के एक विशिष्ट सम्मुच्चय के साथ परिकलित एक मापदण्ड योग्य मापीय के रूप में परिभाषित किया गया है, और प्रत्येक संचालन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] कलन विधि जैसे स्मिथ-वाटरमैन कलन विधि द्वारा आगे सामान्यीकृत किया गया है, जो एक संचालन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
 == औपचारिक परिभाषा और गुण ==
-दो तार दिए गए {{mvar|a}} और {{mvar|b}} वर्णमाला पर {{math|Σ}} (उदाहरण [[ASCII]] वर्णों का सेट, [[बाइट]]्स का सेट [0..255], आदि), संपादन दूरी {{nowrap|d({{mvar|a}}, {{mvar|b}})}} परिवर्तन करने वाले संपादन कार्यों की न्यूनतम-भार श्रृंखला है {{mvar|a}} में {{mvar|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|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|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>
-संचालन के सेट को प्रतिबंधित करके संपादन दूरी के अन्य संस्करण प्राप्त किए जाते हैं। सबसे लंबी सामान्य बाद की समस्या | सबसे लंबी सामान्य अनुवर्ती (एलसीएस) दूरी इकाई लागत पर केवल दो संपादन कार्यों के रूप में सम्मिलन और विलोपन के साथ संपादन दूरी है।<ref name="navarro"/>{{rp|37}} इसी तरह, केवल प्रतिस्थापन (फिर से इकाई लागत पर) की अनुमति देकर, हैमिंग दूरी प्राप्त की जाती है; यह समान-लंबाई वाले तारों तक ही सीमित होना चाहिए।<ref name="navarro"/>जारो-विंकलर दूरी को संपादित दूरी से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।
+अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन प्रक्रिया एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक संचालन द्वारा विशेषता जो  {{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" /> जारो-विंकलर प्रक्रिया को संपादित प्रक्रिया से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।
 === उदाहरण ===
-बिल्ली के बच्चे और बैठने के बीच लेवेनशेटिन की दूरी 3 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:
+'''किटेन और सिटेन के बीच लेवेनशेटिन की प्रक्रिया 3 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:'''
-# बिल्ली का बच्चा → बैठा हुआ (के के लिए स्थानापन्न s)
+# किटेन → सिटेन (k के लिए स्थानापन्न s)
-# बैठे → बैठे (ई के लिए i स्थानापन्न)
+# सिटेन → सिटन (e के लिए i स्थानापन्न)
 # सिटिन → सिटिंग (अंत में g डालें)
-LCS दूरी (केवल सम्मिलन और विलोपन) एक अलग दूरी और न्यूनतम संपादन स्क्रिप्ट देता है:
+LCS प्रक्रिया (केवल सम्मिलन और विलोपन) एक अलग प्रक्रिया और न्यूनतम संपादन स्क्रिप्ट देता है:
-# बिल्ली का बच्चा → इटेन (0 पर k हटाएं)
+# किटेन → इटेन (0 पर k हटाएं)
-# itten → बैठे (0 पर एस डालें)
+# इटेन → सिटेन (0 पर s डालें)
-# बैठे → बैठे (4 पर ई हटाएं)
+# सिटेन → सिटेन (4 पर e हटाएं)
 # सिट्टन → सिट्टिन (4 पर i डालें)
-# सिटिन → सिटिंग (6 पर जी डालें)
+# सिटिन → सिटिंग (6 पर g डालें)
-संचालन की कुल लागत/दूरी के लिए।
+संचालन की कुल लागत/प्रक्रिया के लिए।
 === गुण ===
-गैर-ऋणात्मक लागत के साथ संपादन दूरी एक [[मीट्रिक (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित शर्तें पूरी होती हैं, तो स्ट्रिंग्स के एक [[मीट्रिक स्थान]] को जन्म देता है:<ref name="navarro"/>{{rp|37}}
+गैर-ऋणात्मक लागत के साथ संपादन प्रक्रिया एक [[मीट्रिक (गणित)|मापीय (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित परिस्तिथि पूरी होती हैं, तो श्रृंखला के एक [[मीट्रिक स्थान|मापीय स्थान]] को उत्पन्न करता है:<ref name="navarro"/>{{rp|37}}
-* हर संपादन ऑपरेशन की सकारात्मक लागत होती है;
+* हर संपादन संचालन की सकारात्मक लागत होती है;
-* प्रत्येक ऑपरेशन के लिए समान लागत के साथ एक व्युत्क्रम ऑपरेशन होता है।
+* प्रत्येक संचालन के लिए समान लागत के साथ एक व्युत्क्रम संचालन होता है।
-इन गुणों के साथ, मीट्रिक स्वयंसिद्ध निम्नानुसार संतुष्ट हैं:
+इन गुणों के साथ, मापीय स्वयंसिद्ध निम्नानुसार संतुष्ट हैं:
-:{{mvar|d}}({{mvar|a}}, {{mvar|b}}) = 0 अगर और केवल अगर a = b, क्योंकि प्रत्येक स्ट्रिंग को बिल्कुल शून्य संचालन का उपयोग करके तुच्छ रूप से परिवर्तित किया जा सकता है।
+:{{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}}) > 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>
+=== सामान्य कलन विधि ===
+{{main|वैगनर-फिशर कलन विधि}}
-=== सामान्य एल्गोरिदम ===
+लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (असममितीय) से प्रक्रिया <math>a = a_1\ldots a_m</math> को <math>b = b_1\ldots b_n</math> संपादन <math>d_{mn}</math> द्वारा दिया गया है, [[पुनरावर्ती परिभाषा]] द्वारा निम्न परिभाषित<ref name="slp"/>
-{{main|Wagner–Fischer algorithm}}
-Levenshtein के मूल संचालन का उपयोग करते हुए, (नॉनसिमेट्रिक) से दूरी संपादित करें <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 \\
 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{align}</math>
-पुनरावर्ती खंड के न्यूनीकरण में एक और शब्द जोड़कर पारदर्शिता को संभालने के लिए इस एल्गोरिथ्म को सामान्यीकृत किया जा सकता है।<ref name="ukkonen83"/>
+पुनरावर्ती खंड के न्यूनीकरण में एक और शब्द जोड़कर पारदर्शिता को संभालने के लिए इस कलन विधि को सामान्यीकृत किया जा सकता है।<ref name="ukkonen83"/>
+इस पुनरावृत्ति का मूल्यांकन करने का सीधा, पुनरावर्तन (कंप्यूटर विज्ञान) तरीका [[घातीय समय]] लेता है। इसलिए, यह सामान्यतः एक [[गतिशील प्रोग्रामिंग|गतिशील क्रमादेशन]] कलन विधि का उपयोग करके गणना की जाती है जिसे सामान्यतः वैगनर-फिशर कलन विधि को श्रेय दिया जाता है।<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> पढ़ा जा सकता है।
-इस पुनरावृत्ति का मूल्यांकन करने का सीधा, पुनरावर्तन (कंप्यूटर विज्ञान) तरीका [[घातीय समय]] लेता है। इसलिए, यह आमतौर पर एक [[गतिशील प्रोग्रामिंग]] एल्गोरिदम का उपयोग करके गणना की जाती है जिसे आमतौर पर वैगनर-फिशर एल्गोरिदम को श्रेय दिया जाता है।<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"/>
-=== बेहतर एल्गोरिदम ===
+लैंडौ, मायर्स और श्मिट [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>
-ऊपर वर्णित वैगनर-फिशर एल्गोरिथम में सुधार करते हुए, [[एस्को उकोनेन]] कई रूपों का वर्णन करता है,<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>
+एक परिमित वर्णमाला और संपादन लागत के लिए जो एक दूसरे के गुणक हैं, सबसे तेज़ ज्ञात सटीक एल्गोरिदम मासेक और पैटरसन का है <ref>{{Cite journal|last1=Masek|first1=William J.|last2=Paterson|first2=Michael S.|date=February 1980|title=एक तेज़ एल्गोरिथम कंप्यूटिंग स्ट्रिंग संपादन दूरी|journal=Journal of Computer and System Sciences|volume=20|issue=1|pages=18–31|doi=10.1016/0022-0000(80)90002-1|issn=0022-0000|doi-access=free}}</ref> जिसमें O(nm/logn) का सबसे खराब वस्तुस्थिति कार्यावधि है।।
-एक परिमित वर्णमाला और संपादन लागत के लिए जो एक दूसरे के गुणक हैं, सबसे तेज़ ज्ञात सटीक एल्गोरिथम मासेक और पैटर्सन का है<ref>{{Cite journal|last1=Masek|first1=William J.|last2=Paterson|first2=Michael S.|date=February 1980|title=एक तेज़ एल्गोरिथम कंप्यूटिंग स्ट्रिंग संपादन दूरी|journal=Journal of Computer and System Sciences|volume=20|issue=1|pages=18–31|doi=10.1016/0022-0000(80)90002-1|issn=0022-0000|doi-access=free}}</ref> O(nm/logn) का सबसे खराब केस रनटाइम होना।
 == अनुप्रयोग ==
-एडिट डिस्टेंस [[कम्प्यूटेशनल बायोलॉजी]] और नेचुरल लैंग्वेज प्रोसेसिंग में एप्लिकेशन ढूंढता है, उदा। वर्तनी की गलतियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी स्ट्रिंग्स के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की उम्मीद की जाती है।
+संपादन प्रक्रिया [[कम्प्यूटेशनल बायोलॉजी|अभिकलनात्मक जीवविज्ञान]] और प्रकृत भाषा संसाधन में अनुप्रयोग ढूंढता है, उदा. वर्तनी की त्रुटियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान|अनुमानित श्रृंखला मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी श्रृंखला के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की अपेक्षा की जाती है।
+विभिन्न कलन विधि उपस्थित हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए श्रंखलाओं की एक जोड़ी के बीच की प्रक्रिया की गणना के साथ-साथ समस्याओं को हल करते हैं।
+* हिर्शबर्ग का कलन विधि दो श्रृंखला के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन प्रक्रिया को कम करने के रूप में परिभाषित किया गया है।
+* अनुमानित श्रृंखला मिलान संपादन प्रक्रिया के संदर्भ में तैयार किया जा सकता है। उकोनेन का 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"/>
-विभिन्न एल्गोरिदम मौजूद हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए तारों की एक जोड़ी के बीच की दूरी की गणना के साथ-साथ समस्याओं को हल करते हैं।
-* हिर्शबर्ग का एल्गोरिथ्म दो स्ट्रिंग्स के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन दूरी को कम करने के रूप में परिभाषित किया गया है।
+== भाषा संपादन प्रक्रिया ==
-* अनुमानित स्ट्रिंग मिलान संपादन दूरी के संदर्भ में तैयार किया जा सकता है। उकोनेन का 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. अहो-कोरासिक स्ट्रिंग मैचिंग एल्गोरिद्म|अहो-कोरासिक एल्गोरिद्म, जो समान रूप से किसी भी पैटर्न को खोजने के लिए एक ऑटोमेटन का निर्माण करता है, लेकिन संपादन कार्यों की अनुमति के बिना)। अनुमानित स्ट्रिंग मिलान के लिए एक समान एल्गोरिथ्म [[थकना]] है, जिसे संपादन दूरी के संदर्भ में भी परिभाषित किया गया है।
+श्रृंखला के बीच संपादन प्रक्रिया का एक सामान्यीकरण श्रृंखला और भाषा के बीच भाषा संपादन प्रक्रिया है, सामान्यतः एक [[औपचारिक भाषा]] है। एक श्रृंखला और दूसरे के बीच संपादन प्रक्रिया पर विचार करने के स्थान पर, भाषा संपादन प्रक्रिया न्यूनतम संपादन प्रक्रिया है जिसे एक निश्चित श्रृंखला और श्रृंखला के सम्मुच्चय से ली गई किसी भी श्रृंखला के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा L और श्रृंखला x के लिए एक वर्णमाला {{math|Σ}} के ऊपर, भाषा संपादन प्रक्रिया d(L, x) <math>d(L,x) = \min_{y \in L} d(x,y)
-* [[लेवेनशेटिन ऑटोमेटन]] परिमित-अवस्था वाली मशीनें हैं जो एक निश्चित संदर्भ स्ट्रिंग की सीमित संपादन दूरी के भीतर स्ट्रिंग्स के एक सेट को पहचानती हैं।<ref name="ssm"/>
+</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>
-स्ट्रिंग्स के बीच संपादन दूरी का एक सामान्यीकरण स्ट्रिंग और भाषा के बीच भाषा संपादन दूरी है, आमतौर पर एक [[औपचारिक भाषा]]। एक स्ट्रिंग और दूसरे के बीच संपादन दूरी पर विचार करने के बजाय, भाषा संपादन दूरी न्यूनतम संपादन दूरी है जिसे एक निश्चित स्ट्रिंग और स्ट्रिंग्स के सेट से ली गई किसी भी स्ट्रिंग के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा के लिए L और स्ट्रिंग x एक वर्णमाला के ऊपर {{math|Σ}}, भाषा संपादन दूरी d(L, x) द्वारा दी गई है<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(L,x) = \min_{y \in L} d(x,y)
-</math>, कहाँ <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>
 == यह भी देखें ==
-* ग्राफ़ संपादन दूरी
+* आलेख संपादन प्रक्रिया
-* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या]]
+* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|श्रृंखला-से-श्रृंखला सुधार समस्या]]
-* स्ट्रिंग मीट्रिक
+* श्रृंखला मापीय
-* [[समय ताना संपादन दूरी]]
+* [[समय ताना संपादन दूरी|समय आधार संपादन प्रक्रिया]]
 ==संदर्भ==
@@ Line 119: / Line 125: @@
 {{Strings}}
-[[Category: स्ट्रिंग मेट्रिक्स]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Collapse templates]]
 [[Category:Created On 24/04/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with maths render errors]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:स्ट्रिंग मेट्रिक्स]]

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

Latest revision as of 10:11, 4 May 2023

Contents

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