Как сжать повторяющиеся ветви в ориентированном графе?
Я много работаю с ориентированными графами, полученными из дампов кучи 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%. Используя хеш-коды, как указано выше, я рад, что очень маловероятно, что произойдет коллизия хешей, и алгоритм ошибочно классифицирует молекулу неправильно. Поскольку такие столкновения будут редкими, они вряд ли сильно повлияют на общую картину.
3 ответа
Не вдаваясь в подробности о вашей проблеме, я решил проблему сжатия веб-данных для своего исследования с помощью trie. Вы должны иметь возможность сериализовать ваши данные в три для целей сжатия.
Вероятно, это слишком абстрактный ответ, чтобы действительно помочь, но вы можете создать подграф для каждого повторяющегося шаблона, а затем свернуть каждое вхождение шаблона в один узел (с указателем на соответствующую структуру подграфа). Узел будет управлять всеми ребрами, связанными с шаблоном. Такие ребра также должны помнить узел шаблона, к которому они подключаются, чтобы вы могли предложить обходы графа, которые скрывают детали представления, но пересекают график, как если бы он был "таким, каким он должен быть". Это будет сложно, если вам не удастся абстрагировать внутреннее представление и ваши алгоритмы должны понимать вложенные графы.
В качестве примечания, хотя изоморфизм графов, как правило, является сложной проблемой, в вашем случае у вас на графике так много метаданных (например, типы объектов, имена полей и т. Д.), Что эквивалентно наличию помеченного графа с очень редким, избирательным этикетки. Такие метки значительно сокращают необходимые усилия по поиску изоморфных шаблонов (конечно, до небольшого размера, иначе ваш кэш шаблонов заполнит всю память).
Поскольку будет много объектов, которые будут точно следовать определениям классов (если бы не было наследования, объекты были бы структурами, а их типы времени выполнения точно соответствовали бы определениям), я предсказываю, что то, что вы пытаетесь сделать, имеет много потенциал значительно сжать граф объекта.
Из того, что я могу сказать, это, вероятно, связано с проблемой изоморфизма графов. На странице википедии есть несколько указателей на современные подходы к этой проблеме. Тем не менее, из краткого скимминга, большинство из них, кажется, предназначены для рассмотрения двух целых графов, а не для поиска изоморфных подграфов в большем графе.
Что касается алгоритмов поиска, то мне кажется, что поиск в глубину не является правильным подходом к этой проблеме. Вы можете немного подумать о том, что может сделать обход в ширину. По крайней мере, в конкретном примере, который вы описываете, это позволит вам сначала взглянуть на A1 и A5, прежде чем переходить к определенной форме "молекулы" в любом из них.