- 記入中
- 参照元
- 答え
最長共通部分列(LCS)
2つの単語には、同じ順番で共通する文字がどれだけあるでしょうか。その答えが最長共通部分列で、diff ツールやスペルチェッカー、DNA の比較はこれを土台にしています。2つの単語を入力して、その文字の表が埋まっていく様子を見たら、角から答えを逆にたどりましょう。 「再生」で表が埋まっていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。2つの単語を入力します。1つ目は表の左側に縦に、2つ目は上に横に並びます。各マスには、その行と列までの文字の最長共通部分列の長さが入ります。最後に、右下のマスから逆にたどって文字を読み取ります。「新しい例」で別の単語の組を選びます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 2つの単語を入力します。1つ目は表の左側に縦に、2つ目は上に横に並びます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- 各マスが2つの文字を比べる様子を見たら、オレンジの経路を角から逆にたどって答えを読み取ります。
表のしくみ
マスには、1つ目の単語のその行までの文字と、2つ目の単語のその列までの文字の最長共通部分列の長さが入ります。– の付いた行と列は空の単語を表すので 0 です。マスの2つの文字が等しければ、そのマスは左上のマスより1大きくなります。異なれば、2つの文字のどちらかは答えに含まれないので、マスは上のマスと左のマスの大きいほうの値を取ります。
文字を逆にたどって読む
右下のマスが答えの長さです。文字を見つけるにはそこから始めます。2つの文字が一致する場所では、その文字が部分列に含まれ、左上へ進みます。一致しなければ、上のマスと左のマスのうち大きいほうへ進みます。途中で集めた文字を逆順に読むと、最長共通部分列の1つになります。同じ長さのものがほかにもある場合がありますが、逆にたどるとそのうちの1つが見つかります。
よくある質問
部分列と部分文字列の違いは何ですか?
部分文字列は、RACER の中の ACE のように隣り合った文字の並びです。部分列は順番を保ちますが文字を飛ばしてもよいので、ACE は ABCDE の部分列でもあります。最長共通部分文字列は、似た表を使う別の問題です。
LCS のアルゴリズムはどれくらい速いですか?
長さ m と n の単語では表に m·n 個のマスがあり、それぞれ1ステップで埋まるので、計算量は O(m·n) です。1万行のテキスト2つなら1億マスになります。そのため diff ツールは、同じ考え方にもとづくもっと巧妙な方法を使います。
最長共通部分列は1つに決まりますか?
いいえ。ABCBDAB と BDCABA には、長さ 4 の異なる共通部分列が3つあります。BCBA、BCAB、BDAB です。表からわかるのは長さで、逆にたどるとそのうちの1つが選ばれます。
LCS で2つの単語がどれくらい似ているかわかりますか?
ある程度はわかります。長さ m と n の2つの単語の最長共通部分列の長さが k なら、m − k 文字を削除し n − k 文字を挿入すれば、一方をもう一方に変えられます。文字の置き換えも認める編集距離のほうが、よい尺度であることが多いです。
データはどこかに送信されますか?
いいえ。すべてブラウザー内で計算され、最後の設定はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