將列表中的一組URL作爲樹結構來表示

Question

我有一個存儲URL的字典列表。它只有兩個字段，title和url。例如：

[ 
    {'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'}, 
] 

但是，我會從這個列表中得到一個樹結構。我在尋找這樣的事情：

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

我在第一次嘗試將是一堆的環的湯裏urlparse，我相信有一個更好更快的方式來做到這一點。

我已經看到人們在SO工作魔術與列表解析，lambda函數等我仍然在找出它的過程。

（對於Django開發：我將使用這個我的Django應用我存儲在一個名爲Page模型，它有兩個字段name和title的URL。）

Answer 1

第三次是魅力。這是你在那裏的一些不錯的結構:)。在你的評論中，你提到你「還沒有能夠想象更好的樹格式來表示這樣的數據」 ......這讓我再次冒昧（稍微）改變輸出的格式。爲了動態添加子元素，必須創建一個字典來容納它們。但是對於「葉節點」，這個字典永遠不會被填充。如果需要，它們當然可以通過另一個循環來移除，但在迭代過程中不會發生，因爲對於可能的新節點應該存在空的dict。有些節點在沒有文件的情況下：這些節點將包含一個空的list。

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) 

輸出：

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

這裏是我的解決方案。它似乎工作。從Jro的一個非常不同的方法：

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

我似乎無法弄清楚爲什麼我需要排序在每次遞歸。我敢打賭，如果我在周圍工作，我可以再刮幾秒鐘。