Créer une arborescence hiérarchique à partir du dictionnaire de contenu des pages

Question

Les paires clé: valeur suivantes sont 'page' et 'contenu de la page'.

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

Pour un élément donné, comment puis-je trouver le chemin d'accès à cet élément? Avec ma connaissance très limitée des structures de données dans la plupart des cas, je suppose que ce serait un arbre hiérarchique. S'il vous plaît, corrigez-moi si je me trompe!

UPDATE: Mes excuses, j'aurais dû être plus clair sur les données et sur les résultats attendus.

En supposant que "page-a" soit un index, chaque "page" est littéralement une page apparaissant sur un site Web, où chaque "élément" ressemble à une page de produit qui apparaîtrait sur Amazon, Newegg, etc.

Ainsi, mon résultat attendu pour 'item-d' serait un chemin (ou des chemins) vers cet article. Par exemple (le délimiteur est arbitraire, pour illustration ici): item-d a les chemins suivants:

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

UPDATE2: mon dict d'origine a été mis à jour pour fournir des données plus précises et plus réelles. Ajout de '.html' pour clarification.

Answer 1

Voici une approche simple - c’est O (N carré), donc, pas très évolutive, mais vous servira bien pour un livre de taille raisonnable (si vous avez, par exemple, des millions de pages, vous devez réfléchir approche très différente et moins simple ;-).

Tout d’abord, créez une page de mappage dict in plus utilisable en ensemble de contenu: par exemple, si le dict d'origine est d , créez un autre dict boue sous la forme:

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

Ensuite, faites en sorte que le dict mappe chaque page avec ses pages parentes:

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

Ici, j'utilise des listes de pages parentes (les ensembles conviendraient également), mais ce n'est pas un problème pour les pages contenant 0 ou 1 parent, comme dans votre exemple: vous utiliserez simplement une liste vide pour signifier "no parent", sinon une liste avec le parent comme élément unique. Cela devrait être un graphe orienté acyclique (en cas de doute, vous pouvez vérifier, mais je saute cette vérification).

Maintenant, à partir d'une page, trouver les chemins d'accès de son (ses) parent (s) à un parent sans parent ("page racine") nécessite simplement "marcher". le dict parent . Par exemple, dans le cas parent 0/1:

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

Si vous parvenez à préciser vos spécifications (plages de nombre de pages par livre, nombre de parents par page, etc.), ce code peut sans aucun doute être affiné, mais pour commencer, j'espère qu'il pourra vous aider.

Modifier : comme l'OP l'a précisé, les cas avec > 1 parent (et ainsi, plusieurs chemins) sont effectivement intéressants, laissez-moi vous montrer comment gérer cela:

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)

Bien sûr, au lieu de print ing, vous pouvez renvoyer chaque chemin lorsqu'il atteint une racine (en transformant la fonction dont le corps est dans un générateur) ou autrement traitez-le comme vous le souhaitez.

Modifier à nouveau : un intervenant s'inquiète des cycles dans le graphique. Si cette inquiétude est justifiée, il n’est pas difficile de garder une trace des nœuds déjà vus dans un chemin, de détecter et d’avertir tout cycle. Le plus rapide est de conserver un ensemble à côté de chaque liste représentant un chemin partiel (nous avons besoin de la liste pour la commande, mais la vérification de l'appartenance est O (1) dans les ensembles par rapport à O (N) dans les listes):

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

Par souci de clarté, il vaut probablement la peine de regrouper la liste et de définir un chemin partiel dans une petite classe d’utilitaires Path avec des méthodes appropriées.

Answer 2

Voici une illustration de votre question. Il est plus facile de raisonner sur les graphiques lorsque vous avez une image.

Tout d'abord, abréger les données:

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

Résultat:

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

Convertir au format 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, '}'

Résultat:

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;
}

Tracez le graphique:

$ dot -Tpng -O data.dot

Answer 3

MODIFIER La question étant un peu mieux expliquée, je pense que ce qui suit pourrait être ce dont vous avez besoin, ou du moins, constituer un point de départ.

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

ANCIEN

Je ne sais pas vraiment ce que vous attendez de voir, mais peut-être quelque chose comme cela fonctionnera.

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

Ce serait plus facile, et je pense plus correct, si vous utilisiez un peu structure de données différente:

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

Ensuite, vous n'avez pas besoin de diviser.

Etant donné ce dernier cas, il peut même être exprimé un peu plus court:

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

Et encore plus court, avec les listes vides supprimées:

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

Cela devrait être une seule ligne, mais j’ai utilisé \ comme indicateur de saut de ligne pour pouvoir le lire. sans barres de défilement.