LCPアレイ

LCPアレイ
タイプ	配列
発明者	マンバー＆マイヤーズ（1993）
ビッグ O 記法による時間計算量と空間計算量
平均 最悪の場合 空間 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ 工事 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

コンピュータサイエンスにおいて、最長共通プレフィックス配列( LCP配列) は、サフィックス配列の補助的なデータ構造です。これは、ソートされたサフィックス配列内の連続するサフィックスのすべてのペア間の最長共通プレフィックス (LCP) の長さを格納します。

例えば、A  := [アブ、アブ、アバブ、b、バーブ]は接尾辞配列であり、 A [1] =間の最長共通接頭辞である。アブそしてA [2] =アブは1つの長さが1なので、LCP配列HではH [2] = 1となる。同様に、 A [2]のLCPは=アブそしてA [3] =アバブはアブしたがってH [3] = 2となる。

サフィックス配列をLCP配列で拡張すると、サフィックスツリーのトップダウンとボトムアップのトラバーサルを効率的にシミュレートできるようになり、^{[1] [2]}サフィックス配列上のパターンマッチングが高速化され、 ^[3]圧縮サフィックスツリーの前提条件となります。^[4]

LCP配列は、1993年にUdi ManberとGene Myersによってサフィックス配列とともに導入され、文字列検索アルゴリズムの実行時間を改善しました。^[3]

を長さ の文字列の接尾辞配列とします。ここで は一意で、辞書式に他のどの文字よりも小さいセンチネル文字です。からの範囲のの部分文字列を とします。したがって、 はの 番目の最小の接尾辞です。 ${\displaystyle A}$${\displaystyle S=s_{1},s_{2},\ldots s_{n-1}\$}$${\displaystyle n}$${\displaystyle \$}$${\displaystyle S[i,j]}$${\displaystyle S}$${\displaystyle i}$${\displaystyle j}$${\displaystyle S[A[i],n]}$${\displaystyle i}$${\displaystyle S}$

2 つの文字列との間の最長共通プレフィックスの長さを とします。この場合、LCP 配列は、が未定義で、任意の に対して となるサイズの整数配列です。したがって、辞書式で 番目の最小のサフィックスとその前のサフィックスの最長共通プレフィックスの長さがサフィックス配列に格納されます。 ${\displaystyle \operatorname {lcp} (v,w)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle H[1,n]}$${\displaystyle n}$${\displaystyle H[1]}$${\displaystyle H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])}$${\displaystyle 1<i\leq n}$${\displaystyle H[i]}$${\displaystyle i}$

LCP 配列とサフィックス配列の違い:

• 接尾辞配列: 配列の各接尾辞の辞書編集上のランクを表します。
• LCP 配列: 辞書順に並べ替えられた後、連続する 2 つのサフィックス間のプレフィックス マッチの最大長が含まれます。

次の文字列を考えてみましょう: ${\displaystyle S={\textrm {バナナ\$}}}$

およびそれに対応するソートされた接尾辞配列 : ${\displaystyle A}$

接尾辞が下に縦に書き出された接尾辞配列:

次に、辞書式に連続するサフィックスを比較して、最長共通プレフィックスを決定することによって、 LCP 配列が構築されます。${\displaystyle H}$

たとえば、 は、接尾辞 と が共有する最長の共通接頭辞の長さです。辞書式にこれより小さい接尾辞がないため、 は未定義であることに注意してください。 ${\displaystyle H[4]=3}$${\displaystyle {\text{ana}}}$${\displaystyle A[3]=S[4,7]={\textrm {ana\$}}}$${\displaystyle A[4]=S[2,7]={\textrm {アナナ\$}}}$${\displaystyle H[1]}$

LCP 配列構築アルゴリズムは、サフィックス配列の副産物として LCP 配列を計算するアルゴリズムと、既に構築されたサフィックス配列を使用して LCP 値を計算するアルゴリズムの 2 つのカテゴリに分けられます。

