La búsqueda de texto completo es una de esas herramientas que usamos casi todos los días cuando buscamos información en Internet. La búsqueda de texto completo (FTS) es un método de búsqueda de texto en una colección de documentos. El documento puede vincularse a una página web, artículo de periódico, mensaje de correo electrónico o cualquier texto estructurado.

Hoy vamos a escribir nuestro propio motor FTS. Al final de este artículo, podrá buscar millones de documentos en menos de un milisegundo. Comenzaremos con consultas de búsqueda simples como "Devolver todos los documentos con cat" y luego ampliaremos el motor para admitir consultas lógicas más complejas.

Nota: El motor de búsqueda de texto completo más famoso es Lucene (así como Elasticsearch y Solr construido sobre él).

¿Por qué necesitas FTS?

Antes de escribir cualquier código, puede preguntar: "¿No podría simplemente usar grep o un bucle que verifique la palabra de búsqueda en cada documento?" Sí tu puedes. Pero esa no siempre es la mejor idea.

Alojamiento

Buscaremos fragmentos de anotaciones en Wikipedia en inglés. El último volcado está disponible en dumps.wikimedia.org . A día de hoy, el tamaño del archivo después de descomprimirlo es de 913 MB. El archivo XML contiene más de 600 mil documentos.

Documento de muestra:

<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>

Subiendo documentos

Primero, necesita cargar todos los documentos del volcado usando un paquete integrado muy útil encoding/xml:

import (
    "encoding/xml"
    "os"
)

type document struct {
    Title string `xml:"title"`
    URL   string `xml:"url"`
    Text  string `xml:"abstract"`
    ID    int
}

func loadDocuments(path string) ([]document, error) {
    f, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer f.Close()

    dec := xml.NewDecoder(f)
    dump := struct {
        Documents []document `xml:"doc"`
    }{}
    if err := dec.Decode(&dump); err != nil {
        return nil, err
    }

    docs := dump.Documents
    for i := range docs {
        docs[i].ID = i
    }
    return docs, nil
}

A cada documento se le asigna una identificación única. Para simplificar, al primer documento cargado se le asigna ID = 0, al segundo ID = 1 y así sucesivamente.

Primer intento

Búsqueda de contenido

Ahora que tenemos todos los documentos cargados en la memoria, intentemos encontrar aquellos que mencionen gatos. Primero, revisemos todos los documentos y verifiquemos si hay una subcadena cat:

func search(docs []document, term string) []document {
    var r []document
    for _, doc := range docs {
        if strings.Contains(doc.Text, term) {
            r = append(r, doc)
        }
    }
    return r
}

En mi computadora portátil, la búsqueda toma 103 ms, no está mal. Si un punto de comprobar varios documentos de la cuestión, podemos ver que la función da satisfacción en la palabra oruga y categoría , pero no al gato con una letra mayúscula C . Esto no es exactamente lo que estamos buscando.

Hay dos cosas que corregir antes de continuar:

Haga que la búsqueda no distinga entre mayúsculas y minúsculas (de modo que la salida también incluya Cat ).
Considere los límites de las palabras, no las subcadenas (para que no haya palabras como oruga y comunicación en la salida ).

Buscar con expresiones regulares

Una solución obvia que resuelve ambos problemas son las expresiones regulares .

En este caso, necesitamos (?i)\bcat\b:

(?i) significa que la expresión regular no distingue entre mayúsculas y minúsculas
\b indica correspondencia con los límites de las palabras (un lugar donde hay un carácter en un lado y no en el otro)

Pero ahora la búsqueda tomó más de dos segundos. Como puede ver, el sistema comenzó a ralentizarse incluso en un cuerpo modesto de 600 mil documentos. Si bien este enfoque es fácil de implementar, no se escala muy bien. A medida que crece el conjunto de datos, es necesario escanear más y más documentos. La complejidad temporal de este algoritmo es lineal, es decir, el número de documentos a escanear es igual al número total de documentos. Si tuviéramos 6 millones de documentos en lugar de 600 mil, la búsqueda tomaría 20 segundos. Tendremos que pensar en algo mejor.

