लेम्पेल-ज़िव सम्मिश्रता: Difference between revisions

Latest revision as of 13:37, 29 August 2023

लेम्पेल-ज़िव सम्मिश्रता एक माप है जिसे पहली बार दो इज़राइली कंप्यूटर वैज्ञानिक अब्राहम लेम्पेल और जैकब ज़िव द्वारा "परिमित अनुक्रमों की सम्मिश्रता" नामक लेख (इलेक्ट्रिकल और इलेक्ट्रॉनिक इंजीनियर संस्थान पर आईटी-22,1 1976) में प्रस्तुत किया गया था। यह सम्मिश्रता माप कोल्मोगोरोव सम्मिश्रता से संबंधित है। लेकिन इसका उपयोग करने वाला एकमात्र कार्य प्रतिवर्तन (अर्थात, अस्पष्ट प्रतिलिपि) है।

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

लेम्पेल-ज़िव सम्मिश्रता का उपयोग बाइनरी अनुक्रमों और टेक्स्ट की पुनरावृत्ति को मापने के लिए किया जा सकता है। जैसे गीत या गद्य वास्तविक विश्व के आंकड़ा का आंशिक आयाम या अनुमानों को लेम्पेल-ज़िव सम्मिश्रता के साथ सहसंबंधित दिखाया गया है।^[1]^[2]

सिद्धांत

माना कि S एक द्विआधारी अनुक्रम है जिसकी लंबाई n है। जिसके लिए हमें लेम्पेल-ज़िव सम्मिश्रता की गणना करनी है जिसे C(S) द्वारा निरूपित किया गया है। इस अनुक्रम बाईं ओर से पढ़ा जाता है।

कल्पना कीजिए कि आपके पास एक परिसीमन रेखा है, जिसे गणना के समय अनुक्रम में स्थानांतरित किया जा सकता है। सबसे पहले, यह रेखा अनुक्रम के प्रारम्भ में पहले प्रतीक के ठीक बाद प्रयोग की जाती है। इस प्रारंभिक स्थिति को स्थिति 1 कहा जाता है, जहाँ से हमें इसे स्थिति 2 पर ले जाना होता है, जिसे अगले चरण (और इसी प्रकार) के लिए प्रारंभिक स्थिति माना जाता है। हमें सीमांकक (स्थिति 1 से प्रारम्भ करके) को यथासंभव दाईं ओर ले जाना होता है ताकि स्थिति 1 और सीमांकक स्थिति के बीच का उप-शब्द अनुक्रम का एक शब्द हो जो सीमांकक की स्थिति 1 से पहले प्रारम्भ होता है।

जैसे ही सीमांकक ऐसी स्थिति पर प्रयुक्त होता है जहाँ यह स्थिति पूरी नहीं होती है, हम रुक जाते हैं, सीमांकक को इस स्थिति में ले जाते हैं, और इस स्थिति को एक नई प्रारंभिक स्थिति (अर्थात, स्थिति 1) के रूप में चिह्नित करके पुनः प्रारम्भ करते हैं। अनुक्रम के अंत तक पुनरावृति करते है। लेम्पेल-ज़िव सम्मिश्रता इस प्रक्रिया को पूरा करने के लिए आवश्यक पुनरावृत्तियों की संख्या के अनुरूप होती है।

अन्य प्रकार से कहा गया है कि लेम्पेल-ज़िव सम्मिश्रता विभिन्न उप-स्ट्रिंग (या उप-शब्दों) की संख्या है जो बाइनरी अनुक्रम के रूप में एक धारा (बाएं से दाएं) के रूप में प्रदर्शित की जाती है।

औपचारिक स्पष्टीकरण

लेम्पेल और ज़िव द्वारा प्रस्तावित विधियां पुनरुत्पादन, उत्पादन क्षमता और अनुक्रम का संपूर्ण इतिहास की तीन धारणाओं का उपयोग करती है। जिसको निम्नवत परिभाषित किया गया है।

अंकन

माना कि S लंबाई का द्विआधारी अनुक्रम n है अर्थात n का प्रतीक 0 या 1 को मान लेते हैं। मान लीजिए S(i,j), $1\leq i,j\leq n$ के साथ सूचकांक i से सूचकांक j तक S का उप-शब्द है यदि j<i, S(i,j) रिक्त स्ट्रिंग है। तब S की लंबाई n को l(S) से निरूपित किया जाता है और अनुक्रम Q को S का निश्चित उपसर्ग कहा जाता है यदि $Q=\exists j<{\text{l(S), s.t. S(1,j)}}$ है।

उत्पादकता और पुनरुत्पादन क्षमता

प्रतिलिपि प्रस्तुत करने की योग्यता के उदाहरण के लिए यहां क्लिक करें

एक तरफ लंबाई n के अनुक्रम S को इसके उपसर्ग S(1,j) से पुनरुत्पादित कहा जाता है जब S(j+1,n), S(1,j) का उप-शब्द होता है। तब इसे S(1,j)→S से निरूपित किया जाता है।

अन्य प्रकार से कहा गया है कि S अपने उपसर्ग S(1,j) से पुन: उत्पन्न होता है यदि शेष अनुक्रम S(j+1,n) कुछ भी नहीं है लेकिन S(1,n−1) के एक अन्य उप-शब्द (एक सूचकांक i < j+1 से प्रारम्भ) की एक प्रतिलिपि है।

