Кратчайшая последовательность операций преобразования дерева файлов в другое

Question

Учитывая два файловых дерева A и B, можно ли определить кратчайшую последовательность операций или короткую последовательность операций , необходимую для преобразования А в В?

Операция может быть:

1. Создать новую пустую папку
2. Создать новый файл с любым содержимым
3. Удалить файл
4. Удалить пустую папку
5. Переименовать файл
6. Переименовать папку
7. Переместить файл в другую существующую папку
8. Переместить папку в другую существующую папку

A и B идентичны, когда они будут иметь одинаковые файлы с одинаковым содержимым (или одинаковым размером CRC) и одинаковыми именами в одной структуре папок.

Этот вопрос меня некоторое время озадачивал. На данный момент у меня есть следующая основная идея:

• Вычислить базу данных:
  • Хранить имена файлов и их CRC
  • Затем найдите все папки без подпапок и вычислите CRC из CRC файлов, которые они содержат, и по размеру от общего размера файлов, которые они содержат
  • Поднимитесь по дереву, чтобы сделать CRC для каждой родительской папки
• Используйте следующий цикл, имеющий базу данных A и базу данных B:
  • Вычислить A ∩ B и удалить это пересечение из обеих баз данных.
  • Используйте внутреннее объединение, чтобы найти соответствующие CRC в A и B, сначала папки, упорядоченные по размеру desc
  • пока есть результат, используйте первый результат, чтобы переместить папку или файл (возможно, создавая новые папки при необходимости), удалите из обеих баз данных исходные строки результата. Если произошел переезд, обновите CRC родительских папок нового местоположения в db A.
  • Затем удалите все файлы и папки, на которые есть ссылки в базе данных A, и создайте те, на которые есть ссылки в базе данных B.

Однако я думаю, что это действительно неоптимальный способ сделать это. Что вы могли бы дать мне в качестве совета?

Спасибо!

Answer 1

Эта проблема является частным случаем проблемы дерева редактирования , для которой поиск (оптимальное решение) (к сожалению), как известно, NP-трудный.Это означает, что, вероятно, не существует хороших, быстрых и точных алгоритмов для общего случая.

Тем не менее, статья, которую я связал, содержит несколько хороших обсуждений алгоритмов приближения и алгоритмов, которые работают в ограниченных случаяхэта проблема.Вам может показаться интересным обсуждение, поскольку оно освещает многие проблемы, возникающие при решении этой проблемы.

Надеюсь, это поможет!И спасибо, что опубликовали замечательный вопрос!

Answer 2

Возможно, вы захотите проверить алгоритмы расстояния редактирования дерева. Я не знаю, будет ли это аккуратно отображаться в вашей файловой системе, но это может дать вам некоторые идеи.

https://github.com/irskep/sleepytree (код и бумага)

Answer 3

1. Перечислить все файлы в B и связанные с ними размеры и контрольные суммы; сортировка по размеру / контрольной сумме.

2. Перечислить все файлы в A и связанные с ними размеры и контрольные суммы; сортировка по размеру / контрольной сумме.

3. Теперь, сделав сравнение упорядоченного списка, сделайте следующее:

   а. для каждого файла в A, но не в B, удалите его.

   б. для каждого файла в B, но не в A, создайте его.

   с. для каждого файла в A и B переименуйте столько, сколько вы встретите, от A до B, затем сделайте копии остальных в B. Если вы собираетесь перезаписать существующий файл, сохраните его в отдельном списке. Если вы найдете A в этом списке, используйте его в качестве исходного файла.

Сделайте то же самое для каталогов, удаляя их в A, но не в B, и добавляя их в B, но не в A.

Вы выполняете итерацию по контрольной сумме / размеру, чтобы гарантировать, что вам никогда не придется посещать файлы дважды или беспокоиться об удалении файла, который впоследствии понадобится для повторной синхронизации. Я предполагаю, что вы пытаетесь синхронизировать два каталога без ненужного копирования?

Общая сложность составляет O (N log N) плюс сколько требуется времени для чтения всех этих файлов и их метаданных.

Это не проблема расстояния редактирования дерева; это скорее проблема синхронизации списка, которая возникает при генерации дерева.

Answer 4

Первый шаг - выяснить, какие файлы нужно создать / переименовать / удалить.

• A) Создать хэш-карту файлов дерева A
• B) Просмотрите файлы дерева B
• B.1) Если в хэш-карте есть идентичный файл (имя и содержимое), оставьте его в покое
• B.2) Если содержимое идентично, но имя отличается, переименуйте файл в файл хэш-карты
• B.3) Если содержимое файла не существует в хэш-карте, удалите его
• B.4) (если один из 1,2,3 был верным) Удалить файл из хэш-карты

Файлы, оставленные в хэш-карте, - это те, которые должны быть созданы. Это должен быть последний шаг после того, как структура каталогов была разрешена.

После устранения различий в файлах становится довольно сложно. Я не удивлюсь, если не найдется эффективного оптимального решения этой проблемы (NP-complete / hard).

Трудность заключается в том, что проблема не подразделяется естественным образом. Каждый ваш шаг должен учитывать все дерево файлов. Я подумаю об этом еще немного.

РЕДАКТИРОВАНИЕ: Кажется, что наиболее изученные алгоритмы расстояния редактирования дерева рассматривают только создание / удаление узлов и перемаркировку узлов. Это напрямую не относится к этой проблеме, потому что она позволяет перемещать целые поддеревья, что значительно усложняет задачу. Текущее самое быстрое время выполнения для "более легкой" проблемы редактирования расстояния - O(N^3). Я предполагаю, что время выполнения для этого будет значительно медленнее.

Полезные ссылки / Ссылки

Оптимальный алгоритм разложения для дерева Редактировать расстояние - Demaine, Mozes, Weimann

Answer 5

Единственной нетривиальной проблемой является перемещение папок и файлов. Переименование, удаление и создание тривиально и может быть выполнено на первом этапе (или лучше на последнем, когда вы закончите).

Затем вы можете преобразовать эту проблему в задачу, преобразуя дерево с одинаковыми листьями, но с другой топологией.

1. Вы сами решаете, какие файлы будут перемещены из какой-либо папки / корзины, а какие файлы останутся в папке. Решение основывается на количестве одинаковых файлов в источнике и месте назначения.

2. Вы применяете ту же стратегию для перемещения папок в новой топологии.

Я думаю, что вы должны быть близки к оптимальным или оптимальным, если вы забудете об именах папок и будете думать только о файлах и топологии.