"Você quis dizer...” Como o Google corrige suas buscas?

Se você já errou uma digitação ao pesquisar algo no Google, com certeza já viu a mensagem: "Você quis dizer..." seguida da sugestão correta. Mas já parou para pensar como o Google faz essa correção automática? Como ele consegue identificar o erro e sugerir a palavra correta?

A resposta para isso está em um algoritmo matemático chamado Levenshtein Distance, que mede o quão "distantes" duas palavras estão em termos de edições necessárias para transformá-las uma na outra.

Neste artigo, vou explicar o que é o algoritmo de Distância de Levenshtein, como o Google o utiliza e compartilhar um exemplo de implementação em Golang.

O que o Google faz por baixo dos panos?

Por baixo do capô, o Google utiliza uma combinação de técnicas para corrigir buscas com erros de digitação. Uma dessas técnicas é o Levenshtein Distance, que é um algoritmo de comparação de strings. Ele calcula quantas edições (inserções, remoções ou substituições de caracteres) são necessárias para transformar uma palavra em outra.

Quando você digita uma palavra errada no Google, ele compara sua consulta com um enorme banco de dados de termos mais buscados e verifica quais palavras estão a uma pequena distância de edição daquela que você digitou. Se houver uma palavra popular com uma distância baixa, o Google sugere essa palavra para você.

Mas como exatamente esse algoritmo funciona?

O algoritmo de Levenshtein Distance

O Levenshtein Distance é um algoritmo criado em 1965 pelo matemático russo Vladimir Levenshtein. Ele foi desenvolvido para medir a diferença entre duas sequências de caracteres, determinando a quantidade mínima de edições necessárias para transformar uma string na outra.

As três operações permitidas são:

• Inserção de um caractere ("casa" → "casas").

• Remoção de um caractere ("casa" → "cas").

• Substituição de um caractere ("casa" → "cama").

A ideia é construir uma matriz onde cada célula representa o custo mínimo de edição entre prefixos das duas palavras.

Como o algoritmo funciona?

Imagine que queremos calcular a distância de edição entre as palavras "gato" e "rato".

Etapa 1: Criar uma matriz

Construímos uma matriz onde as linhas representam os caracteres da primeira palavra e as colunas representam os caracteres da segunda palavra.

Etapa 2: Preencher a matriz com os custos de edição

Cada célula da matriz armazena o custo mínimo necessário para transformar um prefixo da primeira palavra em um prefixo da segunda palavra. Esse custo é calculado com base em três operações possíveis:

• Inserção: Adicionar um caractere à palavra.

• Remoção: Remover um caractere da palavra.

• Substituição: Trocar um caractere por outro.

O valor de cada célula é determinado escolhendo a operação de menor custo entre essas três opções. Dessa forma, a matriz é preenchida gradualmente, refletindo o menor número de edições necessárias para converter uma string na outra.

Se quiser entender em detalhes como esse cálculo é feito, recomendo a página da Wikipedia sobre o algoritmo de Levenshtein, que explica cada etapa com exemplos e pseudocódigo. (Link aqui).

Etapa 3: Identificar a distância final

A célula de intersecção entra a linha e a coluna representa o custo de cada edição. Agora some os valores de cada edição e você terá o custo total. Esse valor indica quantas operações são necessárias para transformar a primeira palavra na segunda.

Por exemplo, para "gato" e "rato", a distância é 1, pois apenas uma substituição foi necessária.

Se tivermos "gato" e "sapo", a distância será maior porque serão necessárias mais operações para transformar uma palavra na outra.

A distância entre "gato" e "sapo" é 2, pois teremos que substituir "g" por "r" e "t" por "p".

Esse método é extremamente eficiente para comparação de palavras e é amplamente utilizado em sistemas que lidam com reconhecimento de padrões e correção de textos.

Fluxo da arquitetura

