Kurzfassung

OpenStreetMap ist ein Open-Source-Projekt mit dem Ziel, jedermann freie Geo-Infor­ mationen zur Verfügung zu stellen. Mit den Daten können beliebige Karten generiert werden, z. B. Straßenkarten, Stadtpläne, Wanderkarten, Karten mit dem Netz der öf­ fentlichen Verkehrsmittel. In den Daten sind unter anderem POIs (Points of Interest, z. dt. interessante Orte) enthalten, was es ermöglicht, z. B. Museen, Bibliotheken, Lä­ den und sogar Ampeln in Karten darzustellen oder in Navigationssystemen zu verar­ beiten.

Im Rahmen der Studienarbeit soll eine Möglichkeit geschaffen werden, Daten von OpenStreetMap, die nativ im XML-Format geliefert werden, in ein Binärformat umzu­ wandeln, wodurch der Datenverkehr im Vergleich zu anderen Formaten wie XML ge­ senkt werden soll.

Das neue Format ist mit bereits vorhandenen Formaten zur Übertragung von Karten zu vergleichen. Besonders für mobile Geräte dürfte ein Binärformat von Vorteil sein, weil hier langsamere Übertragungsraten ein Problem darstellen.

Die Formatumwandlung soll mittels eines zusätzlichen Dienstes für den ROSE-Server geschehen, der zu einem gegebenen Rechteck auf der Erde (mittels Längen- und Brei­ tengrad) die XML-Daten von der OpenStreetMap-API lädt, in das noch zu konzeptio­ nierende Format umwandelt und die Binärdaten schließlich an den Client schickt.

Der ROSE-Client soll um die Funktionalität erweitert werden, die Binärdaten um die aktuelle GPS-Position des Mobilgeräts vom Server mittels eines geeigneten Protokolls abzufragen, um dynamisch eine Karte auf dem Mobilgerät zu generieren.

OpenStreetMap stellt zwar vorgerenderte Karten in Form von PNG-Grafiken zur Ver­ fügung, diese haben allerdings feste Detaileinstellungen, was dem Nutzer nicht er­ möglicht, zu wählen, welche Informationen er angezeigt haben möchte und welche nicht.

Das Protokoll zwischen Server und Client soll entsprechend ausgerüstet werden, so­ dass nur vom Nutzer ausgewählte Kartenfeatures (z. B. Fußwege, Bushaltestellen, Einkaufsmöglichkeiten, Abfalleimer, Telefonzellen) vom Server bezogen und schlus­ sendlich auch auf dem Display angezeigt werden.

i

Inhaltsverzeichnis

1  Einleitung  1

1.1  OpenStreetMap  1

1.1.1  Datenformat von OpenStreetMap  2

1.1.2  Beispiele von XML-Daten  3

1.1.3  Gerendertes Kartenmaterial  4

1.2  Ziel dieser Arbeit  5

2  Vorbereitende Analyse-Skripte  7

2.1  Zeilenweise Analyse  7

2.1.1  Stringlänge in den Tag-Values  7

2.1.2  Anzahl Tags, Members und Nds pro Element  8

2.1.3  Relationen: Typen und Rollen  10

2.2  Analyse der Tags  11

2.3  Eintragung in eine MySQL-Datenbank  12

2.3.1  MySQL-Datenbankschema  12

2.3.2  Einsatz des Skripts  14

2.4  Analyse aus der Datenbank  14

2.4.1  Relative Kodierung gemäß OpenStreetMap-Wiki  15

2.4.2  Alternative Kodierung mittels Flex-Byte  15

2.4.3  Gegenüberstellung der Möglichkeiten am Beispiel  15

2.4.4  Ergebnisse  17

3  Entwicklung des Binärformats  19

3.1  Grundliegende Bausteine  19

3.1.1  Bytereihenfolge von Integer-Daten  19

3.1.2  Flexibler Integer  19

3.1.3  Strings  20

3.1.4  Geographische Koordinaten  20

3.1.5  Header-Byte  20

3.2  Element-Header  21

3.3  Kodierung eines Knoten  21

3.4  Kodierung eines Wegs  22

3.5  Kodierung einer Relation  24

