☰

commとdiffは入力/出力レベルで何を達成しようとしていますか？

tag-icon • tag-icon text-processing diff version-control math comm
commとdiffは入力/出力レベルで何を達成しようとしていますか？

2つのファイルが与えられたら、各ファイルの各行に対して実行する方法commそしてdiff決める

  • この行が他のファイルにも表示されますか？
  • もしそうなら、両方のファイルで同じように表示されますか、それとも別々に表示されますか？

各ファイルの行間の順序を考慮しますか？

diff「2つのファイルでは発生しますが別の行」または「1つのファイルでは発生しますが、別のファイルでは発生しません」を確認する方法は？

両方のファイルを減算するために両方が使用されている場合はcommどう違いますか？diff

ありがとうございます。

（一部の初等数学に興味がない場合は、以下を無視してください。上記は、私の質問に関する限り独立しています。）

私は推測する:

数学では、セットは要素間に順序を付けません。 （このようなセットをシーケンスセットと呼びますが、これは別の概念です）

  • 「Ｓ１〜Ｓ２」、すなわち、２つのセットＳ１とＳ２の差分セット演算は、第１セットの要素セットを生成するが、第２セットの要素セットは生成しない。

  • 両方のセットの交差点を見つけるときに要素が両方のセットで考慮される場合、各セット内でその要素が表示される場所は重要ではありません。

ファイルに違いを設定するなどの操作もあります。commcoreutilsからそしてdiffdiffutilsから。ただし、ファイルを行セットとして考えることはできませんが、行は自然に行番号でソートされるため、ソートされた行セットと考えることができます。

また、さまざまな方法で作業しますcomm。diff

概念レベル（入力レベルと出力レベル）でそれぞれ実行されているタスクcommと実行したいタスクは何ですかdiff？数学的にも説明できれば、より明確になります（注文セットに関する基本的な知識が必要な場合があります）。実装レベルでは説明を期待していませんが、役に立ちます（一部のバージョン管理およびバックアップソフトウェアは増分コピーに同じまたは類似のアルゴリズムを使用します）。

ありがとうございます。

答え1

ここに記載されているように。 https://en.m.wikipedia.org/wiki/Diff

「diff演算は、最も長い共通部分修飾問題を解くことに基づいています。」

コメントで指摘したように、わずかに異なるバリエーション（diff、gdiff、vimdiff、git-diff、rdiff-backupなど）を持ついくつかの実装があります。 LCS Wikiページには、あなたが要求した数学的な定義があります。 2つのソートされたセットからすべてのLCSを減算すると、その差が残りになります。

答え2

実装の一般的な問題diffは、削除または挿入が検出された後に次の共通テキストブロックを見つけることです。

有用な結果を得るには、実装時に共通コードが1行後に再同期を検出するのか、それともより多くの共通コードが必要かを判断する必要があります。

その理由は、挿入後にすでに存在する行と同じ単一の行を挿入に含めることができるためです。単一の同じ行が再同期を検出するために使用される場合、diff出力は、予想されたものとは異なる複数の挿入にフラグを立てます。

しかし発見最も長い共通文字列アルゴリズムではなく問題であり、問​​題に対する解決策（アルゴリズム）がいくつかあります。

findこのコマンドは、Douglas McIllroyが1974年にUNIX用に作成した元のアルゴリズムを使用します。

もう1つの有名ですがまったく異なる実装（別のアルゴリズムを使用）は、1980年代後半に誰かがGNU用に書いていました。

再同期化アルゴリズムが完全に異なるため、両方の実装は場合によっては異なる結果を提供することが知られています。

diffUNIXが最小コードサイズの元の最適化を使用していた限り、GNUはUNIXよりも高速でしたが、diff数diff年前、私はdiffUNIX実装の最適化をコードサイズに関係なくできるだけ早く変更しました。一般的な目的でUNIXを使用している限り、ファイルサイズに応じてUNIXはdiffGNUより高速です。diff

Douglas McIllroyが使用したアルゴリズムは、彼の大学のホームページに文書化されています。http://www.cs.dartmouth.edu/~doug/diff.pdf

興味深いことに、diffを見つける反対のプロセスは、diff出力を使用して元のファイルにパッチを適用してファイルの新しいバージョンを取得することです。

SCCSこの問題に対する最初の解決策は、1972年にBell LabsのMarc J. Rochkindが発明したプログラムでした。彼の説明を見てください。http://sccs.sourceforge.net/sccs_invention.htmlsccsホームページから：http://sccs.sourceforge.net/diffの必要性のために、sccs1974年以前は古くなっていましたが、あまり賢くない実装がありましたdiff。

すべての可能なバージョンのストリームを単一のファイルに含めることができるため、ファイルのパッチを回避するSCCS非常に賢いファイル形式を使用してください。weaveファイルから単一のランダムバージョンを抽出すると、抽出したいweaveバージョンによって時間が変わらず、常に同じ速度で完了します。

関連情報