Mô-đun truyền tải và so sánh phân cấp cho Python?

Question

Tôi giải quyết rất nhiều thứ bậc trong việc phát triển từng ngày của tôi. Hệ thống tệp, nút DAG lồng nhau trong Autodesk Maya, v.v.

Tôi tự hỏi, có mô-đun nào tốt cho Python được thiết kế đặc biệt để duyệt và so sánh thứ bậc của các đối tượng không?

Sở thích cụ thể sẽ là cách để thực hiện các so sánh 'mờ' giữa hai số gần như cấu trúc phân cấp giống hệt nhau. Một số lý do để làm điều này sẽ là để phù hợp với hai hệ thống phân cấp nút trong Maya từ hai nhân vật khác nhau để chuyển hình ảnh động từ một đến khác.

Dựa trên những gì tôi đã đọc, tôi có thể cần một cái gì đó có ngưỡng tên (mà tôi có thể tự xây dựng) để so sánh hai tên nút gần nhau như thế nào. Sau đó tôi cần một cách để tùy ý bỏ qua thứ tự các nút con xuất hiện trong cấu trúc phân cấp. Cuối cùng, tôi cần phải đối phó với một ngưỡng sâu, trong trường hợp một nút có thể đã được di chuyển lên hoặc xuống một chút.

Answer 1

Tôi không chắc tôi nhìn thấy sự cần thiết của một module hoàn chỉnh - - các cấu trúc phân cấp là một mẫu thiết kế và mỗi cấu trúc phân cấp có đủ các tính năng độc đáo mà khó có thể khái quát hóa được.

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 

Tôi thấy rằng đây là tất cả những gì tôi cần. Và tôi thấy rằng thật khó để tạo ra một mô-đun có thể tái sử dụng được bởi vì (a) có rất ít ở đây và (b) mỗi ứng dụng thêm hoặc thay đổi quá nhiều mã.

Hơn nữa, tôi thấy rằng hệ thống phân cấp thường được sử dụng nhất là hệ thống tệp, mà tôi có mô-đun os. Thứ bậc phổ biến thứ hai được sử dụng là các thông điệp XML, mà tôi có ElementTree (thường là thông qua lxml). Sau hai, tôi sử dụng các cấu trúc trên như các khuôn mẫu cho các lớp của tôi, không phải là một mô-đun có thể sử dụng lại theo nghĩa đen.

Answer 2

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

những có lẽ hơi quá đáng hay không phù hợp ở tất cả những gì bạn cần:

http://networkx.lanl.gov/

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

Answer 3

Tôi khuyên bạn nên đào xung quanh xmldifff http://www.logilab.org/859 và xem cách chúng so sánh các nút và xử lý các cây song song. Hoặc, hãy thử viết trình tạo [đệ quy] tạo ra mỗi nút [có ý nghĩa] trên cây, nói f(t), sau đó sử dụng itertools.izip(f(t1),f(t2)) để thu thập các cặp nút cùng nhau để so sánh.

Hầu hết các cấu trúc phân cấp mà tôi xử lý có nhiều hơn một "trục", giống như các phần tử và thuộc tính trong XML và một số nút quan trọng hơn các nút khác.

Để có giải pháp kỳ lạ hơn, hãy tuần tự hóa hai cây thành tệp văn bản, hãy ghi chú tham chiếu rằng dòng #n đến từ nút #x trong cây. Làm điều đó cho cả hai cây, cho các tập tin vào khác, và quét kết quả để nhận thấy phần nào của cây đã thay đổi. Bạn có thể ánh xạ dòng #n đó từ tệp 1 (và do đó nút #x trong cây đầu tiên) và dòng #m từ tệp 2 (và do đó nút #y của cây thứ hai) có nghĩa là một phần của mỗi cây giống nhau hoặc khác nhau.

Đối với bất kỳ giải pháp nào, bạn sẽ phải thiết lập "biểu mẫu chuẩn" của cây, có thể xóa tất cả khoảng trống có thể bỏ qua, thuộc tính hiển thị, nút tùy chọn, v.v. Nó cũng có thể có nghĩa là làm một bề rộng đầu tiên so với chiều sâu đầu tiên đi qua của cây (s).