スポンサーサイト

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

差分生成プログラム(試作版)の説明ページ

こちらは、差分生成プログラム(試作版)の説明記事になります。


※今日あたり、差分ファイル生成、パッチ適用プログラムをUPします。
 少々お待ちください。


<追記予定!>

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

動的計画法による、最長共通部分列(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

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

巨大文字列の場合の、差分ファイル作成プログラム実装完了!

前回、文字列が長すぎると、
エディットグラフを分割しないといけない
→分割したら正常に差分が取れない

という問題が発生していたのですが、

■例
AAAABBBB
BBBB

4文字ずつに区切ってエディットグラフを生成すると、
「AAAA」を削除。
「BBBB」を追加。
「BBBB」を追加。
という結果が出る。

最大8文字までのエディットグラフを生成する場合は、
「AAAA」だけを削除、という正しい結果が得られる。



(非効率かもしれませんが)
解決方法を見つけました。


やり方は簡単で、
例えば1000文字ずつエディットグラフを生成する場合、
後半3分の1程度の結果を破棄します。

例えば下記の文字列があるとします。
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN

15文字ずつに区切った場合は、下記の結果が得られます。
AABCDEFGHIJKLMN
AABCZZDEFGHZZMN  IJKLMN

一致した文字は「AABCDEFGHMN」の11個なのですが、
約3分の1程度後退した所までを確定結果とします。(11 - (11 / 3) = 8文字)

つまり、「M」「N」まで一致した(11文字一致した)という結果が出たものの、
8文字目の「G」の所まで巻き戻り、「G」以降は未確定扱いにします。

AABCDEFG    HIJKLMN
AABCZZDEFG  HZZMNIJKLMN

で、未確定扱いになった「H」より後ろの文字列を
また等間隔(今回は最大15文字)でエディットグラフを生成します。

すると下記の結果が得られます。
AABCDEFG    HIJKLMN
AABCZZDEFG  HZZMNIJKLMN


3分の1後退しなかった場合と比べて、
精度の良い結果が出ている事が分かると思います。

■後退しない場合
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN

■後退した場合
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN



この"3分の1程度"というのが、何とも
論理的ではなく
スマートじゃないなとは思ってる
んですが、
現状では、この実装で行こうと思っています。

※一致部分を検出した際、下記の様になる理由は一応あります。
-------------------------------------------
始端 … ほぼ確定でOK
終端 … 未確定にした方が良い場合が多い。
-------------------------------------------
始端の方は、言わば
何百、何千も先の文字列まで確認して出した結論であり、
これが覆る事は確率的にまずないのです。

具体的にいうと、
下記の場合、1000文字以降に新文字列と一致する「ABC」があったとしても、
一致させる場合は、ABCZZZZZZZZ…の1000文字を削除しないといけません。

旧:ABCZZZZZZZZZZZZZZZZZZ… // 中略(1000文字程度) //… ABC
新:ABC

つまり、削除する1000文字の中に、一致する文字が3つ以上あった時点で、
非効率である事が確定
します。
(今回の場合は、旧文字列の初っ端に「ABC」が存在するので、
その時点で1000文字先の「ABC」と一致させるのは非効率である事が確定。)

"似通ったファイルを比較している"場合は、
1000文字の中に全く
一致する文字が出現しない可能性は極めて低くなる
為、
始端の文字列はほぼ確定して良いのです。

(むしろ、「1000文字先まで確認しても、似た文字の並びが全く出現しない」場合は、
 それは"似通ったファイル"ではないと思う。)


逆に終端の場合を考えてみます。
下記の様に、「AAAAAA」を削除、「DDDDDD」を追加という結果が出ており、
「Z」と、終端の「B」が一致しているとします。
※「DDDDDD」「EEEEEE」は、まだ一致検出の対象になっていない領域とする。

ZAAAAAAB DDDDDD
ZDDDDDDB EEEEEE



この場合、
・「AAAAAA」6文字の中に、2文字以上一致する箇所が、次の領域の近くにある
・「DDDDDD」6文字の中に、2文字以上一致する箇所が、次の領域の近くにある


どちらか一方を満たしていれば、
「AAAAAA」「DDDDDD」を追加/削除するのは非効率
である事が確定します。
(今回は近くに「DDDDDD」(6文字一致)があるので、非効率である事が確定。)


要は、一致する文字を確定する場合も、
一致した文字を未確定の状態に戻す場合も、
-------------------------------------------------------
・追加/削除を確定した文字の内、一致する文字が存在する確率
・その一致した文字が、現在の一致文字よりも多くなる確率
  (一致させるために行う追加/削除のコストが低くなる確率)

-------------------------------------------------------
この2つの確率を見比べている訳です。

(で、その確率からして、
始端 … ほぼ確定でOK
終端 … 未確定にした方が良い可能性高

という傾向が出て来る。)


この確率(期待値?)を上手く算出する計算式を作ることが出来れば、
「無条件で、とりあえず終端近くの3分の1くらいを未確定にする」という、
あやふやな対処法から脱却出来そうな気はする。

改良出来たら、改良してみようと思う。
ひとまず、2月中の公開には何とか間に合いそうな感じ。



~今日のひとこと~
無免許で車を運転しても、
罪に問われない場合ってあるらしい
ですね。


そもそも、「運転免許」というのが、
-------------------------------------------------------------------
"公道において"、自動車および原動機付自転車の運転を認める許可のこと。
-------------------------------------------------------------------
らしく、

言い換えれば、
"公道ではない所"(周囲から隔絶された私有地内 / 敷地内など)の運転に関しては、
特に効力を持って無い
ようなのである。


なので、第三者が全く入って来れないような、
隔離された広大な私有地
がある場合、その私有地内で車を運転しても問題無いらしい。

それで運転の練習をして、教習所では実技をらくらく突破する人も居るんだとか。
なるほど…。法律の穴というか、盲点?みたいな話で面白いと思いました。

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

エディットグラフの実装完了!

エディットグラフの実装が完了しました!
※やはり、一部バグがあって修正→バグ発見→修正を幾度か繰り返しました。


ただ、致命的な欠陥があって、
長すぎる文字列の差分が取れない。


文字列A(5文字)と、
文字列B(10文字)があるとして、
それに必要なエディットグラフの生成は5×10=50のサイズの2次元配列が必要です。

これぐらいなら問題ないんですが、
差分を取るファイルのサイズは300万とかあるのです。

簡単に計算すると…
300万×200万 = 6兆

6兆の要素数を持つ2次元配列を用意する
必要があります。

うわーなんだコレ。
桁外れすぎて、ギャグの領域。  無理。


なので、「じゃあ10×10のエディットグラフを繰り返し作成して、差分取ればいいや」
と思ったんですが、これだと差分が取れない。

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

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

それぞれの最初の10文字を比較すると、
「TTTTUUUUPP」を削除、「AAAAAAAAAA」を追加という結果がでます。

そして、旧文字列は後続の文字が無いので比較を終了し、
新文字列の余った「TTTTUUUUPP」は追加するものとします。

するとどうなるかというと、最終的に
-----------------------------------
旧文字列:「TTTTUUUUPP」を削除
新文字列:「AAAAAAAAAA」を追加
新文字列:「TTTTUUUUPP」を追加
-----------------------------------
という結果が出ます。

これ、間違っています。
旧文字列に「AAAAAAAAAA」を追加するだけ、が正解です。


エディットグラフのサンプルが記載されているサイト見てみたのですが、
大抵、短い文字列の比較ばかりで、巨大な文字列の場合の対処法が書いてない。
(自分が見落としている可能性もありますが)

うーむ。
"一致する可能性が高い、短めの範囲"を見つけて、
その範囲でエディットグラフを生成
すればいいのかな…?

難しいとは思っていましたが、想定を超える難易度。

とりあえず、対処法が見つかり次第、
エディットグラフ含め、全般のアルゴリズムの解説記事を書く予定。
目途が立つまで、アクションゲーム制作を進めよう!


~今日のひとこと~
ドラマとかでは、緊急手術で「メス!」とか物々しい雰囲気で言ったりしてますが、
実際は、クラシック音楽などのBGMを流したりして、
リラックス出来る状態にして手術する事が多かったりするらしい。

へー知らなかった!

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

ネットショップを作ってみた(既存サービス)

自作ゲームを販売する為のネットショップを作ってみました。
※今回は、FC2ショッピングカートというサービスを利用。


↓早速、商品を一個 置いてみた。

【参考画像】
Sample_20140122_1.jpg


フリーでダウンロード出来る様に0円にしてみたのですが、
どうもダウンロードの流れがこうなるっぽい。

--------------------------------------
【1】商品をカートに入れる
【2】レジへ進む
【3】名前、住所、電話番号、メールアドレス、決済方法を入力
   ※全部必須。また決済方法は現状、銀行振込のみ。
【4】銀行振込を確認したら、管理画面で「入金済」フラグを立てる
【5】商品を発送した旨を伝える際、「発送済」フラグを立てる
   (購入者が入力したメールアドレスに、発送メールが届く)
【6】ダウンロードURLを購入者に送信(手動で行う)
【7】購入者は、ダウンロードURLが記載されたメールより、
   商品をダウンロード

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

何か…とても煩雑です。
なにこの人力?

要は、こちらが管理画面を監視して、
注文があった事を確認し、ダウンロードURLを送信するボタンを押さなければ、
商品は購入者のもとに届かない。


う…ちょっと想像してたのと違う。
手続きがこんなに厳格になっているなんて。


フリーでダウンロード出来る様にしたいだけの場合は、
ちょっと別の方法を探した
方が良いかもしれない。

いや、むしろ本格的に商品を販売する事になった場合も、
別の決済代行サービスを使ったりしないと、多分、一人じゃ対応できない。
別の方法を探してみます。

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



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