페이지 내용 사전에서 계층 트리 생성

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

주어진 '항목'에 대해 어떻게 해당 항목의 경로를 찾을 수 있습니까? 대부분의 경우 데이터 구조에 대한 지식이 매우 제한되어 있기 때문에 이것이 계층 구조 트리라고 가정합니다. 내가 틀렸다면 나를 바로 잡아주세요!

업데이트: 사과 드, 데이터와 예상 결과에 대해 더 명확해야했습니다.

'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'은 설명을 위해 추가되었습니다.

Answer 1

간단한 접근 방식은 다음과 같습니다. O (N Squared)이므로 확장 가능성이 높지는 않지만 합리적인 책 크기에 도움이 될 것입니다 (예를 들어, 수백만 페이지가 있다면 매우 생각해야합니다. 다르고 덜 간단한 접근 ;-).

먼저, 더 유용한 독기를 만들고, 내용 세트에 페이지를 매핑하십시오 : 예 : 원래 dict가 d, 또 다른 dict를 만드십시오 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 부모가있는 페이지에도 괜찮습니다. ", 그렇지 않으면 부모가 하나의 유일한 항목으로 목록입니다. 이것은 acyclic 지시 그래프 여야합니다 (의심스러운 경우 확인할 수는 있지만 수표를 건너 뛰고 있습니다).

이제 페이지가 주어지면 부모의 부모가 부모가없는 부모 ( "루트 페이지")로 경로를 찾는 것은 단순히 "걷기"가 필요합니다. parent DITT. 예를 들어, 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 각 경로는 루트에 도달 할 때 (신체가 발전기에있는 기능을 만드는) 또는 필요한 방식으로 처리합니다.

다시 편집하십시오: 댓글 작성자는 그래프의 사이클에 대해 걱정하고 있습니다. 그 걱정이 필요하다면, 경로에서 이미 보이는 노드를 추적하고주기에 대해 감지하고 경고하는 것은 어렵지 않습니다. 가장 빠른 부분은 부분 경로를 나타내는 각 목록과 함께 세트를 유지하는 것입니다 (주문 목록이 필요하지만 멤버십을 확인하는 것은 O (1)에서 O (n) 목록에서 O (1)입니다.

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

그것은 한 줄이어야하지만 를 라인 브레이크 표시기로 사용하여 스크롤 바없이 읽을 수 있습니다.