Comment utiliser les recherches floues dans Elasticsearch

Introduction

La recherche en langage naturel est intrinsèquement imprécise. Comme les ordinateurs ne comprennent pas le langage naturel, il existe une multitude d’approches de recherche, chacune avec ses avantages et ses inconvénients. Lucene, la technologie sous-jacente à Elasticsearch, est un couteau suisse composé de nombreux outils de traitement de texte. Chaque outil contenu est une heuristique, un raccourci algorithmique en remplacement d’une véritable compréhension linguistique. Certains de ces outils, comme le stemmer Snowball et l’analyseur phonétique Metaphone, sont assez sophistiqués. Ces outils imitent respectivement les aspects grammaticaux et phonétiques de la compréhension du langage. D’autres outils sont très basiques, comme le type de requête préfixe, qui correspond simplement aux lettres de début des mots. Les requêtes floues se situent quelque part au milieu de cette boîte à outils en termes de sophistication. Elles trouvent des mots nécessitant au maximum un certain nombre de modifications de caractères, appelées « modifications », pour correspondre à la requête. Par exemple, une recherche floue de « ax » correspondrait au mot « axe », puisque seule une suppression, supprimant le « e », est nécessaire pour que les deux mots correspondent.

Une simple correspondance floue

Les requêtes floues peuvent être réalisées plus facilement via des arguments supplémentaires au type de requête de correspondance, comme on le voit dans l’exemple ci-dessous dans ce paragraphe. Dans l’exemple, la demande finale, une recherche de « vaacuum » (aspirateur), qui contient un A supplémentaire, devrait toujours donner le produit « Vacuum ». L’argument flou précise que les résultats correspondent avec une distance maximale de modification de 2. Il convient de noter que le flou ne doit être utilisé qu’avec les valeurs 1 et 2, ce qui signifie qu’un maximum de 2 modifications entre la requête et un terme dans un document est autorisé. Les différences plus importantes sont bien plus coûteuses à calculer efficacement et ne sont pas traitées par Lucene. La documentation officielle fait toujours référence à la définition de flou à des valeurs flottantes, comme 0,5, mais ces valeurs sont en fait obsolètes et sont plus difficiles à raisonner.

# Créer l’index
PUT /fuzzy_products
# Créer le **mapping** du produit
PUT /fuzzy_products/product/_mapping
{
  "product": {
    "properties": {
      "name": {
        "type": "string",
        "analyzer": "simple"
      }
    }
  }
}
# **Télécharger** des documents
PUT /fuzzy_products/product/1
{"name": "Vacuum Cleaner"}
PUT /fuzzy_products/product/2
{"name": "Turkey Baster"}
# Fais une **recherche** floue !
POST /fuzzy_products/product/_search
{
  "query": {
    "match": {
      "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      }
    }
  }
}

Détermination de la distance d’édition

La métrique utilisée par les requêtes floues pour déterminer une correspondance est la formule de la distance de Damerau-Levenshtein. En termes simples, la distance de Damerau-Levenshtein entre deux textes est le nombre d’insertions, suppressions, substitutions et transpositions nécessaires pour que l’une des chaînes corresponde à l’autre. Par exemple, la distance de Levenshtein entre les mots « ax » et « axe » est de 1 en raison de la suppression unique requise.

La formule de la distance de Damerau-Levenshtein est une modification de la formule classique de la distance de Levenshtein, la modifiant en ajoutant la transposition comme opération valide. Les deux formules sont prises en charge, Damerau-Levenshtein étant la norme par défaut, et Levenshtein classique étant sélectionnable en mettant les transpositions sur faux dans la requête. L’utilité des transpositions peut être vue dans le cas de la comparaison des chaînes « aex » et « axe ». En utilisant la formule classique de distance de Levenshtein, « aex » n’est pas une, mais deux modifications. Le « e » doit être supprimé, après quoi un nouveau « e » est inséré à la place appropriée, tandis que dans Damerau-Levenshtein, une seule opération, échangeant le « e » et le « x », suffit. En extrapolant de cela, utiliser le Levenshtein classique signifierait que « aex » est aussi éloigné de « axe » que de « faxes », exemple montrant pourquoi Damerau-Levenshtein a plus de sens intuitif dans la plupart des cas.

