Cómo usar búsquedas difusas en Elasticsearch

Introducción

Buscar en lenguaje natural es intrínsecamente impreciso. Como las computadoras no pueden comprender el lenguaje natural, existen múltiples enfoques para la búsqueda, cada uno con sus ventajas y desventajas. Lucene, la tecnología que sustenta Elasticsearch, es una navaja suiza compuesta por muchas herramientas de procesamiento de texto. Cada herramienta es una heurística, un atajo algorítmico en lugar de una verdadera comprensión lingüística. Algunas de estas herramientas, como el stemmer Snowball y el analizador fonético Metaphone, son bastante sofisticadas. Estas herramientas imitan respectivamente los aspectos gramaticales y fonéticos de la comprensión del lenguaje. Otras herramientas son muy básicas, como el tipo de consulta prefijo, que simplemente coincide con las letras iniciales de las palabras. Las consultas difusas se sitúan en un punto intermedio de este arsenal en cuanto a sofisticación; encuentran palabras que requieren como máximo un cierto número de modificaciones de caracteres, conocidas como "ediciones", para coincidir con la consulta. Por ejemplo, una búsqueda difusa de "ax" coincidiría con la palabra "axe", ya que solo se requiere una eliminación, la de la "e", para que ambas palabras coincidan.

Una coincidencia difusa simple

Las consultas difusas pueden realizarse fácilmente mediante argumentos adicionales al tipo de consulta de coincidencia, como se muestra en el ejemplo a continuación. En el ejemplo, la petición final, una búsqueda de "vaacuum", que tiene una A extra, debería seguir mostrando el producto "Vacuum". El argumento fuzziness especifica que los resultados coinciden con una distancia máxima de edición de 2. Cabe señalar que fuzziness solo debe usarse con valores 1 y 2, lo que significa que se permiten un máximo de 2 ediciones entre la consulta y un término en un documento. Diferencias mayores son mucho más costosas de calcular eficientemente y no son procesadas por Lucene. La documentación oficial aún menciona valores flotantes para fuzziness, como 0.5, pero estos valores están obsoletos y son más difíciles de interpretar.

# Crear el índice
PUT /fuzzy_products
# Crear el mapeo del producto
PUT /fuzzy_products/product/_mapping
{
  "product": {
    "properties": {
      "name": {
        "type": "string",
        "analyzer": "simple"
      }
    }
  }
}
# Subir algunos documentos
PUT /fuzzy_products/product/1
{"name": "Vacuum Cleaner"}
PUT /fuzzy_products/product/2
{"name": "Turkey Baster"}
# ¡Realizar una búsqueda difusa!
POST /fuzzy_products/product/_search
{
  "query": {
    "match": {
      "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      }
    }
  }
}

Determinación de la distancia de edición

La métrica utilizada por las consultas difusas para determinar una coincidencia es la fórmula de la distancia de Damerau-Levenshtein. En pocas palabras, la distancia de Damerau-Levenshtein entre dos fragmentos de texto es el número de inserciones, eliminaciones, sustituciones y transposiciones necesarias para que una cadena coincida con la otra. Por ejemplo, la distancia de Levenshtein entre las palabras "ax" y "axe" es 1 debido a la única eliminación requerida.

La fórmula de la distancia de Damerau-Levenshtein es una modificación de la fórmula clásica de la distancia de Levenshtein, que la altera añadiendo la transposición como operación válida. Ambas fórmulas son compatibles, siendo la de Damerau-Levenshtein la predeterminada, y la clásica de Levenshtein seleccionable configurando transpositions en false en la consulta. La utilidad de las transposiciones puede observarse al comparar las cadenas "aex" y "axe". Usando la fórmula clásica, "aex" está a dos ediciones de distancia; la "e" debe eliminarse, tras lo cual se inserta una nueva "e" en el lugar adecuado, mientras que en Damerau-Levenshtein basta con una sola operación, intercambiando la "e" y la "x". Esto muestra por qué Damerau-Levenshtein tiene más sentido intuitivo en la mayoría de los casos.