यह सिद्ध करने के लिए कि अनुक्रम S को इसके एक उपसर्ग S(1,j) द्वारा पुन: प्रस्तुत किया जा सकता है। जिसको निम्नलोखित रूप मे प्रदर्शित किया गया है:

पुनरुत्पादन क्षमता और उत्पादकता के बीच तुलना के लिए यहां क्लिक करें

$\exists p\leq j,{\text{ s.t. }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)$

उत्पादकता के उदाहरण (यहां क्लिक करें)

दूसरी ओर उत्पादक क्षमता को पुनरुत्पादन से परिभाषित किया जाता है। एक अनुक्रम S इसके उपसर्ग S(1,j) से उत्पन्न होता है यदि S(1,n−1) S(1,j) से पुनरुत्पादित होता है। इसे S(1,j)⇒S द्वारा निरूपित किया जाता है। अन्य प्रकार से कहा गया है कि S(j+1,n−1) को S(1,n-2) के दूसरे उप-शब्द की एक प्रति होना है। S का अंतिम प्रतीक एक नया प्रतीक हो सकता है। S का अंतिम प्रतीक एक नया प्रतीक हो सकता है, लेकिन संभवतः एक नए उप-शब्द के उत्पादन के लिए अग्रणी नहीं हो सकता है, इसलिए यह शब्द उत्पादकता है।

संपूर्ण इतिहास और सम्मिश्रता

उत्पादकता की परिभाषा से रिक्त स्ट्रिंग Λ=S(1,0) ⇒ S(1,1) को पुनरावर्ती उत्पादन प्रक्रिया द्वारा चरण i के लिए S(1,hi) ⇒ S(1,hi+1) है, इसलिए हम इसके उपसर्गों से S का निर्माण कर सकते हैं। चूंकि S(1,i) ⇒ S(1,i+1) (hi+1 =hi + 1 के साथ) सदैव सत्य होता है। S की उत्पादन प्रक्रिया में अधिकतम n=l(S) चरण होते हैं। यह दो $1\leq {\text{m}}\leq l(S)$ और S की इस उत्पाद प्रक्रिया के लिए आवश्यक चरणों की संख्या S को विघटित रूप में लिखा जा सकता है। जिसे S का इतिहास कहा जाता है और H(S) को निरूपित किया जाता है जिसे इस प्रकार परिभाषित किया गया है:

$H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_{m-1}+1,h_{m})$ , $H_{i}(S)=S(h_{i-1}+1,h_{i}),i=1,2\dotsm m,{\text{where}}\;h_{0}=0,h_{1}=1,h_{m}=l(S),{{\text{ is called component of }}H(S)}.$

S को Hi(S) का एक घटक संपूर्ण माना जाता है यदि S(1,hi) S(1,hi−1) द्वारा निर्मित सबसे लंबा अनुक्रम है। अर्थात S(1,hi−1) ⇒ S( 1,hi)) इतना विस्तृत होता है कि S(1,hi−1) S(1,hi) का उत्पादन नहीं करता है:

$S(1,h_{i}-1)\nrightarrow S(1,h_{i})$

सूचकांक p जो सबसे लंबे समय तक उत्पादन करने की स्वीकृति देता है उसे पॉइंटर कहा जाता है।

S के इतिहास को संपूर्ण कहा जाता है यदि इसके सभी घटक संभवतः अंतिम को छोड़कर संपूर्ण होते हैं। परिभाषा से यह प्रदर्शित किया जा सकता है कि किसी भी अनुक्रम S का केवल एक संपूर्ण इतिहास है और यह इतिहास S के सभी संभावित इतिहासों में से सबसे कम घटकों वाला इतिहास है। अंत में S के इस अद्वितीय संपूर्ण इतिहास के घटक की संख्या S को लेम्पेल-ज़िव सम्मिश्रता कहा जाता है।

एल्गोरिथम

सामान्यतः अनुक्रम S की $n=l(S)$ लंबाई के लिए संक्रियक की रैखिक संख्या ${\mathcal {O}}(n)$ में इस सम्मिश्रता की गणना करने के लिए एक बहुत ही कुशल विधि सम्मिलित है।

इस पद्धति का एक औपचारिक विवरण निम्नलिखित एल्गोरिथम द्वारा दिया गया है:

i = p − 1, p सूचक है। (ऊपर देखें)
u वर्तमान उपसर्ग की लंबाई है।
v वर्तमान सूचकांक p के लिए वर्तमान घटक की लंबाई है।
v_max अंतिम लंबाई है जो वर्तमान घटक के लिए सभी संभावित पॉइंटर p पर सबसे बड़ी है।
C लेम्पेल-ज़िव सम्मिश्रता है जो पुनरुत्पादित रूप से अधिक है।

// S is a binary sequence of size n
i := 0
C := 1
u := 1
v := 1
vmax := v
while u + v <= n do
   if S[i + v] = S[u + v] then
      v := v + 1
   else
      vmax := max(v, vmax)
      i := i + 1
      if i = u then  // all the pointers have been treated
         C := C + 1
         u := u + vmax
         v := 1
         i := 0
         vmax := v
      else
         v := 1
      end if
   end if
end while
if v != 1 then
    C := C+1
end if

