Модули обхода иерархии и сравнения для Python? - PullRequest
Новая
       21

Модули обхода иерархии и сравнения для Python?

5 голосов
/ 20 марта 2009

Я имею дело со многими иерархиями в моем повседневном развитии. Файловые системы, вложенные узлы DAG в Autodesk Maya и т. Д.

Мне интересно, есть ли какие-нибудь хорошие модули для Python, специально предназначенные для обхода и сравнения иерархий объектов?

Особый интерес могут представлять способы «нечетких» сравнений между двумя почти одинаковыми иерархиями. Некоторые из причин для этого могут заключаться в сопоставлении двух иерархий узлов в Maya из двух разных символов для передачи анимации от одного к другому.

Исходя из того, что я читал, мне, вероятно, понадобится что-то с порогом имени (которое я мог бы построить сам) для сравнения того, насколько близки два имени узла друг к другу. Тогда мне понадобится способ, при необходимости, игнорировать порядок появления дочерних узлов в иерархии. Наконец, мне нужно иметь дело с порогом глубины в тех случаях, когда узел может быть слегка перемещен вверх или вниз по иерархии.

Ответы [ 3 ]

4 голосов
/ 20 марта 2009

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

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). После этих двух я использую вышеупомянутые структуры в качестве шаблонов для своих классов, а не в качестве буквально многократно используемого модуля.

2 голосов
/ 22 марта 2009

Я рекомендую покопаться в xmldifff http://www.logilab.org/859 и посмотреть, как они сравнивают узлы и обрабатывают параллельные деревья. Или попробуйте написать [рекурсивный] генератор, который выдает каждый [значимый] узел в дереве, скажем, f(t), а затем используйте itertools.izip(f(t1),f(t2)), чтобы собрать вместе пары узлов для сравнения.

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

Для более причудливого решения сериализуйте два дерева в текстовые файлы, сделайте справочное замечание, что строка #n идет от узла #x в дереве. Сделайте это с обоими деревьями, загрузите файлы в diff и просканируйте результаты, чтобы заметить, какие части дерева изменились. Вы можете отобразить эту строку #n из файла 1 (и, следовательно, узел #x в первом дереве) и строку #m из файла 2 (и, следовательно, узел #y второго дерева), означая, что некоторая часть каждого дерева одинакова или отличается.

Для любого решения вам придется установить «каноническую форму» вашего дерева, которая может отбросить все игнорируемые пробелы, отображать атрибуты, дополнительные узлы и т. Д. Из процесса сравнения. Это также может означать прохождение дерева в ширину и сначала в глубину.

1 голос
/ 20 марта 2009

http://code.google.com/p/pytree/

это может быть излишним или вообще не подходит для того, что вам нужно:

http://networkx.lanl.gov/

http://www.osl.iu.edu/~dgregor/bgl-python/

...