開発者ツール · テキスト比較
Unix の差分の短い歴史: ハント、マキロイ、およびラインベースのモデル
· 背景
テキストの差分 アルゴリズム ソフトウェア履歴
1970 年代のベル研究所から今日のツールまでの差分を追跡し、テキストを行ごとに比較することがなぜ標準になったのか、そしてその後のアルゴリズムがそれをどのように改良したかを説明します。
「何が変わったのか」のすべての画像が Unix の差分のように見える理由 — コード ホスティング サイト、レビュー ツール、ブラウザ ツールがすべて同じモデルを継承しているという観察から始まります
最近のレビュー画面では、多くの場合、変更されていないコンテキスト、削除、追加の視覚的な文法が共有されています。この類似点を完全な系統ストーリーに変えたくなる誘惑に駆られますが、このリポジトリは Unix の歴史の主要なアーカイブではなく、ToolAcre の現在の実装の証拠です。
したがって、安全品では 2 つのタスクが区別されます。現在の情報源が何を証明しているのかを詳細に説明し、ブックの歴史的な名前、日付、動機を外部の信頼できる参照が必要であるとマークします。特にアルゴリズムの著者については、知名度は引用の対象にはなりません。
ベル研究所とファイル比較の問題 — 初期の Unix でソース ファイルを比較する必要性と、ダグラス マキロイとジェームス ハントの研究について説明します。
概要では、初期の研究はベル研究所の数字によるものであるとしています。 4 つの Text diff ソース ファイルにはその歴史が記載されておらず、創作または引用されていない主張は禁止されています。したがって、このモジュールでは、確定した事実として伝記の詳細、引用、日付を繰り返しません。
今後の歴史記事では、論文、マニュアル、または機関アーカイブを直接引用する必要があります。これらのソースが証拠セットの一部になるまで、修正は明示的です。ToolAcre は現在 line-diff モデルを実証できますが、モデルの起源のストーリーのすべてのステップを認証することはできません。
Bell Labs の著者と初期 Unix の歴史には、このリポジトリに存在しない外部の一次ソースが必要です
現在のコードは、正規化された改行規則に基づいて分割し、行の配列を比較します。この事実が今日の粒度を説明しています。実装には歴史的な資料がインポートされていないため、テレタイプやストレージの制約が歴史的な設計上の選択を引き起こしたことは証明されません。
この区別は学問を超えて重要です。 「このツールはライン上で動作します」はテストで再現可能です。 「線路はこの歴史的な理由で選ばれた」という因果関係の主張には、当時の文書が必要である。優れたテクニカルライティングでは、現在のコードを過去の意図の遡及的な証拠として使用しません。
リポジトリは、ToolAcre が行を比較することを証明しています。歴史的なシステムがなぜそれらを選んだのかは証明されていない
`toUnifiedText` は、`---` ラベルと `+++` ラベルの後に、スペース (マイナスまたはプラス) が接頭辞として付けられたすべての行を出力します。これはパッチ形式でダウンロードに便利ですが、`@@` ハンク ヘッダーは含まれていません。これを完全に統合された diff と呼ぶと、ここで実装されている形式が誇張されてしまいます。
ルートは、通常のフォーマットまたはコンテキスト フォーマットも生成しません。これらの形式の歴史的進化は外部マニュアルで説明する価値があるかもしれませんが、出荷された出力は、より狭い説明、つまり、使い慣れたマーカーと呼び出し元が提供したラベルを備えた読み取り可能な全行ストリームをサポートしています。
ToolAcre は、完全な履歴の差分形式ではなく、パッチ状のストリームをエクスポートします
概要には、最新のエンジンは Myers を使用していると記載されていますが、ToolAcre は使用していません。そのファイル ヘッダーにはプレーン LCS 動的プログラミングという名前が付けられており、異なる中間での O(n·m) 時間とメモリが文書化されています。この実装は `Uint32Array` テーブルを埋め、それを通る 1 つのパスを再構築します。
これは表面的な修正ではありません。アルゴリズム名には、特定の複雑さと動作が関連付けられています。プレフィックスとサフィックスのトリミングと 2,000 ライン キャップにより、このデザインは境界のある貼り付けられた差分に適しています。読者は、マイヤーズの複雑さの主張を二次行列を含むコードに移すべきではありません。
ToolAcre は Myers ではなく、プレーンな LCS 動的プログラミングを使用します
行ベースの比較では、意味上の等価性、移動されたブロック、または書式設定の意図を識別できません。これらの制限は、順序付けされた文字列キーから直接生じます。コンパイラは、行 diff が置換を報告する間、2 つのソース フラグメントを同等であるとみなしたり、積極的な正規化ではその逆を考慮したりすることがあります。
元のモデルは、その結果が検査可能であるため、依然として有用です。各行にはテキスト、タイプ、およびサイド固有の行番号が含まれます。査読者は、すべての行を考慮しながら、整合性に同意できない可能性がありますが、不透明な「意味が変わった」スコアの場合はさらに難しくなります。
これでカバーされないもの — バイナリ比較、デルタ圧縮、およびバージョン管理の内部機能
バイナリ デルタ、圧縮、リポジトリ オブジェクト ストレージ、およびマージ内部は、このルートと証拠セットの両方の外にあります。この記事では、要求された歴史年表も記憶から埋めるのではなく省略しています。検証されていない主張を公表するよりも、主張を見逃した方が望ましいのです。
これらのトピックについては、説明されているシステムから主な仕様とソースを収集してください。見た目の類似性からファイル形式を推測したり、「最小限」という言葉からアルゴリズムを推測したりしないでください。 ToolAcre の設定ではその単語が使用されていますが、実装ではそれを修飾する正確なメカニズムが提供されています。
要点: 50 年にわたる 1 つの良いアイデア — 系譜を要約し、ToolAcre のテキスト比較がブラウザー タブで同じ行ベースのモデルを適用することを示しています。
永続的な教訓は方法論的なものであり、歴史を実装から切り離すことです。このブラウザ ツールは、正規化された行分割、LCS 再構成、明示的なオプション、異なる行のキャップ、およびローカル レンダリングを証明します。周囲の慣例を誰が、あるいはなぜ発明したのかを証明するものではありません。
ルートを使用して現在のテキストを検査し、一次情報源を使用して過去を伝えます。この境界により、歴史的記事の包括性が損なわれる可能性がありますが、含まれるすべての記述が監査可能になります。正確さは、引用されていない回想から組み立てられた洗練された系譜を上回ります。