開発者ツール · テキスト比較
テキストの差分で変更された行を見つける方法: LCS とマイヤーズ アルゴリズム
· 仕組み
テキストの差分 アルゴリズム 開発者ワークフロー
行ベースの比較の背後にある最長共通部分列の考え方と、マイヤーズ アルゴリズムがブラウザーのタブ内であっても瞬時に実行できるほど高速になった理由について説明します。
2 つのファイル、1 つの質問: どの行が生き残ったか? — 行番号を一致させるのではなく、両方のバージョンに共通する最長の行を見つけるフレーム比較
2 つのリビジョンが、どの行が生き残ったかを示すラベルが付いていません。 ToolAcre はまず各テキストを順序付きリストに分割し、次に両方のリストに同じ順序で出現する長いサブシーケンスを検索します。共有背表紙の外側の行は、推測された変更ではなく、追加または削除になります。
結果には、両側の元の 1 から始まる位置が保持されます。変更されていない行には両側に番号があり、左側には削除のみ、右側には追加のみが含まれます。この計算により、繰り返し行が複数の妥当性を示している場合でも、表示されたストーリーを確認できるようになります。
diff が文字ではなく行で機能する理由 — 改行での分割がテキストを同等の単位のシーケンスにどのように変換するか、またそれによって散文の動作がコードと異なる理由
実装では、完全な行を比較単位として扱います。したがって、改行境界は結果を形成します。1 行に保存された段落内の 1 語の編集はその行全体を置き換えますが、同じ散文を文ごとに配置すると、はるかに小さな領域を分離できます。
行の比較は、別のディスプレイの背後に隠された文字分析ではありません。 `splitLines` は配列を作成し、LCS テーブルはある行キーを別の行キーと比較します。この予測可能な粒度はソース ファイルと構成ファイルに適していますが、一致するように見える置換内で変更された正確な文字を強調表示することはできません。
わかりやすい言葉での最長共通サブシーケンス — 5 行の例で LCS のアイデアを説明し、サブシーケンスの外側のすべてがどのように挿入または削除になるかを示します。
左側の行 A、B、C、D、E と右側の行 A、C、E が順序付けられた共通のサブシーケンスを形成すると想像してください。 B と D はその範囲外にあるため、削除された行と置換行をペアにする必要がなく、結果では 2 つの削除と 3 つの変更されていない行が報告されます。
テーブルには、残りの位置のペアごとに、そこから利用可能な最適な共有長さが記録されます。復興はその価値観を貫いて進んでいきます。等しいキーは両側に進みます。それ以外の場合は、隣接するより大きな値によって、左の削除を発行するか右の追加を発行するかが決まります。
マイヤーズ アルゴリズムと速度が重要な理由 — 最短の編集スクリプトをトレースすることで、数千行のファイルの比較を高速に行う方法を数式を使わずに説明します
ワークブックでは Myers という名前が付けられていますが、`diff.js` は単純な最長共通部分列動的プログラミングを明示的に実装しています。そのコメントには、異なる中間に対する O(n・m) 時間とメモリが記載されています。マイヤーズまたは最短編集グラフの動作を主張すると、実際に出荷されるコードの代わりに使い慣れたアルゴリズムが使用されることになります。
ToolAcre は、割り当て前にコストを制限します。等しいプレフィックスとサフィックスは線形パスで剥がされ、どちらの異なる中間にも最大 2,000 行が含まれる可能性があります。マトリックスは `Uint32Array` です。文書化されている最悪の許容正方形は、無制限のボックス化された値ではなく、約 16 メガバイトを占めます。
ToolAcre は、アウトラインで指定されているマイヤーズ アルゴリズムではなく、LCS テーブルを使用します。
「検索の追加」、「エクスポートの修正」、および「ヘルプの更新」を含む変更ログを、最初と 3 番目のエントリは保持し、最後のエントリの前に「フィルタの追加」を挿入するリビジョンと比較します。共通エントリはパスを固定し、「固定エクスポート」が削除され、「追加フィルター」が追加されます。
アルゴリズムは、そのペアを変更された行とは呼びません。その行語彙は等しい、追加、削除のみであるため、テキストの置換は 1 つの削除とそれに続く 1 つの追加として表示されます。要約では、これらの操作を個別にカウントし、両方のカウントがゼロの場合にのみテキストが同一であるとマークします。
2 つの正しい差分が異なって見える理由 — あるツールが空白行を原因とし、別のツールが閉じ括弧を原因とする同じ短い編集スクリプト間の結びつきがどのように説明されるかを示します
繰り返しまたは交換可能な行により、同じ長さの共通のサブシーケンスがいくつか生成されることがあります。 ToolAcre は、2 つの隣接するテーブル値が等しい場合に削除を優先することで 1 つの同点を解決します。別の正しい実装では、最初に追加を選択し、同じ編集コストで見た目の異なる配置を提示する場合があります。
そのため、空白行または右中括弧がツール間で異なるハンクに接続されて表示されることがあります。不一致は、自動的にどちらかの比較内容が失われたことを意味するものではありません。表現の違いを競合する事実の主張として扱う前に、元の行番号と周囲の変更されていない行を読んでください。
これでカバーされないもの — 意味論的または構造的な比較、移動検出、および単語レベルの強調表示は、行ベースの差分が計算する範囲外です。
このパスには、構文ツリーの解析、名前変更された識別子の認識、移動されたブロックのラベル付け、散文の意味の理解などはありません。移動された段落は共有順序の要件に違反しており、削除として 1 回表示され、追加として 1 回表示される可能性があります。また、このツールは行内の文字レベルまたは単語レベルのハイライトを計算しません。
これらの省略は境界であり、隠しモードではありません。セマンティッククレームには言語を認識したレビューアを使用し、マージ履歴にはバージョン管理を使用します。 Text diff は、2 つの順序付けされた行シーケンスがどのように異なるかというより狭い質問に答え、それらのテキスト編集が重要かどうかを人間が解釈できるようにします。
要点: ハイライトされた行の実際の意味 — 編集の最短のストーリーとして行の差分を読み取る方法と、ToolAcre のテキスト比較が何もアップロードせずにタブでこれを実行する方法をまとめています。
緑と赤の行は、作成者の意図の証明としてではなく、LCS から派生した 1 つの説明として読んでください。接頭辞と接尾辞のトリミングによって作業量は変わりますが、最終行の会計処理は変わりません。大文字と小文字または空白のオプションが一致のためのより緩やかなキーを提供する場合でも、元のテキストはすべての行に残ります。
比較はインポートされたブラウザー モジュールを通じて実行され、DOM テキスト ノードを使用してレンダリングされます。ツールパスに変換エンドポイントがありません。 5 行の例を試し、辺を交換し、パッチ状の出力をダウンロードして、セマンティクスを考え出すことなく、方向が追加を削除にどのように変更するかを確認します。