यह भी देखें

एलजेड-77 और एलजेड-78 आंकड़ा संपीड़न एल्गोरिदम है, जो उप स्ट्रिंग खोजने के समान सूचकांक का उपयोग करते हैं।

नोट्स और संदर्भ

संदर्भ

↑ Burns, T.; Rajan, R. (2015). "Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137". F1000Research. 4: 137. doi:10.12688/f1000research.6590.1. PMC 4648221. PMID 26594331.
↑ Burns, T.; Rajan, R. (2019). "मनुष्यों में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के वस्तुनिष्ठ स्पेक्ट्रो-लौकिक विशेषताओं के सहसंबंध के लिए एक गणितीय दृष्टिकोण". Frontiers in Neuroscience. 13: 794. doi:10.3389/fnins.2019.00794. PMC 6685481. PMID 31417350.

ग्रन्थसूची

Abraham Lempel and Jacob Ziv, « On the Complexity of Finite Sequences », IEEE Trans. on Information Theory, January 1976, p. 75–81, vol. 22, n°1

आवेदन

«क्या पॉप लिरिक्स अधिक दोहराव वाले हो रहे हैं? », कॉलिन मॉरिस द्वारा, एक ब्लॉग पोस्ट है जिसमें बताया गया है कि गीत के बोलों की पुनरावृत्ति को मापने के लिए लेम्पेल-ज़िव सम्मिश्रता का उपयोग कैसे करें (उपलब्ध स्रोत कोड के साथ)।
बर्न्स एंड राजन (2015) ईईजी डेटा के सम्मिश्रता उपायों का संयोजन: गुणा करने वाले उपाय पहले छिपी हुई जानकारी को प्रकट करते हैं। F1000 अनुसंधान। 4:137. [1] (उपलब्ध सार्वजनिक MATLAB कोड के साथ)।
बर्न्स एंड राजन (2019) मानव में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के ऑब्जेक्टिव स्पेक्ट्रो-टेम्पोरल फीचर्स को सहसंबंधित करने के लिए एक गणितीय दृष्टिकोण। न्यूरोसाइंस में फ्रंटियर्स 13:794। [2] (उपलब्ध सार्वजनिक MATLAB कोड के साथ)।

बाहरी संबंध

[1] Burns, T.; Rajan, R. (2015). "Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137". F1000Research. 4: 137. doi:10.12688/f1000research.6590.1. PMC 4648221. PMID 26594331.

[2] Burns, T.; Rajan, R. (2019). "मनुष्यों में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के वस्तुनिष्ठ स्पेक्ट्रो-लौकिक विशेषताओं के सहसंबंध के लिए एक गणितीय दृष्टिकोण". Frontiers in Neuroscience. 13: 794. doi:10.3389/fnins.2019.00794. PMC 6685481. PMID 31417350.

[1]

[2]

