芋の独り言

当ブログへのアクセスは当ブログのプライバシーポリシーに同意したものとみなします.

最長共通部分文字列 LCS: Longest Common Substring

※間違いがあればご指摘ください

最長共通部分列 LCS: Longest Common Subsequence と 最小編集距離 SED: Shortest Edit Distance というものがあります. 以下では文字列を扱うので,”部分列 subsequence”というよりは”部分文字列 substring”というわけですが,

LCSが何なのかと言うと, 二つの文字列xとyがあるとき,xとyの(最長となる)共通した文字の列,またはその文字列の文字数を示したものがLCSです. 文字数に関してはSEDというものと同じということみたいなので, 以上を区別するために本記事では,

共通する文字の列(パターン)をLCS,その列の文字数をSED

と呼ぶこととします.

ここで,

  • 文字列xの文字数をm
  • 文字列yの文字数をn

っとします.

LCSとSEDを求めるには,まず,エディットグラフというものを作成します. エディットグラフは(文字列xの文字数m+1)行×(文字列yの文字数n+1)列の配列(行列といってもいいかな?)です. その配列の各要素(エディットグラフのij列の要素の値)D_{i,j}は以下のように決められます.

ここで,i=0,\cdots,mj=0,\cdots,nです. Pythonの配列やNumpy行列は0行0列から始まるので,それを採用します. 0行0列は行列の1行1列だと考えてください.


\displaystyle
D_{i,j}=
\begin{cases}
0 & i=0\;or\;j=0\\
\max{(D_{i-1,j},D_{i,j-1})} & \text{文字列}x\text{の}i\text{番目の文字}\neq\text{文字列}y\text{の}j\text{番目の文字}\\ 
D_{i-1,j-1}+1 & \text{文字列}x\text{の}i\text{番目の文字}=\text{文字列}y\text{の}j\text{番目の文字}
\end{cases}


以上のようにして作成されたエディットグラフの左最上部(0行0列)から右最下部(m行n列)までの最短経路がSEDであり, エディットグラフの右最下部(m行n列)の要素の値がSEDと同じ値になっています. また,最短経路で通る要素のうち,xとyの文字列が一致している部分がLCSとなっており,これは複数求まることがあります.

以上は抽象的な説明だったので,具体例をもとに,エディットグラフ,SED,LCSを求めてみましょう. 例として,文字列xは”あいあい”,文字列yは”あいうい”として,まず,エディットグラフを作成してみましょう.

”あいあい”と”あいうい”のエディットグラフは,


\require{color}
\begin{array}{@{\,}c|ccccc@{\,}}
\   & 0 & あ & い & う & い \\ \hline
0  & 0 &  0  &  0 &  0  &  0  \\ 
あ& 0 &  \textcolor{blue}{1}  &  1 &  1  &  1  \\
い& 0 &  1  &  \textcolor{blue}{2} &  2  &  2  \\
あ& 0 &  1  &  2 &  2  &  2  \\
い& 0 &  1  &  2 &  2  &  \textcolor{red}{3}  
\end{array}

となります.以上のエディットグラフから,SEDは”3”,LCSは”あいい”となることが分かります.

参考サイト

  1. 最長共通部分列(LCS) - ゲームプログラマーを目指すひと - FC2
  2. アルゴリズム1000本ノック #3. Longest common subsequence - Qiita
  3. LCS(最長共通部分列)とは - 東京工芸大学 工学部
  4. アルゴリズム論 Theory of Algorithms
  5. LCSを用いたWebログ解析におけるスケーラビリティの向上の3.2節あたり
  6. ア3Dオンラインゲームのプレイログによる自動漫画生成:インタラクティブGEによるカメラワーク決定手法 の2.3節
  7. 単語情報及びフレーズによる大局的情報を用いた機械翻訳自動評価手法 では,文字単位ではなく,形態素単位でLCSを求め,形態素の出現位置と数で評価をしていると思われる

PythonでLCS自動算出

以上のことをもとに,PythonSEDとLCSを求めるスクリプトを書いてみました.

# -*- coding:utf-8 -*-
import numpy as np
import sys,itertools,json

