पदानुक्रम ट्रैवर्सल और तुलना मॉड्यूल?

Question

मैं अपने दिन के विकास में कई पदानुक्रमों से निपटता हूं। फाइल सिस्टम, ऑटोडस्क माया, आदि में घोंसला वाले डीएजी नोड्स

मुझे आश्चर्य है, क्या पाइथन के लिए विशेष रूप से किसी भी अच्छे मॉड्यूल हैं जो ऑब्जेक्ट्स के पदानुक्रमों की तुलना करने और तुलना करने के लिए डिज़ाइन किए गए हैं?

विशेष रुचि के दो लगभग समान पदानुक्रमों के बीच 'अस्पष्ट' तुलना करने के तरीके होंगे। ऐसा करने के कुछ कारण एक दूसरे से एनीमेशन स्थानांतरित करने के क्रम में माया में दो नोड पदानुक्रमों से मेल खाने के लिए दो अलग-अलग पात्रों से मेल खाते हैं।

जो मैं पढ़ रहा हूं उसके आधार पर, मुझे शायद एक दूसरे के नाम के करीब दो नोड नामों की तुलना करने के लिए नाम थ्रेसहोल्ड (जिसे मैं स्वयं बना सकता हूं) के साथ कुछ चाहिए। इसके बाद मुझे ऑर्डर को वैकल्पिक रूप से अनदेखा करने का एक तरीका चाहिए कि बाल नोड पदानुक्रम में दिखाई दें। आखिरकार, मुझे गहराई से सीमा से निपटने की ज़रूरत होगी, ऐसे मामलों में जहां एक नोड पदानुक्रम को ऊपर या नीचे ले जाया जा सकता है।

Answer 1

मुझे यकीन है कि मैं एक पूरा मॉड्यूल के लिए की जरूरत को देखने के नहीं कर रहा हूँ - - पदानुक्रम एक डिजाइन पैटर्न हैं, और प्रत्येक पदानुक्रम में पर्याप्त अनूठी विशेषताएं हैं जिन्हें सामान्य बनाना मुश्किल है।

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 मॉड्यूल है। दूसरा सबसे अधिक इस्तेमाल किया जाने वाला पदानुक्रम एक्सएमएल संदेश है, जिसके लिए मेरे पास एलिमेंटट्री है (आमतौर पर एलएक्सएमएल के माध्यम से)। उन दो के बाद, मैं उपरोक्त संरचनाओं का उपयोग अपने वर्गों के लिए टेम्पलेट्स के रूप में करता हूं, न कि एक शाब्दिक पुन: प्रयोज्य मॉड्यूल के रूप में।

Answer 2

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

इन शायद overkill या आपको क्या चाहिए के लिए बिल्कुल भी अनुकूल नहीं:

http://networkx.lanl.gov/

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

Answer 3

मैं xmldifff http://www.logilab.org/859 के आसपास खुदाई करने की सलाह देता हूं और देखता हूं कि वे नोड्स की तुलना कैसे करते हैं और समांतर पेड़ों को कैसे संभालते हैं। या, एक [रिकर्सिव] जेनरेटर लिखने का प्रयास करें जो पेड़ में प्रत्येक [महत्वपूर्ण] नोड उत्पन्न करता है, f(t) कहें, फिर तुलना के लिए नोड्स के जोड़े एकत्र करने के लिए itertools.izip(f(t1),f(t2)) का उपयोग करें।

अधिकांश पदानुक्रमिक संरचनाओं के साथ मैं एक से अधिक "धुरी", जैसे एक्सएमएल में तत्वों और विशेषताओं की तरह है, और कुछ नोड दूसरों की तुलना में अधिक महत्वपूर्ण हैं।

अधिक विचित्र समाधान के लिए, दो पेड़ों को टेक्स्ट फ़ाइलों में क्रमबद्ध करें, एक रेफरेंशियल नोट बनाएं कि लाइन # एन पेड़ में नोड #x से आता है। दोनों पेड़ों के लिए ऐसा करें, फ़ाइलों को diff में खिलाएं, और परिणामों को स्कैन करें कि पेड़ के कौन से हिस्से बदल गए हैं। आप फ़ाइल 1 से उस पंक्ति # एन को मैप कर सकते हैं (और इसलिए पहले पेड़ में नोड #x) और फ़ाइल 2 से लाइन # एम (और इसलिए दूसरे पेड़ के नोड #y) का मतलब है कि प्रत्येक पेड़ का कुछ हिस्सा समान है या विभिन्न।

किसी भी समाधान के लिए आपको अपने पेड़ के "कैनोलिक रूप" को स्थापित करना होगा, जो तुलनात्मक प्रक्रिया से सभी अनजान सफेद जगहों, प्रदर्शन विशेषताओं, वैकल्पिक नोड्स आदि को छोड़ सकता है। इसका मतलब यह भी हो सकता है कि पहले चौड़ाई बनाम गहराई पेड़ के पहले ट्रैवर्सल हो।