@@ Line 1: / Line 1: @@
-लेम्पेल-ज़िव जटिलता एक उपाय है जिसे पहली बार दो इज़राइली कंप्यूटर वैज्ञानिकों, [[अब्राहम लेम्पेल]] और [[जैकब ज़िव]] द्वारा 'ऑन द कॉम्प्लेक्सिटी ऑफ़ फ़ाइनाइट सीक्वेंस' (IEEE Trans. On IT-22,1 1976) लेख में प्रस्तुत किया गया था। यह जटिलता माप कोल्मोगोरोव जटिलता से संबंधित है, लेकिन इसका उपयोग करने वाला एकमात्र कार्य पुनरावर्ती प्रति (यानी, उथली प्रतिलिपि) है।
+'''लेम्पेल-ज़िव सम्मिश्रता''' एक माप है जिसे पहली बार दो इज़राइली कंप्यूटर वैज्ञानिक [[अब्राहम लेम्पेल]] और [[जैकब ज़िव]] द्वारा "परिमित अनुक्रमों की सम्मिश्रता" नामक लेख (इलेक्ट्रिकल और इलेक्ट्रॉनिक इंजीनियर संस्थान पर आईटी-22,1 1976) में प्रस्तुत किया गया था। यह सम्मिश्रता माप कोल्मोगोरोव सम्मिश्रता से संबंधित है। लेकिन इसका उपयोग करने वाला एकमात्र कार्य प्रतिवर्तन (अर्थात, अस्पष्ट प्रतिलिपि) है।
-इस जटिलता माप में अंतर्निहित तंत्र [[दोषरहित डेटा संपीड़न]] के लिए कुछ एल्गोरिदम के लिए शुरुआती बिंदु है, जैसे LZ77 और LZ78|LZ77, LZ78 और Lempel-Ziv-Welch। भले ही यह शब्दों की नकल के एक प्राथमिक सिद्धांत पर आधारित है, यह जटिलता माप इस अर्थ में बहुत अधिक प्रतिबंधात्मक नहीं है कि यह इस तरह के माप से अपेक्षित मुख्य गुणों को संतुष्ट करता है: एक निश्चित नियमितता वाले अनुक्रमों में बहुत बड़ी जटिलता नहीं होती है, और जटिलता बढ़ती है क्योंकि अनुक्रम लंबाई और अनियमितता में बढ़ता है।
-लेम्पेल-ज़िव जटिलता का उपयोग बाइनरी अनुक्रमों और पाठ की पुनरावृत्ति को मापने के लिए किया जा सकता है, जैसे गीत गीत या गद्य। वास्तविक दुनिया के डेटा के [[भग्न आयाम]] अनुमानों को लेम्पेल-ज़िव जटिलता के साथ सहसंबंधित दिखाया गया है।<ref>{{cite journal|title=Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137.|year=2015|pmc=4648221|last1=Burns|first1=T.|last2=Rajan|first2=R.|journal=F1000Research|volume=4|page=137|doi=10.12688/f1000research.6590.1|pmid=26594331}}</ref><ref>{{cite journal|title=मनुष्यों में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के वस्तुनिष्ठ स्पेक्ट्रो-लौकिक विशेषताओं के सहसंबंध के लिए एक गणितीय दृष्टिकोण|year=2019|pmid=31417350|last1=Burns|first1=T.|last2=Rajan|first2=R.|journal=Frontiers in Neuroscience|volume=13|page=794|doi=10.3389/fnins.2019.00794|pmc=6685481|doi-access=free}}</ref>
+इस सम्मिश्रता माप में अंतर्निहित तंत्र दोष रहित [[दोषरहित डेटा संपीड़न|आंकड़ा संपीड़न]] मे कुछ एल्गोरिदम के लिए एलजेड-77, एलजेड-78 और एलजेडडब्ल्यू जैसे प्रारम्भिक बिंदु है। यद्यपि यह शब्दों की प्रतिलिपि के प्राथमिक सिद्धांत पर आधारित है। यह सम्मिश्रता माप इस अर्थ में बहुत अधिक प्रतिबंधात्मक नहीं है कि यह इस प्रकार के माप से अपेक्षित मुख्य गुणों को संतुष्ट करता है। एक निश्चित नियमितता वाले अनुक्रमों में बहुत बड़ी सम्मिश्रता नहीं होती है। जिससे सम्मिश्रता बढ़ती है क्योंकि अनुक्रम लंबाई और अनियमितता में बढ़ती है।
+लेम्पेल-ज़िव सम्मिश्रता का उपयोग बाइनरी अनुक्रमों और टेक्स्ट की पुनरावृत्ति को मापने के लिए किया जा सकता है। जैसे गीत या गद्य वास्तविक विश्व के आंकड़ा का आंशिक आयाम या अनुमानों को लेम्पेल-ज़िव सम्मिश्रता के साथ सहसंबंधित दिखाया गया है।<ref>{{cite journal|title=Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137.|year=2015|pmc=4648221|last1=Burns|first1=T.|last2=Rajan|first2=R.|journal=F1000Research|volume=4|page=137|doi=10.12688/f1000research.6590.1|pmid=26594331}}</ref><ref>{{cite journal|title=मनुष्यों में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के वस्तुनिष्ठ स्पेक्ट्रो-लौकिक विशेषताओं के सहसंबंध के लिए एक गणितीय दृष्टिकोण|year=2019|pmid=31417350|last1=Burns|first1=T.|last2=Rajan|first2=R.|journal=Frontiers in Neuroscience|volume=13|page=794|doi=10.3389/fnins.2019.00794|pmc=6685481|doi-access=free}}</ref>
 == सिद्धांत ==
