ページのコンテンツの辞書から階層ツリーを作成する

StackOverflow https://stackoverflow.com/questions/1809758

質問

次のキーと値のペアは「ページ」と「ページコンテンツ」です。

{
  '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び申し上げます。データと期待される結果についてもっと明確にすべきでした。

「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」が追加されました。

役に立ちましたか？

解決

これは単純なアプローチです-O（Nの2乗）ですので、それほどスケーラブルではありませんが、妥当な本のサイズで十分に機能します（たとえば、数百万ページある場合は、考える必要があります非常に異なる、それほど単純でないアプローチについて;-）。

最初に、より使いやすい辞書を作成し、ページをコンテンツセットにマッピングします。たとえば、元の辞書が 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 dict。たとえば、親が0/1の場合：

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

仕様をより明確にすることができれば（1冊あたりのページ数の範囲、1ページあたりの親の数など）、このコードは間違いなく改良できますが、最初はそれが役立つことを願っています。

編集：OPが＆gt;のケースを明確にしたため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)

もちろん、 print ingの代わりに、ルートに到達したときに各パスを 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に部分パスを表すリストとセットをパックすることは、おそらく価値があります。

他のヒント

質問のイラストです。写真がある場合は、グラフについて簡単に推論できます。

まず、データを短縮します：

#!/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

data.dot

編集質問をもう少し詳しく説明すると、以下が必要なものであるか、少なくとも出発点の何かを提供できると思います。

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

OLD

あなたが何を期待しているのか本当にわかりませんが、 これは動作します。

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行でなければなりませんが、\を改行ブレークインジケータとして使用して読みやすくしました スクロールバーなし。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top