DEV Community: Waelson

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

Waelson — Thu, 06 Feb 2025 14:25:51 +0000

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

Do Caos a Consistência: A Ordem das Mensagens em Sistemas Distribuídos

Waelson — Tue, 04 Feb 2025 11:15:42 +0000

Contextualização

Imagine um cenário onde diversos serviços estão trabalhando simultaneamente para processar pedidos de clientes em uma grande empresa, como o Mercado Livre. Cada serviço é responsável por uma parte específica do fluxo. Desde a verificação do estoque até a finalização do pagamento, precisa se comunicar com os outros para que tudo funcione em perfeita harmonia. Essa é a essência dos sistemas distribuídos: múltiplos componentes trabalhando em conjunto para atingir um objetivo maior, garantindo escalabilidade, agilidade e tolerância a falhas.

No entanto, um dos maiores desafios nesse tipo de arquitetura é justamente manter a ordem das mensagens que trafegam entre os serviços. Por que isso é tão importante? Imagine se, em meio a um processo sincronizado, o comando para confirmar o pagamento viesse antes da verificação do estoque. O resultado seria um caos: transações incorretas, inconsistências nos dados e, no fim das contas, uma experiência ruim para o cliente. A ordem das mensagens não é um mero detalhe técnico; ela é fundamental para assegurar que cada etapa do processo ocorra na sequência correta, garantindo a integridade dos dados do sistema. Sem essa garantia, o que deveria ser uma operação fluida e coordenada se transforma em um jogo de "telefone sem fio", onde a mensagem pode ser perdida, alterada ou interpretada de maneira equivocada.

Por que manter a ordem é um grande desafio?

Quando falamos sobre manter a ordem no processamento de mensagens em sistemas distribuídos, estamos lidando com uma série de desafios que vão muito além de simplesmente “organizar” os dados. Imagine uma orquestra em que cada músico toca seu instrumento sem se preocupar em ouvir o que os outros estão fazendo. O resultado certamente seria uma cacofonia, certo? Pois bem, nos sistemas distribuídos, cada componente ou serviço pode ser visto como um músico, e sem uma coordenação precisa, a harmonia é comprometida.

Um dos primeiros obstáculos é a ausência de um relógio global. Em sistemas distribuídos, cada nó ou servidor tem seu próprio relógio, que pode não estar sincronizado com os demais. Isso significa que, mesmo que duas mensagens sejam enviadas quase simultaneamente, não há uma maneira natural de saber qual deveria ser processada primeiro. A falta desse “tempo universal” dificulta a criação de uma sequência única e confiável de eventos.

Além disso, a latência e a variabilidade da rede complicam ainda mais a situação. Em um ambiente distribuído, os dados podem ter que percorrer longas distâncias, passando por diversos roteadores e conexões, o que pode introduzir atrasos diferentes para cada mensagem. Esses atrasos podem fazer com que uma mensagem enviada primeiro chegue depois de outra enviada posteriormente, desordenando o fluxo esperado.

Outro ponto crucial é a concorrência e o paralelismo. Em busca de performance e escalabilidade, os sistemas distribuídos costumam processar várias tarefas ao mesmo tempo. Essa execução paralela, embora essencial para lidar com grandes volumes de dados e alta demanda, pode criar cenários em que a ordem natural dos eventos se perde. Se não houver um mecanismo robusto para reordenar as mensagens, as interações entre os serviços podem ocorrer de forma aleatória, levando a comportamentos inesperados e inconsistências.

Ainda temos o desafio de lidar com falhas e a necessidade de reprocessar mensagens. Em cenários de recuperação de falhas, mensagens podem resultar em duplicações ou na reordenação dos eventos. Se uma mensagem precisa ser reenviada ou processada novamente, garantir que ela seja inserida na posição correta do fluxo é uma tarefa árdua, especialmente quando se lida com grandes volumes e múltiplos nós.

Abordagens e protocolos para garantir a ordem

