Enkonduko en la aŭtomatan daten-prilaboradon

11 Organizo de datenoj: hierarkioj

La ĝisnunaj lecionoj montris, kiel kodi klare apartigeblajn datenojn, ekz. por unu teksto, letero, bildo, muzikaĵo. Tiajn datenojn oni ofte storas en „dosieroj“, t. e. pecoj de komputila memoro, kiuj posedas jenajn du ecojn:

  • ili estas daŭremaj, tio signifas, ke ilia enhavo ne perdiĝas, kiam oni malŝaltas la komputilon; normale ili fizike troviĝas sur magneta aŭ optika disko aŭ bendo;
  • ili posedas nomon aŭ alian adreson aŭ identigilon, per kiu eblas retrovi ilin.

11 Organisation von Daten: Hierarchien

Die bisherigen Lektionen haben gezeigt, wie man einzelne, unterscheidbare Datenobjekte, zum Beispiel einen Text, einen Brief, ein Bild, ein Musikstück, kodieren kann. Solche Daten werden oft in „Dateien“ gespeichert, das sind Abschnitte von Rechnerspeicher, die zwei Eigenschaften besitzen:

  • sie sind persistent (dauerhaft); das bedeutet, das ihr Inhalt nicht verloren geht, wenn der Rechner ausgeschaltet wird; gewöhnlich befinden sie sich physisch auf einer Magnetplatte oder optischen Platte oder einem Band;
  • sie besitzen einen Namen oder eine andere Art von Adresse oder Identifizierer, durch den/die man sie wiederfinden kann.

Kutime necesas administri multajn tiajn objektojn, kaj estas penige trovi kaj memori apartajn nomojn por ĉiu el ili, se oni ne havas sistemon por tio. Sed ĉar komputiloj bone kapablas uzi sistemojn, ili proponas sistemojn por administri grandajn arojn de dosieroj en superrigardebla formo. Grava principo ĉe tio estas la hierarkieco.

La vorto „hierarkio“ aŭ „hierarĥio“ devenas de la grekaj vortoj „hieros“ (sankta) kaj „arĥejn“ (regi) kaj origine nomis la strukturon de pastra sistemo, en kiu ĉiu pastro havas super si (unu) pli altrangan pastron, sed povas havi sub si plurajn malpli altrangan. Tia pastraro do formas strukturon, kiu similas al „arbo“, sed kiun oni kutime prezentas tiel, ke la „radiko“ (la plej altranga) troviĝas supre, kontraŭe al botaniko. Kiel ekzemplon ni prenu strukturon, en kiu direktoro havas sub si fakestrojn, kiuj sub si havas grupestrojn, kiuj estras grupanojn. Tian strukturon eblas prezenti grafike kiel grafon el verticoj (aŭ nodoj) kaj eĝoj:

Üblicherweise muss eine Vielzahl solcher Objekte verwaltet werden, und es ist mühsam, für jedes einen eigenen Namen zu finden und sich die Namen zu merken, wenn man kein System dafür hat. Rechner sind aber sehr gut in der Verwendung von Systemen; sie bieten Systeme zur Verwaltung großer Mengen von Dateien in überschaubarer Form an. Ein wichtiges Prinzip ist hierbei die hierarchische Anordnung.

Das Wort Hierarchie kommt von den griechischen Wörtern „hieros“ (heilig) und „archejn“ (herrschen) und bezeichnete ursprünglich die Struktur eines Priestersystems, in dem jeder Priester über sich einen höher-rangigen Priester hat und unter sich mehrere niedrigere Priester haben kann. Eine solche Priesterschaft bildet eine Struktur, die einem „Baum“ ähnelt, die man aber gewöhnlich so darstellt, dass die „Wurzel“ (der Ranghöchste) oben steht, im Widerspruch zur Botanik, wo die Wurzel meist unten ist. Als Beispiel betrachten wir eine Struktur, in der ein Direktor (direktoro) unter sich Abteilungsleiter (fakestro) hat, die unter sich Gruppenleiter (grupestro) haben, die Vorgesetzte von Gruppenmitgliedern (grupano) sind. Eine solche Struktur lässt sich grafisch als Graph aus Knoten und Kanten darstellen:

La ĉi-supra prezento bone elstarigas la kvar nivelojn de tiu hierarkio kaj la „dependecojn“ (rilatojn inter subulo kaj superulo) kaj la fakton, ke de ĉiu vertico ekzistas precize unu „vojo“ al la radiko (kiel en ĉiu arbo). Sed ĝi havas ankaŭ problemojn: Unu estas, ke en la subaj niveloj ofte mankas spaco, ĉar ili havas multe pli da anoj ol la supraj. Tial oni emas elekti aliajn manierojn de prezentado. Unu estas precipe facile realigebla en ortangulaj koordinataj sistemoj, do ekzemple sur komputilaj ekranoj. Por ĝi necesas iom turni kaj disŝovi la arban strukturon: Unue ni rotaciigu kaj ŝovu ĝin tiel, ke

Die obige Darstellung verdeutlicht die vier Stufen dieser Hierarchie und die „Abhängigkeiten“ (Beziehungen zwischen Untergebenen und Vorgesetzten) sowie die Tatsache, dass es von jedem Knoten genau einen „Weg“ zur „Wurzel“ gibt (wie in jedem Baum). Die Darstellungsform wirft jedoch auch Probleme auf: Eines davon ist, dass es auf den unteren Stufen oft zu Platzmangel kommt, weil diese Stufen mehr Knoten aufweisen als die höheren. Daher wählt man oft andere Formen der Darstellung. Eine davon ist besonders leicht in rechtwinkligen Koordinatensystem darstellbar, zum Beispiel auf Rechnerbildschirmen. Dazu muss die Baumstruktur etwas gedreht und verschoben werden: Zuerst drehen und verschieben wir sie so, dass

  • la niveloj estu aranĝitaj de maldekstre dekstren,
  • ĉiu ero havu propran linion, kaj
  • inter la linioj de ajnaj du eroj estu nur „subuloj“ de la unua kaj „superuloj“ de la dua:
  • die Stufen (Ebenen) von links nach rechts angeordnet sind,
  • jeder Knoten eine eigene Zeile hat,
  • zwischen den Zeilen von je zwei Knoten sich nur „Untergebene“ des ersten Knotens und „Vorgesetzte“ des zweiten befinden:

La lasta kondiĉo signifas, ke la verticojn oni vertikale ordigas laŭ la plej supra malsama elemento sur ilia vojo al la radiko. La saman rezulton oni atingas, se en ĉiu nivelo oni nomas la anojn alfabete (a, b, c, …) kaj tiam ordigas la nomojn kiel en leksikono („leksikografie“).

Tiam necesas nur iom rearanĝi la eĝojn por veni al formo, kiu estas taŭga por tabel-simila prezentado:

Diese Bedingung bedeutet, dass man die Knoten vertikal nach dem höchsten unterschiedlichen Element auf ihrem Weg zur Wurzel ordnet. Man erhält dasselbe Ergebnis, wenn man die Knoten innerhalb jeder Ebene nach dem Alphabet benennt (a, b, c, …) und dann die Namen wie in einem Wörterbuch („lexikographisch“) ordnet.

Wenn man nun noch die Kanten etwas umformt, kommt man zu einer Form, die sich für eine tabellenartige Darstellung eignet:

precipe se forlasi la „bobelojn“ ĉirkaŭ la eroj (verticoj):

vor allem, wenn man die „Blasen“ um die Elemente (Knoten) weglässt:

direktoro Direktor
fakestro A Abteilungsleiter A
grupestro 1 Gruppenleiter 1
grupano a Mitarbeiter a
grupano b Mitarbeiter b
grupano c Mitarbeiter c
grupestro 2 Gruppenleiter 2
  grupano k Mitarbeiter k
  grupano l Mitarbeiter l
fakestro B Abteilungsleiter B
grupestro 3 Gruppenleiter 3
grupano x Mitarbeiter x
grupano y Mitarbeiter y
grupano z Mitarbeiter z
grupestro 4 Gruppenleiter 4
... ... ... ... … … … …

La lasta formo estas kutime uzata sur komputilaj ekranoj, ĉar ĝi bone adaptiĝas al dudimensiaj ortaj koordinatoj, kutimaj en ekranoj kaj presiloj. Oni trovas ĝin en dosieraj navigiloj („administriloj“), ret-poŝtaj administriloj ktp. Malavantaĝo de ĝi estas, ke samrangaj elementoj („fratoj“) en la altaj niveloj aperas ofte en granda distanco (komparu la „fakestrojn“ en la ekzemplo). Por kompensi tiun malavantaĝon multaj iloj por prezentado de hierarkioj donas la eblon, „kunfaldi“ branĉojn de la arbo, tiel ke videblas nur ties plej alta parto aŭ vertico. Kutime oni grafike distingas la kunfalditajn kaj la disfalditajn branĉojn, ekzemple per plusa (+) kaj minusa (−) signoj. La sekva bildo montras la antaŭan ekzemplon kun la unua „fako“ (kolore markita) kunfaldita.

Diese letzte Form wird häufig in Bildschirmdarstellungen genutzt, da sie sich gut an zweidimensionale rechtwinklige Koordinaten anpasst, die auf Bildschirmen und Druckern üblich sind. Man findet diese Darstellung in Dateisuchern („browser“, „explorer“), Netzpost-Programmen usw. Ein Nachteil dieser Darstellung ist, dass gleichrangige Elemente („Geschwister“) auf höheren Ebenen oft weit voneinander entfernt erscheinen (wie zum Beispiel die „Abteilungsleiter“ in unserem Beispiel). Um diesen Nachteil zu kompensieren, bieten viele Werkzeuge zur Hierarchiedarstellung die Möglichkeit, Zweige des Baumes „zusammenzufalten“, so dass nur deren oberster Teil oder Knoten sichtbar ist. Gewöhnlich kennzeichnet man zusammen- und auseinandergefaltete Zweige graphisch, zum Beispiel durch ein Plus- (+) oder Minus- (−) -Zeichen. Das folgende Bild zeigt das vorige Beispiel mit eingeklappter erster „Abteilung“ (farbig markiert).

direktoro
fakestro A
fakestro B
grupestro 1
grupano x
... ... ... ...

Specimenaj demandoj

  • Kio karakterizas dosierojn?
  • Kio karakterizas hierarkiajn strukturojn?
  • Kial oni nomas hierarkiajn strukturojn „arboj“?
  • Kiom da rekte pli altrangaj (superaj) elementoj povas havi elemento de arbo?
  • Kiom da rekte malpli altrangaj (malsuperaj) elementoj povas havi elemento de arbo?
  • Kiom da vojoj povas ekzisti de arba vertico al la radiko de la arbo?

Beispielfragen

  • Wodurch sind Dateien charakterisiert?
  • Wodurch sind hierarchische Strukturen charakterisiert?
  • Warum nennt man hierarchische Strukturen „Bäume“?
  • Wie viele unmittelbar höher-rangige Elemente („Vorgesetzte“) kann ein Element eines Baumes haben?
  • Wie viele unmittelbar nierdiger-rangige Elemente („Untergebene“) kann ein Element eines Baumes haben?
  • Wie viele Wege kann es von einem Baumknoten zur Wurzel des Baumes geben?