إنشاء شجرة هرمية من قاموس محتويات الصفحات

Question

المفتاح التالي: أزواج القيمة هي "الصفحة" و"محتويات الصفحة".

{
  'section-a.html':{'contents':'section-b.html section-c.html section-d.html'},
  'section-b.html':{'contents':'section-d.html section-e.html'},
  'section-c.html':{'contents':'product-a.html product-b.html product-c.html product-d.html'},
  'section-d.html':{'contents':'product-a.html product-c.html'},
  'section-e.html':{'contents':'product-b.html product-d.html'},
  'product-a.html':{'contents':''},
  'product-b.html':{'contents':''},
  'product-c.html':{'contents':''},
  'product-d.html':{'contents':''}
}

بالنسبة لأي "عنصر" معين، كيف يمكنني العثور على المسار (المسارات) للعنصر المذكور؟نظرًا لمعرفتي المحدودة جدًا بهياكل البيانات في معظم الحالات، أفترض أن هذه ستكون شجرة تسلسل هرمي.أرجوا أن تصحح لي إذا كنت مخطئا!

تحديث: اعتذاري، كان ينبغي أن أكون أكثر وضوحًا بشأن البيانات والنتيجة المتوقعة.

بافتراض أن "page-a" عبارة عن فهرس، فإن كل "صفحة" هي حرفيًا صفحة تظهر على موقع ويب، حيث أن كل "عنصر" يشبه صفحة منتج قد تظهر على Amazon وNewegg وما إلى ذلك.

وبالتالي، فإن الناتج المتوقع لـ 'item-d' سيكون مسارًا (أو مسارات) لذلك العنصر.على سبيل المثال (المحدد تعسفي، للتوضيح هنا):يحتوي item-d على المسارات التالية:

page-a > page-b > page-e > item-d
page-a > page-c > item-d

التحديث 2: تحديث بلدي الأصلي dict لتوفير بيانات أكثر دقة وحقيقية.تمت إضافة ".html" للتوضيح.

Answer 1

إليك طريقة بسيطة -- إنها O(N تربيع)، لذلك، ليست كلها قابلة للتطوير بشكل كبير، ولكنها ستخدمك جيدًا لحجم كتاب معقول (إذا كان لديك، على سبيل المثال، ملايين الصفحات، فأنت بحاجة إلى التفكير في عدد كبير جدًا من الصفحات) نهج مختلف وأقل بساطة؛-).

أولاً، أنشئ إملاءًا أكثر قابلية للاستخدام، وقم بتعيين الصفحة لمجموعة المحتويات:على سبيل المثال، إذا كان الإملاء الأصلي هو d, ، قم بإملاء آخر mud مثل:

mud = dict((p, set(d[p]['contents'].split())) for p in d)

بعد ذلك، قم بإجراء تعيين الإملاء لكل صفحة على صفحاتها الأصلية:

parent = dict((p, [k for k in mud if p in mud[k]]) for p in mud)

هنا، أستخدم قوائم الصفحات الأصلية (المجموعات ستكون جيدة أيضًا)، ولكن لا بأس بذلك بالنسبة للصفحات التي تحتوي على 0 أو 1 أصل كما في المثال الخاص بك أيضًا - ستستخدم قائمة فارغة لتعني "لا يوجد أصل" "، وإلا قائمة مع الأصل باعتباره العنصر الوحيد.يجب أن يكون هذا رسمًا بيانيًا موجهًا غير دوري (إذا كنت في شك، يمكنك التحقق بالطبع، لكنني سأتخطى هذا التحقق).

الآن، في ضوء الصفحة، فإن العثور على المسارات المؤدية إلى الأصل (الوالدين) إلى الأصل الذي ليس له والد ("الصفحة الجذرية") يتطلب ببساطة "السير" على parent قاموس.على سبيل المثال، في الحالة الأصلية 0/1:

path = [page]
while parent[path[-1]]:
  path.append(parent[path[-1]][0])

إذا كان بإمكانك توضيح المواصفات الخاصة بك بشكل أفضل (نطاقات عدد الصفحات في كل كتاب، وعدد الآباء في كل صفحة، وما إلى ذلك)، فلا شك أنه يمكن تحسين هذا الكود، ولكن كبداية آمل أن يكون مفيدًا.

يحرر:كما أوضح OP أن الحالات التي تحتوي على والد واحد (وبالتالي، مسارات متعددة) هي بالفعل ذات أهمية، دعني أوضح كيفية التعامل مع ذلك:

partial_paths = [ [page] ]
while partial_paths:
  path = partial_paths.pop()
  if parent[path[-1]]:
    # add as many partial paths as open from here
    for p in parent[path[-1]]:
      partial_paths.append(path + [p])
  else:
    # we've reached a root (parentless node)
    print(path)

بالطبع بدلا من printجي، يمكنك yield كل مسار عندما يصل إلى جذر (يحول الوظيفة التي يكون جسمها إلى مولد)، أو تعامل معه بأي طريقة تريدها.