def lcs(x:str,y:str):
    m = len(x)
    n = len(y)

    # エディットグラフの初期化
    editgraph = np.zeros((m+1,n+1))

    # エディットグラフの作成
    for i,xi in enumerate(x):
        i = i + 1
        for j,yj in enumerate(y):
            j = j + 1
            if xi == yj:
                editgraph[i,j] = editgraph[i-1,j-1] + 1               
            else:
                editgraph[i,j] = max(editgraph[i-1,j],editgraph[i,j-1])

    # エディットグラフの表示
    if input("editgraph display?(y/n):")=="y":
        import pandas as pd
        print(pd.DataFrame(editgraph,
                           index   = [0]+[i for i in x],
                           columns = [0]+[j for j in y]
                           ))

    # 最適解の文字数
    sed = int(editgraph[m,n])
    print("SED=",sed)


    # 最適解(経路)
    # IndexErrorが出る場合は,以下の+1を増やしてください
    ptn = list(itertools.product([True,False], repeat=max(len(x)+1,len(y)+1)))
    ways=[]

    for p in ptn:
        way=[]
        i=len(x)
        j=len(y)
        no = 0

        while i>0 and j >0:
            if x[i-1]==y[j-1]:
                way.append((i,j))
                i-=1
                j-=1
            else:
                if editgraph[i-1,j]>editgraph[i,j-1]:
                    i-=1
                elif  editgraph[i-1,j]<editgraph[i,j-1]:
                    j-=1
                else:
                    if p[no]:
                        i-=1
                    else:
                        j-=1

                    no+=1

        if len(way)==sed:
            way = [way[no] for no in range(len(way)-1,-1,-1)]
            ways.append(way)
    ways = list(map(json.loads, set(map(json.dumps, ways))))


    # 結果の表示
    for no,way in enumerate(ways):       
        sys.stdout.write("●LCS{}:".format(no+1))
        for w in way:
            sys.stdout.write(str(x[w[0]-1]))
        sys.stdout.write("{}:\n".format(way))
        
        sys.stdout.write('string input1:')
        for i,xi in enumerate(x):
            if i in [pos[0]-1 for pos in way]:
                sys.stdout.write('[{}]'.format(xi))
            else:
                sys.stdout.write(" {} ".format(xi))
        sys.stdout.write('\n')
        sys.stdout.write('string input2:')
        for j,yj in enumerate(y):
            if j in [pos[1]-1 for pos in way]:
                sys.stdout.write('[{}]'.format(yj))
            else:
                sys.stdout.write(" {} ".format(yj))
        sys.stdout.write("\n\n")

    return ways,lcs

if __name__ == "__main__":
    lcs(input("string input1:"),input("string input2:"))

[1]にある例を 以上のスクリプトを実行してエディットグラフとSEDとLCSを求めると...

string input1:ABDCZFZ
string input2:ADBCFZ
editgraph display?(y/n):y
     0    A    D    B    C    F    Z
0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
A  0.0  1.0  1.0  1.0  1.0  1.0  1.0
B  0.0  1.0  1.0  2.0  2.0  2.0  2.0
D  0.0  1.0  2.0  2.0  2.0  2.0  2.0
C  0.0  1.0  2.0  2.0  3.0  3.0  3.0
Z  0.0  1.0  2.0  2.0  3.0  3.0  4.0
F  0.0  1.0  2.0  2.0  3.0  4.0  4.0
Z  0.0  1.0  2.0  2.0  3.0  4.0  5.0
SED= 5
●LCS1:ADCFZ[[1, 1], [3, 2], [4, 4], [6, 5], [7, 6]]:
string input1:[A] B [D][C] Z [F][Z]
string input2:[A][D] B [C][F][Z]

●LCS2:ABCFZ[[1, 1], [2, 3], [4, 4], [6, 5], [7, 6]]:
string input1:[A][B] D [C] Z [F][Z]
string input2:[A] D [B][C][F][Z]

読み込む文字列の順番を逆にしても得られる結果は同じですね.

string input1:ADBCFZ
string input2:ABDCZFZ
editgraph display?(y/n):y
     0    A    B    D    C    Z    F    Z
0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
A  0.0  1.0  1.0  1.0  1.0  1.0  1.0  1.0
D  0.0  1.0  1.0  2.0  2.0  2.0  2.0  2.0
B  0.0  1.0  2.0  2.0  2.0  2.0  2.0  2.0
C  0.0  1.0  2.0  2.0  3.0  3.0  3.0  3.0
F  0.0  1.0  2.0  2.0  3.0  3.0  4.0  4.0
Z  0.0  1.0  2.0  2.0  3.0  4.0  4.0  5.0
SED= 5
●LCS1:ADCFZ[[1, 1], [2, 3], [4, 4], [5, 6], [6, 7]]:
string input1:[A][D] B [C][F][Z]
string input2:[A] B [D][C] Z [F][Z]

●LCS2:ABCFZ[[1, 1], [3, 2], [4, 4], [5, 6], [6, 7]]:
string input1:[A] D [B][C][F][Z]
string input2:[A][B] D [C] Z [F][Z]

その他の例では

string input1:東京工芸大学
string input2:京橋工業芸術大学
editgraph display?(y/n):y
     0    京    橋    工    業    芸    術    大    学
0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
東  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
京  0.0  1.0  1.0  1.0  1.0  1.0  1.0  1.0  1.0
工  0.0  1.0  1.0  2.0  2.0  2.0  2.0  2.0  2.0
芸  0.0  1.0  1.0  2.0  2.0  3.0  3.0  3.0  3.0
大  0.0  1.0  1.0  2.0  2.0  3.0  3.0  4.0  4.0
学  0.0  1.0  1.0  2.0  2.0  3.0  3.0  4.0  5.0
SED= 5
●LCS1:京工芸大学[[2, 1], [3, 3], [4, 5], [5, 7], [6, 8]]:
string input1: 東 [京][工][芸][大][学]
string input2:[京] 橋 [工] 業 [芸] 術 [大][学]

Python Tips

LaTeX Tips

追記 2020/04/15

”日本語入力を支える技術”という本の221ページに最長共通部分列の説明があります. 222ページにはRubyで書かれたコードも書かれています. しかし,このコードは最長共通部分列の長さを求めるもので, 共通部分がどこかは返却してくれるコードではなさそうです. まぁ,別の点でも参考にはなる本だと思います.