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 2 乗) であるため、スケーラビリティはそれほど高くありませんが、適度なサイズの本の場合には十分に役立ちます (たとえば、数百万ページのページがある場合は、非常によく考える必要があります)。異なる、単純ではないアプローチ;-)。

最初に、より使いやすい dict を作成し、ページを一連のコンテンツにマッピングします。たとえば、元の dict が である場合、d別の dictmudを次のように作成します。

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

仕様 (1 冊あたりのページ数の範囲、1 ページあたりの親の数など) をより明確にすることができれば、このコードは間違いなく洗練されたものになる可能性がありますが、最初に役立つことを願っています。

編集：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各パスがルートに到達したときに (本体がジェネレーターになる関数を作成する)、または必要な方法でそれを処理することができます。

再度編集: コメント投稿者は、グラフの循環について心配しています。その心配が正当化されるのであれば、パスですでに見られるノードを追跡し、サイクルを検出して警告することは難しくありません。最も速いのは、部分パスを表す各リストの横にセットを保持することです (順序付けにはリストが必要ですが、メンバーシップのチェックはセットの 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 data.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])

これは 1 行のはずですが、スクロールバーなしで読めるように \ を改行インジケーターとして使用しました。

于 2009-11-27T17:13:44.813 に答える