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

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

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

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

सिद्धांत

माना कि 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 का निश्चित उपसर्ग कहा जाता है यदि $\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) के दूसरे उप-शब्द की एक प्रति होना है। एस का अंतिम प्रतीक एक नया प्रतीक हो सकता है (लेकिन नहीं हो सकता), संभवतः एक नए उप-शब्द के उत्पादन के लिए अग्रणी (इसलिए शब्द उत्पादकता)।

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

उत्पादकता की परिभाषा से, रिक्त स्ट्रिंग Λ=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 के इस अद्वितीय संपूर्ण इतिहास के घटक की संख्या एस की लेम्पेल-ज़िव सम्मिश्रता कहा जाता है।

एल्गोरिथम

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

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

• 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

यह भी देखें

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

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

ग्रन्थसूची

• 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