La concordancia difusa le permite identificar coincidencias no exactas de su elemento objetivo. Es la piedra angular de muchos marcos de trabajo de los motores de búsqueda y una de las principales razones por las que puede obtener resultados de búsqueda relevantes incluso si tiene un error tipográfico en su consulta o un tiempo verbal diferente.
Como era de esperar, hay muchos algoritmos que se pueden utilizar para la búsqueda difusa en el texto, pero prácticamente todos los marcos de los motores de búsqueda (incluyendo bleve) utilizan principalmente la distancia Levenshtein para la coincidencia de cadenas difusas:
Distancia Levenshtein
También conocida como distancia de edición, es el número de transformaciones (eliminaciones, inserciones o sustituciones) necesarias para transformar una cadena de origen en la de destino. Por ejemplo, si el término destino es «libro» y el origen es «espalda», será necesario cambiar la primera «o» por «a» y la segunda «o» por «c», lo que nos dará una Distancia de Levenshtein de 2.La Distancia de Edición es muy fácil de implementar, y es un reto popular durante las entrevistas de código (Puedes encontrar implementaciones de Levenshtein en JavaScript, Kotlin, Java, y muchas otras aquí).
Además, algunos frameworks también soportan la distancia Damerau-Levenshtein:
Distancia Damerau-Levenshtein
Es una extensión de la distancia Levenshtein, permitiendo una operación extra: Transposición de dos caracteres adyacentes:
Ejemplo: TSAR a STAR
Distancia Damerau-Levenshtein = 1 (Cambiar las posiciones de S y T sólo cuesta una operación)
Distancia Levenshtein = 2 (Reemplazar S por T y T por S)
Coincidencia difusa y relevancia
La coincidencia difusa tiene un gran efecto secundario; se desordena con la relevancia. Aunque Damerau-Levenshtein es un algoritmo que tiene en cuenta la mayoría de los errores ortográficos del usuario común, también puede incluir un número importante de falsos positivos, especialmente cuando utilizamos un idioma con una media de sólo 5 letras por palabra, como el inglés. Por este motivo, la mayoría de los marcos de trabajo de los motores de búsqueda prefieren utilizar la distancia Levenshtein. Veamos un ejemplo real de ello:
Primero, vamos a utilizar este conjunto de datos de catálogos de películas. Lo recomiendo encarecidamente si quieres jugar con la búsqueda de texto completo. A continuación, vamos a buscar películas con «libro» en el título. Un código sencillo sería el siguiente
|
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);
|
El código anterior dará los siguientes resultados:
|
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) La ladrona de libros
puntuación: 4.826942606027416
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
2) El libro de Eli
puntuación: 4,826942606027416
Localizaciones de aciertos:
campo:título
término:libro
fragmento:
—————————–
3) El libro de la vida
puntuación: 4,8269426027416
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
4) Libro negro
puntuación: 4.8269426027416
Hit Locations:
campo:título
término:libro
fragmento:
—————————–
5) El libro de la selva
puntuación: 4.8269426027416
Hit Locations:
campo:título
término:libro
fragmento:
—————————–
6) El libro de la selva 2
puntuación: 3.9411821308689627
Hit Locations:
campo:título
término:libro
fragmento:
—————————–
|
Por defecto, los resultados no distinguen entre mayúsculas y minúsculas, pero se puede cambiar fácilmente este comportamiento creando nuevos índices con diferentes analizadores.
Ahora, vamos a añadir una capacidad de coincidencia difusa a nuestra consulta estableciendo la difusividad como 1 (distancia Levenshtein 1), lo que significa que «libro» y «mirada» tendrán la misma relevancia.
|
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);
|
Y aquí está el resultado de la búsqueda difusa:
|
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) Gancho
puntuación: 1.1012248063242538
Ubicaciones de los golpes:
campo:título
término:gancho
fragmento:
—————————–
2) Here Comes the Boom
score: 0.7786835148361213
Hit Locations:
campo:título
término:boom
fragmento:
—————————–
3) Mira quién habla también
puntuación: 0,7047266634351538
Ubicaciones de los golpes:
campo:título
término:mirada
fragmento:
—————————–
4) Mira quién habla
puntuación: 0,7047266634351538
Ubicaciones de los golpes:
campo:título
término:aspecto
fragmento:
—————————–
5) La ladrona de libros
puntuación: 0,52288117537184
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
6) El libro de Eli
puntuación: 0,52288117537184
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
|
Ahora, la película llamada «Hook» es el primer resultado de la búsqueda, que podría no ser exactamente lo que el usuario espera en una búsqueda de «Book».
Cómo minimizar los falsos positivos durante las búsquedas difusas
En un mundo ideal, los usuarios nunca cometerían ningún error tipográfico al buscar algo. Sin embargo, ese no es el mundo en el que vivimos, y si quieres que tus usuarios tengan una experiencia agradable, tienes que manejar al menos una distancia de edición de 1. Por lo tanto, la verdadera pregunta es: ¿Cómo podemos hacer coincidencias de cadenas difusas minimizando la pérdida de relevancia?
Podemos aprovechar una característica de la mayoría de los marcos de los motores de búsqueda: Una coincidencia con una distancia de edición más baja suele tener una puntuación más alta. Esa característica nos permite combinar esas dos consultas con diferentes niveles de fuzziness en una sola:
|
1
2
3
4
5
6
7
8
|
String indexName = «movies_index»;
String word = «Libro»;
MatchQuery titleFuzzy = SearchQuery.match(word).fuzziness(1).field(«title»);
MatchQuery titleSimple = SearchQuery.match(word).field(«title»);
DisjunctionQuery ftsQuery = SearchQuery.disjuncts(titleSimple, titleFuzzy);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, ftsQuery).highlight().limit(20)); printResults(result);
|
Aquí está el resultado de la consulta difusa anterior:
|
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) La ladrona de libros
puntuación: 2.398890092610849
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
campo:título
término:libro
fragmento:
—————————–
2) El libro de Eli
puntuación: 2,398890092610849
Ubicaciones de golpe:
campo:título
término:libro
fragmento:
—————————–
campo:título
término:libro
fragmento:
—————————–
3) El libro de la vida
puntuación: 2,398890092610849
Ubicaciones de golpe:
campo:título
término:libro
fragmento:
—————————–
campo:título
término:libro
fragmento:
—————————–
4) Libro negro
puntuación: 2,398890092610849
Ubicaciones de golpe:
campo:título
término:libro
fragmento:
—————————–
campo:título
término:libro
fragmento:
—————————–
5) El libro de la selva
puntuación: 2,398890092610849
Ubicaciones de golpe:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) El libro de la selva 2
puntuación: 1,958685557004688
Ubicaciones de golpe:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
score: 1.6962714808368062
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: El libro del amor
puntuación: 1,517191317611584
Ubicaciones de éxito:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
score: 0.5052232518679681
Hit Locations:
campo:título
término:gancho
fragmento:
—————————–
10) Here Comes the Boom
puntuación: 0.357246781294941
Ubicaciones de los golpes:
campo:título
término:árbol
fragmento:
—————————–
11) Mira quién habla también
puntuación: 0,32331663301992025
Ubicaciones de los golpes:
campo:título
término:aspecto
fragmento:
—————————–
12) Mira quién habla
puntuación: 0,32331663301992025
Ubicaciones de los golpes:
campo:título
término:aspecto
fragmento:
—————————–
|
Como puede ver, este resultado se acerca mucho más a lo que el usuario podría esperar. Tenga en cuenta que ahora estamos utilizando una clase llamada DisjunctionQuery, las disyunciones son un equivalente al operador «OR» en SQL.
¿Qué más podríamos mejorar para reducir el efecto secundario negativo de un algoritmo de coincidencia difusa? Volvamos a analizar nuestro problema para entender si necesita más mejoras:
Ya sabemos que las búsquedas difusas pueden producir algunos resultados inesperados (por ejemplo, Libro -> Mirada, Gancho). Sin embargo, una búsqueda de un solo término suele ser una consulta terrible, ya que apenas nos da una pista de lo que el usuario intenta conseguir exactamente.
Incluso Google, que tiene posiblemente uno de los algoritmos de búsqueda difusa más desarrollados en uso, no sabe exactamente lo que estoy buscando cuando busco «mesa»:
Entonces, ¿cuál es la longitud media de las palabras clave en una consulta de búsqueda? Para responder a esta pregunta, voy a mostrar un gráfico de la presentación de Rand Fishkin de 2016. (Es uno de los gurús más famosos en el mundo del SEO)
Según el gráfico anterior, el ~80% de las consultas de búsqueda tienen 2 o más palabras clave, así que vamos a intentar buscar la película «Black Book» utilizando la borrosidad 1:
|
1
2
3
4
5
6
|
String indexName = «movies_index»;
MatchQuery query = SearchQuery.match(«Black Book»).field(«title»).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
Resultado:
|
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) Puntuación del Libro Negro
: 0.6946442424065404
Ubicaciones de los golpes:
campo:título
término:libro
fragmento:
—————————–
field:title
term:black
fragment:
—————————–
2) Gancho
puntuación: 0,40139742528039857
Ubicaciones de golpe:
campo:título
término:gancho
fragmento:
—————————–
3) Ataque al bloque
puntuación: 0,2838308365090324
Ubicaciones de golpe:
campo:título
término:bloque
fragmento:
—————————–
4) Here Comes the Boom
score: 0.2838308365090324
Hit Locations:
campo:título
término:boom
fragmento:
—————————–
5) Mira quién habla también
puntuación: 0,25687349813115684
Ubicaciones del golpe:
campo:título
término:mirada
fragmento:
—————————–
6) Mira quién habla
puntuación: 0,256873413115684
Ubicaciones de aciertos:
campo:título
término:mirada
fragmento:
—————————–
7) Grosse Pointe Blank
puntuación: 0.2317469073782136
Hit Locations:
campo:título
término:blanco
fragmento:
—————————–
8) La ladrona de libros
puntuación: 0,19059065534780495
Ubicaciones de golpe:
campo:título
término:libro
fragmento:
—————————–
9) El libro de Eli
puntuación: 0,19059065534780495
Ubicaciones de los aciertos:
campo:título
término:libro
fragmento:
—————————–
10) El libro de la vida
puntuación: 0,19059065534780495
Ubicaciones de golpe:
campo:título
término:libro
fragmento:
—————————–
11) El libro de la selva
puntuación: 0,19059065534780495
Hit Locations:
campo:título
término:libro
fragmento:
—————————–
12) Back to the Future
score: 0.17061000968368
Hit Locations:
campo:título
término:regreso
fragmento:
—————————–
|
No está mal. Tenemos la película que buscábamos como primer resultado. Sin embargo, una consulta de disyunción todavía traería un mejor conjunto de resultados.
Pero aún así, parece que tenemos una nueva propiedad agradable aquí; el efecto secundario de la coincidencia de la borrosidad disminuye ligeramente a medida que el número de palabras clave aumenta. Una búsqueda de «Black Book» con fuzziness 1 todavía puede traer resultados como back look o lack cook (algunas combinaciones con distancia de edición 1), pero es poco probable que sean títulos de películas reales.
Una búsqueda de «libro eli» con fuzziness 2 todavía lo traería como el tercer resultado:
|
1
2
3
4
5
6
|
String indexName = «movies_index»;
MatchQuery query = SearchQuery.match(«libro eli»).field(«título»).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
puntuación: 0.030723793900031805
Ubicaciones de los golpes:
campo:título
término:madera
fragmento:
—————————–
field:title
term:ed
fragment:
—————————–
2) Hombre de Tai Chi
puntuación: 0,0271042761982626
Ubicaciones de los golpes:
campo:título
término:chi
fragmento:
—————————–
field:title
term:tai
fragment:
—————————–
3) El libro de Eli
puntuación: 0,02608335441670756
Ubicaciones de golpe:
campo:título
término:eli
fragmento:
—————————–
field:title
term:book
fragment:
—————————–
4) La buena mentira
puntuación: 0,02439822770591834
Ubicaciones de los golpes:
campo:título
término:mentira
fragmento:
—————————–
field:title
term:good
fragment:
—————————–
|
Sin embargo, como la palabra inglesa media tiene 5 letras, NO recomendaría usar una distancia de edición mayor de 2 a no ser que el usuario busque palabras largas y fáciles de escribir mal, como «Schwarzenegger» por ejemplo (al menos para los no alemanes o no austriacos).
Conclusión
En este artículo, hemos hablado de la concordancia difusa y de cómo superar su principal efecto secundario sin estropear su relevancia. Eso sí, la concordancia difusa es sólo una de las muchas características que deberías aprovechar al implementar una búsqueda relevante y fácil de usar. En esta serie vamos a hablar de algunas de ellas: N-Gramas, Stopwords, Steeming, Shingle, Elision. Etc.
Consulta también la Parte 1 y la Parte 2 de esta serie.
Mientras tanto, si tienes alguna pregunta, tuitéame en @deniswsrosa.
Autor
- Denis Rosa, Developer Advocate, Couchbase –
