レンペル・ジヴ複雑性

Lempel -Ziv 複雑度は、イスラエルの 2 人のコンピュータ科学者、Abraham LempelとJacob Zivによって論文「On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976)」で初めて提示された尺度です。この複雑度尺度はKolmogorov 複雑度に関連していますが、使用される唯一の関数は再帰コピー (つまり、浅いコピー) です。

この複雑性尺度の根底にあるメカニズムは、 LZ77、LZ78、LZWなどのロスレス データ圧縮アルゴリズムの出発点となっています。この複雑性尺度は、単語のコピーという基本原理に基づいていますが、このような尺度に期待される主な品質を満たすという意味で、それほど制限的ではありません。つまり、一定の規則性を持つシーケンスは複雑性が大きすぎることはなく、シーケンスの長さと不規則性が増すにつれて複雑性も大きくなります。

レンペル・ジヴ複雑度は、歌詞や散文などのバイナリシーケンスやテキストの反復性を測定するために使用できます。現実世界のデータのフラクタル次元の推定も、レンペル・ジヴ複雑度と相関することが示されています。^{[1] [2]}

S を長さ n のバイナリ シーケンスとし、これに対して Lempel-Ziv 複雑度 (C(S) と表記) を計算する必要があります。シーケンスは左から読み取られます。

計算中にシーケンス内で移動できる区切り線があるとします。最初、この線はシーケンスの先頭にある最初のシンボルの直後に設定されます。この初期位置は位置 1 と呼ばれ、ここから位置 2 に移動する必要があります。位置 2 は次のステップの初期位置と見なされます (以下同様)。区切り文字 (位置 1 から開始) を可能な限り右に移動して、位置 1 と区切り文字位置の間のサブワードが、区切り文字の位置 1 より前に始まるシーケンスのワードになるようにする必要があります。

区切り文字がこの条件を満たさない位置に設定されるとすぐに停止し、区切り文字をこの位置に移動し、この位置を新しい初期位置 (つまり、位置 1) としてマークして再度開始します。シーケンスの最後まで繰り返します。Lempel-Ziv 複雑度は、この手順を完了するために必要な反復回数に対応します。

言い換えると、Lempel-Ziv 複雑度は、バイナリ シーケンスをストリーム (左から右へ) として見た場合に遭遇する異なるサブ文字列 (またはサブワード) の数です。

Lempel と Ziv によって提案された方法では、再現性、生成可能性、およびシーケンスの網羅的な履歴という 3 つの概念が使用されます。これらをここで定義します。

S を長さ n のバイナリ シーケンス (つまり、 0 または 1 の値を取るシンボル)とします。 、 をインデックス i からインデックス j までの のサブワードとします(は空の文字列の場合)。 S の長さ n は で表され、シーケンスは次の場合の固定プレフィックスであると言われます。 ${\displaystyle n}$${\displaystyle S(i,j)}$${\displaystyle 1\leq i,j\leq n}$${\displaystyle S}$${\displaystyle j<i,S(i,j)}$${\displaystyle l(S)}$${\displaystyle Q}$${\displaystyle S}$

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

一方、長さ n のシーケンス S は、S(j+1,n) が S(1,j) の部分語であるとき、そのプレフィックス S(1,j) から再現可能であると言われます。これは、S(1,j)→S と表されます。

言い換えれば、シーケンスの残りの部分S(j+1,n)がS(1,n−1)の別のサブワード（インデックスi < j+1から始まる）のコピーにすぎない場合、SはそのプレフィックスS(1,j)から再現可能です。

シーケンス S がそのプレフィックス S(1,j) の 1 つによって再現できることを証明するには、次のことを示す必要があります。

${\displaystyle \exists p\leq j,{\text{ st }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)}$

一方、生成可能性は、再現可能性から定義されます。シーケンス S は、S(1,n−1) が S(1,j) から生成可能である場合、そのプレフィックス S(1,j) から生成可能です。これは、S(1,j)⇒S と表されます。言い換えると、S(j+1,n−1) は S(1,n-2) の別のサブワードのコピーである必要があります。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) ステップかかります。S のこの生成プロセスに必要なステップ数を m, とします。S は、S の履歴と呼ばれる分解形式で記述でき、H(S) と表記され、次のように定義されます。 ${\displaystyle 1\leq {\text{m}}\leq l(S)}$

${\displaystyle H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_{m-1}+1,h_{m})}$ ${\displaystyle 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{ は }}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)を生成しない（と表記）場合、網羅的であると言われる。最長の生成を可能にするインデックスpはポインタと呼ばれる。 ${\displaystyle S(1,h_{i}-1)\nrightarrow S(1,h_{i})}$

S の履歴は、最後の 1 つを除いてすべてのコンポーネントが網羅的である場合に網羅的であると言われます。定義から、任意のシーケンス S には網羅的な履歴が 1 つだけあり、この履歴は S のすべての可能な履歴のうちコンポーネントの数が最も少ない履歴であることがわかります。最後に、S のこの唯一の網羅的な履歴のコンポーネントの数は、S の Lempel-Ziv 複雑性と呼ばれます。

幸いなことに、この複雑さを線形回数（シーケンス S の長さ に対して）の演算で計算する非常に効率的な方法が存在します。${\displaystyle {\mathcal {O}}(n)}$${\displaystyle n=l(S)}$

この方法の正式な説明は、次のアルゴリズムによって与えられます。

• i = p − 1、pはポインタ（上記参照）
• uは現在のプレフィックスの長さです
• vは現在のポインタpの現在のコンポーネントの長さです。
• vmaxは、現在のコンポーネントに使用される最終的な長さです（すべての可能なポインタpの中で最大）
• C は Lempel-Ziv 複雑度であり、反復的に増加します。

// S はサイズ 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 // すべてのポインターが処理されました。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 – 一致する部分文字列を見つけるという同様の考え方を使用する圧縮アルゴリズム。

• アブラハム・レンペルとヤコブ・ジヴ、「有限シーケンスの複雑さについて」、IEEE Trans. on Information Theory、1976年1月、p. 75–81、vol. 22、n°1

• Colin Morris による「ポップソングの歌詞はより反復的になっているか?」は、Lempel–Ziv 複雑度を使用して歌詞の反復性を測定する方法を説明したブログ投稿です (ソース コードも利用可能)。
• Burns & Rajan (2015) EEGデータの複雑性指標の組み合わせ：指標を掛け合わせると、これまで隠れていた情報が明らかになる。F1000Research. 4:137. [1] (公開MATLABコードあり)。
• Burns & Rajan (2019)「非言語音の客観的なスペクトル時間的特徴と人間の主観的知覚との相関関係を数学的に調べるアプローチ」Frontiers in Neuroscience 13:794. [2] (公開MATLABコードあり)

• Python 実装の例と StackOverflow での議論 #41336798
• GitHub 上の Python および Cython のオープンソース (MIT) 実装が PyPi で利用可能