Генерация иерархии из плоских данных

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

Мои данные следующие. У меня есть список объектов. Каждый объект имеет навигационную цепочку и текст. Примеры ниже:

Object 1:
---------
breadcrumb: [Person, Manager, Hourly, New]
text: hello world

Object 2:
---------
breadcrumb: [Person, Manager, Salary]
text: hello world again

И мне нужно преобразовать это в иерархию:

Person
  |--Manager
       |--Hourly
            |--New
                 |--hello world
       |--Salary
             |--hello world again

Я делаю это на Java, но подойдет любой язык.


java hierarchy hierarchical-data hierarchical trie
person David    schedule 18.03.2016    source источник
comment
@zEro: я застрял в концепции того, как к этому подойти. Я пытался создать класс Item, в котором есть List<Item> children и Item parent. Но концепция - это то, где я застрял.   -  person David    schedule 18.03.2016
comment
@David: Это выглядит разумным подходом. Не могли бы вы предоставить свой код?   -  person Oli    schedule 18.03.2016
comment
@ Дэвид Хорошо. Итак, как вы упомянули в своем вопросе, вы ищете иерархию. Древовидная структура данных может быть хорошим представлением того, что вы ищете. Посмотрите, работает ли это для вас.   -  person zEro    schedule 18.03.2016

Ответы (1)


arrow_upward
3
arrow_downward

Вам нужна структура данных Trie, где каждый Node содержит дочерние элементы в List<Node>

  1. Само дерево должно содержать один Node--root, изначально пустой;

  2. Когда поступает новая последовательность, перебираем ее элементы, пытаясь найти соответствующее значение среди существующих дочерних элементов в текущем Node, продвигаясь вперед, если соответствующий элемент найден. Таким образом, вы найдете самый длинный префикс, существующий в дереве, общий для данной последовательности;

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

Понимаете, это не так просто. Код реализации будет длинным и не очевидным. К сожалению, в JDK нет стандартных реализаций trie, но вы можете попробовать найти какие-то уже существующие или написать свои.

Дополнительные сведения см. на странице https://en.wikipedia.org/wiki/Trie#Algorithms

person Alex Salauyou    schedule 18.03.2016