C++プログラムにおけるLCS（最長共通部分列）の空間計算量最適化手法

LCS問題とは

本記事では、LCS（最長共通部分列：Longest Common Subsequence）問題を解くための、空間計算量を最適化したアプローチを紹介します。LCSとは、2つの文字列に共通して現れる部分列のうち、最も長いものを指します。例えば、「BHHUBC」と「HYUYBZC」という2つの文字列の場合、最長共通部分列の長さは4になります。

従来の動的計画法（DP）によるアプローチでもLCSは求められますが、この方法では大きなメモリ領域が必要になります。具体的には、1つ目の文字列の文字数をm、2つ目の文字列の文字数をnとすると、m×nのサイズを持つ2次元テーブルを用意しなければなりません。

O(n)の補助記憶域で実現する工夫

ここで紹介するのは、補助記憶域をO(n)に抑える実装方法です。従来のアプローチをよく観察すると、各反復処理において参照しているのは直前の行のデータだけであることが分かります。つまり、それ以前の行のデータはすべて不要なのです。

そこで、サイズが2×(n+1)、すなわち2行分のテーブルを用意するだけで十分です。行番号を0と1で交互に切り替えながら計算を進めることで、メモリ使用量を大幅に削減できます。以下のアルゴリズムで具体的な流れを確認してみましょう。

アルゴリズム

lcs_problem(X, Y) −

begin
   m := 文字列Xの長さ
   n := 文字列Yの長さ
   サイズ L[2, n+1] のテーブルを定義
   index はテーブルLの0行目または1行目を指す
   i を 1 から m まで繰り返す：
      index := index AND 1
      j を 0 から n まで繰り返す：
         if i = 0 または j = 0 の場合：
            L[index, j] := 0
         else if X[i - 1] = Y[j - 1] の場合：
            L[index, j] := L[1 – index, j - 1] + 1
         else：
            L[index, j] := L[1 – index, j] と L[index, j-1] の最大値
         end if
      繰り返し終了
   繰り返し終了
   return L[index, n]
end

C++による実装例

#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
   int m = X.length(), n = Y.length();
   int L[2][n + 1];
   bool index;
   for (int i = 0; i <= m; i++) {
      index = i & 1;
      for (int j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[index][j] = 0;
         else if (X[i-1] == Y[j-1])
            L[index][j] = L[1 - index][j - 1] + 1;
         else
            L[index][j] = max(L[1 - index][j], L[index][j - 1]);
      }
   }
   return L[index][n];
}
int main() {
   string X = "BHHUBC";
   string Y = "HYUYBZC";
   cout << "Length of LCS is :" << lcsOptimized(X, Y);
}

実行結果

Length of LCS is :4

まとめ

このように、2行分のテーブルだけでLCSの長さを正しく求めることができました。ビット演算 i & 1 を使って行インデックスを交互に切り替えるのがポイントです。文字列が非常に長い場合でも、メモリ使用量を従来のm×nからわずか2×(n+1)まで抑えられるため、大規模な入力を扱う際に有効な実用的な最適化手法といえます。