Al tratar con búsquedas difusas, es vital entender que en Elasticsearch el texto primero pasa por un analizador antes de estar disponible para búsqueda. Cuando los datos se indexan, se procesan en lo que se conoce como "términos", las unidades realmente buscables en la base de datos. Son los términos analizados (explicados en Elasticsearch desde abajo hacia arriba), no los documentos almacenados reales, los que se buscan. Esto significa que, al realizar consultas difusas, el texto de la consulta puede compararse con un valor de término inesperado como resultado del análisis, lo que a veces puede dar lugar a resultados confusos. También significa que si los sinónimos están habilitados en un campo, los sinónimos pueden coincidir, incluso si esa palabra no aparece en el texto fuente. Por ejemplo, si se usara una consulta difusa sobre un campo analizado por ngrams, los resultados probablemente serían extraños, ya que los ngrams dividen las palabras en muchas combinaciones pequeñas de letras, muchas de las cuales están a solo una o dos ediciones de distancia, aunque las palabras reales involucradas sean bastante diferentes. Esto también significa que, si se usa un analizador Snowball, una búsqueda difusa de "running" se reducirá a "run", pero no coincidirá con la palabra mal escrita "runninga", que se mantiene como "runninga", porque "run" está a más de 2 ediciones de "runninga". Esto puede causar confusión, y por esta razón, a menudo tiene sentido usar solo el analizador simple en texto destinado a consultas difusas, posiblemente deshabilitando también los sinónimos. Para aclarar esto, a continuación se muestra un diagrama que ilustra una consulta difusa ejecutándose contra un documento analizado con Snowball.

Los diferentes tipos de búsquedas difusas

Elasticsearch soporta varios tipos de búsqueda difusa y las diferencias pueden resultar confusas. La lista que sigue intenta desambiguar estos distintos tipos.

• Consulta match con la opción fuzziness : agregar el parámetro fuzziness a una consulta match convierte una consulta simple en una difusa. Analiza el texto de la consulta antes de realizar la búsqueda.
• Consulta fuzzy : el tipo de consulta fuzzy de Elasticsearch generalmente debe evitarse. Funciona como una consulta de término y no analiza el texto de la consulta primero.
• fuzzy_like_this/fuzzy_like_this_field: una consulta more_like_this que soporta fuzziness y tiene un algoritmo de puntuación ajustado que maneja mejor las características de los resultados emparejados con fuzziness.*
• Sugerentes: los sugerentes no son un tipo de consulta real, sino un tipo de operación separada (construida internamente sobre consultas difusas) que puede ejecutarse junto a una consulta o de forma independiente. Son ideales para la funcionalidad de "¿querías decir?".

Una consulta match con el parámetro fuzziness es quizás la más versátil de las consultas difusas. El tipo de consulta fuzzy soporta el mismo comportamiento, excepto que no permite análisis del texto de la consulta. Además, el tipo de consulta fuzzy es un subconjunto de la funcionalidad de una consulta match, lo que la hace más confusa que útil.

Las consultas fuzzy_like_this, o FLT, son útiles para proporcionar recomendaciones basadas en un gran fragmento de texto fuente que puede contener errores ortográficos u otras inexactitudes separadas por distancia de edición. Existen dos consultas en esta categoría: fuzzy_like_this y fuzzy_like_this_field, que ofrecen la misma funcionalidad, siendo esta última la que simplifica la sintaxis para el caso en que solo se use un campo. Estas consultas toman un parámetro like_text, que consiste en un gran fragmento de texto, por ejemplo, el cuerpo de un artículo, e intentan encontrar documentos "similares" a ese. El texto del artículo se analiza y los términos de consulta se ponderan según su frecuencia en like_text con ajustes especiales (desactivando el factor de coordinación, IDF basado en el texto fuente) para combinar los distintos términos. Las consultas FLT funcionan mejor en casos donde el corpus contiene un gran número de errores ortográficos; de lo contrario, una consulta more_like_this estándar tendrá mejor rendimiento. Más detalles se pueden encontrar en la documentación oficial de Fuzzy More Like This.

Los sugerentes son fantásticos en el caso de que un usuario escriba "New Yrok", para una búsqueda, cuando en realidad quería escribir "New York". Las aplicaciones pueden usar sugerentes para mostrar una caja de "¿querías decir?" en la interfaz, recomendando una posible corrección. Ten en cuenta que para el caso específico de búsqueda predictiva, la Completion API ofrece mejor rendimiento dada la naturaleza sensible a la latencia de las búsquedas predictivas. Más información sobre sugerentes está disponible en la página de búsqueda de sugerencias.

Consideraciones de rendimiento