Lorsqu’on traite particulièrement des recherches floues, il est essentiel de comprendre que dans Elasticsearch, le texte est d’abord passé par un analyseur avant d’être rendu disponible pour la recherche. Lorsque les données sont indexées, elles sont traitées en ce qu’on appelle des « termes », les unités réellement consultables dans la base de données. Ce sont les termes analysés (ce que les termes sont est couvert dans Elasticsearch from the Bottom Up), et non les documents stockés eux-mêmes qui sont recherchés. Cela signifie que lors de l’exécution de requêtes floues, le texte de requête peut être comparé à une valeur de terme inattendue à la suite d’une analyse, ce qui conduit parfois à des résultats confus. Cela signifie aussi que si les synonymes sont activés sur un champ, les synonymes peuvent être appariés, même si ce mot n’apparaît pas du tout dans le texte source. Par exemple, si l’on utilisait une requête floue sur un champ analysé par ngram, les résultats seraient probablement bizarres, car les ngrams divisent les mots en de nombreuses combinaisons de lettres, dont beaucoup ne sont qu’à une ou deux modifications, bien que les mots concernés soient assez différents. Cela signifie aussi que si on utilise, par exemple, un analyseur de boule de neige, une recherche floue de « running », sera dérivée vers « run », mais ne correspondra pas au mot mal orthographié « runninga », qui vient de « runninga », car « run » est à plus de 2 modifications de « runninga ». Cela peut causer beaucoup de confusion, et pour cette raison, il est souvent logique d’utiliser uniquement l’analyseur simple sur un texte destiné à être utilisé avec des requêtes floues, ce qui peut aussi désactiver les synonymes. Pour clarifier cela, un diagramme montrant une requête floue s’exécutant sur un document analysé par boule de neige peut être vu ci-dessous.

Les différents types de recherches floues

Plusieurs types de recherche floue sont pris en charge par Elasticsearch et les différences peuvent être déroutantes. La liste ci-dessous tente de clarifier ces différents types.

• correspondance requête + option de tolérance : Ajouter le paramètre flou à une requête de correspondance transforme une requête de correspondance simple en une requête floue. Analyse le texte de la requête avant d’effectuer la recherche. Requête
• floue : Le type de requête flou Elasticsearch doit généralement être évité. Le fonctionnement est proche d’une requête de terme. Il n’analyse pas d’abord le texte de la requête.
• fuzzy_like_this (flou_comme_ceci)/fuzzy_like_this_field (flou_comme_ce_champ) : Une requête more_like_this (plutot_comme_ceci), mais qui prend en charge la tolérance et dispose d’un algorithme de notation ajusté qui gère mieux les caractéristiques des résultats flous appariés.*
• suggesteurs : Les suggesteurs ne sont pas un type de requête réel, mais plutôt un type d’opération distinct (construit en interne sur des requêtes floues) qui peut être exécuté soit parallèlement à une requête, soit indépendamment. Les suggesteurs sont parfaits pour une fonctionnalité de type « tu voulais dire ? »

Une requête de correspondance avec le paramètre flou est sans doute la plus polyvalente des requêtes floues. Le type de requête flou prend en charge exactement le même comportement, sauf qu’il ne permet aucune analyse du texte de requête. De plus, le type de requête floue est un sous-ensemble de la fonctionnalité d’une requête de correspondance, ce qui la rend plus confuse qu’utile.

Les requêtes fuzzy_like_this, ou FLT, sont utiles pour fournir des recommandations basées sur un long texte source qui peut contenir des fautes d’orthographe ou d’autres inexactitudes séparées par distance de modification. Il existe deux requêtes différentes dans cette catégorie fuzzy_like_this et fuzzy_like_this_field, qui offrent toutes deux la même fonctionnalité, la seconde simplifiant la syntaxe pour le cas où un seul champ est utilisé. Ces requêtes prennent un paramètre, like_text, constitué d’un grand texte, par exemple le corps d’un article, et essaient de trouver des documents « similaires » à celui-ci. Le texte de l’article est vérifié, et les termes de requête sont pondérés en fonction de leur fréquence dans le like_text avec des ajustements spéciaux (désactivation du facteur coordonnée, IDF basé sur le texte source) pour combiner les différents termes du texte source. Les requêtes FLT fonctionnent mieux dans les cas où le corpus contient un grand nombre de fautes d’orthographe, sinon une requête more_like_this standard aura de meilleures performances. Plus de détails sont disponibles dans la documentation officielle de Fuzzy More Like This.

Les suggesteurs sont excellents si un utilisateur tape « New Yrok », pour une recherche, alors qu’il avait l’intention de taper « New York ». Les applications peuvent suggérer de présenter une case « vouliez-vous dire » dans l’interface utilisateur suggérant une correction potentielle. Attention que, pour le cas spécifique de la recherche à l’avance, l’ API d’achèvement offre de meilleures performances compte tenu de la sensibilité à la latence des recherches à l’avance. Plus d’informations sur les suggesteurs sont disponibles sur la page de recherche des suggesteurs.

Considérations de performance

