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

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

संपादन दूरी की विभिन्न परिभाषाएँ स्ट्रिंग संचालन के विभिन्न सेटों का उपयोग करती हैं। लेवेनशेटिन डिस्टेंस ऑपरेशंस स्ट्रिंग में किसी वर्ण को हटाना, सम्मिलित करना या प्रतिस्थापन करना है। सबसे आम मीट्रिक होने के नाते, 'लेवेनशेटिन दूरी' शब्द का प्रयोग अक्सर 'संपादन दूरी' के साथ एक दूसरे के स्थान पर किया जाता है।

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

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

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

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

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

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

एकल प्रतीक का सम्मिलन। अगर a = uv, फिर प्रतीक सम्मिलित करना x पैदा करता है uxv. इसे ε → भी निरूपित किया जा सकता हैx, खाली स्ट्रिंग को निरूपित करने के लिए ε का उपयोग करना।

एकल प्रतीक परिवर्तन का विलोपन uxv को uv (x→ε).

एकल प्रतीक का प्रतिस्थापन x प्रतीक के लिए y ≠ x परिवर्तन uxv को uyv (x→y).

लेवेनशेटिन की मूल परिभाषा में, इनमें से प्रत्येक ऑपरेशन की इकाई लागत होती है (सिवाय इसके कि एक चरित्र के प्रतिस्थापन की लागत शून्य होती है), इसलिए लेवेनशेटिन की दूरी रूपांतरण के लिए आवश्यक संचालन की न्यूनतम संख्या के बराबर होती है a को b. एक अधिक सामान्य परिभाषा गैर-नकारात्मक भार कार्यों को जोड़ती है w_ins(x), w_del(x) और w_sub(x, y) संचालन के साथ। अतिरिक्त आदिम संचालन का सुझाव दिया गया है। डमेराउ-लेवेनशेटिन दूरी एक एकल संपादन के रूप में गिना जाता है एक सामान्य गलती: दो आसन्न पात्रों का स्थानांतरण, औपचारिक रूप से एक ऑपरेशन द्वारा विशेषता जो बदलता है uxyv में uyxv.ऑप्टिकल कैरेक्टर मान्यता आउटपुट को सही करने के कार्य के लिए, मर्ज और स्प्लिट ऑपरेशंस का उपयोग किया गया है जो एकल कैरेक्टर को उनमें से एक जोड़ी या इसके विपरीत में बदल देता है। संचालन के सेट को प्रतिबंधित करके संपादन दूरी के अन्य संस्करण प्राप्त किए जाते हैं। सबसे लंबी सामान्य बाद की समस्या | सबसे लंबी सामान्य अनुवर्ती (एलसीएस) दूरी इकाई लागत पर केवल दो संपादन कार्यों के रूप में सम्मिलन और विलोपन के साथ संपादन दूरी है। इसी तरह, केवल प्रतिस्थापन (फिर से इकाई लागत पर) की अनुमति देकर, हैमिंग दूरी प्राप्त की जाती है; यह समान-लंबाई वाले तारों तक ही सीमित होना चाहिए।जारो-विंकलर दूरी को संपादित दूरी से प्राप्त किया जा सकता है जहां केवल स्थानान्तरण की अनुमति है।

उदाहरण

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

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

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

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

5 संचालन की कुल लागत/दूरी के लिए।

गुण

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

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

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

d(a, b) = 0 अगर और केवल अगर a = b, क्योंकि प्रत्येक स्ट्रिंग को बिल्कुल शून्य संचालन का उपयोग करके तुच्छ रूप से परिवर्तित किया जा सकता है।

d(a, b) > 0 जब a ≠ b, क्योंकि इसके लिए गैर-शून्य लागत पर कम से कम एक ऑपरेशन की आवश्यकता होगी।

d(a, b) = d(b, a) प्रत्येक ऑपरेशन की लागत और उसके व्युत्क्रम की समानता से।

असमानित त्रिकोण: d(a, c) ≤ d(a, b) + d(b, c).

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

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

• एलसीएस दूरी तार की एक जोड़ी की लंबाई के योग से ऊपर है।
• एलसीएस दूरी लेवेनशेटिन दूरी पर ऊपरी सीमा है।
• समान लंबाई के तारों के लिए, हैमिंग दूरी लेवेनशेटिन दूरी पर एक ऊपरी सीमा होती है।

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

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

संगणना

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

सामान्य एल्गोरिदम

Main article: Wagner–Fischer algorithm

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

${\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}$

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

इस पुनरावृत्ति का मूल्यांकन करने का सीधा, पुनरावर्तन (कंप्यूटर विज्ञान) तरीका घातीय समय लेता है। इसलिए, यह आमतौर पर एक गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग करके गणना की जाती है जिसे आमतौर पर वैगनर-फिशर एल्गोरिदम को श्रेय दिया जाता है। हालांकि इसका कई आविष्कारों का इतिहास है।वैगनर-फिशर एल्गोरिथम के पूरा होने के बाद, डायनेमिक प्रोग्रामिंग एल्गोरिथम के दौरान उपयोग किए जाने वाले ऑपरेशंस के बैकट्रेस के रूप में एडिट ऑपरेशंस का एक न्यूनतम अनुक्रम पढ़ा जा सकता है $d_{mn}$.

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

बेहतर एल्गोरिदम

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

गाड लैंडौ, यूजीन मायर्स, और श्मिट [1] द्वारा किए गए और सुधार एक देते हैं O(s² + max(m,n)) समय एल्गोरिथ्म। एक परिमित वर्णमाला और संपादन लागत के लिए जो एक दूसरे के गुणक हैं, सबसे तेज़ ज्ञात सटीक एल्गोरिथम मासेक और पैटर्सन का है O(nm/logn) का सबसे खराब केस रनटाइम होना।

अनुप्रयोग

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

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

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

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

स्ट्रिंग्स के बीच संपादन दूरी का एक सामान्यीकरण स्ट्रिंग और भाषा के बीच भाषा संपादन दूरी है, आमतौर पर एक औपचारिक भाषा। एक स्ट्रिंग और दूसरे के बीच संपादन दूरी पर विचार करने के बजाय, भाषा संपादन दूरी न्यूनतम संपादन दूरी है जिसे एक निश्चित स्ट्रिंग और स्ट्रिंग्स के सेट से ली गई किसी भी स्ट्रिंग के बीच प्राप्त किया जा सकता है। अधिक औपचारिक रूप से, किसी भी भाषा के लिए L और स्ट्रिंग x एक वर्णमाला के ऊपर Σ, भाषा संपादन दूरी d(L, x) द्वारा दी गई है$d(L,x)=\min _{y\in L}d(x,y)$, कहाँ $d(x,y)$ स्ट्रिंग संपादन दूरी है। जब भाषा एल प्रसंग-मुक्त भाषा है, तो 1972 में अहो और पीटरसन द्वारा प्रस्तावित क्यूबिक टाइम डायनेमिक प्रोग्रामिंग एल्गोरिदम है जो भाषा संपादन दूरी की गणना करता है। व्याकरण के कम अभिव्यंजक परिवारों के लिए, जैसे कि नियमित व्याकरण, संपादन दूरी की गणना के लिए तेज़ एल्गोरिदम मौजूद हैं। लैंग्वेज एडिट डिस्टेंस में कई विविध अनुप्रयोग पाए गए हैं, जैसे कि आरएनए फोल्डिंग, त्रुटि सुधार और इष्टतम स्टैक जनरेशन समस्या का समाधान।

यह भी देखें

• ग्राफ़ संपादन दूरी
• स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या
• स्ट्रिंग मीट्रिक
• समय ताना संपादन दूरी