-चलो S एक द्विआधारी अनुक्रम है, जिसकी लंबाई n है, जिसके लिए हमें Lempel-Ziv जटिलता की गणना करनी है, जिसे C(S) निरूपित किया गया है। अनुक्रम बाईं ओर से पढ़ा जाता है।
+माना कि S एक द्विआधारी अनुक्रम है जिसकी लंबाई n है। जिसके लिए हमें लेम्पेल-ज़िव सम्मिश्रता की गणना करनी है जिसे C(S) द्वारा निरूपित किया गया है। इस अनुक्रम बाईं ओर से पढ़ा जाता है।
-कल्पना कीजिए कि आपके पास एक परिसीमन रेखा है, जिसे गणना के दौरान अनुक्रम में स्थानांतरित किया जा सकता है। सबसे पहले, यह रेखा अनुक्रम की शुरुआत में, पहले प्रतीक के ठीक बाद सेट की जाती है। इस प्रारंभिक स्थिति को स्थिति 1 कहा जाता है, जहाँ से हमें इसे स्थिति 2 पर ले जाना होता है, जिसे अगले चरण (और इसी तरह) के लिए प्रारंभिक स्थिति माना जाता है। हमें सीमांकक (स्थिति 1 से शुरू करके) को यथासंभव दाईं ओर ले जाना होगा, ताकि स्थिति 1 और सीमांकक स्थिति के बीच का उप-शब्द अनुक्रम का एक शब्द हो जो सीमांकक की स्थिति 1 से पहले शुरू होता है।
+कल्पना कीजिए कि आपके पास एक परिसीमन रेखा है, जिसे गणना के समय अनुक्रम में स्थानांतरित किया जा सकता है। सबसे पहले, यह रेखा अनुक्रम के प्रारम्भ में पहले प्रतीक के ठीक बाद प्रयोग की जाती है। इस प्रारंभिक स्थिति को स्थिति 1 कहा जाता है, जहाँ से हमें इसे स्थिति 2 पर ले जाना होता है, जिसे अगले चरण (और इसी प्रकार) के लिए प्रारंभिक स्थिति माना जाता है। हमें सीमांकक (स्थिति 1 से प्रारम्भ करके) को यथासंभव दाईं ओर ले जाना होता है ताकि स्थिति 1 और सीमांकक स्थिति के बीच का उप-शब्द अनुक्रम का एक शब्द हो जो सीमांकक की स्थिति 1 से पहले प्रारम्भ होता है।
-जैसे ही सीमांकक ऐसी स्थिति पर सेट होता है जहाँ यह स्थिति पूरी नहीं होती है, हम रुक जाते हैं, सीमांकक को इस स्थिति में ले जाते हैं, और इस स्थिति को एक नई प्रारंभिक स्थिति (यानी, स्थिति 1) के रूप में चिह्नित करके फिर से शुरू करते हैं। अनुक्रम के अंत तक पुनरावृति करते रहें। लेम्पेल-ज़िव जटिलता इस प्रक्रिया को पूरा करने के लिए आवश्यक पुनरावृत्तियों की संख्या से मेल खाती है।
+जैसे ही सीमांकक ऐसी स्थिति पर प्रयुक्त होता है जहाँ यह स्थिति पूरी नहीं होती है, हम रुक जाते हैं, सीमांकक को इस स्थिति में ले जाते हैं, और इस स्थिति को एक नई प्रारंभिक स्थिति (अर्थात, स्थिति 1) के रूप में चिह्नित करके पुनः प्रारम्भ करते हैं। अनुक्रम के अंत तक पुनरावृति करते है। लेम्पेल-ज़िव सम्मिश्रता इस प्रक्रिया को पूरा करने के लिए आवश्यक पुनरावृत्तियों की संख्या के अनुरूप होती है।
-अलग तरह से कहा गया है, लेम्पेल-ज़िव जटिलता विभिन्न उप-स्ट्रिंग्स (या उप-शब्दों) की संख्या है जो बाइनरी अनुक्रम के रूप में एक धारा (बाएं से दाएं) के रूप में देखी जाती है।
+अन्य प्रकार से कहा गया है कि लेम्पेल-ज़िव सम्मिश्रता विभिन्न उप-स्ट्रिंग (या उप-शब्दों) की संख्या है जो बाइनरी अनुक्रम के रूप में एक धारा (बाएं से दाएं) के रूप में प्रदर्शित की जाती है।
 == औपचारिक स्पष्टीकरण ==
-लेम्पेल और ज़िव द्वारा प्रस्तावित विधि तीन धारणाओं का उपयोग करती है: पुनरुत्पादन, उत्पादन क्षमता और एक अनुक्रम का संपूर्ण इतिहास, जिसे हमने यहां परिभाषित किया है।
+लेम्पेल और ज़िव द्वारा प्रस्तावित विधियां पुनरुत्पादन, उत्पादन क्षमता और अनुक्रम का संपूर्ण इतिहास की तीन धारणाओं का उपयोग करती है। जिसको निम्नवत परिभाषित किया गया है।
 === अंकन ===