3.6  Kodierung der Tags  27

ii

3.6.1  Direkte Kodierung in einem Byte  28

3.6.2  Kodierung des Keys  29

3.6.3  highway-Tags  30

3.6.4  amenity-Tags  31

3.6.5  natural-Tags  32

3.6.6  Beschränkungstags  32

3.6.7  railway-Tags  33

3.6.8  waterway-Tags  34

3.6.9  power-Tags  34

3.6.10  boundary-Tags  35

3.6.11  barrier-Tags  35

3.6.12  leisure-Tags  36

3.6.13  shop-Tags  36

3.6.14  tourism-Tags  37

3.6.15  cycleway-Tags  37

3.6.16  man made-Tags  37

3.6.17  sport-Tags  38

3.6.18  Kodierung von allgemeinen Tags  38

3.6.19  Ignorieren bestimmter Tags  38

3.7  Beispiele  38

3.7.1  Beispiel: Kodierung von Knoten  39

3.7.2  Beispiel: Kodierung eines Wegs  40

3.7.3  Beispiel: Kodierung einer Relation  41

4  Implementierung des Binärformats  45

4.1  Implementierung als Stand-Alone-Anwendung  45

4.2  Package osm  45

4.3  Package io  45

4.4  Package parser  46

4.4.1  Klasse Parser  46

4.4.2  Klasse Tools  49

4.4.3  Klasse EnumParser  49

4.5  Package parser.enums  50

4.5.1  Aufzählungsklasse DirectTag  50

4.5.2  Aufzählungsklasse TagKey  50

4.5.3  Aufzählungsklasse TagKeyValue  50

4.5.4  Aufzählungsklassen RestrictionTagKey und RestrictionTagValue  50

4.5.5  Klasse RestrictionTag  50

4.5.6  Aufzählungsklasse DirectRole  51

iii

4.5.7  Aufzählungsklasse RelationType  51

4.6  Default-Package  51

4.7  Analyse des eingesparten Datenvolumens  52

4.7.1  Analyse-Skript  52

4.7.2  Ergebnisse  55

4.7.3  Fazit  56

4.8  Analyse der Laufzeit  56

4.8.1  Analyse-Skript  56

4.8.2  Ergebnisse  57

4.8.3  Fazit  57

5  Einbettung als Server-Dienst in den ROSE-Server  58

5.1  Protokoll  58

5.1.1  Koordinaten  58

5.1.2  Filtern von Elementtypen  59

5.1.3  Filtern von Tags  59

5.1.4  Ausgabe des Ergebnisses  60

5.1.5  Ausgabe im Fehlerfall  61

5.2  Implementierung  61

5.2.1  Klasse OsmBinaryAnfrageController  61

5.2.2  Klasse OsmBinaryErrorCode  62

6  Erweiterung des ROSE-Client  63

6.1  Einschränkungen durch Compiler-Version  63

6.2  Implementierung des Parsers  64

6.2.1  Klasse EnumHandler  64

6.2.2  Package parser.enums  65

6.2.3  Klasse Tools  65

6.2.4  Klasse OSMDataInputStream  65

6.2.5  Klasse OSMTag  65

6.2.6  Klassen OSMNode, OSMWay, OSMRelation, OSMMember, OSMType  66

6.2.7  Klassen Parser und OsmBinaryErrorCode  67

6.3  Aufbau der MapForm im ROSE-Client  69

6.4  Die Overlay-Klasse GMOOpenStreetMap  70

6.4.1  Anforderung eines Daten-Updates  70

6.4.2  Race-Conditions beim asynchronen Daten-Update  71

6.4.3  Cache  71

6.4.4  Berechnung des Koordinatenrechtecks  71

iv

6.4.5  Klasse OpenStreetMapHandler  75

6.4.6  POIs: Symbole und Symbolzuordnung zu den OpenStreetMap-Tags  75

6.4.7  Straßen: Zuordnung von Farben zur Höchstgeschwindigkeit  76

6.5  Einbettung der Overlay-Klasse  76

7  Zusammenfassung und Ausblick  80

7.1  Zusammenfassung  80

7.2  Mögliche Verbesserungsansätze  80

