スポンサーサイト

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

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

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

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

■例
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月中の公開には何とか間に合いそうな感じ。



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


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

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


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

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

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

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



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