La correspondance floue vous permet d’identifier les correspondances non exactes de votre élément cible. C’est la pierre angulaire de nombreux cadres de moteurs de recherche et l’une des principales raisons pour lesquelles vous pouvez obtenir des résultats de recherche pertinents même si vous avez une coquille dans votre requête ou un temps verbal différent.
Comme vous pouvez vous y attendre, il existe de nombreux algorithmes qui peuvent être utilisés pour la recherche floue sur du texte, mais pratiquement tous les cadres de moteurs de recherche (y compris bleve) utilisent principalement la distance de Levenshtein pour la correspondance floue des chaînes de caractères :
Distance de Levenshtein
Aussi connue sous le nom de distance d’édition, c’est le nombre de transformations (suppressions, insertions ou substitutions) nécessaires pour transformer une chaîne de caractères source en chaîne de caractères cible. Par exemple, si le terme cible est « livre » et que la source est « dos », vous devrez changer le premier « o » en « a » et le second « o » en « c », ce qui nous donnera une distance de Levenshtein de 2.La distance d’édition est très facile à mettre en œuvre, et c’est un défi populaire lors des entretiens de code (Vous pouvez trouver des implémentations de Levenshtein en JavaScript, Kotlin, Java, et bien d’autres ici).
En outre, certains frameworks supportent également la distance Damerau-Levenshtein:
Distance Damerau-Levenshtein
C’est une extension de la distance Levenshtein, permettant une opération supplémentaire : Transposition de deux caractères adjacents :
Ex : TSAR en STAR
Damerau-Levenshtein distance = 1 (Intervertir les positions S et T ne coûte qu’une seule opération)
Levenshtein distance = 2 (Remplacer S par T et T par S)
Correspondance floue et pertinence
La correspondance floue a un gros effet secondaire ; elle met le désordre avec la pertinence. Bien que Damerau-Levenshtein soit un algorithme qui prend en compte la plupart des fautes d’orthographe de l’utilisateur commun, il peut également inclure un nombre important de faux positifs, surtout lorsque nous utilisons une langue avec une moyenne de seulement 5 lettres par mot, comme l’anglais. C’est pourquoi la plupart des cadres de moteurs de recherche préfèrent s’en tenir à la distance de Levenshtein. Voyons un exemple réel :
Pour commencer, nous allons utiliser cet ensemble de données de catalogue de films. Je le recommande vivement si vous voulez jouer avec la recherche en texte intégral. Ensuite, recherchons les films avec « book » dans le titre. Un code simple ressemblerait à ce qui suit :
|
1
2
3
4
5
6
|
String indexName = « movies_index » ;
MatchQuery query = SearchQuery.match(« book »).field(« title ») ;
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6)) ;
printResults(movies) ;
|
Le code ci-dessus apportera les résultats suivants :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Le voleur de livres
score : 4.826942606027416
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
2) Le livre d’Eli
score : 4,826942606027416
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
3) Le livre de la vie
score : 4.826942606027416
Lieux des coups :
champ:titre
terme:livre
fragment :
—————————–
4) Livre noir
score : 4,826942606027416
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
5) Le livre de la jungle
score : 4.826942606027416
Lieux de rencontre :
champ:titre
terme:livre
fragment :
—————————–
6) Le livre de la jungle 2
score : 3.9411821308689627
Lieux de rencontre :
champ:titre
terme:livre
fragment :
—————————–
|
Par défaut, les résultats sont insensibles à la casse, mais vous pouvez facilement changer ce comportement en créant de nouveaux index avec différents analyseurs.
Maintenant, ajoutons une capacité de correspondance floue à notre requête en définissant le caractère flou à 1 (distance de Levenshtein 1), ce qui signifie que « book » et « look » auront la même pertinence.
|
1
2
3
4
5
6
|
String indexName = « movies_index » ;
MatchQuery query = SearchQuery.match(« book »).field(« title »).fuzziness(1) ;
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6)) ;
printResults(movies) ;
|
Et voici le résultat de la recherche floue :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Crochet
score : 1.1012248063242538
Emplacements touchés :
champ:titre
terme:crochet
fragment :
—————————–
2) Here Comes the Boom
score : 0.7786835148361213
Lieux des coups :
champ:titre
terme:boom
fragment :
—————————–
3) Regardez qui parle aussi
score : 0,7047266634351538
Emplacements touchés :
champ:titre
terme:regard
fragment :
—————————–
4) Look Who’s Talking
score : 0.7047266634351538
Emplacements touchés :
champ:titre
terme:regard
fragment :
—————————–
5) Le voleur de livres
score : 0.52288117537184
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
6) Le livre d’Eli
score : 0,52288117537184
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
|
Maintenant, le film appelé « Hook » est le tout premier résultat de recherche, ce qui pourrait ne pas être exactement ce que l’utilisateur attend dans une recherche pour « Book ».
Comment minimiser les faux positifs pendant les recherches floues
Dans un monde idéal, les utilisateurs ne feraient jamais de fautes de frappe en recherchant quelque chose. Cependant, ce n’est pas le monde dans lequel nous vivons, et si vous voulez que vos utilisateurs aient une expérience agréable, vous devez gérer au moins une distance d’édition de 1. Par conséquent, la vraie question est la suivante : comment pouvons-nous faire de la correspondance de chaînes de caractères floue tout en minimisant la perte de pertinence ?
Nous pouvons tirer parti d’une caractéristique de la plupart des cadres de moteurs de recherche : Une correspondance avec une distance d’édition plus faible aura généralement un score plus élevé. Cette caractéristique nous permet de combiner ces deux requêtes avec différents niveaux de flou en une seule :
|
1
2
3
4
5
6
7
8
|
Chaîne indexName = « movies_index » ;
String word = « Book » ;
MatchQuery titleFuzzy = SearchQuery.match(word).fuzziness(1).field(« title ») ;
MatchQuery titleSimple = SearchQuery.match(word).field(« title ») ;
DisjunctionQuery ftsQuery = SearchQuery.disjonctives(titleSimple, titleFuzzy) ;
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, ftsQuery).highlight().limit(20)) ; printResults(resultat) ;
|
Voici le résultat de la requête floue ci-dessus :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
1) Le voleur de livres
score : 2.398890092610849
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
2) Le livre d’Eli
score : 2.398890092610849
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
3) Le livre de la vie
score : 2.398890092610849
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
4) Livre noir
score : 2.398890092610849
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
5) Le Livre de la jungle
score : 2.398890092610849
Lieux de frappe :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
6) Le livre de la jungle 2
score : 1.958685557004688
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
7) National Treasure : Book of Secrets
score : 1.6962714808368062
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
8) American Pie Presents : Le livre de l’amour
score : 1,517191317611584
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:book
fragment :
—————————–
9) Crochet
score : 0.5052232518679681
Emplacements touchés :
champ:titre
terme:crochet
fragment :
—————————–
10) Here Comes the Boom
score : 0.357246781294941
Lieux des coups :
champ:titre
terme:arbre
fragment :
—————————–
11) Look Who’s Talking Too
score : 0.32331663301992025
Emplacements touchés :
champ:titre
terme:regard
fragment :
—————————–
12) Look Who’s Talking
score : 0.32331663301992025
Emplacements touchés :
champ:titre
terme:regard
fragment :
—————————–
|
Comme vous pouvez le voir, ce résultat est beaucoup plus proche de ce que l’utilisateur pourrait attendre. Notez que nous utilisons maintenant une classe appelée DisjunctionQuery, les disjonctions sont un équivalent de l’opérateur « OR » en SQL.
Qu’est-ce que nous pourrions encore améliorer pour réduire l’effet secondaire négatif d’un algorithme de correspondance floue ? Réanalysons notre problème pour comprendre s’il nécessite d’autres améliorations :
Nous savons déjà que les recherches floues peuvent produire des résultats inattendus (par exemple, Livre -> Regarder, Crochet). Cependant, une recherche à terme unique est généralement une requête terrible, car elle nous donne à peine un indice de ce que l’utilisateur essaie exactement d’accomplir.
Même Google, qui a sans doute l’un des algorithmes de recherche floue les plus développés en usage, ne sait pas exactement ce que je cherche lorsque je recherche « table » :
Alors, quelle est la longueur moyenne des mots-clés dans une requête de recherche ? Pour répondre à cette question, je vais montrer un graphique tiré de la présentation de Rand Fishkin en 2016. (Il est l’un des gourous les plus célèbres dans le monde du SEO)
Selon le graphique ci-dessus, ~80% des requêtes de recherche ont 2 mots-clés ou plus, alors essayons de rechercher le film « Black Book » en utilisant le flou 1 :
|
1
2
. 3
4
5
6
|
String indexName = « movies_index » ;
MatchQuery query = SearchQuery.match(« Livre noir »).field(« title »).fuzziness(1) ;
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12)) ;
printResults(movies) ;
|
Résultat :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
1) Score du livre noir
: 0.6946442424065404
Emplacements touchés :
champ:titre
terme:livre
fragment :
—————————–
field:title
term:black
fragment :
—————————–
2) Crochet
score : 0.40139742528039857
Emplacements touchés :
champ:titre
terme:crochet
fragment :
—————————–
3) Attaque du bloc
score : 0,2838308365090324
Lieux des coups :
champ:titre
terme:bloc
fragment :
—————————–
4) Here Comes the Boom
score : 0.2838308365090324
Lieux des coups :
champ:titre
terme:boom
fragment :
—————————–
5) Regardez qui parle aussi
score : 0.25687349813115684
Lieux des coups :
champ:titre
terme:regard
fragment :
—————————–
6) Look Who’s Talking
score : 0.25687349813115684
Hit Locations :
champ:titre
terme:regard
fragment :
—————————–
7) Grosse Pointe Blank
score : 0.2317469073782136
Lieux des coups :
champ:titre
terme:blanc
fragment :
—————————–
8) Le voleur de livres
score : 0.19059065534780495
Lieux des coups :
champ:titre
terme:livre
fragment :
—————————–
9) Le livre d’Eli
score : 0,19059065534780495
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
10) Le livre de la vie
score : 0,19059065534780495
Lieux des coups :
champ:titre
terme:livre
fragment :
—————————–
11) Le livre de la jungle
score : 0,19059065534780495
Lieux de coups :
champ:titre
terme:livre
fragment :
—————————–
12) Retour vers le futur
score : 0.17061000968368
Lieux de coups :
champ:titre
terme:retour
fragment :
—————————–
|
Pas mal. Nous avons obtenu le film que nous recherchions comme premier résultat. Cependant, une requête de disjonction apporterait encore un meilleur ensemble de résultats.
Mais quand même, il semble que nous ayons une nouvelle propriété agréable ici ; l’effet secondaire de la correspondance floue diminue légèrement lorsque le nombre de mots-clés augmente. Une recherche pour « Black Book » avec fuzziness 1 peut encore apporter des résultats comme back look ou lack cook (certaines combinaisons avec edit distance 1), mais il est peu probable que ce soient de vrais titres de films.
Une recherche pour « livre eli » avec fuzziness 2 l’apporterait encore comme troisième résultat :
|
1
2
3
4
5
6
|
String indexName = « movies_index » ;
MatchQuery query = SearchQuery.match(« book eli »).field(« title »).fuzziness(2) ;
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12)) ;
printResults(movies) ;
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Ed Wood
score : 0.030723793900031805
Lieux de coups :
champ:titre
terme:bois
fragment :
—————————–
field:title
term:ed
fragment :
—————————–
2) Homme de Tai Chi
score : 0.0271042761982626
Lieux des coups :
champ:titre
terme:chi
fragment :
—————————–
field:title
term:tai
fragment :
—————————–
3) Le livre d’Eli
score : 0.02608335441670756
Lieux des coups :
champ:titre
terme:eli
fragment :
—————————–
field:title
term:book
fragment :
—————————–
4) Le bon mensonge
score : 0.02439822770591834
Lieux de coups :
champ:titre
terme:mensonge
fragment :
—————————–
field:title
term:good
fragment :
—————————–
|
Cependant, comme le mot anglais moyen est long de 5 lettres, je ne recommanderais PAS d’utiliser une distance d’édition supérieure à 2, sauf si l’utilisateur recherche des mots longs et faciles à mal orthographier, comme « Schwarzenegger » par exemple (du moins pour les non-allemands ou les non-autrichiens).
Conclusion
Dans cet article, nous avons discuté de la correspondance floue et de la façon de surmonter son principal effet secondaire sans gâcher sa pertinence. Attention, la correspondance floue n’est qu’une des nombreuses fonctionnalités dont vous devriez tirer parti tout en mettant en œuvre une recherche pertinente et conviviale. Nous allons en aborder quelques-unes au cours de cette série : N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.
Voyez aussi la partie 1 et la partie 2 de cette série.
En attendant, si vous avez des questions, tweetez-moi à @deniswsrosa.
Auteur
- Denis Rosa, Developer Advocate, Couchbase –
.