Qué es el emparejamiento difuso y cómo utilizarlo correctamente

¿Se ha preguntado alguna vez qué es la concordancia difusa? La concordancia difusa permite identificar coincidencias no exactas del elemento buscado. Es la piedra angular de muchos 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 cabría esperar, existen muchos algoritmos de búsqueda difusa que pueden utilizarse para el texto, pero prácticamente todos los marcos de los motores de búsqueda (incluido bleve) utilizan principalmente la distancia Levenshtein para la coincidencia difusa de cadenas:

Distancia Levenshtein

También conocido como Editar Distanciaes el número de transformaciones (supresiones, inserciones o sustituciones) necesarias para transformar una cadena de origen en la de destino. Para un ejemplo de búsqueda difusa, si el término de destino es "libro" y el de 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.Editar Distancia 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 muchos otros aquí).

Además, algunos marcos también admiten la distancia Damerau-Levenshtein:

Distancia Damerau-Levenshtein

Es una extensión de la distancia Levenshtein, que permite una operación extra: Transposición de dos caracteres adyacentes:

Ex: De TSAR a STAR

Distancia Damerau-Levenshtein = 1 (La conmutación de las posiciones S y T sólo cuesta una operación)

Distancia Levenshtein = 2  (Sustituir S por T y T por S)

Correspondencia difusa y relevancia

La concordancia difusa tiene un gran efecto secundario: estropea la relevancia. Aunque Damerau-Levenshtein es un algoritmo de concordancia difusa que tiene en cuenta la mayoría de los errores ortográficos comunes de los usuarios, también puede incluir un número significativo de falsos positivossobre todo cuando utilizamos una lengua con un media de sólo 5 letras por palabracomo el inglés. Por eso, la mayoría de los motores de búsqueda prefieren utilizar la distancia Levenshtein. Veamos un ejemplo real de concordancia difusa:

En primer lugar, 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, busquemos películas con "Libro"en el título. Un código sencillo sería el siguiente:

El código anterior dará los siguientes resultados:

Por defecto, los resultados no distinguen entre mayúsculas y minúsculas, pero puede cambiar fácilmente este comportamiento creando nuevos índices con diferentes analizadores.

Ahora, añadamos una capacidad de coincidencia difusa a nuestra consulta estableciendo la difusidad en 1 (distancia Levenshtein 1), lo que significa que "Libro" y "mira" tendrá la misma relevancia.

Y aquí está el resultado de la búsqueda difusa:

Ahora, la película llamada "Gancho" es el primer resultado de la búsqueda, que puede no ser exactamente lo que el usuario espera en una búsqueda de "Reserve".

Cómo minimizar los falsos positivos en las búsquedas difusas

 En un mundo ideal, los usuarios nunca cometerían errores tipográficos mientras buscan 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 coincidir 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 menor suele tener una puntuación más alta. Esa característica nos permite combinar en una sola esas dos consultas con distintos niveles de imprecisión:

He aquí el resultado de la consulta difusa anterior:

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 a la clase "O"en SQL.

¿Qué más podríamos mejorar para reducir el efecto secundario negativo de un algoritmo de emparejamiento difuso? Analicemos de nuevo nuestro problema para saber si necesita más mejoras:

Ya sabemos que las búsquedas difusas pueden producir algunos resultados inesperados (por ejemplo, Book -> Look, Hook). 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.

Ni siquiera Google, que cuenta con uno de los algoritmos de búsqueda difusa más desarrollados que existen, sabe exactamente lo que busco cuando busco "tabla":

Entonces, ¿cuál es la longitud media de las palabras clave en una consulta de búsqueda? Para responder a esta pregunta, mostraré un gráfico de Presentación de Rand Fishkin en 2016. (Es uno de los gurús más famosos del mundo SEO)

Según el gráfico anterior, ~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 fuzziness 1:

Resultado:

No está mal. Obtuvimos la película que buscábamos como primer resultado. Sin embargo, una consulta disyuntiva nos daría un conjunto de resultados mejor.

Pero aún así, parece que tenemos una nueva propiedad agradable aquí; el efecto secundario de la concordancia difusa disminuye ligeramente a medida que aumenta el número de palabras clave. Una búsqueda de "Libro negro" con desenfoque 1 todavía puede traer resultados como la mirada hacia atrás o la falta de cocinero (algunas combinaciones con la distancia de edición 1), pero estos son poco probable que sean títulos de películas reales.

Una búsqueda de "libro eli" con borrosidad 2 aún lo traería como tercer resultado:

Sin embargo, como la palabra inglesa media tiene 5 letras, me gustaría NO recomiendan utilizar una distancia de edición superior a 2 a menos 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, hablamos de la concordancia difusa y de cómo superar su principal efecto secundario sin estropear su relevancia. Sin embargo, la concordancia difusa es sólo una de las muchas características que debe aprovechar al implementar una búsqueda relevante y fácil de usar. En esta serie hablaremos de algunas de ellas: N-Gramas, Stopwords, Steeming, Shingle, Elisión. Etc.

Consulte también el Parte 1 y Parte 2 de esta serie.

Mientras tanto, si tienes alguna pregunta, envíame un tweet a @deniswsrosa.