17

2 つのファイル ツリー A と B が与えられた場合、 A を B に変換するために必要な操作の最短シーケンスまたは短い操作シーケンスを決定することは可能ですか?

操作は次のとおりです。

  1. 新しい空のフォルダーを作成する
  2. 任意の内容で新しいファイルを作成します
  3. ファイルを削除する
  4. 空のフォルダを削除する
  5. ファイルの名前を変更する
  6. フォルダの名前を変更する
  7. ファイルを別の既存のフォルダー内に移動する
  8. 別の既存のフォルダー内にフォルダーを移動する

A と B は、同じフォルダー構造内に同じ内容 (または同じサイズ、同じ CRC) で同じ名前の同じファイルを持つ場合、同一です。

この質問は、しばらくの間私を困惑させてきました。現時点では、次の基本的な考え方があります。

  • データベースを計算します。
    • ファイル名とその CRC を保存する
    • 次に、サブフォルダーのないすべてのフォルダーを検索し、それらに含まれるファイルの CRC から CRC を計算し、それらに含まれるファイルの合計サイズからサイズを計算します。
    • ツリーを上って、各親フォルダーの CRC を作成します
  • データベース A とデータベース B を持つ次のループを使用します。
    • A ∩ B を計算し、両方のデータベースからこの共通部分を削除します。
    • 内部結合を使用して、A と B で一致する CRC を見つけます。最初にフォルダーをサイズ降順で並べます
    • 結果がある間、最初の結果を使用してフォルダーまたはファイルを移動し (必要に応じて新しいフォルダーを作成する可能性があります)、結果のソース行を両方のデータベースから削除します。移動があった場合は、データベース A の新しい場所の親フォルダーの CRC を更新します。
    • 次に、データベース A で参照されているすべてのファイルとフォルダーを削除し、データベース B で参照されているファイルとフォルダーを作成します。

ただし、これは実際には最適ではない方法だと思います。何をアドバイスしてもらえますか？

ありがとうございました！

4

5 に答える 5

6

この問題は、ツリー編集距離問題の特殊なケースであり、最適解を見つけることは (残念ながら) NP 困難であることが知られています。これは、一般的なケースに適した高速で正確なアルゴリズムがおそらく存在しないことを意味します。

そうは言っても、私がリンクした論文には、問題の限られたケースで機能する近似アルゴリズムとアルゴリズムに関するいくつかの素晴らしい議論が含まれています。この問題を解決する際に実際に発生する問題の多くを明らかにするため、興味深い議論を見つけることができます。

お役に立てれば！そして、素晴らしい質問を投稿していただきありがとうございます。

于 2011-08-05T17:18:07.787 に答える
3

ツリー編集距離アルゴリズムを確認することをお勧めします。これがあなたのファイルシステムにきちんとマッピングされるかどうかはわかりませんが、いくつかのアイデアが得られるかもしれません.

https://github.com/irskep/sleepytree (コードと論文)

于 2011-08-01T20:00:30.867 に答える
1

最初のステップは、どのファイルを作成/名前変更/削除する必要があるかを把握することです。

  • A) ツリー A のファイルのハッシュ マップを作成する
  • B) ツリー B のファイルを調べる
  • B.1) ハッシュ マップに同一の (名前と内容) ファイルがある場合は、そのままにしておく
  • B.2) 内容が同じで名前が異なる場合、ファイルの名前をハッシュ マップの名前に変更します。
  • B.3) ファイルの内容がハッシュ マップに存在しない場合は、削除する
  • B.4) (1、2、3 のいずれかが true の場合) ハッ​​シュ マップからファイルを削除する

ハッシュ マップに残っているファイルは、作成する必要があるファイルです。これは、ディレクトリ構造が解決された後の最後の手順です。

ファイルの違いが解決された後は、かなりトリッキーになります。この問題に対する効率的な最適解 (NP 完全/ハード) がなくても、私は驚かないでしょう。

問題は、問題が自然に細分化されないことにあります。実行する各ステップでは、ファイル ツリー全体を考慮する必要があります。もう少し考えてみます。

EDIT：最も研究されているツリー編集距離アルゴリズムは、ノードの作成/削除とノードの再ラベル付けのみを考慮しているようです。この問題はサブツリー全体を移動できるため、この問題には直接適用できません。「より簡単な」編集距離の問題に対する現在の最速の実行時間は ですO(N^3)。これの実行時間は大幅に遅くなると思います。

役立つリンク/参考文献

ツリー編集距離の最適な分解アルゴリズム- Demaine、Mozes、Weimann

于 2011-08-05T17:05:27.460 に答える
1

  1. B 内のすべてのファイルと、関連するサイズとチェックサムを列挙します。サイズ/チェックサムでソートします。

  2. A 内のすべてのファイルと、関連するサイズとチェックサムを列挙します。サイズ/チェックサムでソートします。

  3. ここで、順序付きリストの比較を行うには、次のようにします。

    を。BではなくAにあるすべてのファイルについて、それを削除します。

    b. AではなくBにあるすべてのファイルに対して、それを作成します。

    c. A と B のすべてのファイルについて、見つけた数だけ A から B に名前を変更し、B の残りのファイルのコピーを作成します。既存のファイルを上書きする場合は、別のリストに保存します。そのリストに A が見つかった場合は、それをソース ファイルとして使用します。

ディレクトリについても同じことを行い、A にあるものを削除し、B にあるものを削除し、B にあるものを A に追加せずに追加します。

チェックサム/サイズを反復処理して、ファイルを 2 回アクセスしたり、後で再同期する必要があるファイルを削除することを心配したりする必要がないようにします。不要なコピーを行わずに 2 つのディレクトリを同期させようとしていると思いますか?

全体的な複雑さは O(N log N) に加えて、これらすべてのファイルとそのメタデータを読み取るのに時間がかかります。

これはツリーの編集距離の問題ではありません。たまたまツリーを生成するのは、リストの同期の問題です。

于 2011-08-09T16:12:58.377 に答える
0

重要な問題は、フォルダーとファイルの移動だけです。名前の変更、削除、および作成は簡単で、最初のステップで実行できます (または、終了時に最後に実行することをお勧めします)。

次に、この問題を、葉が同じでトポロジーが異なるツリーを変換する問題に変換できます。

  1. フォルダー/バケットから移動するファイルと、フォルダーに残すファイルを決定します。決定は、ソースと宛先の同じファイルの数に基づいています。

  2. 同じ戦略を適用して、新しいトポロジでフォルダーを移動します。

フォルダの名前を忘れて、ファイルとトポロジだけを考えれば、最適または最適に近いはずだと思います。

于 2011-08-02T07:42:54.607 に答える