Как сжать повторяющиеся ветви в ориентированном графе?

Question

Я много работаю с ориентированными графами, полученными из дампов кучи Java-программ. Их характеризует то, что они содержат много повторяющихся паттернов. Я хотел бы найти способ сжатия таких шаблонов, сохраняя при этом основную структуру графика. Например, рассмотрим следующие «молекулы»:

  |         |
  A1        A5
 / \       / \
B2  C4     B6 C8
 \ /       \ /
  D3        D7

буква представляет тип объекта, а число представляет его уникальный идентификатор (или dfnum). Очевидно, что вторая молекула является повторением первой только с разными идентификаторами. С точки зрения анализа кучи фактические идентификаторы не важны, так что вы можете заменить молекулу на A5 чем-то, что фактически говорит «другая копия A1». При декомпрессии (например, для ввода в анализаторы кучи) вы можете просто назначить произвольные уникальные идентификаторы.

Я мог бы обнаружить такие паттерны, поддерживая хэш типа объектов во время dfs графа. Таким образом, хэш для A1 будет содержать (например) «A ^ B ^ C ^ D», и это будет соответствовать хэшу для A5.

У меня проблема с молекулами, которые указывают на какую-то внешнюю молекулу. Под внешним я имею в виду то, что было посещено ранее в DFS. Например (извините за уродливую графику ascii):

  |         |
  A1        A5
 / \       / \
B2  C4    B6  C7
 \   \   /   /
  \   \ /   /
   \  | |  /
    \ | | /
     \| |/
       D3

для этой ситуации, когда я прихожу, чтобы спуститься с A5, я обнаружил, что D3 уже был посещен. Поэтому я хотел бы, чтобы хэш-код для A5 ​​представлял уникальное значение для D3, а не только тип. То есть что-то вроде "A ^ B ^ C ^ D3". Таким образом, при сжатии / декомпрессии мы дифференцируем A5 как копию A1, а не как некоторую другую A, чьи B и C указывают на некоторые другие D.

Мой вопрос заключается в том, существуют ли какие-либо хитрости для такого расчета, то есть как определить, что D находится "вне" нашей молекулы, корнем которой является A? Это также должно быть сделано эффективным способом, предпочтительно с одним или двумя dfs. (Heapdumps содержат десятки миллионов объектов). Вы не знаете заранее, что A является кандидатом, поэтому, вероятно, это должен быть алгоритм, который делает это во время dfs. Может быть, с чем-то связано дерево доминатор?

Надеюсь, что это имеет смысл!

Редактировать: обновлены диаграммы, чтобы прояснить тот факт, что сами A1 и A5 имеют родителей и являются просто произвольными узлами, обнаруженными во время обхода DFS всего графа.

Уточнение: для моих целей не важно, чтобы матч был гарантирован на 100%. Используя хеш-коды, как указано выше, я рад, что очень маловероятно, что произойдет коллизия хеш-кода, и алгоритм ошибочно классифицирует молекулу неправильно. Поскольку такие столкновения будут редкими, они вряд ли сильно повлияют на общую картину.

Answer 1

Из того, что я могу сказать, это, вероятно, связано с проблемой изоморфизма графов . На странице википедии есть несколько указателей на современные подходы к этой проблеме. Однако, после краткого скимминга, большинство из них, похоже, предназначены для рассмотрения двух целых графов, а не для поиска изоморфных подграфов в большем графе.

Что касается алгоритмов поиска, то мне кажется, что поиск в глубину не является правильным подходом к этой проблеме. Вы можете немного подумать о том, что может сделать обход в ширину. По крайней мере, в конкретном примере, который вы описываете, это позволит вам сначала взглянуть на A1 и A5, прежде чем переходить к определенной форме «молекулы» в любом из них.

Answer 2

Это, вероятно, слишком абстрактный ответ, чтобы действительно помочь, но вы можете создать подграф для каждого повторяющегося шаблона, а затем свернуть каждое вхождение шаблона в один узел (с указателем на соответствующую структуру подграфа). Узел будет управлять всеми ребрами, связанными с шаблоном. Такие ребра также должны помнить узел шаблона, к которому они подключаются, чтобы вы могли предлагать обходы графа, которые скрывают детали представления, но пересекают график, как если бы он был «таким, каким он должен быть». Это будет сложно, если вам не удастся абстрагировать внутреннее представление и ваши алгоритмы должны понимать вложенные графы.

В качестве примечания, хотя изоморфизм графа, как правило, является сложной проблемой, в вашем случае у вас так много метаданных на графе (например, типы объектов, имена полей и т. Д.), Что эквивалентно , помеченному * График 1004 *, с очень редкими, выборочными метками. Такие метки значительно сокращают необходимые усилия для поиска изоморфных шаблонов (конечно, до небольшого размера, иначе ваш кэш шаблонов заполнит всю память).

Поскольку будет много объектов, которые точно следуют определениям классов (если бы не было наследования, объекты были бы структурами, а их типы времени выполнения точно соответствовали бы определениям), я предсказываю, что вы пытаетесь сделать имеет большой потенциал, чтобы значительно сжать граф объекта.

Answer 3

Не задумываясь о вашей проблеме слишком глубоко, я решил свою проблему сжатия веб-данных для своего исследования, используя trie . Вы должны быть в состоянии сериализовать ваши данные в три для целей сжатия.