7.3  Ausblick  81

A  Literaturverzeichnis  I

v

Abbildungsverzeichnis   

Abbildung  1: Google Earth - Ansicht der Nürnberger Altstadt mit POIs  

Abbildung  2: Mapnik-Karte  

Abbildung  3: Osmarender-Karte  

Abbildung  4: CycleMap-Karte  

Abbildung  5: Hiking-Karte  

Abbildung  6: ÖPNV-Karte  

Abbildung  7: Reit- und Wanderkarte  

Abbildung  8: gerendertes Multi-Polygon  

Abbildung  9: Ansicht der Testergebnisse im Browser  

Abbildung  10: Ausschnitt aus dem OpenStreetMap-Symbolsatz classic  

Abbildung  11: Ausschnitt aus dem OpenStreetMap-Symbolsatz square  

Abbildung  12: Schematischer Aufbau: OpenStreetMap-Kacheln und Overlays  

Abbildung  13: Koordinaten in der Mitte einer Kachel  

Abbildung  14: Koordinaten in der oberen linken Ecke der Kachel  

Abbildung  15: Koordinaten in der oberen rechten Ecke der Kachel  

Abbildung  16: Koordinaten in der unteren linken Ecke der Kachel  

Abbildung  17: Koordinaten in der unteren rechten Ecke der Kachel  

Abbildung  18: erweitertes Koordinatenrechteck  

Abbildung  19: unknown-Symbol  

Abbildung  20: Sequenzdiagramm MapForm  

Abbildung  21: ROSE-Client vorher  

Abbildung  22: ROSE-Client mit OpenStreetMap-Binärdaten  

Abbildung  23: ROSE-Client vorher (Google-Satellitenansicht)  

Abbildung  24: ROSE-Client mit OpenStreetMap-Binärdaten (Google-  

Satellitenansicht  )  

vi

Tabellenverzeichnis   

Tabelle 1:  Stringlänge in den Tag-Values  8

Tabelle 2:  Tags pro Element in europe.osm  9

Tabelle 3:  Knoten pro Weg in europe.osm  9

Tabelle 4:  Mitglieder pro Relation in europe.osm  10

Tabelle 5:  Häufigst vorkommende Typen von Relationen  10

Tabelle 6:  Häufigst vorkommende Rollen in Relationen  11

Tabelle 7:  Häufigst vorkommende (Key, Value)-Kombinationen bei Tags  12

Tabelle 8:  Vergleich zwischen relativer Kodierung und der Flex-Byte-Kodierung  18

Tabelle 9:  Flexibler Integer  19

Tabelle 10:  Header-Byte  21

Tabelle 11:  Element-Header  21

Tabelle 12:  Kodierung eines Knoten  22

Tabelle 13:  Flex-Byte  23

Tabelle 14:  Kodierung eines Wegs  24

Tabelle 15:  Typen von Relationen  25

Tabelle 16:  Direkte Kodierung von Rollen  26

Tabelle 17:  Kodierung einer Relation  26

Tabelle 18:  Kodierung von Relationsmitgliedern  27

Tabelle 19:  Direkte Tags in einem Byte kodiert  28

Tabelle 20:  Direkte Kodierung des Keys  29

Tabelle 21:  Kodierung von highway-Tags  30

Tabelle 22:  Kodierung von amenity-Tags  31

Tabelle 23:  Kodierung von natural-Tags  32

Tabelle 24:  Kodierung von Beschränkungen  33

Tabelle 25:  Kodierung von railway-Tags  33

vii

Tabelle 26:  Kodierung von waterway-Tags  34

Tabelle 27:  Kodierung von power-Tags  34

Tabelle 28:  Kodierung von boundary-Tags  35

Tabelle 29:  Kodierung von barrier-Tags  35

Tabelle 30:  Kodierung von leisure-Tags  36

Tabelle 31:  Kodierung von shop-Tags  36

Tabelle 32:  Kodierung von tourism-Tags  37

Tabelle 33:  Kodierung von cycleway-Tags  37

Tabelle 34:  Kodierung von man made-Tags  37

Tabelle 35:  Kodierung von sport-Tags  38

