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

Revision as of 23:21, 27 April 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 है। एक न्यूनतम संपादन स्क्रिप्ट जो पूर्व को बाद में बदल देती है:

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

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

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

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) द्वारा दी गई है^[14] $d(L,x)=\min _{y\in L}d(x,y)$ , कहाँ $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) दूरी केवल प्रविष्टि और विलोपन की अनुमति देती है, प्रतिस्थापन की नहीं।
-* [[हैमिंग दूरी]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के तारों पर लागू होती है।
+* [[हैमिंग दूरी]] केवल प्रतिस्थापन की अनुमति देती है, इसलिए, यह केवल उसी लंबाई के श्रंखलाों पर लागू होती है।
 * दमेरौ-लेवेनशेटिन दूरी दो आसन्न पात्रों के सम्मिलन, विलोपन, प्रतिस्थापन और ट्रांसपोजिशन (गणित) की अनुमति देती है।
 * जारो दूरी केवल [[स्थानान्तरण (गणित)]] की अनुमति देती है।
-कुछ संपादन दूरियों को अनुमत संपादन कार्यों के एक विशिष्ट सेट के साथ परिकलित एक पैरामीटर योग्य मीट्रिक के रूप में परिभाषित किया गया है, और प्रत्येक ऑपरेशन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] एल्गोरिदम जैसे स्मिथ-वाटरमैन एल्गोरिदम द्वारा आगे सामान्यीकृत किया गया है, जो एक ऑपरेशन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
+कुछ संपादन दूरियों को अनुमत संपादन कार्यों के एक विशिष्ट सेट के साथ परिकलित एक पैरामीटर योग्य मापीय के रूप में परिभाषित किया गया है, और प्रत्येक ऑपरेशन को एक लागत (संभवतः अनंत) सौंपी गई है। यह डीएनए [[अनुक्रम संरेखण]] एल्गोरिदम जैसे स्मिथ-वाटरमैन एल्गोरिदम द्वारा आगे सामान्यीकृत किया गया है, जो एक ऑपरेशन की लागत पर निर्भर करता है जहां इसे लागू किया जाता है।
 == औपचारिक परिभाषा और गुण ==
-दो तार दिए गए {{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}})}} परिवर्तन करने वाले संपादन कार्यों की न्यूनतम-भार श्रृंखला है {{mvar|a}} में {{mvar|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|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"/>जारो-विंकलर दूरी को संपादित दूरी से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।
 === उदाहरण ===
@@ Line 44: / Line 44: @@
 === गुण ===
-गैर-ऋणात्मक लागत के साथ संपादन दूरी एक [[मीट्रिक (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित शर्तें पूरी होती हैं, तो स्ट्रिंग्स के एक [[मीट्रिक स्थान]] को जन्म देता है:<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}}) = {{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|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>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 81: / Line 81: @@
 पुनरावर्ती खंड के न्यूनीकरण में एक और शब्द जोड़कर पारदर्शिता को संभालने के लिए इस एल्गोरिथ्म को सामान्यीकृत किया जा सकता है।<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"/>
+ऊपर वर्णित वैगनर-फिशर एल्गोरिथम में सुधार करते हुए, [[एस्को उकोनेन]] कई रूपों का वर्णन करता है,<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 93: / Line 93: @@
 == अनुप्रयोग ==
-एडिट डिस्टेंस [[कम्प्यूटेशनल बायोलॉजी]] और नेचुरल लैंग्वेज प्रोसेसिंग में एप्लिकेशन ढूंढता है, उदा। वर्तनी की गलतियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी स्ट्रिंग्स के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की उम्मीद की जाती है।
+एडिट डिस्टेंस [[कम्प्यूटेशनल बायोलॉजी|अभिकलनात्मक बायोलॉजी]] और नेचुरल लैंग्वेज प्रोसेसिंग में एप्लिकेशन ढूंढता है, उदा। वर्तनी की गलतियों या ओसीआर त्रुटियों का सुधार, और [[अनुमानित स्ट्रिंग मिलान|अनुमानित श्रृंखला मिलान]], जहां उद्देश्य कई लंबे पाठों में छोटी श्रृंखला्स के लिए मिलान ढूंढना है, ऐसी स्थितियों में जहां कम संख्या में अंतर की उम्मीद की जाती है।
-विभिन्न एल्गोरिदम मौजूद हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए तारों की एक जोड़ी के बीच की दूरी की गणना के साथ-साथ समस्याओं को हल करते हैं।
+विभिन्न एल्गोरिदम मौजूद हैं जो संबंधित प्रकार की समस्याओं को हल करने के लिए श्रंखलाों की एक जोड़ी के बीच की दूरी की गणना के साथ-साथ समस्याओं को हल करते हैं।
-* हिर्शबर्ग का एल्गोरिथ्म दो स्ट्रिंग्स के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन दूरी को कम करने के रूप में परिभाषित किया गया है।
+* हिर्शबर्ग का एल्गोरिथ्म दो श्रृंखला्स के इष्टतम अनुक्रम संरेखण की गणना करता है, जहां इष्टतमता को संपादन दूरी को कम करने के रूप में परिभाषित किया गया है।
-* अनुमानित स्ट्रिंग मिलान संपादन दूरी के संदर्भ में तैयार किया जा सकता है। उकोनेन का 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) द्वारा दी गई है<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)
+श्रृंखला्स के बीच संपादन दूरी का एक सामान्यीकरण श्रृंखला और भाषा के बीच भाषा संपादन दूरी है, सामान्यतः पर एक [[औपचारिक भाषा]]। एक श्रृंखला और दूसरे के बीच संपादन दूरी पर विचार करने के बजाय, भाषा संपादन दूरी न्यूनतम संपादन दूरी है जिसे एक निश्चित श्रृंखला और श्रृंखला्स के सेट से ली गई किसी भी श्रृंखला के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा के लिए 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>
+</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 111: / Line 111: @@
 == यह भी देखें ==
 * ग्राफ़ संपादन दूरी
-* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या]]
+* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|श्रृंखला-टू-श्रृंखला सुधार समस्या]]
-* स्ट्रिंग मीट्रिक
+* श्रृंखला मापीय
 * [[समय ताना संपादन दूरी]]

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 23:21, 27 April 2023

Contents

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