※間違いがあればご指摘ください
最長共通部分列 LCS: Longest Common Subsequence と 最小編集距離 SED: Shortest Edit Distance というものがあります. 以下では文字列を扱うので,”部分列 subsequence”というよりは”部分文字列 substring”というわけですが,
LCSが何なのかと言うと, 二つの文字列xとyがあるとき,xとyの(最長となる)共通した文字の列,またはその文字列の文字数を示したものがLCSです. 文字数に関してはSEDというものと同じということみたいなので, 以上を区別するために本記事では,
と呼ぶこととします.
ここで,
- 文字列xの文字数をm
- 文字列yの文字数をn
っとします.
LCSとSEDを求めるには,まず,エディットグラフというものを作成します. エディットグラフは(文字列xの文字数m+1)行×(文字列yの文字数n+1)列の配列(行列といってもいいかな?)です. その配列の各要素(エディットグラフの行列の要素の値)は以下のように決められます.
ここで,,です. Pythonの配列やNumpy行列は0行0列から始まるので,それを採用します. 0行0列は行列の1行1列だと考えてください.
以上のようにして作成されたエディットグラフの左最上部(0行0列)から右最下部(m行n列)までの最短経路がSEDであり,
エディットグラフの右最下部(m行n列)の要素の値がSEDと同じ値になっています.
また,最短経路で通る要素のうち,xとyの文字列が一致している部分がLCSとなっており,これは複数求まることがあります.
以上は抽象的な説明だったので,具体例をもとに,エディットグラフ,SED,LCSを求めてみましょう. 例として,文字列xは”あいあい”,文字列yは”あいうい”として,まず,エディットグラフを作成してみましょう.
”あいあい”と”あいうい”のエディットグラフは,
となります.以上のエディットグラフから,SEDは”3”,LCSは”あいい”となることが分かります.
参考サイト
- 最長共通部分列(LCS) - ゲームプログラマーを目指すひと - FC2
- アルゴリズム1000本ノック #3. Longest common subsequence - Qiita
- LCS(最長共通部分列)とは - 東京工芸大学 工学部
- アルゴリズム論 Theory of Algorithms
- LCSを用いたWebログ解析におけるスケーラビリティの向上の3.2節あたり
- ア3Dオンラインゲームのプレイログによる自動漫画生成:インタラクティブGEによるカメラワーク決定手法 の2.3節
- 単語情報及びフレーズによる大局的情報を用いた機械翻訳自動評価手法 では,文字単位ではなく,形態素単位でLCSを求め,形態素の出現位置と数で評価をしていると思われる
PythonでLCS自動算出
以上のことをもとに,PythonでSEDと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
- Pythonで、リストの内の要素の組み合わせ(順列)を列挙する - naritoブログ
- すごいぞitertoolsくん - Qiita
- python3でリスト内の重複した辞書を削除する方法 - Qiita
LaTeX Tips
追記 2020/04/15
”日本語入力を支える技術”という本の221ページに最長共通部分列の説明があります. 222ページにはRubyで書かれたコードも書かれています. しかし,このコードは最長共通部分列の長さを求めるもので, 共通部分がどこかは返却してくれるコードではなさそうです. まぁ,別の点でも参考にはなる本だと思います.