Tabelle 36:  Flex-Byte im Detail  41

Tabelle 37:  Ersparnis an Datenvolumen  55

Tabelle 38:  Laufzeit  57

Tabelle 39:  Bitmaske zur Filterung von Elementen  59

Tabelle 40:  Ausgabe im Fehlerfall  61

Tabelle 41:  Farbbelegungen für Straßen gemäß Höchstgeschwindigkeit  76

viii

Einleitung 1

1 Einleitung

Navigation und Karten haben in den letzten Jahren zunehmend an Bedeutung gewon­ nen. Während anfänglich nur Straßenkarten und Routenplanung verfügbar waren, gibt es heute Programme wie Google Earth, die eine interaktive Ansicht der Erde dar­ stellen und dem Benutzer die Möglichkeit geben, beliebige Ebenen wie z. B. Geschäfte, Restaurants, Tankstellen und andere sogenannte Points of Interest (kurz POI) einzu­ blenden [GoogleEarth].

Das Problem bei solchen Diensten, wie hier am Beispiel Google, besteht darin, dass die Karten und Daten nur kommerziell nutzbar sind und somit nicht für neue Anwen­ dungen zur Verfügung stehen [GoogleTerms]. Eine freie Alternative ist erforderlich.

1.1 OpenStreetMap

Die OpenStreetMap ist eine freie Geo-Datenbank, die im August 2004 von Steve Coast initiiert wurde [OsmFacts]. Der Open-Source-Gedanke trägt dazu bei, dass das Pro­ jekt sehr schnell viele Mitglieder und Helfer gefunden hat. Zu Beginn des Jahres 2008 waren 20.000 Mitglieder registriert, zu Beginn von 2009 bereits über 80.000. Aktuell, zu Beginn von 2010, sind es mehr als 200.000 [OsmStats].

OpenStreetMap eignet sich auf Grund der liberalen Lizenzbedingungen für den wis­ senschaftlichen Einsatz. Die Creative Commons Attribution-Share-Alike-2.0-Lizenz [CCSA] erlaubt die kostenlose Nutzung der Daten, solange kenntlich gemacht wird,

Einleitung 2

woher die Daten stammen, d. h. OpenStreetMap explizit genannt wird, und unter wel­ cher Lizenz sie stehen.

1.1.1 Datenformat von OpenStreetMap

Daten von der OpenStreetMap werden in Form des sogenannten Planet-File auf http:// planet.openstreetmap.org / zur Verfügung gestellt. Dies ist eine bzip2-kompri­ mierte XML-Datei [XML] mit allen Geo-Daten der Erde. Im Juni 2009 umfasste das Planet-File über 160 GiB, dass mittels bzip2 auf 6,1 GiB reduziert wurde [OsmPla­ net]. Am 31. Oktober 2009 betrug die Dateigröße der komprimierten Datei bereits 7,3 GiB [OsmPlanetDownload].

Für kleine Rechtecke auf der Erde - wenn maximal 50.000 Elemente darin enthalten sind - kann mittels einer API auch nur ein Ausschnitt abgerufen werden [OsmApi]. Dieses Verfahren eignet sich allerdings nur bedingt, da mit zunehmender Datenmen­ ge v. a. in den Großstädten das Rechteck immer kleiner sein muss, um keine Fehler­ meldung auszulösen.

Die geographischen Informationen werden in drei primitiven Datentypen erfasst, die auf je ein XML-Element abgebildet sind [OSM]. Jedes XML-Element enthält in den Attributen eine - jeweils für den Datentypen - eindeutige ID, sowie Informationen wer wann zuletzt eine Änderung durchgeführt hat.

Es gibt die folgenden Primitiven (in der Arbeit nachfolgend Elemente oder Elementtypen genannt):

• Ein Knoten (Node) entspricht einem Punkt auf der Erde. Er enthält außer sei­ ner - für alle Knoten - eindeutigen ID ein Koordinatenpaar aus geographischer Länge (Longitude) und geographischer Breite (Latitude).

• Ein Weg (Way) ist ein gerichteter Streckenzug aus Knoten. Mittels der IDs der Knoten (Nds) werden Strecken gebildet, die z. B. Straßen, Bahnlinien und Flüs­ se darstellen [OSM].

