लेम्पेल-ज़िव सम्मिश्रता

लेम्पेल-ज़िव जटिलता एक उपाय है जिसे पहली बार दो इज़राइली कंप्यूटर वैज्ञानिकों, अब्राहम लेम्पेल और जैकब ज़िव द्वारा 'ऑन द कॉम्प्लेक्सिटी ऑफ़ फ़ाइनाइट सीक्वेंस' (IEEE Trans. On IT-22,1 1976) लेख में प्रस्तुत किया गया था। यह जटिलता माप कोल्मोगोरोव जटिलता से संबंधित है, लेकिन इसका उपयोग करने वाला एकमात्र कार्य पुनरावर्ती प्रति (यानी, उथली प्रतिलिपि) है।

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

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

सिद्धांत

चलो S एक द्विआधारी अनुक्रम है, जिसकी लंबाई n है, जिसके लिए हमें Lempel-Ziv जटिलता की गणना करनी है, जिसे 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 का निश्चित उपसर्ग कहा जाता है यदि:

$\exists j<{\text{l(S), s.t. S(1,j) = Q .}}$

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

<इमेजमैप>Image:Reproductibilité1.svg|200px|thumb|प्रतिलिपि प्रस्तुत करने योग्यता का उदाहरण यहां क्लिक करें </imagemap>

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

अलग ढंग से कहा गया है, एस अपने उपसर्ग एस (1, जे) से पुनरुत्पादित है यदि शेष अनुक्रम, एस (जे + 1, एन), और कुछ नहीं है, लेकिन एक अन्य उप-शब्द की प्रतिलिपि है (एक सूचकांक i < j + से शुरू) 1) एस(1,एन−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)$ <इमेजमैप>Image:Productibilité.svg|200px|thumb|उत्पादकता का उदाहरण यहां क्लिक करें </imagemap>

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

<इमेजमैप>Image:Prod_reprod1.svg|200px|thumb|प्रजनन क्षमता और उत्पादन क्षमता के बीच तुलना यहां क्लिक करें </imagemap>

संपूर्ण इतिहास और जटिलता

उत्पादकता की परिभाषा से, रिक्त स्ट्रिंग Λ=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)}.$ <इमेजमैप>Image:Hist_exh&complexite1.svg|200px|thumb|प्रजनन क्षमता और उत्पादकता के बीच तुलना यहां क्लिक करें </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) (निरूपित) का उत्पादन नहीं करता है। $S(1,h_{i}-1)\nrightarrow S(1,h_{i})$ इंडेक्स पी जो सबसे लंबे समय तक उत्पादन करने की अनुमति देता है उसे पॉइंटर कहा जाता है।

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

एल्गोरिथम

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

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

• i = p − 1, p सूचक है (ऊपर देखें)
• यू वर्तमान उपसर्ग की लंबाई है
• वी वर्तमान सूचक पी के लिए वर्तमान घटक की लंबाई है
• vmax वर्तमान घटक के लिए उपयोग की जाने वाली अंतिम लंबाई है (सभी संभावित पॉइंटर्स 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

यह भी देखें

• LZ77 और LZ78 - संपीड़न एल्गोरिदम जो मेल खाने वाले सबस्ट्रिंग्स को खोजने के समान विचार का उपयोग करते हैं।

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

ग्रन्थसूची

• 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 कोड के साथ)।

बाहरी संबंध

• Example of a Python implementation and discussion on StackOverflow #41336798
• Open-Source (MIT) implementation on Python and Cython on GitHub available on PyPi