私はmeldを使ってるよ。（今はスマホだから、どれが優れてるか比べられないけど）

• バックアップと復元 - セキュリティの観点からの整合性チェック - NLP、テキスト内の同じトークンを見つけることとか

17年くらい前に、IPパケットやTCPセグメント、ネットワークイベントのペイロードをdiffするものに出会ったことがある。その時、RSAセキュリティでネットワークフォレンジックとセキュリティ分析の製品に関わっていて、CとC++のミックスで書かれていた。私が関わったプロジェクトの一つでは、ユーザーがパケットやセグメント、ペイロードをdiffできるようにする必要があったんだ。当時は、製品にサードパーティのライブラリを追加するのにすごく慎重だった。もっとその文化について書いたことがあるよ： https://news.ycombinator.com/item?id=39951673 要するに、保守的な文化のせいで、ほとんどのデータ構造やアルゴリズムは社内で実装されていた。パケットやセグメント、ペイロードのdiffアルゴリズムも社内で書いたもので、私が担当した。実装は、最長共通部分列問題に対するシンプルな動的プログラミングの解法に基づいていた。確か、最悪の場合O(mn)の時間とO(min(m, n))の空間で動いていたと思う。mとnは二つのシーケンスの長さね。もっと効率的なアルゴリズムがあるのは知ってたけど、このコードはパフォーマンスが重要じゃなかったから、誰でも理解できるようにシンプルに保つことにした。そうすれば、すぐに学べて、バグが出た時にも修正できるからね。それは次の7年間、製品が新しいものに置き換わるまでうまく機能してくれた。関連する話だけど、昔のソフトウェア開発スタイルが恋しい時もある。問題領域に深く入り込んで、それをマスターして、自分たちで解決策をデザインしていたから。でも、単純にノスタルジックになってるわけじゃないよ。現代の開発が確立されたライブラリに依存していることで、通常ははるかに大きな生産性と信頼性をもたらすことはよくわかってる。とはいえ、基礎から物を作るゆっくりとした、意図的なアプローチには独特の魅力があったと思う。

私たちは建設スケジュールのdiffを取るよ！これって、通常は巨大なガントチャート（400～700ページが普通）になる。

契約の赤入れに使われる、もっと専門的なものがたくさんあるよ。法的な分野でも、ディスカバリーの整理は非常に面倒くさいことがある。ここにはたくさんのdiffベースやdiffに似たソリューションがあるけど、ほとんどは完全に独自のもので、ドキュメントもないんだ。

DOMの変異操作を最小限に抑えること。たとえばReactでね。でもそれだけじゃないよ。

詳細な変更履歴が含まれていない、クソみたいなチップ会社のPDFデータシート。

他にもいろいろあるけど、Kubernetesみたいなインフラストラクチャー・アズ・コードの文脈ではすごく役立つよ。今日、仕事でdiffを使って、2つの異なる'docker history'の出力を比較して、契約者がベースイメージを強化するために行った変更の全体像を探ってみたんだ。

「承認」/「ゴールデンマスター」/「スナップショット」/「特性」テストは非常に役立つことがあるね。これらはほぼ同じアイデアを指しているようだ。テストが初めて成功すると、自動的に出力をファイルとしてキャプチャする。これが「承認された」出力で、コードと一緒にコミットされるか、使用しているテストシステムに保存される。次回テストが実行されると、新しい出力をキャプチャして、承認された出力と自動的に比較する。もし同じならテストは合格、異なればテストは失敗して人間がdiffを調査する必要がある。この技術は多くのデータタイプに対応している：* プレーンテキスト。* UIコンポーネントやレンダリングされたウェブページの画像。これによって、コードの変更や新しいブラウザのバージョンが予期せぬ外観の変化を引き起こさないか確認できる。* 音声処理コードによって作成された音声ファイル。* 他にテストがないコードからの大きなテキストログ。リファクタリングの際に役立つかもしれないし、偶発的な副作用が予期しないdiffとして現れることを期待できる。参照：* https://approvaltests.com/ * https://cucumber.io/blog/podcast/approval-testing/ * https://en.wikipedia.org/wiki/Characterization_test

