Version actuelle en date du 26 février 2016 à 23:46

La requête jdonrefv4 du plugin éponyme permet de chercher efficacement des adresses correspondant aux types de JDONREFv4.

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 :

1. de chacun des tokens saisis pour chacun des termes cherchés
2.  sont spécifique à chaque index (adresse, voie, ...)
3. é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 :

1. la présence de plusieurs termes identiques
2. l'absence de termes dans le document (notamment la repetition)
3. 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 :

1. utiliser des filtres efficaces pour limiter la taille des tableaux
2.  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 :

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.

1. des documents contenant 24  : 300 000
2. des documents contenant boulevard  : 600 000
3. des documents contenant hopital  : 250 000
4.  des documents contenant 24 boulevard  : 70 000
5. des documents contenant 24 hopital  : 35 000
6. des documents contenant boulevard hopital  : 80 000
7.  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 à :

1. je cherche 100 documents contenant 24 ou boulevard ou hopital
2. puis je continue avec 100 document contenant 24 et boulevard ou 24 et hopital ou boulevard et hopital
3. 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 :

1. associer des payloads aux termes pour fournir l'information manquante (par exemple le nombre de termes)
2. 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.

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 :

1. 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 ...