Representación de un conjunto de URL en una lista como estructura de árbol

Question

Tengo una lista de dicts que almacena URL. Tiene simplemente dos campos, title y url. Ejemplo:

[ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
] 

Sin embargo, me gustaría obtener una estructura de árbol de esta lista de dicts. Estoy buscando algo como esto:

{ 'www.example.com': 
    [ 
    { 'something': 
     [ 
     { 'thisthing': 
      [ 
      { 'title': 'Detail Page', 'url': 'detail.htm'} 
      ] 
     }, 
     [ 
      { 'title': 'Index Page', 'url': 'index.htm'}, 
      { 'title': 'Other Page', 'url': 'other.htm'} 
     ] 
     ] 
    }, 
    { 'thatthing': 
     [ 
     { 'title': 'About Page', 'url': 'about.htm'} 
     ] 
    } 
    ] 
} 

Mi primer intento de esto sería una sopa urlparse en un montón de los bucles y estoy seguro de que hay una manera mejor y más rápida de hacer esto.

He visto gente en SO que trabaja la magia con listas de comprensión, funciones lambda, etc. Todavía estoy en el proceso de descifrarlo.

(Para los desarrolladores de Django: Voy a utilizar este mi aplicación Django Estoy almacenando las direcciones URL en un modelo llamado Page que tiene dos campos y nametitle.)

Answer 1

La tercera vez es el encanto ... esa es una buena estructura que tienes allí :). En su comentario, menciona que "no se ha podido pensar en un mejor formato de árbol para representar datos como este" ... esto me hizo tomar nuevamente la libertad de (solo ligeramente) alterar el formato de la salida. Para agregar subelementos dinámicamente, se debe crear un diccionario para alojarlos. Pero para "nodos hoja", este diccionario nunca se rellena. Si se desea, estos pueden ser eliminados por otro ciclo, pero no puede suceder durante la iteración porque el dict vacío debe estar presente para posibles nuevos nodos. La parte va para los nodos que no tienen un archivo en el: estos contendrán un list vacío.

ll = [ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
] 

# First build a list of all url segments: final item is the title/url dict 
paths = [] 
for item in ll: 
    split = item['url'].split('/') 
    paths.append(split[2:-1]) 
    paths[-1].append({'title': item['title'], 'url': split[-1]}) 

# Loop over these paths, building the format as we go along 
root = {} 
for path in paths: 
    branch = root.setdefault(path[0], [{}, []]) 
    for step in path[1:-1]: 
     branch = branch[0].setdefault(step, [{}, []]) 
    branch[1].append(path[-1]) 

# As for the cleanup: because of the alternating lists and 
# dicts it is a bit more complex, but the following works: 
def walker(coll): 
    if isinstance(coll, list): 
     for item in coll: 
      yield item 
    if isinstance(coll, dict): 
     for item in coll.itervalues(): 
      yield item 

def deleter(coll): 
    for data in walker(coll): 
     if data == [] or data == {}: 
      coll.remove(data) 
     deleter(data) 

deleter(root) 

import pprint 
pprint.pprint(root) 

Salida:

{'www.example.com': 
    [ 
     {'something': 
      [ 
       {'thisthing': 
        [ 
         [ 
          {'title': 'Detail Page', 'url': 'detail.htm'} 
         ] 
        ] 
       }, 
       [ 
        {'title': 'Index Page', 'url': 'index.htm'}, 
        {'title': 'Other Page', 'url': 'other.htm'} 
       ] 
      ], 
     'thatthing': 
      [ 
       [ 
        {'title': 'About Page', 'url': 'about.htm'} 
       ] 
      ] 
     }, 
    ] 
} 

Answer 2

aquí está mi solución. Parece funcionar.

import itertools 
import pprint 

pages = [ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'dtgtet Page', 'url': 'http://www.example.com/thatthing/'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/thisthing/detail.htm'}, 
] 



def group_urls(url_set, depth=0): 
    """ 
    Fetches the actions for a particular domain 
    """ 
    url_set = sorted(url_set, key=lambda x: x['url'][depth]) 

    tree = [] 

    leaves = filter(lambda x: len(x['url']) - 1 == depth, url_set) 
    for cluster, group in itertools.groupby(leaves, lambda x: x['url'][depth]): 
     branch = list(group) 
     tree.append({cluster: branch}) 

    twigs = filter(lambda x: len(x['url']) - 1 > depth, url_set) 
    for cluster, group in itertools.groupby(twigs, lambda x: x['url'][depth]): 
     branch = group_urls(list(group), depth+1) 
     tree.append({cluster: branch}) 

    return tree 

if __name__ == '__main__': 
    for page in pages: 
     page['url'] = page['url'].strip('http://').split('/') 

    pprint.pprint(group_urls(pages)) 

Me parece que no puede entender por qué necesito para ordenar al comienzo de cada recursión: Un enfoque muy diferente de la de Jro. Apuesto a que si trabajé en eso, podría tomar otro par de segundos.