diff関数を実現するには？

StackOverflow https://stackoverflow.com/questions/236031

  •  04-07-2019
  •  | 
  •  

質問

スタックオーバーフローの質問の改訂履歴など、 diff 関数を実装するにはどうすればよいですか

役に立ちましたか？

解決

ここに、diffアルゴリズムの実装の javascriptの例があります。

ベース：

P. Heckel、ファイル間の相違を分離する手法 うーんACM、21、（4）、264--268（1978）。

実装自体には2つの関数があり、そのうちの1つを使用することをお勧めします：

diffString( String oldFile, String newFile )

このメソッドは2つの文字列を受け取り、それぞれの差を計算します。最終結果は、（oldFileからの削除とnewFileへの追加の両方を示すために）HTMLでマークアップされた「newFile」です。

他のヒント

FreeBSD diffユーティリティのコードを見つけて、それをベースラインとして使用します。ライセンスがこの種のコピーを許可している場合、車輪を再発明する意味はありません。

ほとんどのアルゴリズムは、LCSに基づいています。最長共通サブシーケンス。効率的な方法で実装するのは明らかではありません。おそらく、さまざまな言語のさまざまな実装がネット上で見つかるでしょう。

唯一の方法は、2つの文字列を形成する各文字を比較することだと思います。このようなもの：


void diff(String first,String second) {
   int biggest = (first.length() > second.length()) ? first.length() : second.length();
   for(int i = 0;i < biggest;i++) {
      //compare each char from the longest string with each char from the shorter
      // do something with them if they're not equal
   }
}

これは、私がそれを行う方法の単なるスケッチです。すべては、データをどうするかによって異なります。

修正履歴が必要な場合は、diffからホイールを再発明しないでください。すべてをバージョン管理に投入し、その差分およびログ機能を使用します。単純で線形の履歴については、 RCS のように簡単です。または、最新の大砲を投げて git を使用することもできます。

ほとんどのdiffユーティリティは、行ごとのdiffを実行します。スタックオーバーフローはワード単位の差分を行います。そのためには、 wdiff のようなものが必要です。ほとんどのバージョン管理システムでは、diffユーティリティをプラグインできます。すぐに使用できる git diff --color-words は、ここで行われていることに非常に近いものです。設定を少しいじるだけで、きれいなWebページにできるものを吐き出すことができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top