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

From Vigyanwiki
No edit summary
No edit summary
Line 9: Line 9:
* लेवेंस्टीन दूरी विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
* लेवेंस्टीन दूरी विलोपन, प्रविष्टि और प्रतिस्थापन की अनुमति देती है।
* सबसे लंबी सामान्य अनुगामी (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)
# बिल्ली का बच्चा → बैठा हुआ (के के लिए स्थानापन्न s)
Line 44: Line 46:


=== गुण ===
=== गुण ===
गैर-ऋणात्मक लागत के साथ संपादन दूरी एक [[मीट्रिक (गणित)|मापीय (गणित)]] के स्वयंसिद्धों को संतुष्ट करती है, जब निम्नलिखित शर्तें पूरी होती हैं, तो श्रृंखला्स के एक [[मीट्रिक स्थान|मापीय स्थान]] को जन्म देता है:<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>
:असमानित त्रिकोण: {{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}}
लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (नॉनसिमेट्रिक) से दूरी संपादित करें <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 \\
:<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_{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>
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. अहो-कोरासिक श्रृंखला मैचिंग एल्गोरिद्म|अहो-कोरासिक एल्गोरिद्म, जो समान रूप से किसी भी पैटर्न को खोजने के लिए एक ऑटोमेटन का निर्माण करता है, लेकिन संपादन कार्यों की अनुमति के बिना)। अनुमानित श्रृंखला मिलान के लिए एक समान एल्गोरिथ्म [[थकना]] है, जिसे संपादन दूरी के संदर्भ में भी परिभाषित किया गया है।
* अनुमानित श्रृंखला मिलान संपादन दूरी के संदर्भ में तैयार किया जा सकता है। उकोनेन का 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) <math>d(L,x) = \min_{y \in L} d(x,y)
 
</math> द्वारा दी गई है<ref name=":0">{{cite book|doi=10.1109/focs.2016.48|chapter=Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product|chapter-url=https://theory.stanford.edu/~virgi/RNAfold.pdf|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|pages=375–384|year=2016|last1=Bringmann|first1=Karl|last2=Grandoni|first2=Fabrizio|last3=Saha|first3=Barna|author3-link=Barna Saha|last4=Williams|first4=Virginia Vassilevska|author-link4=Virginia Vassilevska Williams|isbn=978-1-5090-3933-3|arxiv=1707.05095|s2cid=17064578 }}</ref>, जहाँ <math>d(x,y)</math> श्रृंखला संपादन दूरी है। जब भाषा एल [[प्रसंग-मुक्त भाषा]] है, तो 1972 में अहो और पीटरसन द्वारा प्रस्तावित त्रिविमीय काल गतिशील क्रमादेशन कलन विधि है जो भाषा संपादन दूरी की गणना करता है।<ref>{{Cite journal|last1=Aho|first1=A.|last2=Peterson|first2=T.|date=1972-12-01|title=प्रसंग-मुक्त भाषाओं के लिए एक न्यूनतम दूरी त्रुटि-सुधार पार्सर|journal=SIAM Journal on Computing|volume=1|issue=4|pages=305–312|doi=10.1137/0201022|issn=0097-5397}}</ref> व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि [[नियमित व्याकरण]], संपादन दूरी की गणना के लिए तीव्र कलन विधि उपस्थित हैं।<ref>{{cite journal|doi=10.1145/360980.360995|title=आदेश-एन नियमित भाषाओं के लिए सुधार|journal=Communications of the ACM|volume=17|issue=5|pages=265–268|year=1974|last1=Wagner|first1=Robert A.|s2cid=11063282}}</ref>
 
लैंग्वेज संपादन दूरी में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए वलन, त्रुटि सुधार और इष्टतम स्तंभ जनन समस्या का समाधान।<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>


</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>




== यह भी देखें ==
== यह भी देखें ==
* ग्राफ़ संपादन दूरी
* आलेख संपादन दूरी
* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|श्रृंखला-टू-श्रृंखला सुधार समस्या]]
* [[स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या|श्रृंखला-से-श्रृंखला सुधार समस्या]]
* श्रृंखला मापीय
* श्रृंखला मापीय
* [[समय ताना संपादन दूरी]]
* [[समय ताना संपादन दूरी|समय आधार संपादन दूरी]]


==संदर्भ==
==संदर्भ==

Revision as of 04:29, 28 April 2023

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

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


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

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

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

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

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

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

एकल प्रतीक का अंतर्वेशन। यदि a = uv, फिर प्रतीक x सम्मिलित करना uxv उत्पन्न करता है। इसे ε →x भी निरूपित किया जा सकता है, खाली श्रृंखला को निरूपित करने के लिए ε का उपयोग किया जा सकता है।
एकल प्रतीक परिवर्तन का विलोपन uxv को uv (x→ε) में परिवर्तित कर देता है।
एकल प्रतीक का प्रतिस्थापन x प्रतीक के लिए y ≠ x uxv को uyv (x→y) में परिवर्तित कर देता है।

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

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

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

उदाहरण

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

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

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

  1. बिल्ली का बच्चा → इटेन (0 पर k हटाएं)
  2. itten → बैठे (0 पर एस डालें)
  3. बैठे → बैठे (4 पर ई हटाएं)
  4. सिट्टन → सिट्टिन (4 पर i डालें)
  5. सिटिन → सिटिंग (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]


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

Main article: वैगनर-फिशर कलन विधि

लेवेंस्टीन के मूल संचालन का उपयोग करते हुए, (असममितीय) से दूरी को संपादन द्वारा दिया गया है, पुनरावर्ती परिभाषा द्वारा निम्न परिभाषित[2]

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

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

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


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

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

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

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

अनुप्रयोग

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

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

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


भाषा संपादन दूरी

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

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


यह भी देखें

संदर्भ

  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.
  2. ↑ 2.0 2.1 2.2 2.3 Daniel Jurafsky; James H. Martin. भाषण और भाषा प्रसंस्करण. Pearson Education International. pp. 107–111.
  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.
  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 Lp-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.
  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.
  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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=दूरी_संपादित_करें&oldid=152009’