Même si l’implémentation de distance Levenshtein de Lucene est à la pointe de la technologie, et assez rapide, elle reste beaucoup plus lente qu’une simple requête de correspondance. L’exécution de la requête augmente avec le nombre de termes uniques dans l’index. Autrement dit, lors d’une recherche floue, le critère principal n’est pas le nombre de documents qui seront retournés, mais le nombre de termes uniques dans le cluster pour les champs recherchés. S’il y a 100 documents avec 10 000 mots uniques chacun, la recherche dans cet index sera plus lente que celle de 10 000 documents où le champ recherché ne contient que 100 mots uniques.

La principale raison de cette lenteur est qu’une requête de correspondance standard peut rapidement vérifier l’index des termes, une structure de données interne utilisée par Lucene, pour une correspondance et trouver des documents extrêmement rapidement grâce à la recherche binaire. Ce processus est rapide même pour les grands dictionnaires, car les recherches binaires s’adaptent bien. Les requêtes floues, en revanche, utilisent un algorithme plus avancé impliquant un DFA qui doit traiter un grand nombre de termes. Traiter le nombre beaucoup plus important de termes requis pour une recherche floue est toujours plus lent qu’une simple recherche binaire. Par exemple, effectuer une recherche floue sur l’ensemble de données Wikipédia en anglais prend environ 320 ms pour le terme « history » étant donné un min_similarity de 2, tandis qu’une recherche par correspondance simple pour le même terme dure en un simple 35 ms, soit une différence d’un ordre de grandeur. Avec un min_similarity de 1, le temps de recherche n’est que de 150 ms. Il convient de noter que ces tests n’ont pas été réalisés de manière statistiquement fiable, et que ces durées peuvent être significativement influencées par des facteurs propres à chaque application. L’ensemble de données Wikipédia, en particulier, contient bien plus de termes que de nombreux cas d’utilisation courants.

Les performances peuvent être significativement améliorées en exigeant que les correspondances aient des correspondances exactes avec les préfixes de la requête. Cela réduit considérablement l’espace de recherche au risque de ne pas trouver de mots avec une faute d’orthographe. Plus la longueur du préfixe est longue, plus l’accélération est forte. Spécifier un prefix_length de 1 réduit la requête de 320 ms mentionnée ci-dessus à seulement 104 ms. Augmenter ce nombre a permis de gagner encore plus de vitesse. En général, il est conseillé d’exiger un préfixe pour les ensembles de données avec un grand nombre de termes ou la performance sera médiocre, souvent dans les centaines de millisecondes.

Le paramètre max_expansions, qui définit le nombre maximal de termes que la requête floue associera avant d’arrêter la recherche, peut également avoir des effets dramatiques sur la performance d’une requête floue. Cependant, réduire les termes de requête a un effet négatif, car certains résultats valides peuvent ne pas être trouvés en raison de la fin précoce de la requête. Il est important de comprendre que la limite de requête max_expansions fonctionne au niveau de la partition, ce qui signifie que même si elle est fixée à 1, plusieurs termes peuvent correspondre, tous provenant de différentes partitions. Ce comportement peut donner l’impression que max_expansions n’est pas en vigueur, donc attention : compter les termes uniques qui sont retournés n’est pas un moyen valable de déterminer si max_expansions fonctionne.

Alternatives à la correspondance floue

Le jumelage flou n’est pas toujours l’outil idéal pour le travail, souvent des correspondances imprécises peuvent être trouvées par d’autres techniques. Le plug-in d’analyse phonétique contient plusieurs outils fascinants pour approximer les correspondances, comme l’analyseur de métaphone, qui trouve des mots qui ressemblent à d’autres mots. Par exemple, si ce qui est nécessaire est de s’assurer que des mots comme « run » et « ran » sont tous deux considérés comme équivalents, un analyseur intelligent comme un analyseur boule de neige est préférable. Alternativement, pour vérifier les fautes d’orthographe, l’analyse N-gramme, comme décrit dans ce court tutoriel, peut être beaucoup plus rapide au moment de la requête, selon l’ensemble de données. Les N-grammes se font cependant au détriment d’une utilisation supplémentaire de stockage/mémoire, d’un traitement en temps d’indexation légèrement plus élevé, et d’une longue extrême de faux positifs après de bonnes correspondances.

Plus de lectures

• Pour un examen plus approfondi des performances des requêtes floues dans Elasticsearch, Mike McCandless, contributeur principal de Lucene, a écrit un article de blog passionnant sur le sujet. Il existe également une vidéo, Automates à état fini à Lucene et Solr, d’une présentation de Dawid Weiss qui traite de Levenshtein et d’autres automates à Lucene.
• Si vous souhaitez en savoir plus sur Levenshtein Automata, Nick Johnson a écrit un excellent article intitulé Damn Cool Algorithms : Levenshtein Automata.