スポンサーサイト

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

テキスト差分アルゴリズムの実装方法

テキスト差分アルゴリズムはどのように実装すれば良いのだろう
と悩んでいたのですが、

ある程度やり方が確立出来て来たので、その方法を書いてみます。

~やり方~
【1】変更前、変更後それぞれの文字単位での出現数をカウント
【2】変更前、変更後での、文字の増減を算出
【3】任意の場所で、文字列を分割
【4】分割した変更前、変更後での、文字単位での出現数をカウント
【5】分割した変更前、変更後での、文字の増減を算出
【6】手順5と、手順2の増減を比較。比較結果に応じて、
   分割した境界をずらす
【7】分割された文字列に対して、手順1~7の操作を繰り返す


文章だと意味分からないですね。
具体例を書いてみます。

例:
変更前(ファイルA):ABCDEFZZ
変更後(ファイルB):ZZABCDEF


■手順1、手順2(文字をカウント。増減を出す)

まず文字の出現数をカウントします。
   前   後
A: 1個  1個  = 増減なし
B: 1個  1個  = 増減なし
C: 1個  1個  = 増減なし
D: 1個  1個  = 増減なし
E: 1個  1個  = 増減なし
F: 1個  1個  = 増減なし
Z: 1個  1個  = 増減なし


増減はありませんね。


■手順3~5(分割、分割後の増減を出す)
変更前(ファイルA):ABCD    EFZZ
変更後(ファイルB):ZZAB    CDEF


とりあえず、左半分を調べます。

   前   後
A: 1個  1個  = 増減なし
B: 1個  1個  = 増減なし
C: 1個  0個  = 1個減少
D: 1個  0個  = 1個減少
Z: 0個  2個  = 2個増加


で、これを分割前の増減と比較します。
※分割前は、どれも増減なしだったので、
C,Dが減少、Zが増加した
事になります。


■手順6(分割結果に応じて、境界をずらす)
自分が実装した差分作成アルゴリズムでは、
この境界変更こそが要です。

では、やっていきたいと思います。
比較結果では、C,Dが減少、Zが増加していました。

これはどういう事かと言うと、
-------------------------------------------
■分割したら文字数が減少した
⇒必要な文字が、変更後の右側に含まれてしまった

■分割したら文字数が増加した
⇒必要な文字が、変更後の左側に含まれてしまった

-------------------------------------------
↑こういう事になります。

つまり、減少している文字がある場合は、
変更の境界を左へ
ずらします。

変更前(ファイルA):ABCD    EFZZ
変更後(ファイルB):ZZAB    CDEF

        
変更前(ファイルA):AB      CDEFZZ
変更後(ファイルB):ZZAB    CDEF



そして、増加している文字がある場合は、
変更の境界を左へ
ずらします。

…と言いたいところですが、
今回の場合、「Z」を同じ分割グループに入れようとすると、
「A」「B」が異なる分割グル―プに属する事になってしまいます。

つまり、単純に考えると、
A削除、B削除、A追加、B追加、でコストが4つ増えるのです。

なので、今回は割に合わないので、
「Z」の方の境界変更はしません。

変更前(ファイルA):ABCD    EFZZ
変更後(ファイルB):ZZAB    CDEF

        
変更前(ファイルA):AB      CDEFZZ
変更後(ファイルB):         ZZABCDEF

↑ABのコストが増えるからダメ。

■手順7(今までの操作を繰り返す。)
境界の変更が終われば、
後は再帰的に分割された文字列をまた分割…という風に繰り返していきます。

※アンダーバーは空白を意味します。
つまり、下記の様に記載されていれば、空白⇒Z(Zが1個増加、の意味になります)
_


また、下記の様に記載されていれば、Z⇒空白(Zを1個削除、の意味になります)

_


■その後の処理
変更前(ファイルA):A  B     CDEFZZ
変更後(ファイルB):ZZ AB    CDEF

変更前(ファイルA):_ AB    CDEFZZ
変更後(ファイルB):ZZAB    CDEF

変更前(ファイルA):_ _ AB    CDEFZZ
変更後(ファイルB):Z Z AB    CDEF

変更前(ファイルA):_ _ A B    CDEFZZ
変更後(ファイルB):Z Z A B    CDEF

変更前(ファイルA):_ _ A B    CDE FZZ
変更後(ファイルB):Z Z A B    CD EF