Índice invertido

Para acelerar las consultas de búsqueda, procesaremos previamente el texto y crearemos un índice.

El núcleo de FTS es una estructura de datos llamada índice invertido . Vincula cada palabra a documentos que contienen esa palabra.

Ejemplo:

documents = {
    1: "a donut on a glass plate",
    2: "only the donut",
    3: "listen to the drum machine",
}

index = {
    "a": [1],
    "donut": [1, 2],
    "on": [1],
    "glass": [1],
    "plate": [1],
    "only": [2],
    "the": [2, 3],
    "listen": [3],
    "to": [3],
    "drum": [3],
    "machine": [3],
}

A continuación se muestra un ejemplo real de un índice invertido. Este es un índice en un libro donde el término va seguido de números de página:

Análisis de texto

Antes de comenzar a construir el índice, debe dividir el texto de origen en una lista de palabras (tokens) adecuadas para indexar y buscar.

El analizador de texto consta de un tokenizador y varios filtros.

Tokenizer

El tokenizador es el primer paso en el análisis de texto. Su tarea es convertir el texto en una lista de tokens. Nuestra implementación divide el texto en los límites de las palabras y elimina los signos de puntuación:

func tokenize(text string) []string {
    return strings.FieldsFunc(text, func(r rune) bool {
        // Split on any character that is not a letter or a number.
        return !unicode.IsLetter(r) && !unicode.IsNumber(r)
    })
}

> tokenize("A donut on a glass plate. Only the donuts.")

["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]

Filtros

En la mayoría de los casos, simplemente convertir texto en una lista de tokens no es suficiente. Se requerirá una normalización adicional para facilitar la indexación y la búsqueda.

Minúscula

Para que la búsqueda no distinga entre mayúsculas y minúsculas, el filtro de minúsculas convierte los tokens en minúsculas. Las palabras cAt , Cat y caT se normalizan a la forma cat . Posteriormente, al referirnos al índice, también normalizamos las consultas de búsqueda a minúsculas, de modo que la consulta de búsqueda cAt encuentre la palabra Cat .

Eliminando palabras comunes

Casi todos los textos en inglés contienen palabras comunes como a , I , The o be . Se llaman palabras vacías y están presentes en casi todos los documentos, por lo que deben eliminarse.

No hay una lista de palabras irrelevantes "oficial". Eliminemos los 10 primeros en la lista OEC . Siéntase libre de complementarlo:

var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
    "a": {}, "and": {}, "be": {}, "have": {}, "i": {},
    "in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}

func stopwordFilter(tokens []string) []string {
    r := make([]string, 0, len(tokens))
    for _, token := range tokens {
        if _, ok := stopwords[token]; !ok {
            r = append(r, token)
        }
    }
    return r
}

> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

["donut", "on", "glass", "plate", "only", "donuts"]

Derivado

Debido a las reglas gramaticales, existen diferentes formas de palabras en los documentos. La derivación los reduce a su forma básica. Por ejemplo, la pesca , la pesca y el pescador se reducen a la forma principal de pez .

La implementación de la derivación no es una tarea trivial y no se trata en este artículo. Tomemos uno de los módulos existentes :

import snowballeng "github.com/kljensen/snowball/english"

func stemmerFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = snowballeng.Stem(token, false)
    }
    return r
}

> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

["donut", "on", "glass", "plate", "only", "donut"]

Nota: los Stemmers no siempre funcionan correctamente. Por ejemplo, algunos pueden acortar aerolínea a avión de línea .

Montaje del analizador

func analyze(text string) []string {
    tokens := tokenize(text)
    tokens = lowercaseFilter(tokens)
    tokens = stopwordFilter(tokens)
    tokens = stemmerFilter(tokens)
    return tokens
}

El tokenizador y los filtros convierten las oraciones en una lista de tokens:

> analyze("A donut on a glass plate. Only the donuts.")

["donut", "on", "glass", "plate", "only", "donut"]

Los tokens están listos para indexarse.

Construyendo un índice

Volvamos al índice invertido. Hace coincidir cada palabra con los ID de los documentos. El tipo de datos incorporado funciona bien para almacenar un mapa (mostrar) map. La clave será un token (cadena) y el valor será una lista de ID de documentos:

type index map[string][]int

En el proceso de construcción del índice, los documentos se analizan y sus identificadores se agregan al mapa:

func (idx index) add(docs []document) {
    for _, doc := range docs {
        for _, token := range analyze(doc.Text) {
            ids := idx[token]
            if ids != nil && ids[len(ids)-1] == doc.ID {
                // Don't add same ID twice.
                continue
            }
            idx[token] = append(ids, doc.ID)
        }
    }
}

func main() {
    idx := make(index)
    idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
    idx.add([]document{{ID: 2, Text: "donut is a donut"}})
    fmt.Println(idx)
}

¡Todo está funcionando! Cada token en la pantalla se refiere a los ID de los documentos que contienen ese token:

map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]

Consultas

Para consultas al índice, aplicaremos el mismo tokenizador y filtros que usamos para indexar:

func (idx index) search(text string) [][]int {
    var r [][]int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            r = append(r, ids)
        }
    }
    return r
}

> idx.search("Small wild cat")

[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]

Y ahora, finalmente, podemos encontrar todos los documentos que mencionan gatos. ¡La búsqueda de 600 mil documentos tomó menos de un milisegundo (18 μs)!

Con un índice invertido, la complejidad temporal de una consulta de búsqueda es lineal con el número de tokens de búsqueda. En el ejemplo de consulta anterior, además de analizar el texto de entrada, solo se realizan tres búsquedas en el mapa.

Consultas lógicas

La solicitud anterior devolvió una lista de documentos no vinculados para cada token. Pero, por lo general, esperamos que la búsqueda de un pequeño gato salvaje devuelva una lista de resultados que contengan tanto pequeño , salvaje como gato . El siguiente paso es calcular la intersección entre las listas. Así, obtendremos una lista de documentos correspondientes a todos los tokens.

Afortunadamente, los ID de nuestro índice invertido se insertan en orden ascendente. Dado que los ID están ordenados, puede calcular la intersección entre las listas en tiempo lineal. La función intersectionitera a través de dos listas al mismo tiempo y recopila los identificadores que están presentes en ambas:

func intersection(a []int, b []int) []int {
    maxLen := len(a)
    if len(b) > maxLen {
        maxLen = len(b)
    }
    r := make([]int, 0, maxLen)
    var i, j int
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            i++
        } else if a[i] > b[j] {
            j++
        } else {
            r = append(r, a[i])
            i++
            j++
        }
    }
    return r
}

El actualizado searchanaliza el texto de solicitud dado, busca tokens y calcula la intersección dada entre las listas de ID:

func (idx index) search(text string) []int {
    var r []int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            if r == nil {
                r = ids
            } else {
                r = intersection(r, ids)
            }
        } else {
            // Token doesn't exist.
            return nil
        }
    }
    return r
}

El volcado de Wikipedia contiene solo dos documentos que contienen simultáneamente las palabras pequeño , salvaje y gato :

> idx.search("Small wild cat")

130764  The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692  Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.

¡La búsqueda funciona como se esperaba!

Por cierto, aprendí sobre los catopums por primera vez , aquí está uno de ellos:

conclusiones

Entonces, creamos un motor de búsqueda de texto completo. A pesar de su simplicidad, puede proporcionar una base sólida para proyectos más avanzados.

No he mencionado muchos aspectos que puedan mejorar significativamente el rendimiento y hacer que la búsqueda sea más conveniente. Aquí hay algunas ideas para mejoras adicionales:

Agregue operadores lógicos O y NO .
Almacenar índice en disco:
- Se necesita algún tiempo para restaurar el índice cada vez que se reinicia la aplicación.
- Es posible que los índices grandes no quepan en la memoria.
Experimente con formatos de datos optimizados para memoria y CPU para almacenar conjuntos de ID. Eche un vistazo a Roaring Bitmaps .
Indexación de varios campos del documento.
Ordene los resultados por relevancia.

Todo el código fuente se publica en GitHub .

Escribir un motor de búsqueda de texto completo en Go