2つの異なる時点でのディレクトリ構造のスナップショットを表す2つのツリー構造があります。スナップショット間でディレクトリが追加、削除、または変更された可能性があります。2つのツリーを同時に歩き、2つの違いで新しいものをマークする必要があります。つまり、ノードにNew、Modified、Deleted、Unchangedのフラグを付け、削除されたノードを追加して、最終結果が2つのスナップショットの完全なスーパーセットになるようにします。
通常、ツリーは約10の深さですが、非常に幅が広く、数十万、場合によっては数百万のノードが含まれている可能性があります。各ノードでハッシュコードを比較し、コードが一致しない場合にのみ再帰を続けることで、ツリーの大きなチャンクをスキップしたいと思います。
ここで私の友達になる可能性のあるアルゴリズムはありますか？他に何かアドバイスはありますか？
Lindholm、Kangasharju、および Tarkoma による論文「Fast and Simple XML Tree Differencing by Sequence Alignment」には、いくつかのヒントがあります。
1) rsync は、あなたが興味を持っているようなことをします。http://samba.anu.edu.au/ftp/rsync/rsync.htmlを見てください。 rsync --list -聞こえることだけを行います。
2) トリックの 1 つは、ツリー階層を深さ優先検索でトラバースしてシーケンスに変換し、2 つのシーケンスを比較することです。ハッシュ コードの比較に関するアイデアは、ローリング ハッシュ ( http://en.wikipedia.org/wiki/Rolling_hash ) を使用して実装できます。
仕事を段階的に実行しようとするのではなく、最終的に 2 つのシーケンス全体を生成し、それらの間で diff または xdelta に相当するものを実行することになると思います。一部のサブディレクトリがツリー構造内で大きく移動すると、完全にインクリメンタルなアプローチで問題が発生する可能性があります。
各ツリーをファイルとディレクトリのソートされたリストに展開することを想像してください。メソッドは、そのツリーのインターレーターから展開された各ツリーから次の入力を取得できます。次に、ハッシュ コードを比較し、いずれかのツリーをスキップして、削除をメモし、変更をメモすることができました。