変更前(ファイルA):_ _ A B    CD EFZZ
変更後(ファイルB):Z Z A B    CD EF

変更前(ファイルA):_ _ A B  C D EFZZ
変更後(ファイルB):Z Z A B  C D EF

変更前(ファイルA):_ _ A B  C D EF ZZ
変更後(ファイルB):Z Z A B  C D E F

変更前(ファイルA):_ _ A B  C D E FZZ
変更後(ファイルB):Z Z A B  C D E F

変更前(ファイルA):_ _ A B  C D E F ZZ
変更後(ファイルB):Z Z A B  C D E F _

変更前(ファイルA):_ _ A B  C D E F Z Z
変更後(ファイルB):Z Z A B  C D E F _ _


上記を見ても分かりますが、
最終的に、先頭にZを2つ追加、最後のZを2つ削除という結果が出ます。

これが自分の実装した差分ファイル作成アルゴリズムの概要です。
この方法を説明している参考文献が見当たらなかったのですが、
あまり確立されていない方法なのだろうか?
(処理速度が遅くて実用されてないのかもしれないけども)

確立されてなかったら、
文字列分割法とでも名付けておこう。
スポンサーサイト

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

コメント

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

No title

報告ありがとうございます。

ひとまず、下記の対応をいたしました。
------------------------------------------
・フィードを取得しているブログパーツを撤去
・1ページ当たりの表示記事数を5件⇒3件に変更
------------------------------------------
ページの重さが、多少緩和されるかと思われます。

※下記のサイトで原因を解析した結果、
 フィード取得のブログパーツが速度低下の一因でした。
■SRC速度測定
 http://sp.longseller.org/

また、リンク切れでダウンロード出来ない件についてですが、
半永久的にデータを配置できる場所に移しなおして対応したいと思います。

対応完了した際、また報告致します。
※FC2ショッピングカート というサービスを利用予定です。

>とおりすがり さん
参考となるページの記載、ありがとうございます!
ソースコードなども記載されている様なので、大変参考になりますv-411

エディットグラフというものを使用するのと、自分の文字列分割での実装方法と、
どちらが高速に動作するかも比較してみたいと思います。


…それにしても、参考文献の数はやはり少ないですね。

自作ゲームのパッチを配布しているサークル様は
どういう対応をしているのか、気になる所ですv-293

No title

差分ではなく、単純に上書きにしているのかもしれませんね。

No title

おおー軽くなった~
ずっと気になってたんだよねこの重さ

No title

記事をさかのぼって読みました。すでにアルゴリズムなどはご存知だったのですね。すみません。^^;
でも普通は、ゲームなどのパッチはテキストではなくバイナリですよね?わかりやすくテキストで説明されてるのでしょうか。
パッチを配布しているサークルは、フリーソフトを使用しているのではないでしょうか、自前でやってるのかな?
あと一応以下のページもみつけたので貼っておきます。既に知ってたらごめんなさい。
http://ohwhsmm7.blog28.fc2.com/blog-entry-121.html

No title

>skさん
良く考えたら、上書きするのが一番単純な方法ですね…!v-411
(旧exeを新exeで書き換え)

その場合は、パッチファイルにVerUp版のexeファイルを埋め込む事になると思われるので、
もしかしたら、パッチファイルからVerUp版のexeファイルのみ抜き出される可能性があるかもしれないですね。。

ある程度、旧exeの情報がないと新exeが生成出来ない様にしておいた方が良いのかもしれませんv-293

No title

> さん
PCに負担がかからなくなったようで、良かったです…!
フィード取得のブログパーツが負担をかけていたようですねv-393

必要以上のブログパーツは追加しない様に
気を付けたいと思いますv-411

No title

>とおりすがり さん
自分も記事を読み返してみたのですが、
アルゴリズムが全く見当も付いていない状態にしか見えないですねv-292

紛らわしくてすみませんorz

前後の繋がりがある様な記事を作成する際は、
前回把握していた情報なども記載してみようかと思いますv-411

あと参考URLについてですが、
これは知りませんでした…!

ネット経由で自動更新という手法もあるのですね。
…良く考えたら、
「パッチを公開しました。
お手数ですが、パッチを当てて下さい」
という方法よりも、起動した時点で自動的に更新してくれた方が
ユーザーにとって負担はかからない
ですね…!

実装してみたいですが、
いかんせん時間がかかりそうなのが難点ですv-393
コメントの投稿
管理者にだけ表示を許可する



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