从页面内容字典创建层级树

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”是一个索引，每个“页面”实际上就是网站上显示的一页，而每个“项目”就像是亚马逊、Newegg等网站上出现的产品页面。

因此，我对“项目-d”的期望输出将是通往该项目的路径（或多条路径）。例如（分隔符是随意的，这里只是为了说明）： 项目-d有以下路径：

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

更新2：我更新了原来的dict，以提供更准确和真实的数据。为了更清楚，加上了“.html”。

Answer 1

编辑 经过更清楚的解释后，我觉得下面的内容可能正是你需要的，或者至少可以作为一个起点。

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

这应该是一行代码，但我用了 \ 作为换行符，这样可以在不出现滚动条的情况下阅读。

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

这里有一个简单的方法——它的复杂度是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])

如果你能更清楚地说明你的需求（比如每本书的页数范围、每页的父页面数量等等），那么这段代码肯定可以进一步优化，但作为一个起点，希望它能帮到你。

编辑：因为提问者澄清了有多个父页面（也就是多条路径）的情况确实很重要，所以让我来展示一下如何处理这个问题：

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

为了清晰起见，把表示部分路径的列表和集合打包成一个小工具类Path，并提供合适的方法，可能是个不错的主意。