スポンサーサイト

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

差分ファイルの作り方を調べてみた

今日の報告!

「チルノのパーフェクトにほんご教室!」の最新Verへのアップデートを行う為に、
パッチ作成プログラムを開発中だったりします。
※これが完成しないと、アップデートが出来ない。


このパッチ作成プログラム(exeファイル)についてですが、
下記の様にしようと思っています。
---------------------------------------------------
・商業利用 / 個人利用問わず使用可能
・当ブログへの報告不要
・無償で配布

---------------------------------------------------
(更に、プラスアルファの機能を付ける予定)


※その代わり、パッチを当てた際は、
「使用して頂き、ありがとうございます」みたいなWebページに飛ばす予定。
Webサイトを開くのには、ShellExecute関数を使えば良いのだそうだ。

■例
//Googleのページが開く!
ShellExecute(NULL, "open", "https://www.google.co.jp/", NULL, NULL, SW_SHOWNORMAL);




また、現在、実行ファイルをバイナリとして開き、
表示させるプログラム
を作ってみました。
実行結果は下記の様な感じ。

【参考画像】
Sample_20131219_1.jpg

全く同じようにも見えますが、良く見るとやっぱり違う部分がありますね。
これを上手く書き換えるプログラムを作る必要があるのです。


で、書き換えるアルゴリズムは?というと、
エディットグラフというものを作るのだそうだ。

※例えば、下記の文字列A,Bがあり、
文字列Aから、文字列Bに書き換えるとします。
-----------------------------
文字列A: abfed
文字列B: azbed

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

この場合、
書き換える前の文字列Aを縦方向
書き換えた後の文字列Bを横方向に記載し、
格子状の図を作ります。

そして、図の左上をスタート地点とし、
下記のルールに従って、線を引いていきます。
---------------------------
文字の追加: 右へ移動
文字が同一: 右斜め下へ移動
文字の削除: 真下へ移動

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

【参考画像】
Sample_20131219_2.jpg

線を引く方法(文字列Aから文字列Bに書き換える方法)
は、複数パターン
があります。

まずは、これ。
■方法1
a,b,e,dはそのまま、zを追加し、fを削除する


この場合、エディットグラフには
下記の様に線を引く事になります。

【参考画像】
Sample_20131219_4.jpg

次に、下記の方法2、方法3でもやってみましょう。
-----------------------------------
■方法2
adfedを全部削除。その後azbedを追加

■方法3
azbedを追加。adfedを全部削除。

-----------------------------------
すると下記の様になります。

【参考画像】
Sample_20131219_5.jpg


ここで、エディットグラフでの共通点が出て来ます。
どの方法を採っても、線は左上から始まり、右下で終わります。

また、コストと線の長さについて考えてみます。
-----------------------------
文字列A: abfed
文字列B: azbed

-----------------------------
上記の文字列Aを文字列Bに書き換える場合、
方法1~3で一番コストが少ないのが、方法1です。
(aの後にzを追加して、fを削除すればOK。)

エディットグラフの線の長さを見てみます。
斜線の長さを1.4とすると、長さはそれぞれ下記になります。
---------------------------
方法1 … 7.6
方法2 … 10
方法3 … 10

---------------------------
一番手間の少ない方法1の線の長さが、一番短くなっていますね。

つまり、
効率良く文字列Aを文字列Bに書き換える方法は、
エディットグラフの左上から右下への
最短経路を求める事と同義
なのです…!


いや、発想が凄い。
よくこんな方法を思いついたな、と。

とりあえず、差分を求めるアルゴリズムは、
上記のエディットグラフを作成し、最短経路を求める
事で実装出来る様です。
(他にも「文字列の共通部分を見つけ出す方法」もあるらしい。)


参考になりそうなURLを纏めてみる。

【参考URL】文書比較(diff)アルゴリズム
【参考URL】diffの動作原理を知る~どのようにして差分を導き出すのか
【参考URL】レコメンデーションとエディットグラフ

今日の報告は終わり。 以上!!
スポンサーサイト

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

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



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