スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

動的計画法による、最長共通部分列(LCS)算出、差分ファイルを作る方法!


現在、差分ファイル作成、ゲームパッチ適用プログラムを作っており、
その差分ファイルをエディットグラフで実装してみたのですが、

エディットグラフよりも、簡単なアルゴリズムがある様なので、
それもちょっと試してみました。


今回やるのは、
動的計画法による、
最長共通部分列(LCS)算出
です。


まず、最長共通部分算出についてですが、
これは、2つの文字列において、一番長い、共通の順番で出現する文字列の事です。

例えば下記の文字列があるとします。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------

この文字列の場合、LCSは「ABCDEFGI」となります。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------


で、LCSが見つかった際、
「LCSは固定で、LCS以外の文字列を追加/削除すれば
(最小コストの)差分が出る!」
という事らしい。

なので、(今回の例の)旧文字列→新文字列への変換は、
「H」を削除、2つの「Z」を追加するのが最小コストという訳です。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------


では、肝心の動的計画法のやり方を記載してみます。

■やり方
-----------------------------------------------------
【1】文字列+1の2次元配列を用意
【2】下記の条件で、要素番号[1][1]から右下へ、順に走査。
   条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
   条件2:不一致文字の場合は、上と左で大きい方の値を入れる

【3】2次元配列に格納された各値の中で、最も左上にあるものを
   一致文字とする

-----------------------------------------------------

文章だけだと分かりづらいので、
図を用いてやってみましょう。

【1】文字列+1の2次元配列を用意
-----------------------------
旧文字列:ADBCFZ
新文字列:ABDCZFZ

-----------------------------
上記の文字列があるとします。

それぞれ6文字と7文字なので、
横7×縦8の二次元配列を定義します。

【参考画像】
Sample_20140217_1.jpg



【2】要素番号[1][1]から右下へ、順に走査。
---------------------------------------------
条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
条件2:不一致文字の場合は、上と左で大きい方の値を入れる

---------------------------------------------
次に、上記条件に基づいて値を入れていきます。
※二次元配列のすべての要素は、「0」で初期化しておきます。


具体的に書くと、下記になります。
・[1][1]…どちらも「A」なので、[0][0]に1を足した値を[1][1]に入れる
・[1][2]…一致しないので、[0][2]と[1][1]を比較し
    、大きい方の値を[1][2]に入れる
・[1][3]…一致しないので、[0][3]と[1][2]を比較し
    、大きい方の値を[1][3]に入れる
・[1][4]…一致しないので、[0][4]と[1][3]を比較し
    、大きい方の値を[1][4]に入れる

//以下略

【参考画像】
Sample_20140217_2.jpg



【3】各値の中で、最も左上にあるものを共通文字とする
後は共通文字を出すだけなのですが、ここで注意点。

"最も左上"が存在しない場合があります。
今回で言うと、重みが「2」の場合です。


とりあえず、共通文字の算出をやってみましょう。
各値の"最も左上"を見つけるには、下記の手順を行います。
--------------------------------
【1】最も重みの値が大きい場所を現在位置とする
【2】重みが異なる値が出る直前まで上方向に移動
   重みが異なる値が出る直前まで左方向に移動
【3】現在位置を左へ1、上へ1(左斜め上に)変更
【4】値が0の場合は終了。そうでない場合は【2】~【3】を実施。

--------------------------------


具体的に過程を書くと、下記になります。
※下記の過程を読むよりも、図を見て、
各値で、最も左上の場所を見て行った方が分かり易いかもしれません。

--------------------------------
[7][6]を現在位置に設定(重みは5)
上/左へ移動不可。
現在位置を[6][5]に設定(重みは4)
上/左へ移動不可。
現在位置を[5][4]に設定(重みは3)
左へ移動不可。上へ1移動。
現在位置を[3][3]に設定(重みは2)
左へ1移動。上へ移動不可。
現在位置を[2][1]に設定(重みは1)
左へ移動不可。上へ1移動。
現在位置を[0][0]に設定(重みは0)
0なので終了。
--------------------------------

【参考画像】
Sample_20140217_4.jpg
※各値で"最も左上"と判定された場所に色を塗った図。


上記の図を見ると分かるかと思いますが、
LCSは「ADCFZ」になります。簡単ですね!


また、先ほど述べた「左上が無い」パターンについて。
左上が無いパターンは、下記の様に左上が欠けた様な状態になっています。

※"最も左上"があるパターン
■■■
■■■
■■■

※"最も左上"が無いパターン
□■■
■■■
■■■


この左上が欠けた場合はどうすれば良いか、というと
----------------------
・欠けた場所の1つ右
・欠けた場所の1つ下
----------------------
上記2つの内、どちらか好きな方を選べば良いです。
何故なら、書き換えるコストは変わらないからです。


■欠けた部分の1つ下を選択した場合 (LCS … 「ADCFZ」 )
Sample_20140217_4.jpg
旧文字列:ADBCFZ
新文字列:ABDCZFZ

「B」削除、「B」追加、「Z」追加 … コスト3。


■欠けた部分の1つ右を選択した場合 (LCS … 「ABCFZ」 )
Sample_20140217_3.jpg
旧文字列:ADBCFZ
新文字列:ABDCZFZ

「D」削除、「D」追加、「Z」追加 … コスト3。

上記の通り、どちらもコスト3で変わりません。


【補足】
コストは変わりませんが、書き出す差分情報は当然変わってきます。
コストを低く、かつ差分情報のファイルサイズも小さくしたい場合は、
どの文字列をLCSにするか?は考えないといけないと思われます。
(圧縮アルゴリズムとの兼ね合いにより。)


とりあえず、以上が動的計画法によるLCS算出の流れです!



あと、どうして下記の条件でLCSが求められるのか?(証明)についてですが、
----------------------------------------------
条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
条件2:不一致文字の場合は、上と左で大きい方の値を入れる
----------------------------------------------
これは、LCSが求まる際の法則をもとに、
漸化式を再帰的に解く事で答えが得られる事を証明
する必要があります。

ちょっとややこしいかもしれませんが、
証明する方法まで理解したい、という方は下記が参考になるかと思われます(_ _)
【参考URL】最長共通部分列問題 (Longest Common Subsequence)Add Star
スポンサーサイト

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

コメント
コメントの投稿
管理者にだけ表示を許可する



上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。