تحرير مرة أخرى:أحد المعلقين قلق بشأن الدورات في الرسم البياني.إذا كان هذا القلق مبررًا، فليس من الصعب تتبع العقد التي تمت رؤيتها بالفعل في المسار واكتشاف أي دورات والتحذير منها.الأسرع هو الاحتفاظ بمجموعة بجانب كل قائمة تمثل مسارًا جزئيًا (نحتاج إلى القائمة للطلب، ولكن التحقق من العضوية هو O(1) في المجموعات مقابل O(N) في القوائم):

partial_paths = [ ([page], set([page])) ]
while partial_paths:
  path, pset = partial_paths.pop()
  if parent[path[-1]]:
    # add as many partial paths as open from here
    for p in parent[path[-1]]:
      if p in pset:
        print('Cycle: %s (%s)' % (path, p))
        continue
      partial_paths.append((path + [p], pset.union([p])))
  else:
    # we've reached a root (parentless node)
    print('Path: %s' % (path,))

ربما يكون من المفيد، من أجل الوضوح، تعبئة القائمة والمجموعة التي تمثل مسارًا جزئيًا إلى مسار فئة فائدة صغيرة باستخدام الطرق المناسبة.

Answer 2

إليك رسم توضيحي لسؤالك.من الأسهل التفكير في الرسوم البيانية عندما يكون لديك صورة.

أولاً: اختصار البيانات:

#!/usr/bin/perl -pe
s/section-([a-e])\.html/uc$1/eg; s/product-([a-e])\.html/$1/g

نتيجة:

# graph as adj list
DATA = {
  'A':{'contents':'B C D'},
  'B':{'contents':'D E'},
  'C':{'contents':'a b c d'},
  'D':{'contents':'a c'},
  'E':{'contents':'b d'},
  'a':{'contents':''},
  'b':{'contents':''},
  'c':{'contents':''},
  'd':{'contents':''}
}

التحويل إلى تنسيق graphviz:

with open('data.dot', 'w') as f:
    print >> f, 'digraph {'
    for node, v in data.iteritems():
        for child in v['contents'].split():
            print >> f, '%s -> %s;' % (node, child),
        if v['contents']: # don't print empty lines
            print >> f
    print >> f, '}'

نتيجة:

digraph {
A -> C; A -> B; A -> D;
C -> a; C -> b; C -> c; C -> d;
B -> E; B -> D;
E -> b; E -> d;
D -> a; D -> c;
}

رسم الرسم البياني:

$ dot -Tpng -O data.dot

Answer 3

يحرر مع توضيح السؤال بشكل أفضل قليلاً، أعتقد أن ما يلي قد يكون ما تحتاجه، أو على الأقل يمكن أن يوفر شيئًا من نقطة البداية.

data = {
  'section-a.html':{'contents':'section-b.html section-c.html section-d.html'},
  'section-b.html':{'contents':'section-d.html section-e.html'},
  'section-c.html':{'contents':\
                    'product-a.html product-b.html product-c.html product-d.html'},
  'section-d.html':{'contents':'product-a.html product-c.html'},
  'section-e.html':{'contents':'product-b.html product-d.html'},
  'product-a.html':{'contents':''},
  'product-b.html':{'contents':''},
  'product-c.html':{'contents':''},
  'product-d.html':{'contents':''}
}

def findSingleItemInData(item):
    return map( lambda x: (item, x), \
                [key for key in data if data[key]['contents'].find(item) <> -1])

def trace(text):
    searchResult = findSingleItemInData(text)
    if not searchResult:
        return text

    retval = [] 
    for item in searchResult:
        retval.append([text, trace(item[-1])]) 

    return retval

print trace('product-d.html')

قديم

I don't really know what you expect to see, but maybe something like this will work.

data = {
   'page-a':{'contents':'page-b page-c'},
   'page-b':{'contents':'page-d page-e'},
   'page-c':{'contents':'item-a item-b item-c item-d'},
   'page-d':{'contents':'item-a item-c'},
   'page-e':{'contents':'item-b item-d'}
}

itemToFind = 'item-c'

for key in data:
  for index, item in enumerate(data[key]['contents'].split()):
    if item == itemToFind:
      print key, 'at position', index

It would be easier, and I think more correct, if you'd use a slightly different data structure:

 data = {
   'page-a':{'contents':['page-b', 'page-c']},
   'page-b':{'contents':['page-d', 'page-e']},
   'page-c':{'contents':['item-a', 'item-b item-c item-d']},
   'page-d':{'contents':['item-a', 'item-c']},
   'page-e':{'contents':['item-b', 'item-d']}
 }

ثم لن تحتاج إلى الانقسام.

بالنظر إلى هذه الحالة الأخيرة، يمكن التعبير عنها بشكل أقصر قليلاً:

for key in data:
    print [ (key, index, value) for index,value in \
             enumerate(data[key]['contents']) if value == 'item-c' ]

وحتى أقصر، مع إزالة القوائم الفارغة:

print filter(None, [[ (key, index, value) for index,value in \ 
       enumerate(data[key]['contents']) if value == 'item-c' ] for key in data])

That should be a single line, but I used \ as line break indicator so it can be read without scrollbars.