Récemment, dans le cadre d’une mission pour un client, on a eu besoin d’autocomplétion sur une base de maladies rares. Le projet tournant sur MongoDB, le défi était d’utiliser cet outil. N’ayant jamais utilisé MongoDB jusqu’ici, c’était une bonne occasion pour aller explorer ses possibilités.
Le besoin
Quel est le besoin?
- complétion des mots: “cys” doit remonter “cystic” par exemple
- tolérance à la faute: “cis” ou “citsic” doivent aussi remonter “cystic”
- rapidité: l’autocomplétion est basée sur le feedback pour ajuster la recherche en temps réel; objectif: moins de 50 ms
- pertinence: le résultat attendu doit apparaître dans les trois premiers
- possibilité de copier-coller un nom entier de maladie dans le champ de recherche
Hypothèse de départ
Contrairement à un outil comme Elasticsearch, MongoDB ne contient aucune fonctionnalité native pour gérer l’autocomplétion. Il y a bien un index Full Text Search (FTS), mais il ne gère que des tokens entiers. Les exemples sur Internet pointent pour la plupart sur des solutions à base de regex, qui ne nous ont pas convaincu pour deux raisons: utilisation des index très limitée (donc temps de réponse pas terrible) et tolérance à la faute assez minimale. Dans le cadre de mon travail sur Addok (le moteur de recherche dédié aux adresses qui est derrière http://adresse.data.gouv.fr/), j’avais expérimenté un algo à base de trigrammes qui m’a semblé une bonne hypothèse de départ. Les grandes lignes: à l’indexation, on divise les termes de recherche en trigrammes (“cystic” devient [“cys”, “yst”, “sti”, “tic”]), on en fait de même au moment de la recherche, et enfin on cherche les documents qui partagent le plus de trigrammes avec la recherche.
Le jeu de données
Le jeu de données est la base OrphaData, qui classifie les maladies rares. C’est une classification multiparentale, mais dans le cadre de cet exercice on peut se contenter de l’importer à plat. On va utiliser la version anglaise.
Un script d’import python dans MongoDB pourrait ressembler à ça:
from lxml import etree
from pymongo import MongoClient
client = MongoClient()
db = client.mydb
collection = db.disorders
# From http://www.orphadata.org/data/xml/en_product1.xml
root = etree.parse("en_product1.xml")
docs = []
for disorder in root.iterfind("//Disorder"):
docs.append(
{
"name": disorder.find("Name").text,
"_id": int(disorder.find("OrphaNumber").text),
}
)
if len(docs) == 100:
collection.insert_many(docs)
docs = []
On peut vérifier que l’import a bien fonctionné via le shell mongo:
$ mongo mydb
> db.disorders.find()
{ "_id" : 166024, "name" : "Multiple epiphyseal dysplasia, Al-Gazali type" }
{ "_id" : 166032, "name" : "Multiple epiphyseal dysplasia, with miniepiphyses" }
{ "_id" : 58, "name" : "Alexander disease" }
{ "_id" : 166029, "name" : "Multiple epiphyseal dysplasia, with severe proximal femoral dysplasia" }
{ "_id" : 61, "name" : "Alpha-mannosidosis" }
…
> db.disorders.count()
9500
Préparer les données
Il faut maintenant indexer les trigrammes, c’est-à-dire tout simplement créer un champ dédié dans les documents.
Voici une méthode basique pour diviser une chaîne en trigrammes:
def trigrams(value, n=3):
return [value[i : i + n] for i in range(0, len(value) - (n - 1))]
On met à jour notre import:
…
for disorder in root.iterfind("//Disorder"):
name = disorder.find("Name").text
docs.append(
{
"name": name,
# On ajoute trigrams.
"trigrams": trigrams(name),
"_id": int(disorder.find("OrphaNumber").text),
}
)
…
On supprime la db (db.dropDatabase() depuis le shell mongo) et on réimporte:
> db.disorders.find()
{ "_id" : 166024, "name" : "Multiple epiphyseal dysplasia, Al-Gazali type", "trigrams" : [ "Mul", "ult", "lti", "tip", "ipl", "ple", "le ", "e e", " ep", "epi", "pip", "iph", "phy", "hys", "yse", "sea", "eal", "al ", "l d", " dy", "dys", "ysp", "spl", "pla", "las", "asi", "sia", "ia,", "a, ", ", A", " Al", "Al-", "l-G", "-Ga", "Gaz", "aza", "zal", "ali", "li ", "i t", " ty", "typ", "ype" ] }
{ "_id" : 166032, "name" : "Multiple epiphyseal dysplasia, with miniepiphyses", "trigrams" : [ "Mul", "ult", "lti", "tip", "ipl", "ple", "le ", "e e", " ep", "epi", "pip", "iph", "phy", "hys", "yse", "sea", "eal", "al ", "l d", " dy", "dys", "ysp", "spl", "pla", "las", "asi", "sia", "ia,", "a, ", ", w", " wi", "wit", "ith", "th ", "h m", " mi", "min", "ini", "nie", "iep", "epi", "pip", "iph", "phy", "hys", "yse", "ses" ] }
Nos trigrammes sont bien là.
Première recherche
C’est le moment de tester la recherche.
text = trigrams("Fuc")
for doc in collection.find({"trigrams": {"$in": text}}):
print(doc["name"])
Ce qui nous donne:
Fucosidosis
Fuchs heterochromic iridocyclitis
Fuchs endothelial corneal dystrophy
Pas si mal: “Fuc” a bien été complété en “Fucosidosis”.
Testons avec le mot complet:
text = trigrams("Fucosidosis")
for doc in collection.find({"trigrams": {"$in": text}}):
print(doc["name"])
Ouille! 1432 résultats, et les trois premiers sont:
Alpha-mannosidosis
Aspartylglucosaminuria
Beta-mannosidosis
Rien à voir avec notre recherche. Pour ceux qui suivent, c’est pas une surprise: on a demandé à Mongo de trouver tous les documents qui contiennent au moins un trigramme parmi les trigrammes de “Fucosidosis”, c’est-à-dire:
['Fuc', 'uco', 'cos', 'osi', 'sid', 'ido', 'dos', 'osi', 'sis']
Il est temps de pondérer un peu tout ça!
On met de l’ordre
Première hypothèse: on va remonter en premier les documents qui matchent le plus de trigrammes. Ça complexifie un peu la requête: on va utiliser l'aggregation.
Voici à quoi ressemble notre nouvelle requête:
text = trigrams(text)
print(f"Searching {text}")
docs = collection.aggregate(
[
{"$match": {"trigrams": {"$in": text}}},
{
"$project": {
"name": "$name",
# Extract the trigram that matched.
"found": {
"$size": {
"$filter": {
"input": "$trigrams",
"as": "item",
"cond": {"$in": ["$$item", text]},
}
}
},
}
},
{"$sort": {"found": -1}},
{"$limit": 3},
]
)
Ce qui donne en sortie:
{'_id': 349, 'name': 'Fucosidosis', 'found': 9}
{'_id': 118, 'name': 'Beta-mannosidosis', 'found': 6}
{'_id': 61, 'name': 'Alpha-mannosidosis', 'found': 6}
Pas si mal! Fucosidosis est maintenant premier de la liste.
Essayons de regarder ce qu’on vient de faire un peu plus en détails:
L’aggregate est une liste d’opérations (un pipeline dans le langage MongoDB), qui prennent les documents en entrée, les transforment et retournent les documents transformés en sortie.
Première étape, on cherche les documents qui contiennent au moins un trigramme (comme avant):
{"$match": {"trigrams": {"$in": text}}}
Deuxième étape, la plus complexe:
{
"$project": {
"name": "$name",
# Extract the trigram that matched.
{
"$project": {
"name": "$name",
# Extract the trigram that matched.
"found": {
"$size": {
"$filter": {
"input": "$trigrams",
"as": "item",
"cond": {"$in": ["$$item", text]},
}
}
},
}
},
}
},
Ici on va transformer le document initial (qui avait les clés _id, name et trigrams) en un nouveau document avec les clés name et found.
Cette nouvelle clé found contient le nombre de trigrammes de la recherche trouvés dans le document.
Ensuite, avec {"$sort": {"found": -1}} on trie nos documents en mettant en premier ceux qui ont le plus de trigrammes trouvés, et {"$limit": 3} ne conserve que les trois premiers d’entre eux.
Bien. Essayons de challenger notre requête en cherchant la maladie “Cystic Fibrosis” avec l’entrée “Cystic”:
{'_id': 431320, 'name': 'Spastic paraplegia-optic atrophy-neuropathy and spastic paraplegia-optic atrophy-neuropathy-related disorder', 'found': 6}
{'_id': 1851, 'name': 'Multicystic dysplastic kidney', 'found': 6}
{'_id': 2575, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome', 'found': 6}
Aïe! Pas terrible, et on comprend vite pourquoi: “Spastic paraplegia-optic atrophy-neuropathy and spastic paraplegia-optic atrophy-neuropathy-related disorder” contient quatre fois le trigramme “tic”.
Essayons de dédoublonner les trigrammes trouvés via un set:
docs = collection.aggregate(
[
{"$match": {"trigrams": {"$in": text}}},
{
"$project": {
"name": "$name",
# Extract the trigram that matched.
"found": {
"$size": {
# On a ajouté cet opérateur.
"$setUnion": [
{
"$filter": {
"input": "$trigrams",
"as": "item",
"cond": {"$in": ["$$item", text]},
}
}
]
}
},
}
},
{"$sort": {"found": -1}},
{"$limit": 3},
]
)
Nouveau test:
{'_id': 2575, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome', 'found': 4}
{'_id': 2111, 'name': 'Cystic hamartoma of lung and kidney', 'found': 4}
{'_id': 586, 'name': 'Cystic fibrosis', 'found': 4}
Mieux! “Cystic fibrosis” est bien dans les trois premiers résultats, et d’ailleurs les trois résultats commencent par “Cystic”, c’est-à-dire le terme cherché.
Tolérance à la faute
Et si on cherche “cistic firbosis” ?
Acceptable, le résultat est troisième:
{'_id': 79118, 'name': 'Neonatal diabetes-congenital hypothyroidism-congenital glaucoma-hepatic fibrosis-polycystic kidneys syndrome', 'found': 7}
{'_id': 2575, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome', 'found': 7}
{'_id': 586, 'name': 'Cystic fibrosis', 'found': 7}
Et si on cherche “cistic”?
Beuark!
{'_id': 183663, 'name': 'Hyper-IgM syndrome with susceptibility to opportunistic infections', 'found': 3}
{'_id': 183666, 'name': 'Hyper-IgM syndrome without susceptibility to opportunistic infections', 'found': 3}
{'_id': 540, 'name': 'Familial hemophagocytic lymphohistiocytosis', 'found': 3}
C’est qu’on a omis un point important: nettoyer la chaîne! Commençons par le plus évident: mettre en majuscule et enlever les caractères non alphanumériques (notamment les “-” dans notre jeu de données). Mais profitons-en pour faire un peu de nettoyage pour éviter les fautes de frappe les plus courantes:
- remplaçons les “y” par des “i”
- remplaçons les “c” par des “k” sauf devant une voyelle
- remplaçons les “s” par des “z” entre deux voyelles
- supprimons les doubles consonnes
De façon générale, tout ce qui est n’est pas discriminant dans un corpus peut être nettoyé sans risque d’augmenter les faux positifs. Par exemple, dans notre corpus, aucun mot ne diffère d’un autre juste parce qu’il aurait un “i” à la place d’un “y”.
Voilà à quoi pourrait ressembler une telle fonction de nettoyage:
def clean_text(text):
text = re.sub(" {2,}", " ", re.sub(r"[^\w]", " ", text)).lower().strip()
rules = (
("c(?=[^ieyw])", "k"),
("c$", "k"),
("(?<=[aeiouy])s(?=[aeiouy])", "z"),
("ph", "f"),
("(?<=[^sc])h", ""),
("^h(?=.)+", ""),
("(?<=[^0-9])y", "i"),
("(\\D)(?=\\1)", ""), # Remove duplicate letters.
)
for pattern, repl in rules:
text = re.sub(pattern, repl, text)
return text
Il faut l’appeler à la fois au moment de l’indexation et au moment de la recherche, avant d’appeler trigrams.
Réimportons, et testons de nouveau avec “cistic”:
{'_id': 169095, 'name': 'Alymphoid cystic thymic dysgenesis', 'found': 4}
{'_id': 731, 'name': 'Autosomal recessive polycystic kidney disease', 'found': 4}
{'_id': 586, 'name': 'Cystic fibrosis', 'found': 4}
Mieux! Mais on aimerait bien que les documents dont le nom commence par “Cystic” arrivent en premier.
Une astuce possible, c’est de mettre un caractère spécial (ici ^) pour délimiter le début de nos chaînes avant de les transformer en trigrams:
def trigrams(value, n=3):
value = f"^{value}"
return [value[i : i + n] for i in range(0, len(value) - (n - 1))]
Ça va créer un trigram de plus pour chaque document “^xx” avec les deux premières lettres du document, dans notre cas “^ci”, et comme on en fait autant au moment de la recherche, les documents qui effectivement commencent par les mêmes lettres que la recherche seront surpondérés par rapport aux documents qui contiennent ces lettres ailleurs qu’au début.
Si on réindexe et teste de nouveau:
{'_id': 2575, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome', 'found': 5}
{'_id': 2111, 'name': 'Cystic hamartoma of lung and kidney', 'found': 5}
{'_id': 586, 'name': 'Cystic fibrosis', 'found': 5}
C’est mieux, mais intuitivement, c’est un peu déroutant de ne pas avoir en premier le résultat le plus court, et donc le plus proche des termes recherchés.
Scoring, pertinence et précision
Il y a une part de psychologie dans la qualité d’un résultat de recherche: on aura confiance dans un outil s’il sort des résultats qui nous semblent cohérents, sans trop de résultats farfelus, et sans trop de magie apparente.
Pour remettre l’algo sur ses pieds, il faut tâcher de calculer la pertinence des résultats. C’est-à-dire en gros essayer d’évaluer à quel point un résultat est proche de la recherche initiale, à quel point il est « satisfaisant » pour l’utilisateur.
Pour ça, on va calculer deux scores:
- la « pertinence » : à quel point les termes recherchés représentent le document, c’est-à-dire tout simplement le rapport entre le nombre de trigrams recherchés présents dans ce document et le nombre de trigrams totaux dans ce document
- la « précision » : à quel point un document matche les termes recherchés, c’est-à-dire concrètement le nombre de trigrams recherchés trouvés dans le document
Pour produire un score final, on va mettre chacun de ces scores sur une échelle de 0 à 1 et les ajouter. Pour affiner, on pourrait repondérer chacun des scores pour leur donner plus ou moins d’importance dans le score final, mais ne compliquons pas trop.
Voici ce que donne notre requête avec un score:
text = trigrams(clean_text(text))
print(f"Searching {text}")
docs = collection.aggregate(
[
{"$match": {"trigrams": {"$in": text}}},
{
"$project": {
"name": "$name",
"found": {
"$size": {
# Dedupe the matched trigrams.
"$setUnion": [
{
# Extract the trigram that matched.
"$filter": {
"input": "$trigrams",
"as": "item",
"cond": {"$in": ["$$item", text]},
}
}
]
}
},
"length": {"$size": "$trigrams"},
}
},
{
"$project": {
"score": {
"$divide": [
{
"$add": [
# How much the query matched THAT document.
{"$divide": ["$found", "$length"]},
# How much THAT document match the query
{"$divide": ["$found", len(text)]},
]
},
2,
]
},
"name": "$name",
}
},
{"$sort": {"score": -1}},
{"$limit": 3},
]
)
Vous avez vu qu’on a rajouté une étape dans le pipeline: d’abord on calcule le nombre de trigrams trouvés, puis on compare ce nombre d’une part au nombre de trigrams dans le document, et d’autre part au nombre de tokens dans la recherche, et on remet ce score sur une échelle de 0 à 1.
Testons de nouveau notre requête “cistic fibrosis”:
{'_id': 586, 'score': 1.0, 'name': 'Cystic fibrosis'}
{'_id': 2575, 'score': 0.6296296296296297, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome'}
{'_id': 213, 'score': 0.5476190476190476, 'name': 'Cystinosis'}
Parfait, on a ce qu’on voulait!
Quelques tests pour confirmer nos hypothèses:
$ python orphacomplete.py search cistic
{'_id': 79486, 'score': 0.7083333333333334, 'name': 'Cystic hygroma'}
{'_id': 586, 'score': 0.6785714285714286, 'name': 'Cystic fibrosis'}
{'_id': 400, 'score': 0.6388888888888888, 'name': 'Cystic echinococcosis'}
$ python orphacomplete.py search cist
{'_id': 213, 'score': 0.6666666666666666, 'name': 'Cystinosis'}
{'_id': 214, 'score': 0.6666666666666666, 'name': 'Cystinuria'}
{'_id': 1560, 'score': 0.625, 'name': 'Cysticercosis'}
$ python orphacomplete.py search fuc
{'_id': 349, 'score': 0.6, 'name': 'Fucosidosis'}
{'_id': 263479, 'score': 0.5344827586206896, 'name': 'Fuchs heterochromic iridocyclitis'}
{'_id': 2060, 'score': 0.5333333333333333, 'name': 'Fukuda-Miyanomae-Nakata syndrome'}
$ python orphacomplete.py search "cist fib"
{'_id': 586, 'score': 0.5357142857142857, 'name': 'Cystic fibrosis'}
{'_id': 2575, 'score': 0.40343915343915343, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome'}
{'_id': 213, 'score': 0.38095238095238093, 'name': 'Cystinosis'}
$ python orphacomplete.py search "cisticfibrozis"
{'_id': 586, 'score': 0.8159340659340659, 'name': 'Cystic fibrosis'}
{'_id': 213, 'score': 0.5641025641025641, 'name': 'Cystinosis'}
{'_id': 2575, 'score': 0.5249287749287749, 'name': 'Cystic fibrosis-gastritis-megaloblastic anemia syndrome'}
$ python orphacomplete.py search Fucosidosis
{'_id': 349, 'score': 0.9, 'name': 'Fucosidosis'}
{'_id': 79212, 'score': 0.45833333333333337, 'name': 'Mucolipidosis'}
{'_id': 309144, 'score': 0.4423076923076923, 'name': 'Gangliosidosis'}
On voit sur ce dernier cas des résultats très peu pertinents. On peut optionnellement directement les filtrer en ne conservant que les scores supérieurs à 0.5, en ajoutant cette étape dans le pipeline:
{"$match": {"score": {"$gt": 0.5}}},
Temps de réponse
Et les temps de réponse dans tous ça? Ajoutons un timer.
start = time.perf_counter()
# requête
duration = time.perf_counter() - start
for doc in docs:
print(doc)
print(f"Duration: {duration:.5f}")
Testons avec “cistic”: Duration: 0.04937, pile en dessous de notre objectif de 50 ms!
Essayons d’ajouter un index:
collection.create_index("trigrams")
Testons de nouveau avec “cistic”: Duration: 0.02260, hop! temps divisé par deux.
Note: dans l’aggrégationn, seul un $match exécuté avant un $project (ou équivalent) peut utiliser un éventuel index.
Conclusion
Pour un jeu de données pas trop volumineux comme celui d’OrphaData, MongoDB a tout ce qu’il faut pour se passer d’un outil en plus pour gérer l’autotocomplétion.
Le script final est disponible ici.
Ne ratez pas nos prochains articles DevOps et Cloud Native! Suivez Enix sur Twitter!