Stimmen die IDs des ersten und letzten Streckenpunktes überein, so wird eine Fläche (Area) aufgespannt. Damit werden z. B. Gebäude, Wald- oder Agrarflä­ chen und Grenzlinien modelliert [OSM].

• Eine Relation (auch Beziehung) kann zwischen mehreren Knoten, Wegen oder auch anderen Relationen bestehen. Die an der Relation teilnehmenden Elemen­ te werden Mitglieder (Members) genannt. Jedem Mitglied wird eine Rolle (Role) zugeordnet, die es in der Relation spielt. Z. B. werden die Haltestellen und Rou­ tenverlauf einer Buslinie zusammengefasst oder mehrere Flächen zu komple­ xen Polygonen zusammengeschlossen.

Für alle drei Elemente können zusätzlich Tags angegeben werden. Dies sind Paare aus Name (Key) und Wert (Value), die für zusätzliche Informationen genutzt werden. Es gibt zwar im Wiki der OpenStreetMap eine Auflistung von Tags, die benutzt wer­ den sollten [OsmFeatures], grundsätzlich sind aber keine Einschränkungen gesetzt, für welche Informationen Tags eingesetzt werden können.

Einleitung 3

Im Folgenden werden Tags kurz in der Form Name=Wert geschrieben.

1.1.2 Beispiele von XML-Daten

Um sich ein Bild machen zu können, hier einige Beispiele:

Dieses Tag definiert einen Knoten an der angegebenen Position 49,4317501°N, 11,0018765°O. In den Tags des Knoten sind zusätzlich die Informationen zu finden, dass sich dort eine überdachte Bushaltestelle befindet, die von der VAG betrieben wird und dort die Linien 67 und N8 bedienen.

Die ersten drei XML-Elemente legen drei Knoten fest. Hier sind keine weiteren Infor­ mationen hinterlegt. Der nachfolgende Weg benutzt diese Knoten dann, um eine as­ phaltierte Straße namens Neumühlweg zu beschreiben. Die Straße führt durch ein Wohngebiet, maximal darf mit 30 km/h gefahren werden und es ist eine Sackgasse.

Einleitung 4

Hier werden vier Wege in Beziehung gesetzt. Die besagten Wege werden von der Bus-Linie 67 befahren, die von der VAG eingesetzt wird. Der Tarifverbund heißt VGN.

1.1.3 Gerendertes Kartenmaterial

Die XML-Daten sind für den Benutzer eher unhandlich, deshalb werden die Daten von Karten-Render-Programmen zu Bildern verarbeitet. OpenStreetMap setzt zwei ver­ schiedene Programme (Osmarender und Mapnik) ein, die das Planet-File rendern und in einer Google-Maps-ähnlichen Oberfläche für den Benutzer in einem Internet-Brow­ ser zugänglich machen [OsmSlippyMap].

Mittlerweile gibt es eine große Vielfalt von weiteren Projekten, die die OpenStreet­ Map-Daten verwenden und jeweils andere Details verwenden, um Karten zu erzeu­ gen.

Nachfolgend sind mehrere verschiedene Darstellungen der Nürnberger Innenstadt ge­ zeigt:

Quelle: www.openstreetmap.org Quelle: www.openstreetmap.org

Einleitung 5

Quelle: www.openstreetmap.org Quelle: osm.lonvia.de/world_hiking.html

Quelle: www.öpnvkarte.de Quelle: topo.geofabrik.de

Wie zu sehen ist, können die Karten komplett unterschiedlich aussehen, je nachdem, welche Elemente dargestellt werden und welche nicht.

1.2 Ziel dieser Arbeit

Das XML-Format [XML] ist unnötig aufgebläht, wie aus den Beispielen ersichtlich ist. Leerzeichen und Zeilenumbrüche sind nicht notwendig. Auch Attribute, welcher User wann zuletzt eine Änderung vorgenommen hat, ist für die meisten Anwendungen nicht von Relevanz.

