Сокращение дерева атрибутов

Question

у меня есть дерево из нескольких тысяч узлов, украшено логических атрибутов, что-то вроде этого (атрибуты в скобках):

Root (x=true, y=true, z=false) 
    Interior 1 
     Leaf 1 (x=false, z=false) 
     Leaf 2 (x=false, y=false, z=false) 
    Interior 2 
     Leaf 3 
    etc. 

То, что я хотел бы сделать, это найти наименьшее количество украшений необходимо сохранять значения атрибутов, учитывая следующие ограничения/Информация:

1. атрибуты наследуются дочерними узлами
2. только результирующие атрибуты узлов листа являются важными (включая унаследованные атрибуты). Поэтому, если установка атрибута «по умолчанию» на внутреннем узле позволяет мне сбросить кучу атрибутов на своих дочерних элементах, это нормально.
3. В нашей модели есть стенография для установки всех атрибутов как истинных, так и ложных. Например, (x=false,y=false,z=false) может быть представлен одним декоратором, тогда как (x=false,y=false,z=true) займет три.
4. Число дочерних узлов будет значительно превышать внутренние узлы (не менее 25 до 1)
5. Исходное состояние дерева будет иметь много избыточности.
6. Я использую Java и добавление внешнего lib для решения этой проблемы не имеет большого значения.

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

Я думаю, что ограничение №3 бросает меня за цикл, потому что без него я могу просто разобраться с каждым атрибутом индивидуально, что просто (и я уже реализовал решение этого, прежде чем я понял, что пришло больше атрибутов).

Надеюсь, это достаточно описательно, чтобы дать общую картину проблемы. При необходимости я могу привести больше примеров или информации. Спасибо!

Answer 1

Я думаю, что (3.) можно в основном игнорировать, потому что нас интересуют только его листья. Вот что я хотел бы предложить:

1. для каждого листа со всеми булевы один из способов, с помощью клавиш (3.).

2. Затем для каждого внутреннего узла присвойте атрибутам значение большинства для листьев ниже, не обрабатывается 1, и удалите теперь избыточные назначения.

3. Для более высоких внутренних узлов, сделайте то же самое, глядя на непосредственных детей, вплоть до корня.

Это эвристика, и я не пробовал, но был бы моим первым выстрелом, если бы я был вами. Дайте мне знать, как это происходит.