Как пройти две произвольно сложные древовидные структуры одновременно и создать надмножество?

Question

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

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

Есть ли алгоритм, который мог бы быть моим другом здесь? Любой другой совет?

Answer 1

В статье Линдхольма, Кангашарью и Таркома «Быстрое и простое разграничение деревьев XML по выравниванию последовательностей» есть несколько указателей:

1) rsync делает то, что вас интересует. Посмотрите на http://samba.anu.edu.au/ftp/rsync/rsync.html,, и, возможно, стоит проверить, что rsync --list-only делает то, на что это похоже.

2) Один из приемов состоит в том, чтобы превратить древовидную иерархию в последовательность, обойдя ее сначала путем поиска по глубине, а затем сравнив две последовательности. Ваша идея о сравнении хеш-кодов может быть реализована с помощью скользящего хеша (http://en.wikipedia.org/wiki/Rolling_hash).

Я подозреваю, что в итоге вы создадите две целые последовательности, а затем запустите некоторый эквивалент diff или xdelta между ними, вместо того, чтобы пытаться выполнять работу постепенно. У полностью инкрементного подхода могут возникнуть проблемы, когда какой-либо подкаталог перемещается в древовидной структуре на долгий путь.

Answer 2

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