Aunque la implementación de la distancia Levenshtein de Lucene es de última generación y bastante rápida, sigue siendo mucho más lenta que una consulta match simple. El tiempo de ejecución de la consulta crece con el número de términos únicos en el índice. Es decir, al realizar una búsqueda difusa, el criterio principal no es cuántos documentos se devolverán, sino cuántos términos únicos hay en el cluster para los campos que se están buscando. Si hay 100 documentos con 10 000 palabras únicas cada uno, buscar en ese índice será más lento que buscar en 10 000 documentos donde el campo que se busca solo tiene 100 palabras únicas.

La razón principal de esta lentitud es que una consulta match estándar puede comprobar rápidamente el índice de términos, una estructura de datos interna usada por Lucene, para encontrar una coincidencia y encontrar documentos extremadamente rápido usando búsqueda binaria. Este proceso es rápido incluso para diccionarios grandes, ya que las búsquedas binarias escalan bien. Las consultas difusas, en cambio, usan un algoritmo más avanzado que involucra un DFA que debe procesar un gran número de términos. Procesar el número mucho mayor de términos requerido para una búsqueda difusa siempre es más lento que una simple búsqueda binaria. Por ejemplo, realizar una búsqueda difusa en el conjunto de datos de Wikipedia en inglés tarda aproximadamente 320 ms para el término "historia" dado un min_similarity de 2, mientras que una búsqueda match simple para el mismo término dura apenas 35 ms, una diferencia de un orden de magnitud. Dado un min_similarity de 1, el tiempo de búsqueda es solo de 150 ms. Cabe señalar que estas pruebas no se realizaron de manera estadísticamente sólida, y estos tiempos pueden verse afectados significativamente por factores particulares de cada aplicación. El conjunto de datos de Wikipedia, en particular, tiene muchos más términos que muchos casos de uso comunes.

El rendimiento puede mejorar significativamente exigiendo que las coincidencias tengan prefijos exactos con la consulta. Esto acorta significativamente el espacio de búsqueda a costa de no encontrar palabras con un error ortográfico al principio. Cuanto mayor es la longitud del prefijo, más rápido es el aumento de velocidad. Especificar un prefix_length de 1 reduce la consulta de 320 ms mencionada anteriormente a apenas 104 ms. Aumentar este número genera más ganancias de velocidad. Generalmente, es recomendable requerir un prefijo para sets de datos con un gran número de términos o el rendimiento será deficiente, a menudo en decenas de milisegundos.

La configuración max_expansions, que define el número máximo de términos que la consulta difusa puede coincidir antes de detener la búsqueda, también puede tener efectos dramáticos en el rendimiento de una consulta difusa. Sin embargo, reducir los términos de consulta tiene un efecto negativo, ya que algunos resultados válidos pueden no encontrarse debido a la terminación temprana de la consulta. Es importante entender que el límite max_expansions funciona a nivel de shard, lo que significa que incluso si se establece en 1, varios términos pueden coincidir, todos procedentes de diferentes shards. Este comportamiento puede hacer que parezca que max_expansions no está en efecto, por lo que contar términos únicos que aparecen no es una forma válida de determinar si max_expansions está funcionando.

Alternativas a la coincidencia difusa

La coincidencia difusa no siempre es la herramienta adecuada para el trabajo; muchas veces se pueden encontrar coincidencias imprecisas mediante otras técnicas. El plugin de análisis fonético contiene varias herramientas fascinantes para aproximar coincidencias, como el analizador Metaphone, que encuentra palabras que suenan similares a otras. Por ejemplo, si se requiere que palabras como "run" y "ran" se consideren equivalentes, un analizador inteligente como Snowball es preferible. Alternativamente, para corregir errores ortográficos, el análisis N-gram, tal como se describe en este breve tutorial, puede funcionar mucho más rápido en el momento de la consulta, dependiendo del conjunto de datos. Sin embargo, los N-grams tienen el costo de un uso adicional de almacenamiento y memoria, un poco más de procesamiento en tiempo de índice y una larga cola de falsos positivos tras buenas coincidencias.

Más lecturas

• Para un análisis más profundo del rendimiento de las consultas difusas en Elasticsearch, Mike McCandless, colaborador principal de Lucene, escribió una entrada de blog sobre el tema. También hay un video, Finite State Automata in Lucene and Solr, de una presentación de Dawid Weiss que cubre Levenshtein y otros autómatas en Lucene.
• Si quieres saber más sobre Levenshtein Automata, Nick Johnson tiene una gran entrada titulada Damn Cool Algorithms: Levenshtein Automata.