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

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

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

Создать новую, пустую папку
Создать новый файл с любым содержимым
Удалить файл
Удалить пустую папку
Переименовать файл
Переименовать папку
Переместить файл в другую существующую папку
Переместить папку в другую существующую папку

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

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

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

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

Спасибо!

Ответ 1

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

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

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

Ответ 2

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

https://github.com/irskep/sleepytree (код и документ)

Ответ 3

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

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

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

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

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

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

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

Оптимальный алгоритм декомпозиции для расстояния редактирования дерева - Демейн, Мозес, Вейманн

Ответ 4

Перечислить все файлы в B и связанные с ними размеры и контрольные суммы; сортировать по размеру/контрольной сумме.
Перечислить все файлы в и связанные с ними размеры и контрольные суммы; сортировать по размеру/контрольной сумме.
Теперь, выполнив упорядоченное сравнение списка, сделайте следующее:

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

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

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

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

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

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

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

Ответ 5

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

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

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

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