Im Rahmen dieser Arbeit soll ein Binärformat entwickelt werden, um Bandbreite bei der Übermittlung der Geo-Informationen einzusparen. Das Format soll speziell für das am Lehrstuhl entwickelte ROSE-Projekt [Rose] optimiert werden. Anschließend soll die Effizienz des neuen Formats analysiert werden.

Es soll ein ROSE-Server-Dienst implementiert werden, der XML-Daten von Open­ StreetMap mittels der API abruft und in das neu entwickelte Format umwandelt. Ein geeignetes Protokoll wird dem Server die gewünschten Koordinaten mitteilen und wel­ che Informationen der Client zusätzlich benötigt.

Einleitung 6

Im Rahmen der Fußgängernavigation [RoseTransport] liegt das Interesse besonders auf POIs wie Telefonzellen, Gebäude, Ausflugsziele, Postämter, Briefkästen, um nur ein paar Beispiele zu nennen.

Zum Schluss soll der ROSE-Client dahingehend erweitert werden, dass er die aktuel­ len GPS-Koordinaten des Mobilgeräts an den neuen Dienst auf dem Server sendet und eine dynamische Karte auf dem Display rendert.

Vorbereitende Analyse-Skripte 7

2 Vorbereitende Analyse-Skripte

Das in dieser Arbeit zu entwickelnde Binärformat wird sich vom Grundaufbau stark an dem Entwurf, der im OpenStreetMap-Wiki zu finden ist [OsmBinaryFormat], ori­ entieren. Dieses wird verbessert und die Zuordnung der OpenStreetMap-Tags auf Bi­ närdaten gezielt darauf optimiert, dass Informationen über Straßen oder für Fußgän­ ger relevante POIs weniger Speicher benötigen als andere Informationen.

Um das zu entwickelnde Format optimal zu gestalten, werden vorab einige statisti­ sche Betrachtungen gemacht.

Da das Planet-File für diesen Zweck zu groß ist und die Laufzeit für die eingesetzten Skripts zu lang ist, werden nur kleinere Teile des Planeten (Kontinente, Staaten oder Bundesländer) untersucht. GEOFABRIK bietet derartige Bruchteile des großen Plan­ et-Files zum Download an [GeoFabrik]. Im Folgenden wird auf diese Daten Bezug ge­ nommen.

2.1 Zeilenweise Analyse

Mittels des PHP-Skripts analyse.php wurden Datensätze unterschiedlicher Größe statistisch ausgewertet. Es wurden Datensätze von Bayern, Deutschland und Europa verwendet.

analyse.php liest zeilenweise eine .osm-Datei ein und sammelt in einem assoziativen Array alle für diese Arbeit relevanten Fakten. Die OpenStreetMap-Dateien sind viele Gigabytes groß, weswegen SimpleXML leider nicht zum Einsatz kommen kann, da hier die komplette Eingabedatei in den Arbeitsspeicher passen müsste [PHP]. Es wur­ de deshalb eine Lösung mittels regulärer Ausdrücke (RegExp) entwickelt.

Als Ausgabedateien legt analyse.php zwei Dateien an:

• result.txt - Das assoziative Array wird dort mittels print_r() hineinge­ schrieben

• result_serialized.txt - Das assoziative Array wird mittels PHP serialisiert und in diese Datei gespeichert. Dies hat den Zweck, dass das Ergebnisarray per Skript wieder in Array-Form hergestellt und weiterverarbeitet werden kann.

Es wird davon ausgegangen, dass die Daten von Europa repräsentativ sind und für die anderen Erdregionen ähnliche Ergebnisse liefern würde. Von einer aufwändigen Ana­ lyse des über 160 GiB großen Planet-Files wird deshalb abgesehen.

2.1.1 Stringlänge in den Tag-Values

Es ist wichtig zu wissen, welche Länge Strings in den OpenStreetMap-Tags aufwei­ sen. Das Analyse-Skript hat hierbei untersucht, wie viele Strings bestimmte Längen überschreiten. Besonders interessant: Wie viele Strings passen in 2 ⁷ bzw. 2 ⁸ Bytes? Wie viele Strings benötigen mehr als 2 ⁸ Bytes Speicher? Grund für diese Überlegung

