ページのコンテンツの辞書から階層ツリーを作成する
-
05-07-2019 - |
質問
次のキーと値のペアは「ページ」と「ページコンテンツ」です。
{
'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が>のケースを明確にしたため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 = {
'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行でなければなりませんが、\を改行ブレークインジケータとして使用して読みやすくしました スクロールバーなし。