Exportation GeoJSON, recherche d'arrêts

JSON (pour JavaScript Object Notation) est un format textuel relativement simple permettant de représenter des données organisées en hiérarchie. Ce format est très utilisé sur le Web pour échanger des données entre ordinateurs.

Un document JSON peut être composé de valeurs atomiques — c.-à-d. qui ne sont pas composées d'autres valeurs plus petites — et de valeurs composites.

Les deux seuls types de valeurs atomiques que nous utiliserons dans ce projet sont :

• les nombres, dont la syntaxe est, à quelques détails près, la même que celle des valeurs de type double en Java,
• les chaînes, dont la syntaxe est, à quelques détails près, la même que celle des chaînes en Java.

En plus de ces types de valeurs atomiques, nous utiliserons également les deux types de valeurs composites de JSON, qui sont :

• les tableaux, dont les éléments sont entourés par des crochets ([ et ]) et séparés par des virgules (,),
• les « objets », similaires à des tables associatives, dont les paires clef/valeur sont entourées par des accolades ({ et }) et séparées par des virgules (,) ; la clef et la valeur d'une paire sont séparées par un deux-points (:).

Les espaces entre les différents éléments sont ignorées.

Par exemple, le document JSON suivant représente un tableau contenant 4 éléments, chacun d'entre eux étant un objet constitué de deux paires clef/valeur, la première ayant pour clef name, la seconde ayant pour clef radius.

[ { "name": "Earth", "radius": 6371.0 }, { "name": "Mars", "radius": 3389.5 }, { "name": "Venus", "radius": 6051.8 }, { "name": "Jupiter", "radius": 69911 } ]

GeoJSON (pour Geographic JSON) est une version de JSON permettant de représenter des données géospatiales, c.-à-d. des données géométriques — points, lignes, polygones, etc. — à la surface de la Terre.

Dans le cadre de ce projet, nous utiliserons le format GeoJSON pour exporter le tracé (approximatif) d'un voyage afin de le visualiser sur un site Web externe. Le seul type de donnée que nous utiliserons pour cela est la ligne brisée (polyline ou line string) et c'est donc le seul qui sera décrit ici.

Dans le format GeoJSON, une ligne brisée est représentée par un objet ayant deux paires clef/valeur :

1. la première a pour clef type et pour valeur LineString, et identifie l'objet comme étant une ligne brisée,
2. la seconde a pour clef coordinates et pour valeur un tableau de tableaux de nombres, chaque sous-tableau contenant deux nombres représentant les coordonnées géographiques (longitude et latitude, en degrés) d'un point de la ligne brisée.

Par exemple, le document GeoJSON suivant représente une ligne brisée reliant, dans cet ordre, les gares de Lausanne, Palézieux, Romont et Fribourg:

{ "type": "LineString", "coordinates": [[6.62909, 46.51679], [6.83787, 46.54276], [6.91181, 46.69351], [7.15105, 46.80315]] }

Ce document GeoJSON peut être validé et visualisé sur différents sites Web comme GeoJSONLint, geojson.io ou uMap.

Pour trouver les arrêts dont le nom correspond à une requête, celle-ci est tout d'abord découpée en sous-requêtes (sub-queries), séparées les unes des autres par des espaces. Par exemple, la requête mez vil est composée de deux sous-requêtes, mez et vil. L'ordre des sous-requêtes n'est pas important, donc la requête vil mez est totalement équivalente à mez vil.

Les noms d'arrêts correspondant à une requête sont ceux qui contiennent chacune des sous-requêtes. Toutefois, le test pour déterminer si un nom d'arrêt contient une sous-requête n'est pas effectué de manière stricte, dans la mesure où :

• une lettre non accentuée est considérée comme équivalente à n'importe laquelle de ses variantes accentuées,
• si la sous-requête ne comporte aucune majuscule, alors une lettre minuscule est considérée comme équivalente à sa variante majuscule.

La table ci-dessous précise la première de ces règles en montrant les 6 lettres qui sont considérées comme équivalentes à d'autres lettres — généralement leurs variantes accentuées — ainsi que ces équivalences :

Par exemple, le nom d'arrêt Mézières FR, village correspond à la requête mez vil car :

• il contient — au sens non strict décrit ci-dessus — la sous-requête mez, puisque Méz est considéré comme équivalent à mez,
• il contient la sous-requête vil.

Ce même nom d'arrêt ne correspond toutefois pas à la requête meZ vil, car le Z majuscule de la première sous-requête force le test d'appartenance à respecter les majuscules et minuscules. De même, il ne correspond pas à la requête mèz vil, car le è (e grave) de la première sous-requête n'est pas équivalent au é (e aigu) présent dans le nom.

Une fois que les noms des arrêts correspondant à la requête ont été obtenus, ils doivent encore être triés par pertinence, de la plus élevée à la plus basse.

La pertinence d'un nom d'arrêt par rapport à une requête est déterminée en attribuant un « score de pertinence » à chaque nom d'arrêt. Ce score est déterminé comme suit.

Le score de base d'une sous-requête est le pourcentage — arrondi vers le bas à l'entier le plus proche — du nom de l'arrêt correspondant à la sous-requête. Par exemple, le score de base de la sous-requête mez pour le nom d'arrêt Mézières FR, village vaut 15, car 15% des caractères du nom — 3 sur 20 — correspondent à la sous-requête.

Ce score de base est encore éventuellement multiplié par :

• un facteur 4 si la sous-requête correspond au début d'un mot, c.-à-d. si elle se trouve tout au début du nom de l'arrêt, ou si le caractère la précédant dans ce nom n'est pas une lettre,
• un facteur 2 si la sous-requête correspond à la fin d'un mot, c.-à-d. si elle se trouve tout à la fin du nom, ou si le caractère la suivant n'est pas une lettre.