Vorbereitende Analyse-Skripte 8

ist es, herauszufinden, ob die Stringlänge in einem oder in zwei Bytes kodiert werden muss.

In Tabelle 1 sind die Ergebnisse für die Stringlängen der Tag-Values aufgelistet: Mehr als 99,5% aller Value-Strings der Tags sind kürzer als 64 Zeichen. Der Anteil an Tags mit einer Value-Stringlänge von mehr 128 liegt bei weniger als 0,001%.

Tabelle 1: Stringlänge in den Tag-Values

Neben der Stringlängen aller Tags wurden zusätzlich noch die durchschnittlichen Stringlängen nur bestimmter Tags untersucht. Diese Tags sind

• name

• Tags, die auf _name enden

• Tags, die mit addr: beginnen

Von diesen Tags war eventuell zu erwarten, dass die Value-Strings länger als andere sind. Es wurden aber keine auffälligen Anomalien in den Stringlängen der Values ge­ funden, sodass die Ergebnisse für diese Arbeit nicht von Belang sind.

2.1.2 Anzahl Tags, Members und Nds pro Element

Elemente haben bestimmte Unterelemente:

• Knoten, Wege und Relationen können ein oder mehrere Tags enthalten.

• Wege enthalten eine Liste von mehreren Knoten-IDs.

• Relationen enthalten eine Liste von mehreren Mitgliedern.

Für die Kodierung aller Elemente wird später erst übertragen, wie viele Unterelemen­ te folgen.

Das Analyse-Skript zählt während der zeilenweisen Bearbeitung der XML-Datei mit, indem mit Öffnen eines -, - oder -Tags der Tag-Name gespei­ chert wird und die Zähler auf 0 gesetzt werden. Bei -, - oder -Tags werden die Zähler inkrementiert. Bei den schließenden -, - oder -Tags wird dann die Anzahl der Unterelemente, sowie Durchschnitts-,

Vorbereitende Analyse-Skripte 9

Maximal- und Minimalwerte, erfasst. Wie bei den Stringlängen ist das Augenmerk wieder auf den Bit-Grenzen.

Anders als bei den Stringlängen werden für die Tag-Anzahl zwei Werte reserviert. Es ist einerseits möglich, dass ein Element keine Tags enthält. Andererseits wird ein Wert dafür verwendet, um anzuzeigen, dass viel mehr Tags vorliegen und die Anzahl extra kodiert werden muss. Es werden daher die Grenzen 6 (2 ³ -2), 14 (2 ⁴ -2) und 30 (2 ⁵ -2) verwendet.

Die Ergebnisse für die Tag-Anzahl sind in Tabelle 2 zu finden:

Tabelle 2: Tags pro Element in europe.osm

Für die Anzahl von Knoten pro Weg werden die Grenzen 127 und 255 untersucht, was 7 oder 8 Bits entspricht. Zwar sollte ein Weg immer aus mindestens 2 Knoten beste­ hen, doch die Analyse hat gezeigt, dass es auch Wege mit nur einem Knoten gab. Vor­ sichtshalber werden deshalb Werte für 0 Knoten und 1 Knoten freigehalten.

Die Ergebnisse für die Knoten-Anzahl pro Weg sind in Tabelle 3 zu finden:

Für die Anzahl von Mitgliedern pro Relation werden analog zu den Knoten pro Weg die Grenzen 127 und 255 untersucht.

Die Ergebnisse für die Mitglieder-Anzahl sind in Tabelle 4 zu finden:

Vorbereitende Analyse-Skripte 10

2.1.3 Relationen: Typen und Rollen

Die meisten Relationen haben mittels eines Tags einen Typ zugeordnet, jedes Mitglied hat eine Rolle. Um später eine effiziente Zuordnung realisieren zu können, wird ana­ lysiert, welche Werte am häufigsten auftreten.

Für den Typ einer Relation wird abgefangen, wenn in einem -Element ein Tag mit dem Namen type auftritt und der Wert gespeichert. Für die Rolle eines Mit­ glieds wird das XML-Attribut role analysiert und gezählt.

Die Ergebnisse dieser Analysen sind in den Tabellen 5 und 6 zu finden: