Рекурсивный алгоритм N-way слияния / различий для деревьев каталогов?

Question

Какие алгоритмы или библиотеки Java доступны для N-way, рекурсивного сравнения / слияния каталогов?

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

Цели:

• Найдите пары каталогов, в которых много похожих файлов.
• Создание короткого списка пар каталогов, которые могут быть синхронизированы с двухсторонним объединением для устранения дубликатов
• Должен работать рекурсивно (могут быть вложенные дубликаты каталогов верхнего уровня)
• Время выполнения и память должны быть O (n log n) в количестве каталогов и файлов
• Должен иметь возможность использовать встроенную БД или страницу на диск для обработки большего количества файлов, чем умещается в памяти (более 100 000 +).
• Необязательно: создать происхождение и набор изменений между папками
• Необязательно: сортируйте операции слияния по количеству дубликатов, которые они могут увеличить

Я знаю, как использовать хэши, чтобы находить дубликаты файлов примерно в O (n) пространстве, но я не знаю, как перейти к поиску частично перекрывающихся наборов между папками и их дочерними элементами.

РЕДАКТИРОВАТЬ: некоторые уточнения Сложность заключается в разнице между «точно одинаковым» содержимым (иначе хэши файлов будут работать) и «похожим» (что не будет). По сути, я хочу передать этот алгоритм в набор каталогов и заставить его возвращать набор двухсторонних операций слияния, которые я могу выполнить, чтобы максимально сократить количество дубликатов при минимальном количестве возможных конфликтов. Это эффективно создает дерево предков, показывающее, какие папки являются производными друг от друга.

Конечная цель - позволить мне объединить несколько разных папок в одно общее дерево. Например, у меня может быть папка с проектами программирования, а затем скопировать часть ее содержимого на другой компьютер для работы на нем. Тогда я мог бы сделать резервную копию и промежуточную версию на флешку. За исключением того, что у меня может быть 8 или 10 разных версий, с немного разными организационными структурами или именами папок. Мне нужно иметь возможность объединять их по одному шагу за раз, чтобы я мог выбирать, как включать изменения на каждом этапе пути.

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

Answer 1

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

Вот что приходит на ум.

• Загрузить все данные из файловой системы. Он будет большим, но он уместится в памяти.

• Составьте список возможных пар каталогов с оценками сходства. За каждое имя каталога, отображаемое в обоих деревьях, наберите 1 балл за все пары каталогов, которые имеют это имя. За каждое имя файла, которое появляется в обоих деревьях (но не так часто, что оно бессмысленно), наберите 1 балл за все пары каталогов, которые содержат файл с этим именем. Набрать бонусные баллы, если два файла идентичны. Набрать бонусные баллы, если имя файла не появляется где-либо еще. Каждый раз, когда вы даете очки, также присваивайте несколько очков всем парам предков, так что если a / x / y / foo.txt похож на b / z / y / foo.txt, то пары (a/x/y, b/z/y) и (a/x, b/z) и (a, b) все получают очки.

• По желанию, откажитесь от всех пар со слишком низкими показателями, чтобы их беспокоить, и критически осмотрите другие пары. До сих пор мы рассматривали только то, как каталоги похожи. Посмотрите еще раз и оштрафуйте пары каталогов, которые показывают признаки , а не , имеющих общее происхождение. (Общий способ сделать это - вычислить максимальный балл, который могут быть у двух каталогов, если у них обоих есть все файлы, и все они идентичны; и отклонить пару, если на самом деле была достигнута только небольшая часть этого возможного балла. Но может быть лучше сделать что-нибудь дешевое и эвристическое или пропустить этот шаг целиком.)

• Выберите наиболее подходящую пару каталогов кандидатов. Выведите это. Удалите эти каталоги и все их подкаталоги из конкуренции. Повторить.

Выбор правильных структур данных оставлен в качестве упражнения.

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

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