差分アルゴリズム?[閉まっている]

StackOverflow https://stackoverflow.com/questions/805626

  •  03-07-2019
  •  | 
  •  

質問

私は、効果的で効率的な diff アルゴリズムの説明を夢中で探してきました。

私が得た最も近いものは このリンクは RFC 3284 へのリンクです (いくつかの Eric Sink ブログ投稿より)、完全にわかりやすい言葉で説明されています。 データ形式 ここには差分の結果が保存されます。ただし、プログラムが diff を実行中にどのようにしてこれらの結果に到達するかについてはまったく言及されていません。

私は個人的な好奇心からこれを調査しようとしています。なぜなら、差分アルゴリズムを実装するときにトレードオフがあるに違いないと確信しているからです。差分を見て、「なぜ差分プログラムがこれを変更として選択したのか」と疑問に思うとき、それは時々非常に明らかです。その代わりに？」

最終的に VCDIFF を出力する効率的なアルゴリズムの説明はどこで見つけられますか?
ちなみに、SourceGear の DiffMerge で使用される実際のアルゴリズムの説明があれば、さらに良いでしょう。

注記：最長共通部分列は VCDIFF で使用されるアルゴリズムではないようです。使用するデータ形式を考えると、もっと賢いことを行っているようです。

役に立ちましたか？

解決

O（ND）差分アルゴリズムとそのバリエーションは素晴らしい論文です。そこから始めます。これには、疑似コードと、差分の実行に関係するグラフ走査の素晴らしい視覚化が含まれています。

論文の

セクション4 では、アルゴリズムを改良して、非常に効果的にしています。

これを正常に実装すると、ツールボックスに非常に便利なツールが残ります（そしておそらく素晴らしい経験もあります）。

必要な出力形式を生成するのは難しい場合がありますが、アルゴリズムの内部を理解していれば、必要なものをすべて出力できるはずです。ヒューリスティックを導入して、出力に影響を与え、特定のトレードオフを行うこともできます。

こちらのページには、完全なソースコード、および前述のアルゴリズムの手法を使用したdiffアルゴリズムの例。

ソースコードは、基本的なアルゴリズムに忠実に従っており、読みやすくなっています。

入力の準備についても少し説明がありますが、これは役に立つかもしれません。文字またはトークン（単語）で区別する場合、出力には大きな違いがあります。

がんばって！

他のヒント

diffの実際のソースコードを確認することから始めます。GNUはこれを利用可能。

そのソースコードが実際にどのように機能するかについての理解については、そのパッケージ内のドキュメントはそれをインスパイアした論文を参照しています：

  

基本的なアルゴリズムは、「An O（ND）Difference Algorithm and its Variations」、Eugene W. Myers、「Algorithmica」Vol。 1 No. 2、1986、pp。251-266;および＆quot; A File   比較プログラム」、Webb MillerおよびEugene W. Myers、「Software--Practice and Experience」Vol。 15 No. 11、1985、pp。1025-1040。このアルゴリズムは、「近似文字列マッチングのアルゴリズム」、E。Ukkonen、「Information and Control」Vol。 64、1985、pp。100-118。

論文を読んでから実装のソースコードを見るだけで、その仕組みを理解するのに十分なはずです。

私は diff アルゴリズムを探してここに来て、その後独自の実装を作成しました。申し訳ありませんが、vcdiff についてはわかりません。

ウィキペディア:最長の共通部分シーケンスから diff のような出力を取得するのは、ほんの小さなステップです。項目がサブシーケンスには存在しないが、元のシーケンスには存在する場合、その項目は削除されている必要があります。(以下の「-」マーク。) サブシーケンスには存在しないが、2 番目のシーケンスには存在する場合は、追加されている必要があります。(「+」マーク。)

の素敵なアニメーション LCSアルゴリズムはこちら.

高速へのリンク LCS Rubyの実装はこちら.

私のゆっくりとしたシンプルな Ruby 適応は以下の通りです。 

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Emmelaichが提供したリンクに基づいて、 Neil FraserのWebサイトで、Diff Strategiesの大まかな要約もあります。 （ライブラリの作成者の1人）。

彼は基本的な戦略をカバーし、記事の終わりに向かって、マイヤーのアルゴリズムとグラフ理論に進みます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top