-S को लंबाई n का एक बाइनरी अनुक्रम होने दें (अर्थात, n प्रतीक मान 0 या 1 लेते हैं)। माना S(i,j), साथ में <math>1\leq i,j\leq n</math>, अनुक्रमणिका i से अनुक्रमणिका j तक S का उप-शब्द हो (यदि j<i, S(i,j) खाली स्ट्रिंग है)। S की लंबाई n को l(S) से निरूपित किया जाता है, और एक अनुक्रम Q को S का निश्चित उपसर्ग कहा जाता है यदि:
+माना कि S लंबाई का द्विआधारी अनुक्रम n है अर्थात n का प्रतीक 0 या 1 को मान लेते हैं। मान लीजिए S(i,j), <math>1\leq i,j\leq n</math> के साथ सूचकांक i से सूचकांक j तक S का उप-शब्द है यदि j<i, S(i,j) रिक्त स्ट्रिंग है। तब S की लंबाई n को '''''l(S)''''' से निरूपित किया जाता है और अनुक्रम Q को S का निश्चित उपसर्ग कहा जाता है यदि <math> Q = \exists j<{\text{l(S), s.t. S(1,j)}}</math> है।
+=== उत्पादकता और पुनरुत्पादन क्षमता ===
-<math>\exists j<{\text{l(S), s.t. S(1,j) = Q .}}</math>
+[[File:Productibilité.svg|thumb|177x177px|प्रतिलिपि प्रस्तुत करने की योग्यता के उदाहरण [http://upload.wikimedia.org/wikipedia/commons/a/ad/Reproductibilit%C3%A91.svg के लिए यहां क्लिक करें]]]
+एक तरफ लंबाई n के अनुक्रम S को इसके उपसर्ग S(1,j) से पुनरुत्पादित कहा जाता है जब S(j+1,n), S(1,j) का उप-शब्द होता है। तब इसे S(1,j)→S से निरूपित किया जाता है।
-=== पुनरुत्पादन और उत्पादकता ===
-<इमेजमैप>Image:Reproductibilité1.svg|200px|thumb|प्रतिलिपि प्रस्तुत करने योग्यता का उदाहरण [http://upload.wikimedia.org/wikipedia/commons/a/ad/Reproductibilit%C3%A91.svg यहां क्लिक करें] </imagemap>
-एक तरफ, लंबाई एन के अनुक्रम एस को इसके उपसर्ग एस (1, जे) से पुनरुत्पादित कहा जाता है जब एस (जे + 1, एन) एस (1, जे) का उप-शब्द होता है। इसे S(1,j)→S निरूपित किया जाता है।
-अलग ढंग से कहा गया है, एस अपने उपसर्ग एस (1, जे) से पुनरुत्पादित है यदि शेष अनुक्रम, एस (जे + 1, एन), और कुछ नहीं है, लेकिन एक अन्य उप-शब्द की प्रतिलिपि है (एक सूचकांक i < j + से शुरू) 1) एस(1,एन−1) का।
-यह सिद्ध करने के लिए कि अनुक्रम S को इसके एक उपसर्ग S(1,j) द्वारा पुन: प्रस्तुत किया जा सकता है, आपको यह दिखाना होगा:
+अन्य प्रकार से कहा गया है कि S अपने उपसर्ग S(1,j) से पुन: उत्पन्न होता है यदि शेष अनुक्रम S(j+1,n) कुछ भी नहीं है लेकिन S(1,n−1) के एक अन्य उप-शब्द (एक सूचकांक i < j+1 से प्रारम्भ) की एक प्रतिलिपि है।
+यह सिद्ध करने के लिए कि अनुक्रम S को इसके एक उपसर्ग S(1,j) द्वारा पुन: प्रस्तुत किया जा सकता है। जिसको निम्नलोखित रूप मे प्रदर्शित किया गया है:
+[[File:Prod reprod1.svg|thumb|163x163px|पुनरुत्पादन क्षमता और उत्पादकता के बीच तुलना के लिए [https://upload.wikimedia.org/wikipedia/commons/8/87/Prod_reprod1.svg यहां क्लिक करें]]]
 <math>\exists p\leq j, {\text{ s.t.  }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)</math>
-<इमेजमैप>Image:Productibilité.svg|200px|thumb|उत्पादकता का उदाहरण [https://upload.wikimedia.org/wikipedia/commons/1/13/Productibilit%C3%A9.svg यहां क्लिक करें] </imagemap>
+[[File:Productibilité.svg|thumb|189x189px|उत्पादकता के उदाहरण [https://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Prod_reprod1.svg/800px-Prod_reprod1.svg.png (यहां क्लिक करें)]]]
+दूसरी ओर उत्पादक क्षमता को पुनरुत्पादन से परिभाषित किया जाता है। एक अनुक्रम S इसके उपसर्ग S(1,j) से उत्पन्न होता है यदि S(1,n−1) S(1,j) से पुनरुत्पादित होता है। इसे S(1,j)⇒S द्वारा निरूपित किया जाता है। अन्य प्रकार से कहा गया है कि S(j+1,n−1) को S(1,n-2) के दूसरे उप-शब्द की एक प्रति होना है। S का अंतिम प्रतीक एक नया प्रतीक हो सकता है। S का अंतिम प्रतीक एक नया प्रतीक हो सकता है, लेकिन संभवतः एक नए उप-शब्द के उत्पादन के लिए अग्रणी नहीं हो सकता है, इसलिए यह शब्द उत्पादकता है।
-दूसरी ओर, प्रजनन क्षमता को पुनरुत्पादन से परिभाषित किया जाता है: एक अनुक्रम S इसके उपसर्ग S(1,j) से उत्पन्न होता है यदि S(1,n−1) S(1,j) से पुनरुत्पादित होता है। इसे S(1,j)⇒S निरूपित किया जाता है। अलग तरीके से कहा गया है, S(j+1,n−1) को S(1,n-2) के दूसरे उप-शब्द की एक प्रति होना है। एस का अंतिम प्रतीक एक नया प्रतीक हो सकता है (लेकिन नहीं हो सकता), संभवतः एक नए उप-शब्द के उत्पादन के लिए अग्रणी (इसलिए शब्द उत्पादकता)।
+=== संपूर्ण इतिहास और सम्मिश्रता ===
+उत्पादकता की परिभाषा से रिक्त स्ट्रिंग Λ=S(1,0) ⇒ S(1,1) को पुनरावर्ती उत्पादन प्रक्रिया द्वारा चरण i के लिए S(1,hi) ⇒ S(1,hi+1) है, इसलिए हम इसके उपसर्गों से S का निर्माण कर सकते हैं। चूंकि S(1,i) ⇒ S(1,i+1) (hi+1 =hi + 1 के साथ) सदैव सत्य होता है। S की उत्पादन प्रक्रिया में अधिकतम n=l(S) चरण होते हैं। यह दो<math>1\leq {\text{m}}\leq l(S)</math> और S की इस उत्पाद प्रक्रिया के लिए आवश्यक चरणों की संख्या S को विघटित रूप में लिखा जा सकता है। जिसे S का इतिहास कहा जाता है और H(S) को निरूपित किया जाता है जिसे इस प्रकार परिभाषित किया गया है:
-<इमेजमैप>Image:Prod_reprod1.svg|200px|thumb|प्रजनन क्षमता और उत्पादन क्षमता के बीच तुलना [https://upload.wikimedia.org/wikipedia/commons/8/87/Prod_reprod1.svg यहां क्लिक करें] </imagemap>
+<math>H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_{{m-1}}+1,h_{m})</math>,<math>H_{i}(S)=S(h_{{i-1}}+1,h_{i}),i=1,2\dotsm m,
+{\text{where}  }\; h_{0}=0,h_{1}=1,h_{m}=l(S),{\text{ is called component of } H(S)}.
+</math>
-=== संपूर्ण इतिहास और जटिलता ===
+S को Hi(S) का एक घटक संपूर्ण माना जाता है यदि S(1,hi) S(1,hi−1) द्वारा निर्मित सबसे लंबा अनुक्रम है। अर्थात S(1,hi−1) ⇒ S( 1,hi)) इतना विस्तृत होता है कि S(1,hi−1) S(1,hi) का उत्पादन नहीं करता है:
-उत्पादकता की परिभाषा से, रिक्त स्ट्रिंग Λ=S(1,0) ⇒ S(1,1). तो एक पुनरावर्ती उत्पादन प्रक्रिया द्वारा, चरण i पर हमारे पास S(1,hi) ⇒ S(1,hi+1) है, इसलिए हम इसके उपसर्गों से S का निर्माण कर सकते हैं। और चूंकि S(1,i) ⇒ S(1,i+1) (hi+1 =hi + 1 के साथ) हमेशा सत्य होता है, S की उत्पादन प्रक्रिया में अधिकतम n=l(S) चरण होते हैं। मुझे यह करने दो, <math>1\leq {\text{m}}\leq l(S)</math>, S की इस उत्पाद प्रक्रिया के लिए आवश्यक चरणों की संख्या हो। S को विघटित रूप में लिखा जा सकता है, जिसे S का इतिहास कहा जाता है, और H(S) को निरूपित किया जाता है, जिसे इस प्रकार परिभाषित किया गया है:
-<math>H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_{{m-1}}+1,h_{m})</math>
+<math>S(1,h_{i}-1)\nrightarrow S(1,h_{i})</math>
-<math>H_{i}(S)=S(h_{{i-1}}+1,h_{i}),i=1,2\dotsm m,
-{\text{where}  }\; h_{0}=0,h_{1}=1,h_{m}=l(S),{\text{ is called component of } H(S)}.
-</math>
-<इमेजमैप>Image:Hist_exh&complexite1.svg|200px|thumb|प्रजनन क्षमता और उत्पादकता के बीच तुलना [https://upload.wikimedia.org/wikipedia/commons/3/3c/Hist_exh%26complexite1.svg यहां क्लिक करें] </imagemap>
-S, Hi(S) का एक घटक संपूर्ण माना जाता है यदि S(1,hi) S(1,hi−1) द्वारा निर्मित सबसे लंबा अनुक्रम है (अर्थात, S(1,hi−1) ⇒ S( 1,hi)) लेकिन इतना है कि S(1,hi−1) S(1,hi) (निरूपित) का उत्पादन नहीं करता है। <math>S(1,h_{i}-1)\nrightarrow S(1,h_{i})</math> इंडेक्स पी जो सबसे लंबे समय तक उत्पादन करने की अनुमति देता है उसे पॉइंटर कहा जाता है।
+सूचकांक p जो सबसे लंबे समय तक उत्पादन करने की स्वीकृति देता है उसे पॉइंटर कहा जाता है।
-एस के इतिहास को संपूर्ण कहा जाता है यदि इसके सभी घटक संपूर्ण हैं, संभवतः अंतिम को छोड़कर। परिभाषा से, कोई यह दिखा सकता है कि किसी भी अनुक्रम S का केवल एक संपूर्ण इतिहास है, और यह इतिहास S के सभी संभावित इतिहासों में से सबसे कम घटकों वाला इतिहास है। अंत में, S के इस अद्वितीय संपूर्ण इतिहास के घटक की संख्या एस की लेम्पेल-ज़िव जटिलता कहा जाता है।
+S के इतिहास को संपूर्ण कहा जाता है यदि इसके सभी घटक संभवतः अंतिम को छोड़कर संपूर्ण होते हैं। परिभाषा से यह प्रदर्शित किया जा सकता है कि किसी भी अनुक्रम S का केवल एक संपूर्ण इतिहास है और यह इतिहास S के सभी संभावित इतिहासों में से सबसे कम घटकों वाला इतिहास है। अंत में S के इस अद्वितीय संपूर्ण इतिहास के घटक की संख्या S को लेम्पेल-ज़िव सम्मिश्रता कहा जाता है।
 == एल्गोरिथम ==
-सौभाग्य से, ऑपरेशन की एक रैखिक संख्या में, इस जटिलता की गणना करने के लिए एक बहुत ही कुशल विधि मौजूद है (<math>\mathcal{O}(n)</math> के लिए <math>n=l(S)</math> अनुक्रम एस की लंबाई)।
+सामान्यतः अनुक्रम S की <math>n=l(S)</math> लंबाई के लिए संक्रियक की रैखिक संख्या <math>\mathcal{O}(n)</math> में इस सम्मिश्रता की गणना करने के लिए एक बहुत ही कुशल विधि सम्मिलित है।
-इस पद्धति का एक औपचारिक विवरण निम्नलिखित [[ कलन विधि ]] द्वारा दिया गया है:
+इस पद्धति का एक औपचारिक विवरण निम्नलिखित एल्गोरिथम द्वारा दिया गया है:
-* i = p − 1, p सूचक है (ऊपर देखें)
+* i = p − 1, p सूचक है। (ऊपर देखें)
-* यू वर्तमान उपसर्ग की लंबाई है
+* u वर्तमान उपसर्ग की लंबाई है।
-* वी वर्तमान सूचक पी के लिए वर्तमान घटक की लंबाई है
+* v वर्तमान सूचकांक p के लिए वर्तमान घटक की लंबाई है।
-* vmax वर्तमान घटक के लिए उपयोग की जाने वाली अंतिम लंबाई है (सभी संभावित पॉइंटर्स p पर सबसे बड़ी)
+* v<sub>max</sub> अंतिम लंबाई है जो वर्तमान घटक के लिए सभी संभावित पॉइंटर p पर सबसे बड़ी है।
-* और C लेम्पेल-ज़िव कॉम्प्लेक्सिटी है, जो पुनरावृत्त रूप से बढ़ा है।
+* C लेम्पेल-ज़िव सम्मिश्रता है जो पुनरुत्पादित रूप से अधिक है।
 <syntaxhighlight lang="pascal">
@@ Line 91: / Line 83: @@
 end if
 </syntaxhighlight>
 == यह भी देखें ==
-* [[LZ77 और LZ78]] - संपीड़न एल्गोरिदम जो मेल खाने वाले सबस्ट्रिंग्स को खोजने के समान विचार का उपयोग करते हैं।
+* [[LZ77 और LZ78|एलजेड-77 और एलजेड-78]] आंकड़ा संपीड़न एल्गोरिदम है, जो उप स्ट्रिंग खोजने के समान सूचकांक का उपयोग करते हैं।
 == नोट्स और संदर्भ ==
@@ Line 108: / Line 98: @@
 === आवेदन ===
-* [https://pudding.cool/2017/05/song-repetition/ «क्या पॉप लिरिक्स अधिक दोहराव वाले हो रहे हैं? », कॉलिन मॉरिस द्वारा], एक ब्लॉग पोस्ट है जिसमें बताया गया है कि गीत के बोलों की पुनरावृत्ति को मापने के लिए लेम्पेल-ज़िव जटिलता का उपयोग कैसे करें [https://colinmorris.github.io/pop-compression/ (उपलब्ध स्रोत कोड के साथ)]।
+* [https://pudding.cool/2017/05/song-repetition/ «क्या पॉप लिरिक्स अधिक दोहराव वाले हो रहे हैं? », कॉलिन मॉरिस द्वारा], एक ब्लॉग पोस्ट है जिसमें बताया गया है कि गीत के बोलों की पुनरावृत्ति को मापने के लिए लेम्पेल-ज़िव सम्मिश्रता का उपयोग कैसे करें [https://colinmorris.github.io/pop-compression/ (उपलब्ध स्रोत कोड के साथ)]।
-* बर्न्स एंड राजन (2015) ईईजी डेटा के जटिलता उपायों का संयोजन: गुणा करने वाले उपाय पहले छिपी हुई जानकारी को प्रकट करते हैं। F1000 अनुसंधान। 4:137. [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4648221/] (उपलब्ध सार्वजनिक MATLAB कोड के साथ)।
+* बर्न्स एंड राजन (2015) ईईजी डेटा के सम्मिश्रता उपायों का संयोजन: गुणा करने वाले उपाय पहले छिपी हुई जानकारी को प्रकट करते हैं। F1000 अनुसंधान। 4:137. [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4648221/] (उपलब्ध सार्वजनिक MATLAB कोड के साथ)।
 * बर्न्स एंड राजन (2019) मानव में उनकी व्यक्तिपरक धारणाओं के साथ गैर-भाषाई ध्वनियों के ऑब्जेक्टिव स्पेक्ट्रो-टेम्पोरल फीचर्स को सहसंबंधित करने के लिए एक गणितीय दृष्टिकोण। न्यूरोसाइंस में फ्रंटियर्स 13:794। [https://www.frontiersin.org/articles/10.3389/fnins.2019.00794/full] (उपलब्ध सार्वजनिक MATLAB कोड के साथ)।
@@ Line 116: / Line 106: @@
 * [https://GitHub.com/Naereen/Lempel-Ziv_Complexity Open-Source (MIT) implementation on Python and Cython on GitHub] [https://pypi.org/project/Lempel-Ziv_Complexity/ available on PyPi]
-{{DEFAULTSORT:Lempel-Ziv complexity}}[[Category: संगणनीयता सिद्धांत]] [[Category: सूचना सिद्धांत]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]]
+{{DEFAULTSORT:Lempel-Ziv complexity}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 19/05/2023|Lempel-Ziv complexity]]
-[[Category:Created On 19/05/2023]]
+[[Category:Machine Translated Page|Lempel-Ziv complexity]]
+[[Category:Pages with script errors|Lempel-Ziv complexity]]
+[[Category:Templates Vigyan Ready]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत|Lempel-Ziv complexity]]
+[[Category:संगणनीयता सिद्धांत|Lempel-Ziv complexity]]
+[[Category:सूचना सिद्धांत|Lempel-Ziv complexity]]

Anonymous

Search

लेम्पेल-ज़िव सम्मिश्रता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 13:37, 29 August 2023

Contents

सिद्धांत

औपचारिक स्पष्टीकरण