Loading article…
レンペル・ジブ複雑度は、イスラエルのコンピュータ科学者であるアブラハム・レンペルとヤコブ・ジブの2人が論文「有限シーケンスの複雑性について」 （IEEE Trans. On IT-22,1 1976）で初めて発表した尺度です。この複雑度尺度はコルモゴロフ複雑度と関連していますが、使用する関数は再帰的コピー（つまり、浅いコピー）のみです。
この複雑度尺度の根底にあるメカニズムは、LZ77、LZ78、LZWなどの可逆データ圧縮アルゴリズムの出発点となっています。単語コピーという基本的な原理に基づいているにもかかわらず、この複雑度尺度は、そのような尺度に期待される主要な特性を満たしているという意味で、過度に制約的ではありません。つまり、一定の規則性を持つシーケンスは複雑度が大きくなりすぎず、シーケンスの長さと不規則性が増すにつれて複雑度も大きくなります。
レンペル・ジブ複雑度は、歌の歌詞や散文などのバイナリシーケンスやテキストの反復性を測定するために使用できます。実世界のデータのフラクタル次元推定値も、レンペル・ジブ複雑度と相関することが示されています。[ 1 ] [ 2 ]
S を長さ n のバイナリ シーケンスとし、そのレンペル・ジブ複雑度 C(S) を計算する。シーケンスは左から読み取る。
計算中にシーケンス内で移動できる区切り線があると想像してください。最初は、この線はシーケンスの先頭、最初の記号の直後に設定されます。この初期位置を位置 1 と呼び、そこから位置 2 に移動する必要があります。位置 2 は次のステップの初期位置とみなされます (以下同様)。位置 1 から始まる区切り線を可能な限り右に移動して、位置 1 と区切り線の位置の間のサブワードが、区切り線の位置 1 より前に始まるシーケンスのワードになるようにする必要があります。
区切り文字がこの条件を満たさない位置に設定されたら、処理を停止し、区切り文字をその位置に移動させ、その位置を新しい初期位置（つまり位置 1）としてマークして処理を再開します。シーケンスの最後まで繰り返します。レンペル・ジブ複雑度は、この手順を完了するために必要な反復回数に対応します。
言い換えれば、レンペル・ジブ複雑度とは、バイナリシーケンスを（左から右へ）ストリームとして見た場合、遭遇する異なる部分文字列（または部分単語）の数のことである。
レンペルとジブが提案した方法は、ここで定義した3つの概念、すなわち、再現性、生成可能性、およびシーケンスの網羅的な履歴を使用します。
S を長さ n のバイナリ シーケンスとする (つまり、値0または1を取る記号)、 と、のサブワードであるインデックス i からインデックス j へ (もしは空文字列です。S の長さ n は次のように表されます。、そしてシーケンス固定の接頭辞であると言われているもし：
一方、長さ n のシーケンス S は、S(j+1,n) が S(1,j) の部分語である場合に、その接頭辞 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) のいずれかによって再現できることを証明するには、次のことを示す必要があります。
一方、生成可能性は再現可能性から定義されます。シーケンス 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(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) ステップかかります。m とします。は、S のこの製品プロセスに必要なステップ数とする。S は、S の履歴と呼ばれる分解形式で記述でき、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をポインタと呼ぶ。
S の履歴は、最後の要素を除いてすべての要素が網羅的である場合に、網羅的であると言われます。定義から、任意のシーケンス S には網羅的な履歴がただ 1 つだけ存在し、この履歴は S の可能なすべての履歴の中で要素の数が最小であることがわかります。最後に、S のこの唯一の網羅的な履歴の要素の数を S の Lempel–Ziv 複雑度と呼びます。
幸いなことに、この複雑さを計算する非常に効率的な方法があり、線形回数の演算で計算できます（のために配列Sの長さ）。
この手法の正式な説明は、以下のアルゴリズムによって示される。
// 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