सूचना दूरी

सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक कंप्यूटर में बदल देती है यह जटिलता का विस्तार है इसमें एकल परिमित वस्तु की कोलमोगोरोव जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु से या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित और जांच की गई थी ऊष्मागतिकीय सिद्धांतों पर आधारित यह सामान्यीकृत संपीड़न दूरी और सामान्यीकृत दूरी में लागू होता है।

गुण

औपचारिक रूप से सूचना दूरी के $ID(x,y)$ बीच में $x$ और $y$ द्वारा परिभाषित किया गया है

$ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},$

साथ $p$ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को में परिभाषित करें इससे यह सिद्ध है कि$ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ साथ

$E(x,y)=\max\{K(x\mid y),K(y\mid x)\},$ जहाँ $K(\cdot \mid \cdot )$ द्वारा परिभाषित कोलमोगोरोव की जटिलता है।

सार्वभौमिकता

सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे $D(x,y)$ जो घनत्व की स्थिति को संतुष्ट करता है

$\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,$

यह अप्रासंगिक दूरियों को बाहर करता है जैसे $D(x,y)={\frac {1}{2}}$ के लिए $x\neq y$ यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है तो $D\in \Delta$ तब $E(x,y)\leq D(x,y)$ यह एक निरंतर योगात्मक शब्द तक की दूरी संभाव्यता अभिव्यक्तियाँ सूचना सममित में पहला वर्ग है जिसे सार्वभौमिकता संपत्ति के रूप में जाना जा सकता है।

मीट्रिक

दूरी $E(x,y)$ योज्य तक एक प्रवेशिका स्थान है जो $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ प्रवेशिका 1981 में हान द्वारा दिखाया गया कि प्रवेशिका का संभाव्य संस्करण में अद्वितीय है।

अधिकतम अतिच्छादन

अगर $E(x,y)=K(x\mid y)$ एक कार्यक्रम होता है तो $p$ लंबाई $K(x\mid y)$ में परिवर्तित हो जाता है $y$ को $x$ और एक कार्यक्रम $q$ लंबाई का $K(y\mid x)-K(x\mid y)$ ऐसा रूपांतरण है कि कार्यक्रम $qp$ धर्मान्तरित $x$ तथा $y$.अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है $K(x\mid y)\leq K(y\mid x)$ इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें $x$ वस्तु के लिए $y$और दूसरा कार्यक्रम जो पहले धर्मान्तरित के साथ जुड़ा हुआ है जैसे $y$ तथा $x$ जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।

न्यूनतम अतिच्छादन

कार्यक्रम को वस्तुओं के बीच बदलने के लिए $x$ और $y$ न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ $p$ लंबाई$O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ है यहाँ $y$ तथा $x$ छोटी जटिलता है जब $x$ ज्ञात है तो ($K(p\mid x)\approx 0$).जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है इसमें शैन्य सूचना सिद्धांत और जटिलता सिद्धांत के बीच समानता रखनी चाहिए।

अनुप्रयोग

सैद्धांतिक

इसमें ऊपर न्यूनतम अतिच्छादन पर एक महत्वपूर्ण सैद्धांतिक अनुप्रयोग दिखाया जा रहा है कि इसमें कुछ संकेत एकत्रित हैं यह किसी वस्तु से परिमित लक्ष्य पर जाने के लिए कार्यरत् है जो लक्ष्य वस्तु पर निर्भर करता है ।

व्यावहारिक

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

संबंधित साहित्य

• Arkhangel'skii, A. V.; Pontryagin, L. S. (1990), General Topology I: Basic Concepts and Constructions Dimension Theory, Encyclopaedia of Mathematical Sciences, Springer, ISBN 3-540-18178-4

श्रेणी:सांख्यिकीय दूरी