最長共通部分列
定義
LCS (最長共通部分列：Longest Common Subsequence) とは，2つの文字列 X[1,...,m] , Y[1,…,n] において、双方に現れる部分文字列の中で最長の文字列と定義されています。部分列は連続している必要はありませんが，順序を変更してはいけません。
例えば、「東京工芸大学」と「京橋工業芸術大学」のLCSは「京工芸大学」で、長さは5です。このことは、2つの文字列には、以下のような対応があることから分かります。
− 京 橋 工 業 芸 術 大 学
東 京 − 工 − 芸 − 大 学
LCSを求めることは、類似文書の検索、文書の流用の程度の判定、ミスを含む入力の是正、ＤＮＡの解析など、幅広い応用があり、実務で広く使用されています。また、LCSを改良した様々なアルゴリズムの研究が行われています。
任意の長さの２つの文字列に対して、LCSを計算するアルゴリズムは以下のマトリックスによって計算できます。
このマトリックス（LCS）の計算方法は、下記の通りです。
i を文字列 X[1,...,m]のインデックスとします。ただし、文字列がない、すなわち空文字列も含めて扱うために0
≦ i ≦m とします（ i=0は空文字列）。同様に、jを文字列 Y[1,...,n] のインデックスとします。すなわち、0
≦ j ≦n
とします。このとき、2つの文字列の共通部分列長len[i, j] は、以下で定義できます。
l i = 0 もしくは j = 0 のとき、 len[ i, j ] = 0（空文字列との共通部分列長は 0であるため）
l X[i] = Y[j] のとき、len[ i,
j ] = len[ i-1, j-1 ] + 1 （文字が一致したので、１つ前の共通部分列長に 1を加える）
l X[i] ≠ Y[j] のとき、len[ i, j ] = max( len[ i, j-1 ] , len[ i-1,
j ] ) （文字が一致しないので、１つ前の共通部分列長の最大の値を、新たな共通部分列長とする）
以上をまとめて表記すると下記になります。
A) len[i, j] = 0 (i=0 または j=0)
B) len[i, j] = LCS[i − 1, j − 1] +1 (1≦i≦m かつ 1≦j≦n かつ X[i] = Y[j])
C) len[i, j] = max( len[i − 1, j], len[i, j − 1]) (1≦i≦m かつ 1≦j≦n かつX[i] ≠ Y[j])
D) LCS= len[m, n]
共通部分列長の最大のもの、すなわちLCSは、len[m, n] となります。
LCSの実装
LCSをプログラミングする方法について説明します。プログラミング言語としては、Javaを使います。Javaを使う理由は、無料で使えること、豊富な機能とライブラリがあり、ほぼあらゆる分野のプログラミングに使えることです。
プログラムを作るためには、計算方法（アルゴリズム）を定める必要があります。LCSの場合、LCSの定義から、容易に計算方法を定めることができます。
LCSの定義
A) len[i, j] = 0 (i=0 または j=0)
B) len[i, j] = LCS[i − 1, j − 1] +1 (1≦i≦m かつ 0≦j≦n かつ X[i] = Y[j])
C) len[i, j] = max( len[i − 1, j], len[i, j − 1]) (1≦i≦m かつ 0≦j≦n かつX[i] ≠
Y[j])
D) LCS= len[m, n]
まず、文字列X[1,...,m]
とY[1,...,n]の表現方法です。Javaで文字列を表現する方法としては、String型、Char型の配列、Vector型を使う方法が考えられます。
ここでは、LCSの定義に近いコーディングをするために、String型を使ってみます。
String str1="京橋工業芸術大学";
String str2="東京工芸大学";
JavaのString型のインデックスは0から始まりますので、X[i] (第1文字列の第i文字目)は、str1.charAt(i-1) となります。
配列len[i, j] を生成します。
int m = str1.length();
int n = str2.length();
int[][] len = new int [m+1][n+1];
文字列の長さはあらかじめ想定できませんので、length()メソッドを使って入力された文字列の長さを取得し、配列len[i, j] を生成しています。int [m+1][n+1]となっているのは、空文字列を含めた文字列X[1,...,m]
とY[1,...,n]を扱うためです。
A) の実装
for (i
= 0; i<=m; i++) len[i][0] = 0;
for (j = 0; j<=n; j++) len[0][j] = 0;
B) とC) の実装
for (i
= 1; i<=m; i++){
for(j = 1; j<=n; j++){
if(str1.charAt(i-1) ==
str2.charAt(j-1)){
len[i][j] = len[i-1][j-1] + 1;
} else {
len[i][j] = Math.max(len[i][j-1],
len[i-1][j]);
}
}
}
LCSは頻繁に使われる文字処理です。そのため、具体的なJavaソースコードは、国内・海外の多くのサイトから入手できます。コーディングの方法は色々ありますが、基本的な考え方は同じです。色々な実装を確認して、プログラミングテクニックを磨いてください。
――Copyright(C) 2014 Tokyo Polytechnic University (東京工芸大学) All rights reserved――