LCS アルゴを使用して、C++ で独自の diff を実装しています。LCS アルゴ ペーパーを見て、SES (最短編集スクリプト) を見つけようとすると、行の変更が発生することがあります。次のグラフの例では、挿入と削除のみを示しています。したがって、グラフを逆方向にたどると、水平線が削除され、垂直線が挿入されます。「c」の変更ケースがある場合はどうなりますか? 水平線の後に垂直線が続くと想定しています。つまり、削除してから挿入すると、変更と見なされます。SES を直接作成している C++ のコードは見たことがありません。グラフを作成して反転させずにSESを作成する方法はわかりませんが、O(ND)またはより良い時間の複雑さを得ることができるより良い実装があるかもしれません。LCSを実装してグラフを作成し、それをトラバースできます。SESを作成するための正確なルールを事前に知りたいだけです。この場合、削除と挿入の2つの状態を維持する必要があるようです。行と見なされます変更しますか？変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。この場合、SES を作成するための正確な規則は、行の変更と見なされるために削除と挿入の 2 つの状態を維持する必要があるように思われますか? 変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。この場合、SES を作成するための正確な規則は、行の変更と見なされるために削除と挿入の 2 つの状態を維持する必要があるように思われますか? 変更点 3,4c4,6 を取得する次のファイルを参照してください (以下を参照)。誰かがこれを行っているサンプル コードを持っている場合、特に以下に示す現在の diff バイナリ形式での diff 出力の作成に関して、参照として役立ちます。ランタイムを最大化し、そのためにスペースを犠牲にしているため、このバージョンを使用していました。
グラフの SES 逆を示す例のグラフを含むドキュメントの 3 ページを参照してください。
http://www.xmailserver.org/diff2.pdf
Linuxで通常の差分を使用した変更差分の例
fileA.txt
a
b
c
d
e
f
g
fileB.txt
w
a
b
x
z
y
e
diff fileA.txt fileB.txt
0a1
> w
3,4c4,6
< c
< d
---
> x
> z
> y
6,7d7
< f
< g