Hoje vamos escrever nosso próprio motor FTS. Ao final deste artigo, ele será capaz de pesquisar milhões de documentos em menos de um milissegundo. Começaremos com consultas de pesquisa simples, como "Retornar todos os documentos com cat" e, em seguida, estender o mecanismo para oferecer suporte a consultas lógicas mais complexas.
Observação: o mecanismo de pesquisa de texto completo mais famoso é o Lucene (e também o Elasticsearch e o Solr foi construído em cima dele).
Por que você precisa de FTS
Antes de escrever qualquer código, você pode perguntar: "Você não poderia simplesmente usar grep ou um loop que verifica cada documento em busca da palavra de pesquisa?" Sim você pode. Mas nem sempre é a melhor ideia.
Habitação
Procuraremos fragmentos de anotações da Wikipedia em inglês. O dump mais recente está disponível em dumps.wikimedia.org . A partir de hoje, o tamanho do arquivo após a descompactação é de 913 MB. O arquivo XML contém mais de 600 mil documentos.
Documento de amostra:
<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>Carregando documentos
Primeiro, você precisa carregar todos os documentos do dump usando um pacote integrado muito ú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
}Cada documento recebe um ID exclusivo. Para simplificar, o primeiro documento carregado recebe ID = 0, o segundo ID = 1 e assim por diante.
Primeira tentativa
Pesquisa de conteúdo
Agora que temos todos os documentos carregados na memória, vamos tentar encontrar aqueles que mencionam gatos. Primeiro, vamos examinar todos os documentos e verificar se há uma substring
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
}No meu laptop, a pesquisa leva 103 ms - nada mal. Se verificarmos vários documentos da edição no local, podemos ver que a função dá satisfação na palavra lagarta e categoria , mas não em Gato com C maiúsculo . Não é exatamente isso que procuramos.
Há duas coisas a corrigir antes de continuar:
- Torne a pesquisa sem distinção entre maiúsculas e minúsculas (para que a saída inclua Cat também )
- Considere os limites das palavras, não substrings (para que não haja palavras como lagarta e comunicação na saída ).
Pesquisa com expressões regulares
Uma solução óbvia que resolve os dois problemas são as expressões regulares .
Nesse caso, precisamos
(?i)\bcat\b:
(?i)significa que a regex não diferencia maiúsculas de minúsculas
\bindica a correspondência com os limites das palavras (um lugar onde há um caractere de um lado e não do outro)
Mas agora a busca demorava mais de dois segundos. Como você pode ver, o sistema começou a ficar lento mesmo em um modesto corpo de 600 mil documentos. Embora essa abordagem seja fácil de implementar, ela não se adapta muito bem. Conforme o conjunto de dados cresce, mais e mais documentos precisam ser digitalizados. A complexidade de tempo desse algoritmo é linear, ou seja, o número de documentos a serem digitalizados é igual ao número total de documentos. Se tivéssemos 6 milhões de documentos em vez de 600 mil, a busca demoraria 20 segundos. Teremos que inventar algo melhor.
Índice invertido
Para acelerar as consultas de pesquisa, iremos pré-processar o texto e construir um índice.
O núcleo do FTS é uma estrutura de dados chamada índice invertido . Ele vincula cada palavra a documentos que contêm essa palavra.
Exemplo:
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],
}Abaixo está um exemplo real de um índice invertido. Este é um índice em um livro onde o termo é seguido por números de página:
Análise de texto
Antes de começar a construir o índice, você precisa dividir o texto fonte em uma lista de palavras (tokens) adequadas para indexação e pesquisa.
O analisador de texto consiste em um tokenizer e vários filtros.
Tokenizer
O tokenizer é a primeira etapa na análise de texto. Sua tarefa é converter o texto em uma lista de tokens. Nossa implementação divide o texto nos limites das palavras e remove os sinais de pontuação:
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
Na maioria dos casos, simplesmente converter o texto em uma lista de tokens não é suficiente. Normalização adicional será necessária para facilitar a indexação e a pesquisa.
Minúsculas
Para tornar a pesquisa insensível a maiúsculas e minúsculas, o filtro de minúsculas converte tokens em minúsculas. As palavras cAt , Cat e caT são normalizadas para cat . Posteriormente, ao fazer referência ao índice, também normalizamos as consultas de pesquisa para letras minúsculas, para que a consulta de pesquisa cAt encontre a palavra Cat .
Removendo palavras comuns
Quase todo texto em inglês contém palavras comuns como a , I , The ou be . Eles são chamados de palavras irrelevantes e estão presentes em quase todos os documentos, portanto, devem ser removidos.
Não existe uma lista de palavras irrelevantes "oficial". Vamos eliminar os 10 primeiros da lista OEC . Sinta-se à vontade para complementá-lo:
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"]Stemming
Devido às regras gramaticais, existem diferentes formas de palavras nos documentos. O stemming os reduz à forma básica. Por exemplo, a pesca , pescado e Fisher todos se resumem a principal peixes forma .
A implementação de lematização não é uma tarefa trivial e não é abordada neste artigo. Vamos pegar um dos 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: os lematizadores nem sempre funcionam corretamente. Por exemplo, alguns podem encurtar a linha aérea para airlin .
Montagem do analisador
func analyze(text string) []string {
tokens := tokenize(text)
tokens = lowercaseFilter(tokens)
tokens = stopwordFilter(tokens)
tokens = stemmerFilter(tokens)
return tokens
}O tokenizer e os filtros convertem as frases em uma lista de tokens:
> analyze("A donut on a glass plate. Only the donuts.")
["donut", "on", "glass", "plate", "only", "donut"]Os tokens estão prontos para indexação.
Construindo um índice
Vamos voltar ao índice invertido. Ele combina cada palavra com IDs de documentos. O tipo de dados interno funciona bem para armazenar um mapa (exibição)
map. A chave será um token (string) e o valor será uma lista de IDs de documentos:
type index map[string][]intNo processo de construção do índice, os documentos são analisados e seus identificadores são adicionados ao 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)
}Tudo está funcionando! Cada token na tela se refere aos IDs dos documentos que contêm esse token:
map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]Inquéritos
Para consultas ao índice, aplicaremos o mesmo tokenizer e filtros que usamos para indexação:
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, ...]]E agora, finalmente, podemos encontrar todos os documentos que mencionam gatos. A pesquisa de 600 mil documentos levou menos de um milissegundo (18 μs)!
Com um índice invertido, a complexidade de tempo de uma consulta de pesquisa é linear com o número de tokens de pesquisa. No exemplo de consulta acima, além de analisar o texto de entrada, apenas três pesquisas de mapa são realizadas.
Consultas lógicas
A solicitação anterior retornou uma lista não vinculada de documentos para cada token. Mas nós geralmente esperam uma pesquisa para pequeno gato selvagem para retornar uma lista de resultados que contenham tanto pequena , selvagem e gato . A próxima etapa é calcular a interseção entre as listas. Assim, obteremos uma lista de documentos correspondentes a todos os tokens.
Felizmente, os IDs em nosso índice invertido são inseridos em ordem crescente. Uma vez que os IDs são classificados, você pode calcular a interseção entre as listas em tempo linear. A função
intersectionitera por meio de duas listas ao mesmo tempo e coleta os identificadores que estão presentes em 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
}O atualizado
searchanalisa o texto da solicitação fornecida, procura tokens e calcula a interseção dada entre as 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
}O despejo da Wikipedia contém apenas dois documentos que contêm simultaneamente as palavras pequeno , selvagem e 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.A pesquisa funciona conforme o esperado!
A propósito, eu aprendi sobre catopums , aqui está um deles:
conclusões
Então, fizemos um mecanismo de busca de texto completo. Apesar de sua simplicidade, pode fornecer uma base sólida para projetos mais avançados.
Não mencionei muitos aspectos que podem melhorar significativamente o desempenho e tornar a pesquisa mais conveniente. Aqui estão algumas idéias para melhorias adicionais:
- Adicione operadores lógicos OU e NÃO .
- Armazene o índice no disco:
- Leva algum tempo para restaurar o índice sempre que o aplicativo é reiniciado.
- Índices grandes podem não caber na memória.
- Leva algum tempo para restaurar o índice sempre que o aplicativo é reiniciado.
- Experimente formatos de dados otimizados para memória e CPU para armazenar conjuntos de ID. Dê uma olhada em Roaring Bitmaps .
- Indexando vários campos do documento.
- Classifique os resultados por relevância.
Todo o código-fonte é publicado no GitHub .