Lorsqu'une sous-requête correspond à la fois au début et à la fin d'un mot, son score de base est multiplié par les deux facteurs, donc 8 au total.

Si une sous-requête apparaît plusieurs fois dans un nom d'arrêt, alors seule sa première occurrence est utilisée pour déterminer son score.

Finalement, les scores de toutes les sous-requêtes sont additionnés pour obtenir le score de la requête complète.

La table ci-dessous donne les scores de la requête mez vil pour les 4 arrêts de l'horaire officiel auxquels elle correspond.

Pour les deux premiers arrêts, le score (120) est déterminé ainsi : les deux sous-requêtes ont la même longueur, donc le même score de base, qui vaut 15 ; les deux sont de plus au début d'un mot, mais pas à la fin, donc ces scores de base sont multipliés par 4 pour donner 60. Finalement, ces deux scores individuels des sous-requêtes sont additionnés pour obtenir celui de la requête, qui vaut donc 120.

À première vue, la recherche d'une sous-requête dans un nom d'arrêt paraît difficile à mettre en œuvre, car elle doit se faire de la manière non stricte décrite plus haut — en considérant une lettre non accentuée comme équivalente à n'importe laquelle de ses variantes accentuées, et en ignorant généralement la distinction entre les majuscules et les minuscules. Toutefois, grâce au concept d'expression régulière (regular expression) et aux classes de la bibliothèque Java permettant de les manipuler, il est possible de la mettre en œuvre relativement aisément.

Brièvement, une expression régulière — ER dans ce qui suit — est une notation compacte pour décrire un ensemble de chaînes de caractères. Au moyen d'une ER, il est donc possible de décrire facilement toutes les variantes d'une sous-requête à rechercher.

Par exemple, la sous-requête Mez correspond à un total de 5 chaînes différentes (Mez, Méz, Mèz, Mêz et Mëz) car le e non accentué est équivalent à n'importe laquelle de ses variantes accentuées. Cet ensemble de 5 chaînes s'écrit facilement sous la forme d'une ER, ainsi :  M[eéèêë]z . En effet, dans une ER, un ensemble de caractères placé entre crochets représente n'importe lequel de ces caractères. (Les crochets ont été mis en rouge ici pour qu'il soit bien clair qu'ils ne font pas partie des chaînes décrites par l'ER, mais indiquent simplement un choix entre les caractères qu'ils entourent.)

Il découle de ce qui précède que la recherche d'une sous-requête peut se faire en :

1. la transformant en une ER, puis
2. recherchant cette ER dans les noms d'arrêts.

La transformation d'une sous-requête en une ER consiste simplement à remplacer chaque caractère de la première colonne de la table de la §2.2.1 par l'ensemble des caractères de la seconde colonne. Par exemple, la sous-requête Mezier est transformée en l'ER  M[eéèêë]z[iíìîï][eéèêë]r .

La recherche de l'ER dans les noms d'arrêts peut se faire facilement en Java, dont la bibliothèque offre des classes permettant de représenter des ER et de les rechercher dans des chaînes. Cette recherche peut de plus se faire sans tenir compte des différences entre majuscules et minuscules, ce qui permet de facilement mettre en œuvre la seconde équivalence décrite plus haut.

La classe Pattern de la bibliothèque Java représente une expression régulière. Sa méthode compile permet de transformer une chaîne contenant une expression régulière en l'instance de Pattern correspondante. Par exemple, l'appel suivant :

Pattern vowels = Pattern.compile("[aeiou]");

permet d'obtenir une expression régulière décrivant l'ensemble des chaînes constituées d'une seule voyelle.

Il existe également une variante de la méthode compile qui prend en second argument des « fanions » (flags) permettant d'activer différentes options. Ces fanions sont passés sous la forme d'un entier de type int dont les différents bits représentent chacun une option. Ainsi, pour obtenir une expression régulière pour laquelle la différence entre les majuscules et les minuscules est ignorée, on peut appeler la méthode ainsi :

int flags = Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE;
Pattern noCaseVowels = Pattern.compile("[aeiou]", flags);

Une fois une expression régulière obtenue, on peut l'utiliser de différentes manières. Par exemple, les méthodes split et splitWithDelimiters permettent de découper une chaîne à chaque occurrence d'une expression régulière. Cela s'avère très utile pour découper la requête en sous-requêtes, et pour séparer chaque sous-requête en les parties à transformer en ensembles de caractères — les voyelles et la lettre c — et les parties « constantes », à préserver telles quelles.

Lors de la construction de l'ER correspondant à une sous-requête il faut prendre garde à appeler la méthode quote sur toutes les parties constantes avant de les ajouter à la chaîne à passer à compile. Cela garantit que même si ces parties contiennent des caractères ayant une signification particulière dans les ER, comme les crochets, elles sont interprétées de manière littérale. Ainsi, l'ER pour la sous-requête mez doit être construite d'une manière équivalente à celle-ci :

Pattern mez = Pattern.compile(Pattern.quote("m")
                              + "[eéèêë]"
                              + Pattern.quote("z"));

Pour rechercher une expression régulière dans une chaîne, il faut tout d'abord obtenir un matcher correspondant, au moyen de la méthode matcher. Cela fait, on peut appeler la méthode find de cet objet pour lui faire rechercher la prochaine occurrence de l'expression régulière dans la chaîne. S'il y en a une, les méthodes start et end permettent d'obtenir ses positions de début et de fin dans la chaîne.

Notez pour terminer que la programmation par flots permet d'écrire le code de StopIndex de manière particulièrement concise et élégante, et il vaut donc la peine d'essayer de l'utiliser.