Quando pensamos em como garantir a ordem em sistemas distribuídos, é interessante enxergar o desafio como um quebra-cabeça que exige várias peças para se encaixarem perfeitamente. Existem diversas abordagens e protocolos que podem ser adotados, cada um com suas peculiaridades e adequados a diferentes cenários e requisitos de negócio.

Modelos de Ordenação

Um dos primeiros passos é entender os modelos básicos de ordenação:

FIFO (First-In, First-Out):
Esse é o modelo mais intuitivo, onde a ordem das mensagens é preservada de acordo com a sequência em que foram enviadas por cada produtor. Ou seja, se um serviço envia as mensagens A, B e C nessa ordem, elas serão processadas exatamente assim. Esse modelo funciona muito bem em cenários onde cada produtor se comunica com um único consumidor ou quando a ordem local é suficiente para o contexto da aplicação.
Ordenação causal:
Aqui o foco é manter a relação de causa e efeito entre os eventos. Por exemplo, se o evento B é gerado em resposta ao evento A, é essencial que A seja processado antes de B, mesmo que outros eventos estejam acontecendo simultaneamente em outros pontos do sistema. Esse modelo de ordenação é mais sofisticado, pois exige que o sistema reconheça e preserve essas dependências lógicas entre as mensagens, o que pode ser um desafio em ambientes com alto paralelismo.
Ordenação total:
Em alguns casos, não basta garantir a ordem por produtor ou preservar relações causais – é necessário ter uma ordem única e global para todos os eventos no sistema. A ordenação total assegura que, independentemente de onde e quando uma mensagem é gerada, ela se encaixe em uma sequência global consistente. Essa abordagem é bastante robusta, mas também é a mais difícil de implementar, pois requer mecanismos avançados de coordenação entre os nós distribuídos.

Protocolos de Consenso e Sincronização

Além dos modelos de ordenação, existem protocolos que ajudam a orquestrar a comunicação e a sincronização entre os nós:

Protocolos de consenso (como Paxos e Raft):
Esses protocolos são fundamentais para garantir que todos os nós de um sistema distribuído cheguem a um acordo sobre a ordem dos eventos, mesmo na presença de falhas. Eles permitem que, mesmo que algum nó falhe ou que haja inconsistências temporárias na comunicação, o sistema consiga definir uma ordem única e correta para os eventos, assegurando a integridade dos dados.
Timestamps e lógica vetorial:
Em alguns casos, utiliza-se a marcação temporal para ajudar a ordenar as mensagens. No entanto, como os relógios dos servidores podem estar desincronizados, técnicas como lógica vetorial são aplicadas para rastrear as dependências entre eventos de forma mais precisa. Esse método ajuda a identificar quais eventos ocorreram antes de outros, mesmo em ambientes onde os tempos locais não são confiáveis.
Barreiras de sincronização e algoritmos de reordenação:
Outra abordagem prática é a implementação de barreiras que retêm o processamento até que um conjunto de mensagens seja recebido, preservando a ordem. Esse método, embora possa introduzir uma leve latência, garante que a ordem seja preservada. Além disso, algoritmos de reordenação podem ser aplicados para reorganizar mensagens que chegaram fora de sequência, de modo a restaurar a ordem correta antes de seu processamento.

Integração com Ferramentas e Plataformas

Vale ressaltar que muitas soluções de mensageria modernas, como o Apache Kafka, já incorporam esses conceitos de ordenação e consenso. Essas plataformas oferecem mecanismos nativos para definir partições, onde cada partição preserva a ordem FIFO, e ainda permitem estratégias para manter a consistência dos dados mesmo quando múltiplos produtores estão envolvidos. Essa integração facilita a implementação de arquiteturas distribuídas robustas, onde a garantia de ordem é tratada de forma transparente, permitindo que os desenvolvedores foquem na lógica de negócio.

Casos práticos e desafios reais

Quando mergulhamos no universo dos sistemas distribuídos, logo percebemos que os desafios teóricos se transformam em situações bem reais quando implementados em ambientes de produção. Vamos explorar alguns casos práticos, as ferramentas que ajudam a contornar esses desafios e, claro, as lições aprendidas ao longo do caminho.