Agora chegamos à cereja do bolo: a parte da arquitetura. Quero deixar claro que este desenho foi elaborado após o estudo de artigos escritos por profissionais que trabalharam no Google e a leitura de dezenas de posts e fóruns sobre o tema (sim, eles existem, pode pesquisar no Google). Portanto, embora esta não seja exatamente a arquitetura utilizada pelo Google, ela contém todos os componentes necessários para implementar essa funcionalidade.

1. Entrada do usuário

O usuário digita: "como fazr, um ból de chcolate"

2. Pré-Processamento
Remove caracteres especiais e normaliza:

como fazr, um ból de chcolate → como fazr um bol de chcolate

3. Identificação de Erros

Identifica palavras não reconhecidas ("fazr", "bol", "chcolate") consultando um banco de palavras válidas. Ou seja, não encontrou no banco de dados, não é uma palavra válida.

4. Correção com Distância de Levenshtein

Para cada palavra desconhecida encontrada na etapa de Identificação de Erro, calcula-se a Distância de Levenshtein para palavras conhecidas e utiliza aquelas com as menores distâncias. Essa palavras conhecidas vem de uma base de dados como Redis ou ElasticSearch.

"fazr" → "fazer" (distância = 1)
"bol" → "bolo" (distância = 1)
"chcolate" → "chocolate" (distância = 1)

5. Reranking com Machine Learning

O que é Reranking?
Reranking é o processo de reorganizar e priorizar os resultados de uma busca ou sugestão com base em critérios específicos, garantindo que as opções mais relevantes apareçam primeiro. No contexto da correção de consultas no Google, o reranking ajuda a selecionar a melhor sugestão possível entre várias alternativas geradas na etapa anterior.

Após identificar possíveis correções, um modelo de Machine Learning classifica e seleciona a sugestão mais adequada com base nos seguintes critérios:

• Frequência da palavra: Termos mais populares no Google têm maior relevância.
• Correções validadas pelos usuários: O modelo aprende com sugestões aceitas no passado.
• Similaridade de contexto: A palavra sugerida deve se encaixar bem no restante da frase.

Esse processo garante que a correção apresentada ao usuário seja não apenas ortograficamente correta, mas também a mais provável e útil para a consulta realizada.

"como fazer um bolo de chocolate"

6. Resposta ao Usuário
A interface exibe:

"Você quis dizer: como fazer um bolo de chocolate?"

Se o usuário clicar, a busca é refeita com a sugestão corrigida.

Para finaliza

Como mencionei no início, aqui está um exemplo de implementação do algoritmo em Golang. Se precisar convertê-lo para outra linguagem, siga meu conselho: economize tempo e use o ChatGPT.

package main

import (
    "fmt"
)

// LevenshteinDistance calcula a distância entre duas strings
func LevenshteinDistance(a, b string) int {
    la, lb := len(a), len(b)
    if la == 0 {
        return lb
    }
    if lb == 0 {
        return la
    }

    matrix := make([][]int, la+1)
    for i := range matrix {
        matrix[i] = make([]int, lb+1)
    }

    for i := 0; i <= la; i++ {
        matrix[i][0] = i
    }
    for j := 0; j <= lb; j++ {
        matrix[0][j] = j
    }

    for i := 1; i <= la; i++ {
        for j := 1; j <= lb; j++ {
            cost := 0
            if a[i-1] != b[j-1] {
                cost = 1
            }
            matrix[i][j] = min(
                matrix[i-1][j]+1,   // Remoção
                matrix[i][j-1]+1,   // Inserção
                matrix[i-1][j-1]+cost, // Substituição
            )
        }
    }
    return matrix[la][lb]
}

func min(a, b, c int) int {
    if a < b && a < c {
        return a
    }
    if b < c {
        return b
    }
    return c
}

func main() {
    fmt.Println("Distância entre 'gato' e 'rato':", LevenshteinDistance("gato", "rato"))
}

Conclusão

O algoritmo de Levenshtein Distance é fundamental para sistemas que precisam identificar similaridade entre textos. O Google o utiliza para correção ortográfica, buscas tolerantes a erro e até em reconhecimento de voz.

Referências

• How Does Google’s ‘did you mean’ algorithm work?
• How to compute the Levenshtein distance in BigQuery?