Создание иерархического дерева на основе словаря содержимого страниц

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':''}
}

Для любого данного "элемента", как я мог бы найти пути к указанному элементу?Учитывая мои очень ограниченные знания структур данных в большинстве случаев, я предполагаю, что это будет иерархическое дерево.Пожалуйста, поправьте меня, если я ошибаюсь!

Обновить: Приношу свои извинения, мне следовало более четко изложить полученные данные и мой ожидаемый результат.

Предполагая, что "страница-a" - это индекс, каждая "страница" - это буквально страница, появляющаяся на веб-сайте, где каждый "товар" - это что-то вроде страницы продукта, которая появится на Amazon, Newegg и т.д.

Таким образом, моим ожидаемым результатом для 'item-d' был бы путь (или путей) к этому элементу.Например (разделитель является произвольным, для иллюстрации здесь):элемент-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)

Затем установите dict, сопоставляющий каждую страницу с ее родительскими страницами:

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

Здесь я использую списки родительских страниц (наборы тоже подойдут), но это нормально для страниц с 0 или 1 родителем, как и в вашем примере - вы просто будете использовать пустой список для обозначения " нет родителя " ;, иначе список с родителем в качестве единственного элемента. Это должен быть ациклический ориентированный граф (если у вас есть сомнения, вы можете проверить, конечно, но я пропускаю эту проверку).

Теперь, для данной страницы, для поиска путей от своего родителя (ов) до родительского родителя («корневой страницы») просто требуется «ходьба». parent dict. Например, в родительском случае 0/1:

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

Если вы сможете лучше уточнить свои спецификации (диапазоны количества страниц в книге, количества родителей на страницу и т. д.), этот код, без сомнения, может быть доработан, но в начале я надеюсь, что он может помочь.

Изменить : как пояснил ОП, случаи с > 1 родитель (и так, несколько путей) действительно представляет интерес, позвольте мне показать, как справиться с этим:

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 ing вы можете 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,))

Вероятно, для ясности целесообразно упаковать список и набор, представляющий частичный путь, в небольшой служебный класс 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')

Старый

Я действительно не знаю, что вы ожидаете увидеть, но, возможно, что-то вроде это сработает.

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

Было бы проще, и я думаю, что более правильно, если вы будете использовать немного другой структурой данных :

 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])

Это должна быть одна строка, но я использовал \ в качестве индикатора разрыва строки, чтобы ее можно было прочитать без полос прокрутки.