Bäume und Netze

Effizienz oder Details? Das Dilemma

Die Informationsökonomie ist eine Herausforderung für die Informationsverarbeitung. Je mehr Informationen ich zur Hand habe, umso präziser wird mein System. Je mehr Informationen ich aber berücksichtigen muss, umso langsamer wird mein System auch. 

In diesem Dilemma befinden wir uns immer. Wir können natürlich Rechenkapazität und die Speichermöglichkeit unserer Systeme hochschrauben, und auf eine logische Verbesserungen unserer Algorithmen verzichten, doch letztlich ist genau dies immer sinnvoll: Die logische Struktur verbessern. Denn je effizienter ich die Struktur meiner Daten halte, umso präziser und gleichzeitig schneller gelange ich zu meinen Ergebnissen.

Doch ist der klassische Baum die richtige Struktur?

Datenstruktur und Rechengeschwindigkeit

Die Datenstruktur entscheidet, ob die Algorithmen schnell zu den Antworten finden, oder ob sie sich auf Umwege begeben müssen, die wertvolle Rechenzeit kosten. 

Ganz prinzipiell können wir unterscheiden:

• Strukturlose Menge
• Lineare Folge (Stream)
• Bäume
• Netze

Bäume und Netze, als die zwei raffinierteren Möglichkeiten, Informationen miteinander zu verknüpfen, interessieren uns hier. Beide haben ihre Vor- und Nachteile, die es sich zu kennen lohnt.

Immer geht es um die Verbindungen der Elemente. Je komplexer die Struktur der Verbindungen wird, umso mehr Möglichkeiten gibt es, Informationen dicht zu packen und gezielt zu verarbeiten. Eine schlichte Menge hat keine Struktur. Bei einem Stream kennt jedes Element seinen Vorläufer und seinen Nachfolger. Die Folge ist geordnet, in einer Linie oder Achse. Höhere Strukturen kennen mehr als eine lineare Folge (Dimension) und bilden daraus idealerweise ein Netz.

Information als lineare Datenfolge?

Information kann sich zum Beispiel reduktionistisch auf einzelne Bits stützen. Doch für sinnvolle und bedeutungstragende Information reichen einzelne Bits nicht. Mehrere Teilinformationen müssen verbunden werden und dabei wird die Art der Verbindung der Bits wichtig. Dies kann eine einfache lineare Folge der Bits sein, wenn ein Informationsbit auf das nächste folgt, so wie beim Sprechen ein Laut auf den anderen folgt. Doch sobald komplexere Inhalte dargestellt werden, erweist sich eine solche eindimensionale Reihung als unklar, denn die einzelnen Teilinformation habe in Wirklichkeit nicht nur Bezug zu ihren beiden direkten Nachbarn in der linearen Reihung, dem Vor- und dem Nachgänger, sondern sie bilden komplexere Strukturen mit entfernteren Teilinformationen und es entstehen Verschachtelungen und mehrdimensionale Strukturen. Genau diese muss man darstellen können, um als Informationsverarbeiter ausreichend schell und gleichzeitig präzis genug zu sein.

Ein Bitstream, d.h. ein Folge von Bits (z.B. «0-0-1-1-0-1-0-0-1-1-0-1-0-1-1-1-1-0-1-0») ist immer eine klassische lineare Folge.

Die nicht-lineare Komplexität darstellen: Bäume und Netze

Wenn komplexe Informationsstrukturen dargestellt werden und mehrere Elemente in einen Kontext darzustellen sind, reicht eine einfache Aufzählung nicht. Dann kommen die nächst höher strukturierten Formen zur Anwendung. Und hier zeigen sich die beiden grundlegenden Komplexitätsstrukturen: Bäume und Netze.

Diese beiden formalen Strukturen sind komplexer als einfache linearen Folgen. Sie haben sehr unterschiedliche Vor- und Nachteile.

Bäume

Bäume sind überall, Sie finden sich z.B. in:

