記事検索

検索ワードを入力してください。
Sky Tech Blog
2つの​文字列から​同じ​部分を​探す方​法に​ついて

2つの​文字列から​同じ​部分を​探す方​法に​ついて

最長共通部分列問題(LCS)は、2つの文字列から最長の共通部分列を探すアルゴリズムです。例として「ABCDCE」と「ACCDEX」を用い、対応表を作成して探査します。

2つの文字列から一致する文字を検出するアルゴリズムの紹介になります。

最長共通部分列問題(LCS)と呼ばれる2つの文字列から最長の共通部分列を探すアルゴリズムになります。
※ DNAの解析とかでも使われるアルゴリズムのようです。

例を用いて考え方の紹介いたします。

以下の2つの文字列内の最長文字分列を見つけます。

  • 文字列1(”ABCDCE”)
  • 文字列2(”ACCDEX”)

① : それぞれの​文字列を​先頭から​順番で​取り出します。

② : 一致する​ものが​あった​場合は​両方の​要素を​同時に​取り出します。

③ : 一致する​ものが​ない​場合は、​取り出した​文字を​捨て、​次の​文字を​取り出します。

④ : ①~③を​繰り返して​最大の​一致数に​なった​ものが​LCSと​なります。

少しまとめると、それぞれの先頭から順番に文字をキューから抜き出していき最終的に一緒に取り出した数が多い取り方を探すというものです。

では、今回の例で最長文字分列はどうなるのでしょうか?

  • 文字列1(”ABCDCE”)
  • 文字列2(”ACCDEX”)

直感的には”ACDE”となりそうな気がしますね。

実際に最長の共通部分列を求める際は対応表を作成し探査していくことになります。

① 横軸を​文字列1、​縦軸を​文字列2で​対応表を​作成します。

一致として取り出した文字数を対応表に記載していきます。

※ マッチせずに捨てた文字がわかるように、先頭に空文字を入れた表を作成します。下の表だとお互いに取り出していない個所は0になります。

② 次に​文字列1の​”A”を​取り出す際に​文字列2から​最大何個取り出せるか​記載します。

③ 文字列1の​"AB"を​取り出す際に​文字列2から​最大何個取り出せるか​記載します。

”B”に一致する文字が文字列2に存在しないので、”A”を取り出した時と数の変化はありません。

④ 文字列1の​"ABC"を​取り出す際に​文字列2から​最大何個取り出せるか​記載します。

"A"を取り出した以降で、"C"を取り出せる場合は"A"と"C"を取り出せることになるため、2となります。

⑤ 一文​字ずつ​取り出す文字を​増やしていき、​文字列2から​最大何個取り出せるか​記載します。

⑥ 表の​右下から​左上に​向けて​数字が​高い​ものを​通るように​辿っていきます。

※ 隣接する数字がすべて同じ場合は、斜め上に移動します。

今回の例で辿るルートは以下になります。

数値が変動する箇所は文字列1と文字列2の両方から文字を取り出したことになります。

今回の文字列1と文字列2で最長文字分列は"ACCE"となります。

あれ?思っていた”ACDE”と違う・・・

今回の例で、実はもう一つ最長文字分列を取れるルートが存在します。

ちゃんと"ACDE"も最長文字分列でした。

この最長文字分列を探すためのルートで、以下のことも判断できます。

  • ↑は「文字列1に存在しない文字」
  • ←は「文字列2に存在しない文字」

↑と←に注目することで、2つの文字列の違いを検出することもできます。
最長文字分列が"ACDE"となるルートの場合は、以下の違いになります。

文字として一致している部分だけでなくどの部分が欠損しているのか、追加されているのかといった違いを検出することもできますので差分表示が必要なケースなどでは、一つの案として検討していただければと思います。

以上です。
最後まで読んでいただきありがとうございました。


XFacebookLINE
Sky株式会社のソフトウェア開発や製品、採用に関するお問い合わせについては、下記のリンクをご確認ください。
お問い合わせ
ホーム