Technická příručka k OSM seriálu

Update 5. 10. 2019: Přidali jsme ukázkový kód i v Pythonu 3, viz konec stránky.

Update 14. 10. 2019: Oprava ukázkového kódu v Pythonu 3, aby po elementech nezůstávala alokovaná paměť.

Update 15. 10. 2019: Drobné opravy a zjednodušení ukázkového kódu v Pythonu 3.

Seriál 32. ročníku KSP je věnovaný práci s velkými daty a některé jeho díly pracují s daty z projektu OpenStreetMap (neboli OSM). Tato stránka poskytuje ke stáhnutí testovací data, a doplňuje některé technické detaily, na které v textu seriálu nebylo místo.

Stažení dat

Data z OpenStreetMap si lze opatřit dvěma způsoby:
  • Dotazem na API, kterému se zadá obdélník a OSM server pošle jako odpověď výřez. Toto se hodí, když chceme malý kousek, větší server odmítne vydat. Používá se běžně na editaci kousků map.
  • Z projektu Planet OSM. Tam se dají stáhnout mapová data pro celý svět nebo výřezy pro celé státy. Pokud by tě zajímala jedna ulice, tak budeš zbytečně stahovat gigabajty. Ale my si teď chceme hrát s mapou celé Evropy, takže zvolíme tuto možnost.

API i Planet OSM vám dají data ve stejném formátu, takže vás o moc neochudíme, když budeme řešit jen Planet OSM. Na Planet OSM si můžete stáhnout mapu celého světa, zajímá vás Latest Weekly Planet XML File. Pravděpodobně ale nechcete celý svět, v takovém případě se podívejte na Planet.osm na OSM Wiki. Tam najdete seznam serverů, na kterých je Planet OSM zrcadlený a kde mají i výřezy. Mezi zajímavé patří:

  • Stabilní německý Geofabrik poskytuje výřez asi pro každou zemi s docela pěkným rozhraním.
  • Nově existující francouzský OSM download nemá tolik formátů, ale zase má pro některé státy i podregiony.
  • Pro Českou republiku může být zajímavý zdroj OSM archiv Kýblsoft včetně historie.

Testovací data k úlohám

Pro účely řešení našich úloh jsme pro vás připravili konkrétní výřezy. Svá řešení prosím spouštějte proti těmto datům, ať máte stejné výsledky jako my.

  • Evropa [42.5GB .osm.gz, 392GB odzipované]
  • Brno [20.4MB .osm.gz, 185.7MB odzipované]
  • Hrochův Týnec [307KB .osm.gz, 2.6MB odzipované]

XML

Z Planet OSM si můžete stáhnout data ve dvou formátech - zakódovaná v XML a nebo v PBF. XML je poměrně často používaný textový formát, zkratka znamená "eXtensible Markup Language", česky něco jako "rozšiřitelný značkovací jazyk". PBF je binární formát a jeho název je zkratkou za "protocol buffer". Oba jsou to obecné jazyky pro zápis dat a potkáme se s nimi nejen při práci s OSM ale i na mnoha dalších místech. I když je PBF formát úspornější na velikost dat, tak se v seriálu budeme držet formátu XML, protože si myslíme, že s ním bude méně starostí a ukážeme si na něm více zajímavých věcí.

XML dokument je poskládaný z elementů a atributů – pokud jste někdy viděli HTML, tak je to velmi podobné. Elementy a jejich atributy mají vždy jméno, atributy mají libovolnou textovou hodnotu, elementy mají atributy a obsah. Jednoduchý XML dokument může vypadat nějak takto:


<?xml version='1.0' encoding='UTF-8'?>+
<osm version="0.6" generator="osmconvert 0.8.10" timestamp="2019-08-17T20:15:02Z">
	<node id="344942189" lat="49.9743305" lon="15.8992473" version="2" timestamp="2009-10-01T22:39:31Z" changeset="0"/>
	<node id="344942429" lat="49.9676795" lon="15.9035589" version="4" timestamp="2015-08-08T14:59:30Z" changeset="0">
		<tag k="name" v="Stíčany"/>
		<tag k="place" v="village"/>
		<tag k="source" v="csu:uir-zsj"/>
		<tag k="name:cs" v="Stíčany"/>
		<tag k="ref:zsj" v="048313"/>
		<tag k="ref:cobe" v="048313"/>
		<tag k="population" v="300"/>
	</node>
</osm>

Soubor začíná hlavičkou, která říká akorát verzi XML a kódování. Nic moc zajímavého. Pak je v XML souboru právě jeden element, v našem případě se jmenuje osm (špičaté závory jej ohraničují, ty nejsou součástí jména). Za jménem má element atributy version, generator a timestamp s hodnotami za znakem = v uvozovkách. Uvnitř elementu osm (mezi značkami <osm ...> a </osm> vidíte další tagy, tentokrát node. Ty tvoří obsah elementu osm, elementy takto můžou další elementy a celý XML dokument je tak vlastně jenom strom.

Asi už snadno vidíte, že každý node má atributy id, lat, lon, version, timestamp, changeset a může mít v sobě libovolný počet elementů tag.

Za zmínku ještě stojí syntaxe <node ... /> – značka, která obsahuje na konci lomítko, definuje tag, který nemá obsah. Je to tedy vlastně jenom zkratka za <node ...></node>.

XML nám ale vůbec neříká jaké elementy smíme používat, jaké mají mít atributy a co vlastně znamenají. To je užitečné, protože se tak dá jeden formát použít skoro na cokoliv, ale je potřeba jeho použití ještě doplnit další dokumentací. V případě OSM jí najdete na OSM Wiki.

Gzip a bzip2

Protože XML je velmi "ukecaný" formát (obsahuje pořád dokola názvy elementů a atributů), tak se mapová data alespoň komprimují algoritmem gzip nebo bzip2. To bude drobná komplikace při zpracování, ale pro většinu jazyků najdete snadno knihovnu, která bude umět dekomprimovat gzip streamově (důvody a princip streamového zpracování jsme popsali v textu prvního dílu seriálu).

Volba jazyka a ukázky parsování

K řešení můžete zvolit libovolný svůj oblíbený programovací jazyk. Jen si ověřte, že má alespoň nějaké rozumné knihovny pro práci s XML soubory a pro jejich streamové parsování – bez toho se vám úlohy na velkých datech asi vyřešit nepovede.

My jsme úlohy ozkoušeli na třech jazycích a to na Pythonu 3, Go a C#. V Pythonu využíváme knihovnu lxml, což je vlastně jen Pythoní napojení na C knihovnu libxml2, a díky tomu je i Python rozumně rychlý na zpracování velkých XML. I tak ale Python dosahuje (podle našich hrubých měření) sotva třetinového výkonu třeba oproti řešení v Go. Pokud se tedy rozhodnete řešit úlohy v něm, tak vám doporučujeme si vyhradit ještě více času na to, aby vám doběhl výpočet i na velkém vstupu.

Níže můžete najít ukázky streamového parsování ve všech třech jmenovaných jazycích. Pro ukázku zde zkoušíme najít všechny vrcholy i cesty, které označují nějakou knihovnu (mají tag amenity=library):