Manber と Myers (1993) は、時間内にサフィックス配列と並行して LCP 配列を計算するアルゴリズムを提供しています。Kärkkäinen と Sanders (2003) は、時間アルゴリズムを変更して LCP 配列も計算できることを示しています。Kasai ら (2001) は、テキストとサフィックス配列が与えられた場合に LCP 配列を計算する最初の時間アルゴリズム (FLAAP) を提示しています。 ${\displaystyle O(n\log n)}$${\displaystyle O(n)}$${\displaystyle O(n)}$

各テキスト シンボルが 1 バイトを占め、サフィックスまたは LCP 配列の各エントリが 4 バイトを占めると仮定すると、このアルゴリズムの主な欠点は、元の出力 (テキスト、サフィックス配列、LCP 配列) がバイトしか占めないのに対し、バイトの占有領域が大きいことです。そのため、Manzini (2004) は Kasai ら (2001) のアルゴリズムの改良版 (lcp9) を作成し、占有領域をバイトにまで削減しました。Kärkkäinen、Manzini、Puglisi (2009) は、実行時間を改善する Kasai のアルゴリズムの別の改良版 ( -アルゴリズム) を提供しています。このアルゴリズムは、実際の LCP 配列ではなく、値が辞書順ではなくテキスト順に表示される 並べ替えられたLCP (PLCP) 配列を構築します。${\displaystyle 13n}$${\displaystyle 9n}$${\displaystyle 9n}$${\displaystyle \Phi}$

Gog & Ohlebusch (2011) は、理論的には遅い ( ) ものの、実際には上記のアルゴリズムよりも高速な 2 つのアルゴリズムを提供しています。${\displaystyle O(n^{2})}$

2012 年現在^{[アップデート]}、最も高速な線形時間 LCP 配列構築アルゴリズムは Fischer (2011) によるもので、これは Nong、Zhang、Chan (2009) による最高速のサフィックス配列構築アルゴリズムの 1 つ (SA-IS) に基づいています。Yuta Mori の DivSufSort に基づく Fischer & Kurpicz (2017) はさらに高速です。

Abouelhoda、Kurtz、Ohlebusch (2004) が指摘しているように、いくつかの文字列処理問題は、次の種類のツリー トラバーサルによって解決できます。

• 完全な接尾辞ツリーのボトムアップ走査
• 接尾辞ツリーのサブツリーのトップダウン走査
• サフィックス リンクを使用したサフィックス ツリーのトラバーサル。

Kasai et al. (2001) は、サフィックス配列と LCP 配列のみを使用して、サフィックス ツリーのボトムアップ トラバーサルをシミュレートする方法を示しています。Abouelhoda、Kurtz、Ohlebusch (2004) は、LCP 配列と追加のデータ構造を使用してサフィックス配列を拡張し、この拡張サフィックス配列を使用して3 種類のサフィックス ツリー トラバーサルをすべてシミュレートする方法を説明しています。Fischer と Heun (2007) は、範囲最小クエリ用に LCP 配列を前処理することで、拡張サフィックス配列のスペース要件を削減しました。したがって、 サフィックス ツリー アルゴリズムで解決できるすべての問題は、拡張サフィックス配列を使用しても解決できます。^[2]

長さのパターンが長さの文字列の部分文字列であるかどうかを判断するには、サフィックス配列のみを使用すると時間がかかります。LCP情報を追加で使用すれば、この制限を100分に短縮できます。^[3] Abouelhoda、Kurtz、Ohlebusch (2004) は、この実行時間をさらに短縮して最適な時間を達成する方法を示しています。つまり、サフィックス配列とLCP配列情報を使用すると、サフィックスツリーを使用する場合と同じくらい速く決定クエリに回答できます。 ${\displaystyle P}$${\displaystyle m}$${\displaystyle S}$${\displaystyle n}$${\displaystyle O(m\log n)}$${\displaystyle O(m+\log n)}$${\displaystyle O(m)}$

