最長共通部分文字列

Wikibooks には、アルゴリズム実装/文字列/最長共通部分文字列に関する書籍があります。

コンピュータサイエンスでは、2 つ以上の文字列の最長共通部分文字列とは、それらすべての部分文字列である最長の文字列です。最長共通部分文字列は複数存在する場合があります。用途には、データ重複排除や盗作検出などがあります。

この図は、問題に複数の解がある 2 つの文字列を示しています。部分文字列の出現は常に重なり合っていますが、それらを「結合」してより長い共通部分文字列を取得することはできません。

文字列「ABABC」、「BABCA」、および「ABCBA」には、長さ 3 の「ABC」という最長の共通部分文字列が 1 つだけあります。その他の共通部分文字列は、「A」、「AB」、「B」、「BA」、「BC」、および「C」です。

  ABABC
    |||
   バブカ
    |||
    ABCBA

長さとの2 つの文字列が与えられた場合、と の両方の部分文字列である最長の文字列を見つけます。 ${\displaystyle S}$${\displaystyle m}$${\displaystyle T}$${\displaystyle n}$${\displaystyle S}$${\displaystyle T}$

一般化はk共通部分文字列問題です。文字列の集合(ただし)が与えられます。各 について、少なくとも 個の文字列の部分文字列として出現する最長の文字列を見つけます。 ${\displaystyle S=\{S_{1},\ldots ,S_{K}\}}$${\displaystyle |S_{i}|=n_{i}}$${\textstyle \sum n_{i}=N}$${\displaystyle 2\leq k\leq K}$${\displaystyle k}$

一般化された接尾辞木の助けを借りれば、 との最長共通部分文字列の長さと開始位置を時間内に見つけることができます。入力アルファベットのサイズが であれば、計算のワード RAMモデルでより高速なアルゴリズムを実現できます。 特に、このアルゴリズムは空間を使用して時間内に実行されます。^[1]動的計画法で問題を解くには のコストがかかります。 一般化された問題の解決には、動的計画法では空間と時間がかかり、一般化された接尾辞木では時間がかかります。 ${\displaystyle S}$${\displaystyle T}$${\displaystyle \Theta }$${\displaystyle (n+m)}$${\displaystyle \sigma }$${\displaystyle 2^{o\left({\sqrt {\log(n+m)}}\right)}}$${\textstyle O\left((n+m)\log \sigma /{\sqrt {\log(n+m)}}\right)}$${\displaystyle O\left((n+m)\log \sigma /\log(n+m)\right)}$${\displaystyle \Theta (nm)}$${\displaystyle \Theta (n_{1}+\cdots +n_{K})}$${\displaystyle \Theta (n_{1}\cdots n_{K})}$${\displaystyle \Theta (n_{1}+\cdots +n_{K})}$

文字列セットの最長共通部分文字列は、文字列の一般化された接尾辞ツリーを構築し、その下にあるサブツリー内のすべての文字列のリーフ ノードを持つ最も深い内部ノードを見つけることで見つけることができます。右の図は、文字列 "ABAB"、"BABA"、"ABBA" の接尾辞ツリーで、固有の文字列ターミネータが埋め込まれて "ABAB$0"、"BABA$1"、"ABBA$2" になります。"A"、"B"、"AB"、"BA" を表すノードはすべて、すべての文字列から派生した子孫リーフを持ち、番号は 0、1、2 です。

サフィックスツリーの構築には時間がかかります（アルファベットのサイズが一定の場合）。各ノードの下にどの文字列が表示されるかを示すビットベクトルを使用してツリーを下から上へトラバースすると、k共通部分文字列問題は時間内に解決できます。サフィックスツリーが定数時間の最小共通祖先検索用に準備されている場合、時間内に解決できます。^[2]${\displaystyle \Theta (N)}$${\displaystyle \Theta (NK)}$${\displaystyle \Theta (N)}$

次の疑似コードは、動的プログラミングを使用して 2 つの文字列間の最長共通部分文字列のセットを検索します。

関数LongestCommonSubstring(S[1..r], T[1..n])
    L :=配列(1..r, 1..n)
    0 := 0
    戻り値:= {}

    i := 1..r
        の場合j := 1..n
            の場合S[i] = T[j]
                の場合i = 1またはj = 1 の場合
                    L[i,j] := 1 である。
                それ以外
                    L[i, j] := L[i − 1, j − 1] + 1
                L[i, j] > zの場合
                    z := L[i, j]
                    ret := {S[i − z + 1..i]}
                それ以外の 場合、 L[i, j] = z
                    ret := ret ∪ {S[i − z + 1..i]}
            それ以外
                L[i,j] := 0 となる。
    リターンret

このアルゴリズムは時間で実行されます。配列には、それぞれ位置 と で終わる接頭辞との最長共通接尾辞の長さが格納されます。変数 は、これまでに見つかった最長共通部分文字列の長さを格納するために使用されます。セット は、長さ の文字列のセットを格納するために使用されます。セットは、 の代わりに最長共通部分文字列 (サイズ z) の最後の文字であるインデックス を格納するだけで効率的に保存できます。したがって、 の各 i について、すべての最長共通部分文字列は になります。${\displaystyle O(nr)}$LS[1..i]T[1..j] ijzretzretiS[i-z+1..i]retS[(ret[i]-z)..(ret[i])]

実装のメモリ使用量を削減するには、次のトリックを使用できます。

• メモリを節約するために、DPテーブルの最後の行と現在の行のみを保持します（の代わりに） ${\displaystyle O(\min(r,n))}$${\displaystyle O(nr)}$
  • 最後の行と現在の行は、内側のループを逆方向にたどることで同じ1D配列に格納できます。
• 行にはゼロ以外の値のみを格納します。これは、配列の代わりにハッシュ テーブルを使用して実行できます。これは、大きなアルファベットの場合に便利です。

• 最長回文部分文字列
• nグラム、文字列に含まれる長さnのすべての可能な部分文字列

Wikibookアルゴリズム実装には、最長共通部分文字列に関するページがあります。

• アルゴリズムとデータ構造の辞書: 最長共通部分文字列
• 動的プログラミングアルゴリズムの Perl/XS 実装
• サフィックスツリーアルゴリズムの Perl/XS 実装
• ウィキブック上のさまざまな言語での動的プログラミングの実装
• 動的プログラミングアルゴリズムの AS3 実装
• 2つの文字列の最長共通部分文字列の接尾辞ツリーベースのC実装