सूचना दूरी

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

गुण

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

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

साथ $p$ फिक्स्ड यूनिवर्सल कंप्यूटर के लिए एक परिमित बाइनरी प्रोग्राम इनपुट के रूप में बाइनरी स्ट्रिंग्स को परिमित करें $x,y$. में यह सिद्ध है $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 )$ द्वारा परिभाषित कोलमोगोरोव जटिलता है उपसर्ग प्रकार का। यह $E(x,y)$ महत्वपूर्ण मात्रा है।

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

होने देना $\Delta$ ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो $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$ लंबाई का $K(x\mid y)$ की योगात्मक अवधि तक $O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ वह मानचित्र $y$ को $x$ और छोटी जटिलता है जब $x$ ज्ञात है ($K(p\mid x)\approx 0$). हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है शैनन सूचना सिद्धांत और कोल्मोगोरोव जटिलता सिद्धांत के बीच समानता को ध्यान में रखते हुए, कोई कह सकता है कि यह परिणाम स्लीपियन-वुल्फ कोडिंग | स्लीपियन-वुल्फ और कोर्नर-इमरे सिस्ज़ार-मार्टन प्रमेयों के समानांतर है।

अनुप्रयोग

सैद्धांतिक

An.A का परिणाम। ऊपर न्यूनतम ओवरलैप पर मुचनिक एक महत्वपूर्ण सैद्धांतिक अनुप्रयोग दिखा रहा है कि कुछ कोड मौजूद हैं: किसी भी वस्तु से परिमित लक्ष्य वस्तु पर जाने के लिए एक कार्यक्रम है जो लगभग केवल लक्ष्य वस्तु पर निर्भर करता है! यह परिणाम काफी सटीक है और त्रुटि शब्द में महत्वपूर्ण सुधार नहीं किया जा सकता है। पाठ्यपुस्तक में सूचना दूरी सामग्री थी, यह एनसाइक्लोपीडिया ऑन डिस्टेंस में होता है।

व्यावहारिक

जीनोम, भाषा, संगीत, इंटरनेट हमले और वर्म्स, सॉफ़्टवेयर प्रोग्राम आदि जैसी वस्तुओं की समानता निर्धारित करने के लिए, सूचना दूरी को सामान्यीकृत किया जाता है और कोलमोगोरोव जटिलता की शर्तों को वास्तविक दुनिया कंप्रेशर्स द्वारा अनुमानित किया जाता है (कोलमोगोरोव जटिलता एक निम्न सीमा है वस्तु के एक संकुचित संस्करण के बिट्स में लंबाई)। परिणाम वस्तुओं के बीच सामान्यीकृत संपीड़न दूरी (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

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