LCP配列は、サフィックスリンクや最小共通祖先クエリなどの完全なサフィックスツリー機能を提供する圧縮サフィックスツリーの重要な部分でもあります。 ^{[5] [6]}さらに、サフィックス配列と一緒に使用して、Lempel-Ziv LZ77分解を時間内に計算することもできます。^{[2] [7] [8] [9]}${\displaystyle O(n)}$

長さの文字列の最長繰り返し部分文字列問題は、サフィックス配列と LCP 配列の両方を使用して時間内に解決できます。LCP 配列の最大値と、 が格納されている対応するインデックスを見つけるには、LCP 配列を線形スキャンするだけで十分です。少なくとも 2 回出現する最長の部分文字列は、 によって与えられます。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle \Theta (n)}$${\displaystyle A}$${\displaystyle v_{max}}$${\displaystyle i}$${\displaystyle v_{max}}$${\displaystyle S[A[i],A[i]+v_{max}-1]}$

このセクションの残りの部分では、LCP 配列の 2 つのアプリケーションについて詳しく説明します。文字列のサフィックス配列と LCP 配列を使用して、対応するサフィックス ツリーを構築する方法と、LCP 配列の範囲最小クエリを使用して任意のサフィックスの LCP クエリに応答する方法です。

与えられた文字列（長さ）がテキスト（長さ）内で何回出現するかを調べるには、 ^[3]${\displaystyle P}$${\displaystyle m}$${\displaystyle T}$${\displaystyle N}$

• のすべての出現の開始位置と終了位置を見つけるために、の接尾辞配列に対してバイナリ検索を使用します。${\displaystyle T}$${\displaystyle P}$
• ここで、検索を高速化するために、LCP アレイ、具体的には LCP アレイの特別なバージョン (以下、LCP-LR) を使用します。

標準的なバイナリ検索 (LCP 情報なし) を使用する場合の問題は、必要な比較のそれぞれで、P をサフィックス配列の現在のエントリと比較することです。これは、最大 m 文字の完全な文字列比較を意味します。したがって、複雑さは です。 ${\displaystyle O(\log N)}$${\displaystyle O(m\log N)}$

LCP-LR アレイは、次のようにしてこれを に改善するのに役立ちます。 ${\displaystyle O(m+\log N)}$

バイナリ検索アルゴリズムの実行中は、いつでも、通常どおり、接尾辞配列の範囲とその中心点を考慮し、左のサブ範囲 で検索を続けるか、右のサブ範囲 で検索を続けるかを決定します。決定を下すには、の文字列 と比較します。 がと同一である場合、検索は完了です。 しかし、同一でない場合は、 の最初の文字を既に比較しており、 が辞書式で より小さいか大きいかを判断しています。 がより大きいという結果になったと仮定しましょう。そこで、次のステップでは、と中央の 新しい中心点を考慮します。${\displaystyle (L,\dots ,R)}$${\displaystyle M}$${\displaystyle (L,\dots ,M)}$${\displaystyle (M,\dots ,R)}$${\displaystyle P}$${\displaystyle M}$${\displaystyle P}$${\displaystyle M}$${\displaystyle k}$${\displaystyle P}$${\displaystyle P}$${\displaystyle M}$${\displaystyle P}$${\displaystyle M}$${\displaystyle (M,\dots ,R)}$${\displaystyle M'}$

             マ……マ'……R
             |
      私たちは知っています：
         lcp(P,M)==k

ここでの秘訣は、LCP-LR が事前に計算されており、-lookup によっておよびの最長共通プレフィックスがわかるという点です。${\displaystyle O(1)}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle \mathrm {lcp} (M,M')}$

すでに（前のステップから） :自体に共通の文字の接頭辞があることがわかっています。この場合、次の 3 つの可能性があります。 ${\displaystyle M}$${\displaystyle k}$${\displaystyle P}$${\displaystyle \mathrm {lcp} (P,M)=k}$

• ケース 1:つまり、M と共通する接頭辞文字の数は、M と M' と共通する接頭辞文字の数より少ない。つまり、M' の (k+1) 番目の文字は M の文字と同じであり、P は辞書式で M よりも大きいため、辞書式で M' よりも大きい必要がある。そこで、右半分 (M',...,R) を続行する。${\displaystyle k<\mathrm {lcp} (M,M')}$${\displaystyle P}$
• ケース 2:つまり、 はと共通するプレフィックス文字が と共通するプレフィックス文字よりも多いということです。したがって、と比較すると、共通プレフィックスは より小さくなり、 はより辞書式に大きくなるため、実際に比較せずに、左半分で比較を続けます。${\displaystyle k>\mathrm {lcp} (M,M')}$${\displaystyle P}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle P}$${\displaystyle M'}$${\displaystyle k}$${\displaystyle M'}$${\displaystyle P}$${\displaystyle (M,\dots ,M')}$
• ケース 3:したがって、最初の文字ではM と M' は両方とも と同一です。左半分を続けるか右半分を続けるかを決定するには、番目の文字から始めてと比較するだけで十分です。${\displaystyle k=\mathrm {lcp} (M,M')}$${\displaystyle P}$${\displaystyle k}$${\displaystyle P}$${\displaystyle M'}$${\displaystyle (k+1)}$
• 再帰的に続けます。

全体的な効果としては、 のどの文字もテキストのどの文字とも複数回比較されないことです（詳細については^[3]を参照）。文字比較の総数は に制限されるため、全体の複雑さは です。 ${\displaystyle P}$${\displaystyle m}$${\displaystyle O(m+\log N)}$

LCP-LR を事前計算して、サフィックス配列の任意の 2 つのエントリ間の lcp を時間内に通知できるようにする必要があります。標準の LCP 配列では、任意の に対して、連続するエントリの lcp のみが得られることがわかっています。ただし、上記の説明のと は、必ずしも連続するエントリであるとは限りません。 ${\displaystyle O(1)}$${\displaystyle \mathrm {lcp} (i-1,i)}$${\displaystyle i}$${\displaystyle M}$${\displaystyle M'}$

ここで重要なのは、バイナリ検索中に特定の範囲のみが発生することを認識することです。バイナリ検索は常に から始まり、それを中央で分割し、次に左または右に進み、その半分をもう一度分割するなどします。別の見方をすると、サフィックス配列の各エントリは、バイナリ検索中に正確に 1 つの可能な範囲の中心点として発生します。したがって、バイナリ検索中に役割を果たす可能性のある範囲は正確に N 個あり、それらの可能な範囲に対してと を事前に計算すれば十分です。したがって、これらは個別の事前計算値であり、したがって LCP-LR はサイズになります。 ${\displaystyle (L,\dots ,R)}$${\displaystyle (0,\dots ,N)}$${\displaystyle (L\dots M\dots R)}$${\displaystyle \mathrm {lcp} (L,M)}$${\displaystyle \mathrm {lcp} (M,R)}$${\displaystyle N}$${\displaystyle 2N}$${\displaystyle O(N)}$

さらに、標準 LCP 配列から時間 内の LCP-LR の値を計算する簡単な再帰アルゴリズムがあります。${\displaystyle 2N}$${\displaystyle O(N)}$

総括する：

• LCP から時間と空間における LCP-LR を計算することが可能です。${\displaystyle O(N)}$${\displaystyle O(2N)=O(N)}$
• バイナリ検索中に LCP-LR を使用すると、から までの検索手順が高速化されます。${\displaystyle O(M\log N)}$${\displaystyle O(M+\log N)}$
• 2 つのバイナリ検索を使用して、 の一致範囲の左端と右端を決定できます。一致範囲の長さは、 P の出現回数に対応します。${\displaystyle P}$

長さ の文字列の接尾辞配列と LCP 配列が与えられている場合、次のアイデアに基づいて、その接尾辞ツリーを時間内に構築できます。辞書式に最小の接尾辞の部分接尾辞ツリーから始めて、接尾辞配列で指定された順序で他の接尾辞を繰り返し挿入します。 ${\displaystyle A}$${\displaystyle H}$${\displaystyle S=s_{1},s_{2},\ldots s_{n}\$}$${\displaystyle n+1}$${\displaystyle ST}$${\displaystyle O(n)}$

の部分サフィックスツリーを とします。さらに、のルートからノード までのすべてのパスラベルの連結の長さを とします。 ${\displaystyle ST_{i}}$${\displaystyle 0\leq i\leq n}$${\displaystyle d(v)}$${\displaystyle ST_{i}}$${\displaystyle v}$

ルートのみで構成されるツリー から開始します。に挿入するには、最近挿入されたリーフからルートまでの右端のパスをたどり、の最も深いノードに到達するまで進みます。 ${\displaystyle ST_{0}}$${\displaystyle A[i+1]}$${\displaystyle ST_{i}}$${\displaystyle A[i]}$${\displaystyle v}$${\displaystyle d(v)\leq H[i+1]}$

次の 2 つのケースを区別する必要があります。

• ${\displaystyle d(v)=H[i+1]}$: これは、ルートからパスへのラベルの連結が、サフィックスとの最長共通プレフィックスに等しいことを意味します。この場合、 をノードの新しいリーフとして挿入し、エッジにのラベルを付けます。 したがって、エッジ ラベルは、ルートからパスへのラベルの連結でまだ表されていないサフィックスの残りの文字で構成されます。これにより、部分サフィックス ツリーが作成されます。${\displaystyle v}$${\displaystyle A[i]}$${\displaystyle A[i+1]}$
  ${\displaystyle A[i+1]}$${\displaystyle x}$${\displaystyle v}$${\displaystyle (v,x)}$${\displaystyle S[A[i+1]+H[i+1],n]}$${\displaystyle A[i+1]}$${\displaystyle v}$
  ${\displaystyle ST_{i+1}}$

  

• ${\displaystyle d(v)<H[i+1]}$: これは、ルートからパスへのラベルの連結では、サフィックスとの最長共通プレフィックスよりも少ない文字が表示され、不足している文字はの右端のエッジ ラベルに含まれていることを意味します。したがって、そのエッジを次のように分割する必要があります 。の右端のパスの の子をとします。${\displaystyle v}$${\displaystyle A[i]}$${\displaystyle A[i+1]}$${\displaystyle v}$
  ${\displaystyle w}$${\displaystyle v}$${\displaystyle ST_{i}}$

1. エッジを削除します。${\displaystyle (v,w)}$
2. 新しい内部ノードとラベル の新しいエッジを追加します。新しいラベルは、 と の最長共通プレフィックスの欠落している文字で構成されます。したがって、ルートからパスへのラベルの連結には、との最長共通プレフィックスが表示されるようになります。${\displaystyle y}$${\displaystyle (v,y)}$${\displaystyle S[A[i]+d(v),A[i]+H[i+1]-1]}$${\displaystyle A[i]}$${\displaystyle A[i+1]}$${\displaystyle y}$${\displaystyle A[i]}$${\displaystyle A[i+1]}$
3. 新しく作成された内部ノードに、というラベルの付いたエッジで接続します。新しいラベルは、削除されたエッジのうち、エッジ のラベルとして使用されなかった残りの文字で構成されます。${\displaystyle w}$${\displaystyle y}$${\displaystyle (y,w)}$${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$${\displaystyle (v,w)}$${\displaystyle (v,y)}$
4. を新しいリーフとして追加し、というラベルの付いたエッジで新しい内部ノードに接続します。したがって、エッジ ラベルは、ルートからパスへのラベルの連結によってまだ表されていないサフィックスの残りの文字で構成されます。${\displaystyle A[i+1]}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (y,x)}$${\displaystyle S[A[i+1]+H[i+1],n]}$${\displaystyle A[i+1]}$${\displaystyle v}$
5. これにより、部分的なサフィックス ツリーが作成されます。${\displaystyle ST_{i+1}}$

単純な償却の議論により、このアルゴリズムの実行時間は次のように制限されることがわかります。 ${\displaystyle O(n)}$

の右端のパスをたどってステップ で走査されるノード(最後のノードを除く)は、 が新しいリーフとしてツリーに追加されたときに、右端のパスから削除されます。これらのノードは、後続のすべてのステップで再び走査されることはありません。したがって、合計で最大で 個のノードが走査されることになります。 ${\displaystyle i}$${\displaystyle ST_{i}}$${\displaystyle v}$${\displaystyle A[i+1]}$${\displaystyle j>i}$${\displaystyle 2n}$

LCP 配列には、サフィックス配列 内の連続するサフィックスの各ペアの最長共通プレフィックスの長さのみが含まれます。ただし、逆サフィックス配列( 、つまり内の位置で始まるサフィックスは内の位置に格納されます) と に対する定数時間範囲最小クエリを使用すると、任意のサフィックスの最長共通プレフィックスの長さを時間内で決定できます。 ${\displaystyle H}$${\displaystyle A}$${\displaystyle A^{-1}}$${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$${\displaystyle S[j,n]}$${\displaystyle j}$${\displaystyle S}$${\displaystyle A^{-1}[j]}$${\displaystyle A}$${\displaystyle H}$${\displaystyle O(1)}$

サフィックス配列の辞書式順序のため、サフィックス と のすべての共通プレフィックスは、サフィックス配列 の の位置とサフィックス配列 の の位置の間にあるすべてのサフィックスの共通プレフィックスである必要があります。したがって、これらすべてのサフィックスで共有される最長プレフィックスの長さは、間隔 の最小値です。 が範囲最小クエリに対して前処理されている場合、この値は定数時間で見つけることができます。 ${\displaystyle S[i,n]}$${\displaystyle S[j,n]}$${\displaystyle i}$${\displaystyle A^{-1}[i]}$${\displaystyle j}$${\displaystyle A^{-1}[j]}$${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$${\displaystyle H}$

したがって、長さ の文字列と、文字列内の 2 つの任意の位置 が与えられた場合、接尾辞 と の最長共通接頭辞の長さは次のように計算できます。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle i,j}$${\displaystyle S}$${\displaystyle A^{-1}[i]<A^{-1}[j]}$${\displaystyle S[i,n]}$${\displaystyle S[j,n]}$${\displaystyle \operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). 「拡張サフィックス配列によるサフィックスツリーの置き換え」. Journal of Discrete Algorithms . 2 : 53–86. doi : 10.1016/S1570-8667(03)00065-0 .
• Manber, Udi; Myers, Gene (1993). 「サフィックス配列: オンライン文字列検索の新しい方法」SIAM Journal on Computing . 22 (5): 935. CiteSeerX  10.1.1.105.6571 . doi :10.1137/0222058. S2CID  5074629.
• Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001).サフィックス配列における線形時間最長共通プレフィックス計算とその応用。第 12 回組み合わせパターン マッチングに関する年次シンポジウムの議事録。コンピュータ サイエンスの講義ノート。第 2089 巻。pp. 181–192。doi : 10.1007/3-540-48194- X_17。ISBN 978-3-540-42271-6。
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010). CST++ . 文字列処理と情報検索. コンピュータサイエンスの講義ノート. Vol. 6393. p. 322. doi :10.1007/978-3-642-16321-0_34. ISBN 978-3-642-16320-3。
• Kärkkäinen, Juha; Sanders, Peter (2003). 単純な線形作業接尾辞配列の構築。オートマトン、言語、プログラミングに関する第30回国際会議の議事録。pp. 943–955 。 2012年8月28日閲覧。
• フィッシャー、ヨハネス (2011)。LCP配列の誘導。アルゴリズムとデータ構造。コンピュータサイエンスの講義ノート。第 6844 巻。pp. 374–385。arXiv : 1101.3448。doi : 10.1007 / 978-3-642-22300-6_32。ISBN 978-3-642-22299-3。
• Manzini, Giovanni (2004)。線形時間 LCP 配列計算のための 2 つのスペース節約トリック。アルゴリズム理論 - SWAT 2004。コンピュータ サイエンスの講義ノート。第 3111 巻。p. 372。doi : 10.1007 / 978-3-540-27810-8_32。ISBN 978-3-540-22339-9。
• Kärkkäinen, Juha ; Manzini, Giovanni; Puglisi, Simon J. (2009).並べ替えられた最長共通プレフィックス配列。組み合わせパターンマッチング。コンピュータサイエンスの講義ノート。第 5577 巻。p. 181。doi : 10.1007/978-3-642-02441-2_17。ISBN 978-3-642-02440-5。
• Puglisi, Simon J.; Turpin, Andrew (2008)。最長共通プレフィックス配列計算における空間と時間のトレードオフ。アルゴリズムと計算。コンピュータサイエンスの講義ノート。第 5369 巻。p. 124。doi : 10.1007/978-3-540-92182-0_14。ISBN 978-3-540-92181-3。
• Gog, Simon; Ohlebusch, Enno (2011). 高速で軽量な LCP 配列構築アルゴリズム(PDF) . アルゴリズム エンジニアリングと実験に関するワークショップの議事録、ALENEX 2011。pp. 25–34 . 2012-08-28に取得。
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009)。ほぼ純粋な誘導ソートによる線形サフィックス配列の構築。2009 データ圧縮会議。p. 193。doi :10.1109/ DCC.2009.42。ISBN 978-0-7695-3592-0。
• フィッシャー、ヨハネス、ヒューン、フォルカー (2007) 。RMQ 情報の新しい簡潔な表現と拡張サフィックス配列の改善。組み合わせ論、アルゴリズム、確率論および実験的方法論。コンピュータ サイエンスの講義ノート。第 4614 巻。p. 459。doi : 10.1007 /978-3-540-74450-4_41。ISBN 978-3-540-74449-8。
• Chen, G.; Puglisi, SJ; Smyth, WF (2008). 「Lempel–Ziv 因数分解による少ない時間とスペースの使用」.コンピュータサイエンスにおける数学. 1 (4): 605. doi :10.1007/s11786-007-0024-4. S2CID  1721891.
• Crochemore, M.; Ilie, L. (2008). 「線形時間での最長前因数の計算とその応用」。Information Processing Letters . 106 (2): 75. CiteSeerX  10.1.1.70.5720 . doi :10.1016/j.ipl.2007.10.006. S2CID  5492217.
• Crochemore, M.; Ilie, L.; Smyth, WF (2008). Lempel Ziv 分解を計算するための簡単なアルゴリズム。データ圧縮会議 (dcc 2008)。p. 482。doi :10.1109 / DCC.2008.36。hdl : 20.500.11937/ 5907。ISBN 978-0-7695-3121-2。
• Sadakane, K. (2007). 「完全な機能を備えた圧縮サフィックスツリー」.コンピューティングシステムの理論. 41 (4): 589–607. CiteSeerX  10.1.1.224.4152 . doi :10.1007/s00224-006-1198-x. S2CID  263130.
• Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (2009). 「エントロピー制限付き圧縮サフィックスツリーの高速化」.理論計算機科学. 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
• Fischer, Johannes; Kurpicz, Florian (2017 年 10 月 5 日)。「 DivSufSortの解体」。プラハ弦楽学会議 2017 の議事録。arXiv : 1710.01896。

ウィキメディア・コモンズには、 LCP アレイに関連するメディアがあります。

• Fischer (2011) で説明されているコードのアドホック実装のミラー
• SDSL: 簡潔なデータ構造ライブラリ - さまざまな LCP 配列実装、範囲最小クエリ (RMQ) サポート構造、その他多くの簡潔なデータ構造を提供します。
• サフィックス配列と LCP 配列を使用してエミュレートされたボトムアップ サフィックス ツリー トラバーサル (Java)
• テキストインデックス作成プロジェクト (サフィックスツリー、サフィックス配列、LCP 配列、Burrows–Wheeler 変換の線形時間構築)