1

以下键：值对是“页面”和“页面内容”。

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

对于任何给定的“项目”，我如何找到所述项目的路径？在大多数情况下，由于我对数据结构的了解非常有限，我假设这将是一个层次结构树。如果我错了，请纠正我！

更新：对不起，我应该更清楚地了解数据和我的预期结果。

假设“page-a”是一个索引，每个“页面”实际上就是一个出现在网站上的页面，而每个“项目”都类似于出现在 Amazon、Newegg 等网站上的产品页面。

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

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

UPDATE2：更新了我的原件dict以提供更准确和真实的数据。添加了“.html”以进行澄清。

4

3 回答 3

2

这是一个简单的方法——它是 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 个父页面的页面也可以，就像您的示例一样 - 您将只使用一个空列表来表示“没有父页面” "，否则以父项为唯一项的列表。这应该是一个无环有向图（如果您有疑问，当然可以检查，但我跳过了检查）。

现在，给定一个页面，查找其父级到无父级（“根页面”）的路径只需要“遍历”parent字典。例如，在 0/1 父案例中：

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

如果您能更好地阐明您的规范（每本书的页数范围、每页的父级数量等），那么这段代码无疑可以改进，但作为开始，我希望它可以提供帮助。

编辑：正如 OP 澄清的那样，具有 > 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在每条路径到达根时（将其主体 this 的函数变成生成器），或者以您需要的任何方式处理它。

再次编辑：评论者担心图中的循环。如果这种担心是有根据的，那么跟踪路径中已经看到的节点并检测和警告任何循环并不难。最快的是在表示部分路径的每个列表旁边保留一个集合（我们需要该列表进行排序，但检查成员资格是 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 中可能是值得的。

于 2009-11-27T17:11:50.603 回答
1

这是您的问题的插图。当你有图片时，更容易推理图表。

首先，缩写数据：

#!/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 数据.dot

数据点

于 2009-11-28T15:30:15.397 回答
0

编辑问题解释得更好一点，我认为以下内容可能是您需要的，或者至少可以提供一些起点。

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

那应该是一行，但我使用 \ 作为换行指示符，因此可以在没有滚动条的情况下读取它。

于 2009-11-27T17:13:44.813 回答