[OSM-dev-fr] [veille] Canal TP libère du code pour OpenStreetMap

[Philippe Verdy]

Autrement dit une autre bibliothèque en C++ pour lire un fichier PBF dont
les specs viennent déjà d'OSM, fonctionnant un peu comme un parseur SAX
pour XML (donc à l'aide de 3 callbacks sur les 3 éléments élémentaires
d'OSM : nœud, way et relation).

Rien n'est fournit concernant les auteurs, historiques, et métadonnées des
changesets.

La doc dit bien que quand un way ou une relation est retourné, le vecteur
contenant les références n'est pas encore complet car les objets référencés
ne sont pas encore parsés, ce qui oblige à les accumuler en mémoire d'un
bout à l'autre, pour ne faire un filtrage qu'à la fin quand les noeuds
membres de tous les chemins et les membres de toutes les relations ont
absolument tous été lus : même pour régénérer un fichier XML en résultat,
il faudra tout stocker en mémoire, ou dans une base de données temporaire,
pour ne générer le fichier XML complet qu'à la fin, après le parsing: on
n'a pas ce problème de façon aussi aigu avec un parseur SAX d'un fichier
XML dont ont sait quand chaque élément est complet sans avoir à lire la
totalité ou conserver en mémoire la totalité des données.

La bibliothèque serait en revanche plus utile si elle ne renvoyait dans les
callbacks QUE des objets complets dont les listes de références ne
contiennent QUE des objets déjà décrits dans une callback précédente (dans
une analyse "bottom-up") ou à l'inverse dans une analyse "top-town"
permettant à la callback de retourner un statut indiquant si on est
intéressé par le détail de ses membres, pui appelant une autre callback
pour chacun de ses membres puis une autre en fin d'énumération des membres
pour indiquer que l'objet parent a fini d'être énuméré et indiquant si un
ou plusieurs des membres enfants ont été ignorés. Voire un mode mixte
utilisant une analyse ordonnée top-down et botomm-iup en retour, avec un
préfiltrage des enfants intéressants par un parcours en largeur d'abord
avant leur exploration en profondeur.

Parser un PBF pour faire des requêtes consiste à parcourir un graphe
orienté : les principales méthodes de parcours de graphe doivent y figurer
: en profondeur d'abord, en largeur d'abord. Pour la combinaison des deux
modes, il doit être possible de faire un premier parcours en largeur
d'abord (après avoir fait une visite à l'entrée du parent) pour indiquer
une liste d'éléments intéressants à parcourir ensuite en profondeur et de
retourner ensuite un objet vecteur ou agrégat des valeurs retournées par
les visites des enfants, puis de revisiter en sortie le parent avec cet
objet renseigné. Pour cela une référence opaque à un objet "contexte" doit
permettre à chaque callback appelée lors des visites de savoir quoi faire
et indiquer si une sous-visite est utile, ainsi ue de dire au parseur s'il
peut éliminer cette référence lors du parcour des enfants voisins (il faut
une autre callback pour faire cette purge partielle des anciens éléments
visités, par exemple pour n'en garder qu'un attribut identifiant comme
"w1234" mentionnant le type d'objet et son identifiant).

Regardez l'exemple d'utilisation en C++ fourni : il faut bien prévoir une
structure de stockage intermédiaire (l'exemple le fait en mémoire en
stockant tous les nœuds et tous les chemins trouvés, avant de savoir quoi
en faire pour sortir des infos sur les bordures connectées de polygones ;
il ne sort rien au sujet des relations donc il ne les stocke pas et
n'utilise pas la callback des relations).

Il y a des modèles C++ standardisés de parcours de graphes orientés, et je
pense que ce devrait constituer l'interface naturelle d'une telle
bibliothèque parseur destiné à effectuer des parcours.

De plus un fichier PBF contient un index sur les objets par identifiant :
on peut faire des accès directs sans avoir à parcourir avant tout le graphe
en largeur et en profondeur, du début à la fin de façon linéaire : cela
permet d'écrire des requêtes efficaces et rapides de recherche.

Pouvoir garantir un ordre de lecture est fondamental pour faire des
recherches efficaces et complètes (donc pouvoir retourner dans une callback
au minimum les infos de chaque "groupe" indexable contenant un jeu de
noeuds (et/ou de nœuds denses), un jeu de chemins et un jeu de relations,
sans garantie que le "groupe" soit autosuffisant, et les groupes pouvant
être dans le désordre.

Si on stocke tout au fur et à mesure, jusqu'au bout, la quantité de mémoire
sera très supérieure à la taille totale du PBF (on a perdu la compression
notamment des chaines de texte et des coordonnées de points ou références
au sein de chaque group : un groupe que ferait jusqu'à 32K dans un PBF
verra en mémoire nécessaire pendant le parsing sa taille multipliée par 5
ou 20, plus peut-être, et rien de libéré jusqu'à la fin on stocke donc en
mémoire tout le fichier multiplié par un facteur 5 à 20 ou plus. L'autre
solution c'est de stocker dans une base SGBD relationnelle intermédiaire
(au moins indexée sur les ID), pour ensuite pouvoir éventuellement faire
une recherche indexée géographiquement sur les objets qui restent, et
resortir ces données filtrées et les réénumérer si possible avec une API de
pacours commune (ce qui ne sera pas le cas ici).

Je ne suis donc pas convaincu que cette bibliothèque soit ce qui est
cherché car l'API ne contient strictement aucun système de requête et
filtrage pour faire des sous-sélections: on lit le fichier PBF d'un bout à
l'autre, en récupérant dans le désordre les noeuds, ways et relations, sans
savoir au fur et à mesure comment ils sont liés.

CONCLUSION :

La bibliothèque sert alors surtout à convertir un PBF dans un autre format,
mais toute notion de compression par proximité géographique codée dans le
PBF est perdue. On doit le réimplémenter.

La bibliothèque en revanche sera pas trop compliquée pour des recherches
simples où on ne cherche QUE des noeuds et aucun chemin ni aucune relation
(car là il faut un filtrage relationnel, pouvant même nécessiter une
récursion (pour connecter dans l'ordre les chemins formant une boucle
fermée), mais elle sera très lente à fournir les réponses car elle parcourt
le fichier d'un bout à l'autre : créer avec cette bibiloth_que un index
géographique des noeuds sera plus efficace pour permettre des recherches
ultérieures.

Le script de conversion OSM vers OpenGIS pour PostgreSQL en fait beaucoup
plus !

Ce genre de bibliothèque C++ peut être une base possible pour réécrire cet
outil d'export vers un schéma OpenGIS comparable mais pour d'autres moteurs
de bases de données. Voire pour regénérer un fichier .osm minimum en XML,
mais il me semble qu'on a déjà un outil de conversion PBF vers XML/OSM.

La bibliothèque ne gère rien non plus concernant la création des PBF :
c'est de la lecture seule, linéaire d'un bout à l'autre, un simple parseur
énumérateur dépourvu de tout filtre et incapable de retourner des chemins
complets ou des relations complètes et inutilisable pour faire des
recherches efficaces (sur des gros PBF).

Le code C++ libéré en revanche est très léger, juste suffisant pour faire
un décodage linéaire d'une partie du contenu du PBF, notamment de ses
"blobs" et de ses "stringtables". Le code est plus léger que celui en démo
dans les specs du format PBF/OSM, ou celui en démo dans les specs du format
PBF enveloppe de base (documenté par Google).

Dommage que Canal TP n'aient pas libéré plutôt une API permettant d'accéder
à des données de transport en temps réel (des données qui cependant
viendrait des réseaux de transport qu'ils équipent, et devraient être
libérées séparément).

2012/11/14 Cyrille Giquello <cyrille37 at gmail.com>

> Canal TP libère du code pour OpenStreetMap
>
> http://www.canaltp.fr/non-classe/canal-tp-libere-du-code-pour-openstreetmap/
>
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/dev-fr/attachments/20121114/913c207b/attachment.html>