• Dateisystemen: Das klassische Windows Dateisystem in meinem Computer ist ein Baum.
• Botanische und zoologische Systematiken
• Regalsysteme in Archiven mit Schränken, Etagen, Schubladen und Fächern.
• Klassifikationen, z.B. die ICD-Klassifikationen in der Medizin
• Mind Maps
• Hierarchische Datenbanken
• Straffen Organisationen, z.B. im Militär

Es gibt noch viele weitere Baumsysteme, die alle die gleiche formale Grundstruktur aufweisen, nämlich ein durchgehendes Muster von 1 : n Verzweigungen. Dieses Muster findet sich auch bei Pyramiden und Mind-Map-Sternen. Es hat sehr viele Vorteile, vor allem bezüglich Einfachheit, operativer Effizienz und Übersichtlichkeit. Komplexere Situationen lassen sich allerdings mit Bäumen nicht darstellen.

Formale Eigenheiten von Wissensbäumen

Die klassische Verzweigung des Baums ist 1 : n

Was ist die Form eines Baums? Ein klassischer Baum verweigt sich vom Stamm kontinuierlich nach oben, zu Ästen und Zweigen. Dabei können die Verzweigungen über viele Stufen erfolgen, doch es handelt sich stets um 1 : n Verzweigungen. So hat ein Stamm mehrere, d.h. n Äste und jeder Ast kann wieder mehrere Unteräste haben. Dieses 1:n Muster zieht sich in einem klassischen Baum durch, über alle Stufen.

Der Baum hat auch ein Wurzelwerk unterhalb des Stamms. Auch hier gibt es das gleiche Muster, der Stamm verzweigt sich unter der Erde zuerst in grössere und dann in kleiner Wurzeläste. Stets verzweigt sich beim klassischen Baum jeder grössere Wurzelast in mehrere Unteräste, es zeigt sich also das gleiche 1:n Muster wie oberhalb der Erde.

In der Abbildung sehen sie an der Spitze die Wurzel (W) des Baumes und unten ein Blatt (B). Es gibt immer genau

• Eine Wurzel
• Viele Blätter.

Ein Blatt definiert Zweige und Äste eindeutig

Jedes Blatt in einem klassischen Baum ist über einen eindeutigen Pfad mit der Wurzel verbunden.

Die Information, die in der Nennung des Blattes steckt, impliziert dadurch alle Informationen, die entlang des Pfades bis zur Wurzel anfallen. Diese Informationen müssen vom Wissensbearbeiter nicht mehr zusätzlich angegeben werden, sie stecken bereits in der Datenstruktur des Baumes.
Das hat Vorteile bezüglich der Ökonomie der Wissensrepräsentation, denn viele Angaben folgen automatisch, sobald ein Blatt bekannt ist.
Der Nachteil ist, dass diese Angaben zwingend folgen; die Baumstruktur ist in der Praxis dann oft zu rigid.

Pyramiden als kopfstehende Bäume

Wir verwenden das Wort Baum, auch wenn wir die «Wurzel» oben an der Spitze sehen, als wäre der Baum eine Art Pyramide. Bäume und Pyramiden zeigen effektiv den gleichen Schichtaufbau. Die Stufen sind bei den ägyptischen Pyramiden sofort sichtbar und auch die 1:n Struktur. Ganz oben reicht ein Stein, darunter sind es zum Beispiel vier (n), und so gibt es für jeder Ebene mehr Steine pro Fläche.

Eine solche hierarchische Pyramide zeigt auch die Systematik der Tierarten.

Sterne als ausgefächerte Bäume

Sterne kennen Sie sicher von den Mind Maps Darstellungen. Auch hier handelt es sich stets um 1:n Verzweigungen, diese gehen zwar in alle Himmelsrichtungen, doch das kontinuierlich weitergezogene 1:n Muster bleibt auch bei Sternen erhalten. Man kann den 360° Fächer des Sterns zusammenschieben, sodass der Stern nur noch in eine Richtung in eine Richtung zeigt, z.B. nach unten, dann gleicht er einer Pyramide, oder nach oben, dann gleicht er einem Baum.

Bäume, Pyramiden und Sterne lassen sich eineinander überführen

Von der Informationsstruktur her gesehen, sind Bäume, Pyramiden und Sterne identisch. Genauso wie Pyramiden um 180° gedrehte Bäume sind, sind Sterne nur weit ausgefächterte Bäume. Formal, d.h. topologisch, handelt es sich um die gleiche Struktur, ob Baum, Pyramide oder Stern. Wir haben es mit einer klassischen Grundstruktur zu tun, die wir überall beobachten können.

Gemeinsamkeit: Ein Zentrum (= Wurzel)

Die Gemeinsamkeit von Bäumen, Pyramiden und Sternen liegt darin, dass sie genau ein Zentrum haben:

• Die Wurzel des Baumes
• Die Spitze der Pyramide
• Das Zentrum des Sterns

Von diesem gemeinsamen Zentrum gehen die Verzweigungen aus. Formal, im Sinn der Verknüpfungen, spielt es keine Rolle, in welche Richtung die Verzweigungen gehen; wichtig ist nur, dass es stets 1:n Verzweigungen sind, dass also keine Schleifen (m:n) entstehen, denn dann wäre der eindeutige Pfad nicht mehr gewährleistet.

Bäume, Pyramiden und Sterne sind deshalb formal (bezüglich der Verknüpfungen) identische Strukturen.

Ihre Grundstruktur des hierarchischen Baums unterscheidet sich grundsätzlich von der Grundstruktur eines Netzes.

​Netze als Alternative

Im Unterschied zu Pyramiden und Sternen, lassen sich Netze lassen nicht in Bäume überführen. Es handelt sich um eine grundlegend andere formale Struktur. Netze enthalten Schleifen. Sie ermöglichen dadurch Selbstreferenzialität. Bäume haben mit ihrer Wurzel einen klaren Ausgangspunkt (genauso wie Sterne und Pyramiden). Bei Netzen ist dies nicht der Fall.

Mathematiker bezeichnen Netze als Graphen.

Wurzeln und Schleifen

Die Wurzel ist der Startpunkt eines Baums, bzw. der oberste Stein einer Pyramide. Netze aber haben keinen solchen Startpunkt. Sie bestehen nicht aus Verzweigungen wie der Baum, sondern aus Schleifen. Und eine Schleife ist rund und hat keinen eindeutigen Startpunkt. Weil die Netze aus Schleifen bestehen, haben sie keine Wurzel. Diese formalen Unterschiede in der Datenanordnung hat grosse Konsequenzen für den Ablauf von Algorithmen in Bäumen, bzw. in Netzen.

Ein Netz besteht aus Schleifen (Loops), hier blau eingezeichnet. Ein Hierarchie hat keine Schleifen, denn dann wäre das 1:n Prinzip verletzt. Dafür hat die Hierarchie eine einzige Wurzel, das Netz hat keine. Die Hierarchie verknüpft 1:n, das Netz m:n.

Komplexität

Komplexe Strukturen können mit simplen Bäumen nicht mehr dargestellt werden, weshalb Netze ins Spiel kommen. Sie sind schwieriger formal zu behandeln, sind jedoch unabdingbar für jedes komplexere Wissensmanagement. Sie benötigen logische Methoden, welche die Beschränkungen, die in der formalen Struktur der Bäume liegen, überwinden. Im Besonderen muss auf das Vorhandensein von Schleifen (Loops) eingegangen werden.

Fazit

Sobald wir über einfache Aneinanderreihung von Informationen hinausgehen und Informationen miteinander komplexer verknüpfen, sind die beiden nächsteinfacheren Strukturen Bäume und Netze.

Bäume
Formal gehören zu den Bäumen auch die Pyramiden und Sterne, also alles mit einem klaren Ausgangspunkt, einer klaren Wurzel. Bäume, Pyramiden und Sterne haben keine Schleifen, sondern stets Verzweigungen, also 1 : n Verknüpfungen, zwischen ihren Elementen.

Netze
Netze sind komplexer. Sie enthalten stets m : n Verknüpfungen. Sie sind schwieriger mit Algorithmen zu behandeln als Bäume, können aber noch komplexere Sachverhalte ausdrücken.

Meine Erfahrung zeigt mir: Wir brauchen beides, Bäume und Netze.

Dies ist ein Beitrag zur Informationstheorie.