Nähe von Elementen in hierarchischen Strukturen ermitteln

[Thomas K.]

Guten Tag,

ich habe heute ein ausgefallenes Problem mit hierarchischen Strukturen:

Es gibt einen monohierarchischen Baum von Elementen. Jedes Element kommt dabei im Baum nur an einer Stelle vor, es gibt also zu jedem Element nur ein einziges übergeordnetes Element.

Die Elemente sollen Kategorien sein. Sie haben eine beliebige Verschachtelungs- und Verzweigungstiefe.

Es gibt verschiedene Möglichkeiten, dies in einer Datenbank abzubilden, z.B. in dem man jeder Kategorie eine parent_id mitgibt oder in Form sog. Nested Sets und andere Techniken. Darum geht es hier nicht.

Gesucht ist jetzt eine Nähe bzw. Verwandschaft zwischen den Kategorien auf Basis ihrer Position im Baum. Weltlich erklärt:

( ROOT )
                 /        \                 /          \   +------------+            +-----------+
  | Tiere      |            | Pflanzen  |
  +------------+            +-----------+
   |     |                    |
   |     |                    |
   |     +----------+       +---------+
   |     | Hund     +       | Tulpe   |
   |     +----------+       +---------+
   |
   +-------+
   | Katze |
   +-------+

Als "Nachbar" von "Katze" ist es klar, dass "Hund" zu "Katze" eine engere Verwandtschaft hat als zu "Tulpe".

Möchte man nun die Verwandtschaft
   "Hund" <-> "Katze"
und
   "Hund" <-> "Tulpe"
miteinander vergleichen, ist es naheliegend, einfach den Baum als Graphen zu betrachten und die kürzeste Distanz (kürzester Weg) berechnen:

"Hund" <-> "Katze"  = Hund->Tiere->Katze = 1

"Hund" <-> "Tulpe"  = Hund->Tiere->Root->Pflanzen->Tulpe = 3

Hat jetzt Katze weitere Unterkategorien "Löwe" und "Hauskatze", ist die für den Menschen logische Verwandtschaft zwischen "Hund" und "Hauskatze" durch dieses System nicht mehr ganz gegeben.

Außerdem müsste, wenn man nun Inhalte der Kategorien miteinander vergleichen will, einen neu einzutragenden Inhalt mit allen schon bereits bestehenden vergleichen.

Lieber wäre mir eine ein- oder vielleicht zweidimensionale, numerische Repräsentation der Position im Baum. Diese numerische Repräsentation nennen wir "m". Wir speichern zu "Hund" nun "2", zu "Katze" 2.5 und zu Tulpe 5.

Platt gesagt: 2-2.5 >> 2-5,
ergo: Ein Hund ist eher eine Katze als eine Tulpe ;-))

Natürlich möchte ich diese numerische Repräsentation m nicht manuell redaktionell zu den Kategorien pflegen, sondern diese sollte berechenbar sein.

Ist klar, worauf ich hinaus will?

Hat jemand eine Idee oder einen Link?

Danke,
Thomas