diffアルゴリズムは驚くほど広く適用できるね。cursesは、2400ボーのターミナル画面をTUIプログラムのメモリイメージのように更新するというタスクを持っていた。（TUIはvi、nethack、メニューシステム、データベースエントリ画面、ntalkなど、何でもあり。）シンプルな解決策は画面全体を再描画することだけど、80x24は2000バイトで、2400ボーでは8秒かかる。ユーザーは、最新のキー入力から8秒も反応がないプログラムは使わないよね。だからcursesはdiffアルゴリズムとターミナル機能データベースを使って、シリアルラインで送信する最小限の更新セットを見つけるんだ。（一部のターミナルには行や文字を挿入または削除するためのエスケープシーケンスがあって、データ送信を大幅に節約できるけど、他のターミナルにはないものもある。）Reactの仮想DOMも同じアイデアだよ。du -k > tmp.duを実行すると、後でdu -k | diff -u tmp.du -を使って、どのディレクトリのサイズが変わったかを確認できる。何かが急速にディスクを埋めていて、それを止める必要があるけど、何かわからないときに非常に役立つ。sha1sum $(find -type f) > good.shasを使えば、同じようにdiffを使って、どのファイルが変更されたかを見ることができる。rsyncは、遅いまたは高価な接続の両端にある2台のコンピュータ間でdiffを計算するためにローリングハッシュを使用して、古いファイルを最新の状態に効率的に更新する。これはcursesのようなもので、ファイルに対して行われ、ターミナル機能に制限されない。rdiffはrsyncアルゴリズムを使用して、ファイルの複数のバージョンを効率的に保存する。これは一般的にソースコードを含む必要はない。重複排除ファイルシステムもこのアプローチを使用できるけど、しばしばそうはしていない。でも、Resticのようなデータバックアップシステムでは一般的だね。ユニットテストでは、ある式の結果が大きなデータ構造であるべきだと言われることが多いが、時にはわずかに異なる大きなデータ構造を生成して失敗することがある。diffアルゴリズムは、テストが失敗した理由を理解するのに非常に価値がある。py.testはこれをデフォルトで行っている。ゲノム解析は、2つのゲノムのバージョンのどの部分が同じで、どの部分が異なるかを見つけることで機能する。Gene MyersによるBLASTは、このための一般的なアルゴリズムだ。これは、種の進化の歴史を理解したり、腫瘍からのDNAにおける癌を引き起こす変異を特定したり、ひいおばあちゃんが夫を裏切った相手を発見したりするなど、非常に多くのことに役立つ。すべてのバイオインフォマティクスは、diffアルゴリズムの現実のユースケースだと言ってもいいかもしれない。これらは、転置や長い繰り返しのような難しい病理学的ケースに対処する必要がある。H.264のようなビデオ圧縮は、「モーション推定」によって大きく機能する。圧縮器は、前のフレームのどの部分が現在のフレームに最も似ているかを特定し、違いだけをエンコードする。これは、ピクセル値が画像を横切って移動する際に、明るくなったり、暗くなったり、ぼやけたり、シャープになったり、回転したりする可能性があるため、1次元のソースコードdiff問題のより難しい一般化だ。さらに、これは2次元でもある。これはある意味でcursesの問題に似ていて、画面画像を更新するために必要な帯域幅を最小限に抑えようとするものだ。

私が絶対に見逃したくない使い方の一つはテストだね。期待される結果と実際の結果の違いを理解するのは本当に貴重だから。

ツリーや構造化されたdiffで出会ったもう一つのことは、アイデンティティの概念だね。diff([{id:1,name:foo}],[{id:2,name:foo}])は、id:1のオブジェクトが削除されてid:2が追加されたことを示すべきで、idが1から2に変わったとはならない。難しいのは、そうするとdiffアルゴリズムがオブジェクトの構造を意識する必要があるから（個人的には、「このキーを含むオブジェクトはない」と言うのは、ユーザー生成データを受け入れるときにはかなり難しいと思う）。

確率的なdiffにも取り組んだことがあるけど、木構造ベースで、パースエラーに対して寛容なんだ。

pの例がマージできない理由を説明してもらえる？bの方はできるみたいだけど、タグ以外に違いが見当たらないんだよね。

JSONのスーパーセット用に木構造ベースのdiffを実装したよ。 https://github.com/gritzko/go-rdx これは結局、1次元的なもので、JSONやDOMツリーが線形テキストとして表現されるのとすごく似てる。

ちょっと気になったんだけど、BLASTより速いアルゴリズムってあるの？

彼はまだバイオインフォマティクスの分野で活躍しているみたいだね。https://github.com/thegenemyers/FASTK

ミニマルなdiffっていうのは、編集の数が最小限のものを指すんだ。編集された行の周りのコンテキストは編集にはカウントされないから、マッチしてる行だからね。とはいえ、ミニマルっていうのはあくまで代理的なもので、緩和するのが良い特性なんだ。

https://semanticdiff.com/は見たことある？

よく見ると、gitもファイルレベルで同じことをしてるんだよね。ファイルが変更されても、名前の変更を検出するから。

これらのアイデアが実際に実装された例ってある？一般的には同意するけど、「知識拡張」アルゴリズムにはたくさんの機会があるよね。