나는 자바 프로그램의 힙 덤프 (heap dump)로 인해 유향 그래프 (directed graphs)를 많이 사용한다. 그것들을 특징 짓는 한 가지는 반복되는 패턴이 많이 포함되어 있다는 것입니다. 그래프의 필수 구조를 유지하면서 그러한 패턴을 압축하는 방법을 찾고 싶습니다. 예를 들어 다음과 같은 "분자"를 고려해유향 그래프에서 반복 분기를 압축하는 방법은 무엇입니까?
| |
A1 A5
/\ /\
B2 C4 B6 C8
\/ \/
D3 D7
편지 개체의 유형을 나타내는 숫자는 고유 ID (또는 dfnum)를 나타냅니다. 분명히 두 번째 분자는 서로 다른 ID를 가진 첫 번째 분자의 반복이다. 힙 분석 관점에서 실제 ID는 중요하지 않으므로 A5의 분자를 "A1의 다른 사본"이라고 효과적으로 말하는 것으로 대체 할 수 있습니다. 감압시 (예를 들어 힙 분석기에 입력하기 위해) 임의의 고유 ID를 지정할 수 있습니다.
그래프의 dfs 중에 오브젝트 유형의 해시를 유지함으로써 이러한 패턴을 발견 할 수 있습니다. 따라서 A1의 해시에는 (예를 들어) "A^B^C^D"가 포함되며 A5의 해시와 일치합니다.
내가 가진 문제는 외부 분자를 가리키는 분자 때문입니다. 외부에서 나는 dfs에서 더 일찍 방문한 것을 의미합니다. 이 상황에 대한
| |
A1 A5
/\ /\
B2 C4 B6 C7
\ \ //
\ \//
\ | |/
\ | |/
\| |/
D3
내가 A5에서 내가 D3 이미 방문한 된 것을 찾아 내려 온 (추한 아스키 그래픽에 대한 죄송합니다) 예를 들어. 그래서 A5의 해시 코드가 형식이 아닌 D3의 고유 값을 나타 내기를 바랍니다. 나는. "A^B^C^D3"과 같은 것입니다. 그래서 압축/압축 해제에서 우리는 A5를 다른 A가 아닌 A의 복사본으로 차별화합니다. B와 C는 다른 D를 가리 킵니다.
제 질문은 그러한 계산을 수행하는 트릭이 있는지 여부입니다. D가 우리의 분자 인 "외부"에 있다고 말할 수 있습니까? 이것은 또한 효율적인 방법으로, 바람직하게는 하나 또는 두 개의 dfs로 수행되어야합니다. (힙 덤프에는 수천만 개의 개체가 포함되어 있습니다.) A가 후보라는 것을 미리 알 수 없으므로 아마도 dfs 중에 알고리즘을 수행해야합니다. 어쩌면 지배자 나무가 관련이 있을까요?
희망이 맞습니다!
편집 : A1 및 A5 자체가 부모를 가지며 전체 그래프의 DFS 보행 중에 발견 된 임의의 노드라는 사실을 명확히하기 위해 다이어그램을 업데이트했습니다.
명확한 설명 : 본인의 목적 상 100 % 보장된다는 것은 중요하지 않습니다. 위와 같이 해시 코드를 사용하면 해쉬 콜리 전 (hash collision)이 발생할 가능성이 매우 적어서 알고리즘이 잘못 분자를 잘못 분류하게됩니다. 이러한 콜리 존은 드물기 때문에 전반적인 그림에 많은 영향을 미치지 않습니다.
무슨 뜻인지 이해가 안됩니다. 우리는 후보 분자가 어디서 시작되는지 미리 알지 못한다는 것을 기억하십시오. 위의 다이어그램에서 A1과 A5 자체는 부모를 가지며 DFS 중에 우리가 마주 치는 노드 일뿐입니다. 퍼즐은 A5가 A1의 복사본임을 인식하는 것입니다. –