スポンサーサイト

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

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

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


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


文字列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を流したりして、
リラックス出来る状態にして手術する事が多かったりするらしい。

へー知らなかった!
スポンサーサイト

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

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



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