创造阶层树从字典的网页内容

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

对于任何给定的'item'我怎么找到路径(s)所述的项目？我非常有限的知识的数据结构在大多数情况下，我假定这将是一个层次结构中树。请纠正我，如果我错了！

更新： 我道歉，我应该已经更清楚有关数据和我的预期结果。

假设'页-a'是一个指数的每一页'实际上是一种网页上出现一个网站，作为每个'item'是什么样的产品页，会出现在亚马逊全，等等。

因此，我预期产出为'项目-d'将是一个道(或者)该项目。例如(delimiter是任意的，用于说明这):项目d有以下途径：

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

UPDATE2: 更新原来的我 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父母，因为在您的例子，太-你就可以使用空白名单意思是"没有父"，别列表与父母作为唯一一个项目。这应该是一个非环向图(如果你在疑问，你可以检查，当然，但是我跳过，检查)。

现在，给出一个网页，寻找路径，其父(s)要父母亲("根页")只需要"走"了 parent 词典。E.g.， 在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)

当然，而不是的 printing,你可以 yield 每一个路径当它达到一个根(使功能的身体，这是进入发电机)，或另外对待它在什么方式。

再编辑:一位评论者担心周期在图。如果这一担心是必要的，这不是难以跟踪的节点已经出现在一个道路和探测和警告有关的任何个周期。最快的就是保持一套与每个表示部分路径(我们需要的列表用于订购的，但检查会员是O(1)在集vs 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,))

这可能是值得的，为了清楚起见，包装清单和组代表一部分的路径进入一个小的实用程序类的路径与合适的方法。

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

这应该是一个单一的线，但我用\如断线指标，所以它可以阅读 不滚动条。