C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

ログ内検索

キーワードを複数指定する場合は半角スペースで区切ってください。
検索条件は、(AND)=[A かつ B] (OR)=[A または B] となっています。
[返信]をクリックすると返信ページへ移動します。

キーワード	/	検索条件	/
検索範囲	/	強調表示	/ ON (自動リンクOFF)
結果表示件数	/	記事No検索	/ ON
大文字と小文字を区別する

No.49388 の関連記事表示

ヒット / 1件

<< 0 >>

■49388

　Re[2]: Ｃ＃でDF.exeのような比較ツール作成での改行判断

□投稿者/ れい -(2010/05/03(Mon) 00:30:40)

■No49370 (なっとさん) に返信
> テキストファイルの比較による差分表示は、非常に難しいアルゴリズムだと聞いたことがありますが…。
> 掲示板で聞いてポンと答えが返ってくるのでしょうか。(^-^;

数学的には少し難しいかもしれませんが、
プログラム的にはそんな難しいものではないですよ。

ただ、「差分」というのが曖昧なので、
言葉の定義から入らないといけませんから、
「ポン」と返すのは難しい。

Ａ，Ｂがあって、9割一致するときに。

「Ａの内容を全部削除」して「Ｂの内容を全部追加」したとすればそれで
ＡからＢを再現できますが、「差分」とは言えません。

「Ａの内容を半分削除」して「Ｂの内容を半分追加」したとしたら
一応「差分」っぽいですが、まだまだ最適ではありませんよね。

「最も少ない編集」になるとうれしい。

で、「編集」ですが、

1　Ａのn行目に「xxx\n」を挿入
2　Ａのn行目に「yyy\n」を挿入

というのと

1　Ａのn行目に「yyy\n」を挿入
2　Ａのn+1行目に「xxx\n」を挿入

というのは「同じ結果」になります。
「同じ目的地に行くための、別の行き方」とみなせるわけです。

当然

1　Ａのn行目に「xxx\n」を挿入
2　Ａのn行目に「aaa\n」を挿入
3　Ａのn行目を削除
4　Ａのn行目に「yyy\n」を挿入

も、同じ結果になります。
(最後のパターンは明らかに「無駄な編集」が入っているので「差分」としてはよくないのですが。
これは「回り道」なわけです。

つまり、一連の編集は「経路」として捉えることが可能で、
経路は無限にあることがわかります。

文章の比較アルゴリズムは結局この無限にある編集経路のうち、
「最も短い経路」を探すアルゴリズムとなります。

ここまでわかればあとはただの経路探索アルゴリズムです。
「サラリーマン巡回」と違って「前に戻る」経路や「関係のない編集」は明らかに「無駄な編集」ですから、
初めから経路に選ぶ必要がありません。

つまりＡをＢに編集する経路において、
各編集における選択肢は「行追加」「行削除」の2通りしかないことがわかりますし、
頭から1行ずつ判定していけば十分であることがわかります。

ここまで考えた時点で探すべき経路数は2^N通りになります。(NはＡの行数です
この経路をすべて虱みつぶしに探せば最短経路を探すことができます。

頭を使うとこれをもっと小さくできます。
いろいろ有名なアルゴリズムがありますが、それは検索でもすればすぐに見つかります。
理論上最短が保証されたアルゴリズムはまだ無かったと思いますが、本当のところは知りません。

昔、.Netにジェネリックが追加されたとき、
ジェネリックの勉強を兼ねて作った差分リストのコードを持っています。

提供しますので適当に使ってください。

記事No.49367 のレス /過去ログ83より / 関連記事表示
削除チェック/

<< 0 >>

パスワード/

- Child Tree -