Модули обхода иерархии и сравнения для Python?
Вопрос
В своей повседневной разработке я имею дело со множеством иерархий.Файловые системы, вложенные узлы DAG в Autodesk Maya и т.д.
Мне интересно, есть ли какие-нибудь хорошие модули для Python, специально разработанные для обхода и сравнения иерархий объектов?
Особый интерес представляли бы способы проведения "нечетких" сравнений между двумя почти идентичные иерархии.Некоторые из причин для этого могут заключаться в сопоставлении двух иерархий узлов в Maya из двух разных символов, чтобы перенести анимацию с одного на другой.
Основываясь на том, что я читал, мне, вероятно, понадобилось бы что-то с пороговым значением имени (которое я мог бы создать сам) для сравнения того, насколько близки имена двух узлов друг к другу.Затем мне понадобился бы способ необязательного игнорирования порядка отображения дочерних узлов в иерархии.Наконец, мне нужно было бы иметь дело с порогом глубины в тех случаях, когда узел, возможно, был немного перемещен вверх или вниз по иерархии.
Решение
Я не уверен, что вижу необходимость в полноценном модуле - иерархии - это шаблон проектирования, и каждая иерархия обладает достаточным количеством уникальных функций, которые трудно обобщить.
class Node( object ):
def __init__( self, myData, children=None )
self.myData= myData
self.children= children if children is not None else []
def visit( self, aVisitor ):
aVisitor.at( self )
aVisitor.down()
for c in self.children:
aVisitor.at( c )
aVisitor.up()
class Visitor( object ):
def __init__( self ):
self.depth= 0
def down( self ):
self.depth += 1
def up( self ):
self.depth -= 1
Я нахожу, что это все, что мне нужно.И я обнаружил, что из этого трудно создать повторно используемый модуль, потому что (а) здесь так мало информации и (б) каждое приложение добавляет или изменяет так много кода.
Кроме того, я нахожу, что наиболее часто используемая иерархия - это файловая система, для которой у меня есть os
модуль.Вторая наиболее часто используемая иерархия - это XML-сообщения, для которых у меня есть ElementTree (обычно через lxml).После этих двух я использую вышеупомянутые структуры в качестве шаблонов для своих классов, а не как буквальный повторно используемый модуль.
Другие советы
Я рекомендую покопаться в xmldifff http://www.logilab.org/859 и видеть, как они сравнивают узлы и обрабатывают параллельные деревья.Или попробуйте написать [рекурсивный] генератор, который выдает каждый [значимый] узел в дереве, скажем f(t)
, затем используйте itertools.izip(f(t1),f(t2))
собрать вместе пары узлов для сравнения.
Большинство иерархических структур, с которыми я имею дело, имеют более одной "оси", как элементы и атрибуты в XML, и некоторые узлы более значимы, чем другие.
Для более странного решения сериализуйте два дерева в текстовые файлы, сделайте ссылочное примечание, что строка # n исходит из узла # x в дереве.Проделайте это с обоими деревьями, передайте файлы в diff и просканируйте результаты, чтобы заметить, какие части дерева изменились.Вы можете сопоставить, что строка # n из файла 1 (и, следовательно, узел # x в первом дереве) и строка # m из файла 2 (и, следовательно, узел # y второго дерева) означают, что какая-то часть каждого дерева одинакова или отличается.
Для любого решения вам придется установить "каноническую форму" вашего дерева, такую, которая могла бы исключить все игнорируемые пробелы, атрибуты отображения, необязательные узлы и т.д. Из процесса сравнения.Это также может означать , что сначала нужно сделать шаг вширь по сравнениюпервый обход дерева (деревьев) на глубину.
http://code.google.com/p/pytree/
возможно, они излишни или вообще не подходят для того, что вам нужно: