Fahrplaninformationssysteme

Entwicklung

Speicherung der Fahrplan-Daten

Bei der Eingabe der Fahrplandaten im Editor müssen große Mengen von Daten gespeichert werden. Beim HVV-Fahrplan gibt es zum Beispiel 682 Linien mit insgesamt 9.548 Stationen (Stand 2007). Für jede dieser Linien existieren unterschiedliche Fahr-Zeiten für die Werktage (MO-FR), für samstags (SA) sowie für sonntags (SO). Außerdem finden die Fahrten natürlich in beide Richtungen statt.

Geht man bei 682 Linien von 25 Stationen (=Zeilen im Fahrplan), sowie 100 unterschiedliche Fahr-Zeiten (=Spalten im Fahrplan) aus, so ergeben sich 1.705.000 Einträge. Werden pro Eintrag 5 Zeichen für die Zeit verwendet (##:##) sind das 8.525.000 Zeichen für die Zeiten. Rechnet man noch 50 Zeichen für die Stations-Namen (= Maximalgröße) in den 6 Einzelplänen (für MO-FR, SA, SO in beiden Richtungen) für jede Linie dazu, kömmen noch einmal 204.600 Zeichen dazu. Damit werden schätzungsweise 8,73 Megabyte für die reinen Fahrplandaten benötigt.

Normalerweise ist es kein Problem diese Daten auf der Festplatte unterzubringen. Unter den folgenden Gesichtspunkten kann eine Komprimierung der Daten jedoch nützlich oder sogar notwendig sein:

1. Je mehr Daten im Hauptspeicher gehalten werden, desto weniger Platz steht für die teilweise sehr datenintensive Fahrplansuche zur Verfügung.
2. Für den Download der Daten im Internet ist eine geringe Dateigröße benutzerfreundlicher.
3. Für erweiterte Funktionen, wie beipielsweise das Verbinden mehrere Datenquellen (= Verkehrsnetze), wird zusätzlich Speicherplatz benötigt.

Bei der Betrachtung eines Verkehrsnetzes kann man grundsätzlich zwischen Stationen mit mehreren Linien-Anschlüssen und Stationen mit nur einem Linien-Anschluß unterscheiden. Erstere werden im weiteren Verlauf als 'Umsteigebahnhöfe' bezeichnet während letztere als 'Haltestationen' bezeichnet werden.

Bei der Suche nach Fahrplanverbindungen wird auf die Umsteigebahnhöfe wesentlich öfter zugegriffen: Handelt es sich bei der Start- und/oder Ziel-Station um Haltestationen, so werden zunächst die Verbindungen zu den nächstliegenden Umsteigebahnhöfen gesucht. Anschließend wird für die Suche nur noch das Netz mit den Umsteigebahnhöfen benötigt.
Für eine schnellere Verbindungsabfrage ist es daher sinnvoll, ein Netz aufzubauen, daß nur die Umsteigebahnhöfe enthält. Dieses könnte dann im Speicher gehalten werden, während die übrigen Daten nach Bedarf von externen Speichermedien geladen werden. Die Fahrplandaten der Umsteigebahnhöfe werden daher getrennt von den übrigen Fahrplandaten gespeichert.

Im folgenden Abschnitt wird die Speicherung und Komprimierung schrittweise erläutert. Dabei wird zunächst von einer maximalen Komprimierung ausgegangen. Die Effizienz der einzelnen Schritte kann anschließend durch Tests ermittel werden.

Möglichkeiten zur Speicherung und Komprimierung

1. Zeiten als Zahl speichern
   Speichert man die Zeiten der Fahrpläne als Zahl, benötigt man statt 5 Byte lediglich 2 Byte, da für die Zeit lediglich 1440 unterschiedliche Zahlen benötigt werden (24 Stunden * 60 Minuten). Außerdem werden noch einige Werte für Sonderfälle benötigt.
2. Fahrpläne mit Umsteigebahnhöfen erstellen
   Zur Erstellung eines Fahrplans, der nur Umsteigebahnhöfe enthält, werden aus den einzelnen Fahrplänen die Zeiten der entsprechenden Stationen herausgesucht und getrennt gespeichert.
3. Fahrpläne in Abschnitte unterteilen
   Als nächstes werden die Fahrpläne in Abschnitte unterteilt, wobei die Umsteigebahnhöfe als Abschnitts-Grenzen dienen. Die Haltestationen zwischen 2 Umsteigebahnhöfen stellen also immer ein Abschnitt dar.
4. Zeiten in Zeitabstände umwandeln
   Speichert man anstatt der Abfahrts- und Ankunftszeiten lediglich die Zeitabstände (in Minuten zur vorigen bzw. nächsten Station, benötigt man hierfür im Normalfall lediglich 1 Byte statt 2 Byte. Bei Zeitabständen von mehr als 255 Minuten ist hierfür eine Sonderbehandlung notwendig.
5. Spalten der Abschnitte zusammenfassen
   Betrachtet man sich die Spalten der einzelnen Abschnitte, so stellt man fest, daß die Zeitabstände zwischen den Stationen oft gleich sind. Diese können so zusammengefasst werden, daß pro Spalte und Abschnitt ein Zeiger auf die eigentlichen Zeitabstände gespeichert wird.
6. Spalten der Fahrpläne mit Umsteigebahnhöfen zusammenfassen
   Abschließend können auf ähnlicher Weise die Spalten der Fahrpläne mit Umsteigebahnhöfen zusammengefaßt werden. Dies ist jedoch etwas komplizierter. Es müssen zusätzlich die Abfahrtszeiten von der ersten Station angegeben werden, wobei zu berücksichtigen ist, daß die einzelnen Fahrten an unterschiedlichen Stationen beginnen können.