JDONREFv4 Query
La requête jdonrefv4 du plugin éponyme permet de chercher efficacement des adresses correspondant aux types de JDONREFv4.
Sommaire
Requête et résultat
{
"query": {
"jdonrefv4" : {
"value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
}
}
}
Il s'agit d'une requête multi-termes. Ils sont décrit dans la page traitant des index.
Avec une requête POST du type :
curl -XPOST 'http://localhost:9200/jdonref/_search' -d '{ "query": { "jdonrefv4" : { "value" : "24 BOULEVARD DE L HOPITAL 75005 PARIS" } } }'
le résultat est de la forme :
{
"_shards":{
"total" : 5,
"successful" : 5,
"failed" : 0
},
"hits":{
"total" : 1,
"hits" : [
{
"_index" : "jdonref",
"_type" : "adresse",
"_id" : "1",
"_score" : 200.0,
"_source" : {
"adr_id" : "123456789X",
"code_insee" : "75105",
"code_departement": "75",
"numero" : "24",
"type_de_voie" : "BOULEVARD",
"article" : "DE L",
"libelle" : "HOPITAL",
"commune" : "PARIS",
"code_postal" : "75005",
"ligne4": "24 BOULEVARD DE L HOPITAL",
"ligne6": "75005 PARIS",
"ligne7": "FRANCE",
"geometrie": { "type" :"point", "coordinates": [123, 456] }
}
}
]
}
}
Les types "voie", "commune", "departement", "pays" peuvent aussi être retournés. Les coordonnées sont en WGS84 par défaut dans la version 0.2, une version ultérieure permettra de le transformer à la volée en Lambert 93.
Filtres
Il est possible de la combiner avec des filtres, par exemple pour limiter les résultats à un département précis :
{
"filtered" : {
"query": {
"jdonrefv4" : {
"value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
}
},
"filter": {
"term" : { "code_departement" : "75" }
}
}
}
Ou de restreindre la recherche à une zone géographique :
{
"filtered" : {
"query": {
"jdonrefv4" : {
"value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
}
},
"filter" : {
"geo_shape": {
"geometrie" : {
"shape" : {
"type" : "enveloppe",
"coordinates": [[13,53],[14,52]]
}
}
}
}
}
}
Fonctionnement
JDONREFv4Query s'appuie sur un mélange de multiples sous-requêtes et de mécanismes de scoring.
Les sous-requêtes sont constituées :
- de chacun des tokens saisis pour chacun des termes cherchés
- sont spécifique à chaque index (adresse, voie, ...)
- évoluent au fil de la requête. Une requête très permissive est d'abord effectuée, puis moins permissive, puis encore moins ...
Le score est influencé par plusieurs éléments :
- la présence de plusieurs termes identiques
- l'absence de termes dans le document (notamment la repetition)
- divisé par le score maximum possible pour un document
J'explique ces choix dans le détail.
Elasticsearch (tout comme lucene) fourni un outil manipulant des index inversés. Ce qui est très efficace lorsque le scoring s'appuie sur la somme des notes associées au termes cherchés. Pour être très simplificateur, l'algorithme consiste alors à faire la somme des valeurs d'un tableau. Néanmoins, un tableau de 5 000 éléments reste différent d'un tableau de 5 000 000 d'éléments, et le parcourir est généralement 1000 fois plus long. Suivant la fréquence des termes, il est facile de voire passer une requête de 1ms à 1s.
Deux principes ont alors été appliqués à notre requête :
- utiliser des filtres efficaces pour limiter la taille des tableaux
- faire évoluer la requête en cours de calcul
Des filtres efficaces
Le premier point est facile à comprendre. Je prends un exemple. Une recherche sur une adresse n'a pas de sens si le numéro n'est pas saisi. Dans le cas contraire, la recherche d'une voie serait encombrée de l'ensemble des adresses de cette voie ! Peut-être que quelques numéros sont pertinents, mais certainement pas tous. Un exemple de filtre efficace est alors, uniquement pour les adresses, d'imposer le numéro.
Comment imposer un numéro pour une adresse ? Le meilleur endroit est au niveau du parser de la requête. A ce niveau, nous pouvons détecter l'index sur lequel la requête est en cours d'exécution et adapter la requête en conséquence. Il aurait aussi été possible de modifier la requête dans la requête elle-même, au niveau de sa réécriture (rewrite). Mais quitte à être modifiée, autant la modifier le plus tôt possible. Dans le code, c'est
if (matchesIndices(parseContext.index().name(), "*adresse*")
&& terms.stream().filter((i)->isInteger(i)).count()>0 // au moins un numéro dans la requête
&& terms.size()>1) // et deux éléments saisis
Les types suivant ne sont ainsi retournés en résultat que lorsque les filtres spécifiés sont vérifiés :
| type | filtres |
| poizon | un élément de la ligne1 doit être présent |
| adresse | le numéro exact et l'éventuelle répétition exacte doivent être présent |
| voie | un élement de la ligne 4 |
| commune | un élément de la commune ou un code postal, insee, département, arrondissement voire le code insee de la commune parente |
| departement | le code département |
| pays | un élément de la ligne7 |
Changer de requête en cours de calcul
Prenons la requête
numero:24 ou type_de_voie:24 ou type_de_voie:boulevard ou type_de_voie:hopital ou libelle:24 ou libelle:boulevard ou libelle:hopital
qui correspond à la recherche de 24 BD HOPITAL (en omettant les codes, la commune, et la répétition pour l'exemple).
Cette requête peut retourner plusieurs catégories de résultat.
- des documents contenant 24 : 300 000
- des documents contenant boulevard : 600 000
- des documents contenant hopital : 250 000
- des documents contenant 24 boulevard : 70 000
- des documents contenant 24 hopital : 35 000
- des documents contenant boulevard hopital : 80 000
- des documents contenant 24 boulevard hopital : 10 000
Il va sans dire que la catégorie la plus représentée est celle où les termes trouvés sont seuls, et la catégorie la moins représentée celle où les 3 termes sont trouvés. Et pourtant, il est fort probable que le document cherché soit un de ceux où les 3 termes sont trouvés. En laissant la requête telle quelle, les meilleurs résultats seront certes ceux attendus, mais au total, 1 150 000 documents auront été parcourus.
Les 300 000 documents contenant uniquement 24 sont-ils réellement utiles ? JDONREFv4 fait le postulat que non, et que parmi ces 300 000 documents, l'utilisateur ne saura pas retrouver ceux qui l'intéresse. Par contre, il est peut-être utile dans laisser quelques uns.
L'algorithme suivi correspond ainsi à peut près à :
- je cherche 100 documents contenant 24 ou boulevard ou hopital
- puis je continue avec 100 document contenant 24 et boulevard ou 24 et hopital ou boulevard et hopital
- puis je continue avec 100 documents contenant 24 et boulevard et hopital
Cela ne donne que 300 documents ? Et le votre n'est pas dedans ? C'est possible. Mais les 300 documents retournés sont légitimes. Si vous avez assez de temps pour fouiller dans 300 documents, je pense que vous avez aussi le temps d'attendre que la requête complète soit exécutée. Nous ne parlons donc pas de la même chose.
Il s'agit ensuite d'adapter le principe à la recherche avec faute d'orthographe et l'auto-complétion.
L'influence sur le score
Les filtres qui sont décrit ici n'apporte rien en terme de performances, et peuvent être potentiellement challengés si des solutions plus efficaces existent. Il s'agit uniquement de mettre les documents dans le bon ordre, ou de filtrer les résultats.
Elasticsearch comme lucene ne permettent pas de savoir si une répétition est présente ou pas dans le document sous forme de requête. En effet, la requête générée consiste à chercher les documents qui ne matchent aucun des termes présent dans l'index ! Ce n'est efficace que pour un nombre réduit de valeurs. Mais les répétitions sont une trentaine (les lettres plus les versions longues). Le challenge, c'est de savoir identifier si la requête n'a pas matché une répétition mais que le document en a une. Le type de chaque sous-requête étant connu, il est simple de faire la liste des types qui ont matché. Le code suivant est alors utilisé dans le Scorer de la requête :
if (((getTypeMask()&2)==0) && isRepetitionInDoc(doc))
this.score = 0;
Il est facile de savoir si un terme saisi n'a pas été trouvé dans le document.
Et d'influencer le score en conséquence. C'est fait ainsi :
this.score *= ((ICountable)innerScorer).count();
this.score /= this.maxCoord;
Mais il est plus difficile de savoir combien de termes dans le document aurait pu être trouvés pour influencer le score. Par exemple, par défaut, elasticsearch (comme lucene) retourne le même score pour la recherche
9 BD PALAIS
sur les documents
9 BD PALAIS 9 BD PALAIS ROYAL
car seul les termes saisis ont une influence sur le code. J'ai testé deux méthodes :
- associer des payloads aux termes pour fournir l'information manquante (par exemple le nombre de termes)
- utiliser la valeur d'un autre terme
La première méthode prend beaucoup de place mémoire, et ralenti le processus. Les deux méthodes nécessitant un précalcul, je me suis tourné vers la deuxième, plus légère. Le terme choisi est un champ "score". Il contient le score maximal à laquelle une recherche peut aboutir pour un document. Il s'agit d'un choix. Le numéro vaut 30. La répétition vaut 30. Un toke de libelle 50. etc ... Pour que l'absence d'un terme dans la requête influence le score, on prend le total, on le divise par le score du document, ... et c'est tout. Ainsi, si le score des documents est :
9 BD PALAIS => 100 9 BD PALAIS ROYAL => 150
et que la recherche aurait conduit au score :
9 BD PALAIS => 100
Les résultats pour chaque document deviennent :
9 BD PALAIS => 100 % 9 BD PALAIS ROYAL => 66 %
et le premier document a maintenant un meilleur score.
Par défaut, elasticsearch (et lucene) privilégient les documents dans lequel le terme cherché apparaît plusieurs fois.
C'est très gênant pour les adresses. De nombreuses adresses disposent d'un terme présent à la fois dans le libellé et dans le nom de commune par exemple.
Il faudrait déjà savoir que le terme est trouvé plusieurs fois !
Pour chaque sous-requête est alors stocké le token correspondant. Lorsque 1 même token matche 2 sous-requête pour un même document, une défausse de point est effectué. Cela prend cette forme dans le code :
this.score -= countBits(multiTokenMatch())*20;
Exemples de calcul
Les exemples qui suivent ne sont pas exhaustifs mais présentent le comportement recherché par la requête. La note donnée ici est indicative.
| requête | résultat | note indicative | calcul |
| 130 RUE REMY DUHEM 59500 DOUAI | 130 RUE REMY DUHEM 59500 DOUAI FRANCE | 200 | Tous les éléments de ligne4, code postal, et commune sont présents. Le pays est absent, mais son poids est de 0. |
| 130 RUE REMY DUHEM 59 DOUAI | 130 RUE REMY DUHEM 59500 DOUAI FRANCE | 200 | Tous les éléments de ligne4 et commune sont présents. Le code de département est correct. Le pays est absent, mais son poids est de 0. |
| 130 RUE REMY 59500 DOUAI DUHEM | 130 RUE REMY DUHEM 59500 DOUAI FRANCE | 166 = ((50 + 50 + 50 + 50)*0.5/4 + 50 + 50 + 0)*200/150 | Tous les éléments de ligne4 (50+50+50+50), code postal et commune (50+50) sont présents. Le pays est absent, mais son poids est de 0. L'ordre des éléments de la ligne 4 n'est pas respecté (*0.5). Le tout pondéré (/150) et ramené à 200 (*200). |
| RUE REMY DUHEM 59500 DOUAI | RUE REMY DUHEM 59500 DOUAI FRANCE | 200 | Tous les éléments de ligne4, code postal, et commune sont présents. Le pays est absent, mais son poids est de 0. |
| RUE REMY DUHEM 59500 DOUAI | 130 RUE REMY DUHEM 59500 DOUAI FRANCE | 0 | Tous les éléments du code postal et commune sont présents. Le pays est absent, mais son poids est de 0. Un malus est toutefois appliqué du fait de l'absence du numéro d'adresse dans la requête, ce qui attribue une note de 0 au total. |
| RUE REMY 59 DOUAI | RUE REMY DUHEM 59500 DOUAI FRANCE | 177 = ((50 + 50)/3 + 50 + 50 + 0) * 200 / 150 | Le code postal et la commune sont présent (50 + 50). Le pays est absent, mais son poids est de 0. Seuls 2 termes sur 3 sont présents dans la ligne 4 ((50 + 50)/3). Le tout pondéré (/150) et ramené à 200 (*200). |
| RUE REMY 59 DOUAI | RUE REMY DUHEM 59500 DOUAI FRANCE | 177 = ((50 + 50)/3 + 50 + 50 + 0) * 200 / 150 | Le code postal et la commune sont présent (50 + 50). Le pays est absent, mais son poids est de 0. Seuls 2 termes sur 3 sont présents dans la ligne 4 ((50 + 50)/3). Le tout pondéré (/150) et ramené à 200 (*200). |
| RUE REM DUH 59 DOUAI | RUE REMY DUHEM 59500 DOUAI FRANCE | 163 = ((50*75/100 + 50*60/100)/3 + 50 + 50 + 0) * 200 / 150 | Le code postal et la commune sont présent (50 + 50). Le pays est absent, mais son poids est de 0. Seuls 2 termes sur 3 sont présents dans la ligne 4, et partiels ((50*75/100 + 50*60/100)/3). Le tout pondéré (/150) et ramené à 200 (*200). |
| 59500 DOUAI | 59500 DOUAI FRANCE | 200 | Le code postal et la commune sont présent. Le pays est absent, mais son poids est de 0. |
| 59500 DOUAI | RUE REMY DUHEM 59500 DOUAI FRANCE | 133 = (0 + 50 + 50 + 0) * 200 / 150 | Le code postal et la commune sont présent (50+50). La ligne 4 est absente (0). Le pays est absent, mais son poids est de 0. Le tout pondéré (/150) et ramené à 200 (*200). |
| 59505 DOUAI | 59500 DOUAI FRANCE | 100 = (0 + 50 + 0) * 200 /100 | La commune est présente (50), mais le code postal est faux (0). Le pays est absent, mais son poids est de 0. NB: pour améliorer cette note (le code postal est très proche), une évolution du TokenFilter de JDONREF devrait être effectuée). NB : à l'heure actuelle, ce score est de 0 : les erreurs ne sont pas tolérées par le mapping défini. |
| 59 | 59 FRANCE | 200 | Le code département est présent. |
| FRANCE | FRANCE | 200 | La ligne 7 est présente. |
Ces exemples ne présentent pas la prise en compte de la phonétique, qui n'intervient pas dans la notation. Deux requêtes qui disposent de la même phonétique ont les mêmes résultats.
Changer de champ pour la recherche
Si vous avez personnalisé votre mapping, il vous est peut-être nécessaire de modifier le champ utilisé par défaut comme analyzer de la recherche. Il s'agit d'utiliser le paramètre default_field. Par défaut, il vaut libelle, mais vous pouvez le modifier.
{
"query": {
"jdonrefv4" : {
"value" : "24 BOULEVARD DE L HOPITAL 75 PARIS",
"default_field" : "libelle"
}
}
}
Effets de bord
Les exemples présentés ci-dessus induisent nécessairement des effets de bords compréhensibles sur certaines recherches.
Par exemple :
- Il ne faut pas s'attendre à trouver comme meilleur résultat l'avenue de France en effectuant une recherche sur le seul mot clé "FRANCE". C'est bien entendu le pays qui aura la meilleure note ...