Estudos de Caso

Imagine uma grande plataforma de streaming que precisa processar milhões de eventos de usuário, desde cliques e visualizações até interações com conteúdos recomendados tudo em tempo real. Em determinado momento, a equipe percebeu que as recomendações personalizadas estavam inconsistentes: alguns usuários recebiam sugestões baseadas em um histórico que parecia ter saltado etapas, comprometendo a experiência de uso. Ao investigar, descobriu-se que a desordem nas mensagens processadas por diferentes serviços era a culpada. Cada componente enviava seus eventos sem um mecanismo eficaz para garantir a ordem, resultando em uma sequência errada de dados.

Outro exemplo interessante foi o de um sistema de pagamentos de uma fintech. Nesse cenário, a ordem das mensagens é absolutamente crítica para evitar a duplicação de transações ou a realização de operações fora de sequência. Quando um nó enfrentou uma falha e precisou reenviar mensagens, a falta de um controle de reordenação acabou causando confusão, levando a transações que eram processadas em ordem errada. Esses casos ilustram bem como problemas de ordenação não são meras inconveniências técnicas, eles podem impactar diretamente a credibilidade e a operação do negócio.

Ferramentas e tecnologias

Para enfrentar esses desafios, muitas empresas contam com ferramentas especializadas que já vêm preparadas para lidar com a ordenação dos eventos. Uma das estrelas nesse cenário é o Apache Kafka, que permite a criação de partições onde cada uma mantém a ordem das mensagens no estilo FIFO. Além do Kafka, plataformas como RabbitMQ e ActiveMQ oferecem mecanismos para controle de fluxo e reordenação de mensagens, facilitando a implementação de garantias de ordem em ambientes distribuídos.

Não podemos deixar de mencionar também os protocolos de consenso, como Paxos e Raft, que ajudam a manter a consistência e a ordem dos dados mesmo em situações de falha ou alta concorrência. Em muitos casos, a combinação desses protocolos com estratégias de sincronização baseadas em timestamps e lógica vetorial se mostrou essencial para reconstruir uma ordem correta dos eventos, mesmo quando as mensagens chegam fora de sequência.

Lições aprendidas

Um dos grandes aprendizados ao lidar com a ordenação em sistemas distribuídos é a importância de planejar e testar a arquitetura sob cenários de falha e alta carga. Algumas lições que se destacam são:

Planejamento preventivo:
Investir tempo na fase de design e simulação de falhas pode evitar dores de cabeça futuras. Testes de stress e simulações de latência ajudam a identificar pontos fracos na ordenação das mensagens antes que eles afetem os usuários finais.
Monitoramento contínuo:
Implementar soluções de monitoramento e logging detalhado se mostrou crucial para detectar rapidamente quando a ordem dos eventos está sendo comprometida. Isso permite intervenções rápidas e ajustes finos no sistema.
Flexibilidade nas soluções:
Nenhuma abordagem única resolve todos os problemas. A combinação de diferentes estratégias, como o uso de partições para manter a ordem local e protocolos de consenso para sincronizar entre nós – mostrou-se mais robusta e adaptável a cenários variados.
Cultura de compartilhamento e melhoria contínua:
Muitas vezes, os maiores avanços surgem quando as equipes compartilham seus aprendizados e discutem abertamente os desafios enfrentados. A troca de experiências entre profissionais permite a evolução constante das práticas adotadas, beneficiando toda a comunidade.

Conclusão

Garantir a ordem em sistemas distribuídos é um desafio multifacetado, que exige a combinação de modelos teóricos, protocolos de consenso e ferramentas práticas. A escolha das estratégias deve considerar trade-offs entre complexidade, latência e requisitos do negócio. Para profissionais da área, o aprendizado contínuo e o compartilhamento de experiências são fundamentais para dominar esses conceitos e construir sistemas escaláveis, resilientes e preparados para o futuro.