Um mecanismo de busca feito em 80 linhas de Python

• microsearch é uma implementação de brinquedo para entender diretamente o funcionamento interno de um mecanismo de busca; a classe principal do motor de busca tem menos de 80 linhas, mas o projeto é maior quando inclui crawler, API e templates HTML
• Tendo como pano de fundo o problema de pequenos sites e blogs não serem facilmente encontrados em grandes mecanismos de busca, ele coleta textos de 642 feeds RSS para criar os dados de busca
• Com crawling assíncrono baseado em asyncio, o tempo de coleta caiu de 20 minutos para 20 segundos, e o conteúdo limpo é armazenado como dados Parquet
• A busca funciona sobre um índice invertido que conecta palavras à contagem de ocorrências por URL, e usa BM25 baseado em conteúdo no lugar de PageRank baseado em links para ordenar os resultados
• A UI em FastAPI oferece a caixa de busca e a página de resultados, mas ainda não tem recursos como operadores de consulta, indexação por n-gram, expansão de consulta/documento e indexação durante o crawling

---

Objetivo e escopo do microsearch

• microsearch é uma implementação de mecanismo de busca em Python publicada no repositório no GitHub
• O objetivo não é um mecanismo de busca para produção, mas criar um exemplo de brinquedo utilizável que mostre como um mecanismo de busca funciona por dentro
• O alvo da busca está mais próximo de pequenos sites e blogs que não são bem encontrados na competição de SEO do Google
• A implementação central do mecanismo de busca tem menos de 80 linhas, mas o projeto completo é maior quando se inclui código auxiliar como crawler de dados, API e templates HTML
• A implementação foi criada no processo de trabalhar com Solr e Lucene para entender mais profundamente o funcionamento de mecanismos de busca

Crawler baseado em RSS

• Para criar os dados de busca, ele faz crawling de feeds RSS de blogs
• Foram usados ao todo 642 feeds RSS
  • cerca de 100 são blogs que o autor lê diretamente, sobre ML, ciência de dados, matemática etc.
  • os cerca de 500 restantes vieram do projeto surprisetalk blogs.hn
• O fluxo do crawling é extrair URLs de posts de cada feed RSS, baixar o HTML do post e então limpar o texto do conteúdo principal
• A limpeza do HTML usa BeautifulSoup para remover script e style, organizar quebras de linha e espaços, e converter em texto
• Com crawling assíncrono usando aiohttp e asyncio, o tempo de execução caiu de 20 minutos para 20 segundos
• O resultado é transformado em um DataFrame com URL e conteúdo limpo, e salvo em output.parquet

Estrutura do índice invertido

• A primeira estrutura de dados central do mecanismo de busca é o índice invertido
• O índice invertido mapeia palavras-chave para documentos, permitindo encontrar rapidamente em quais documentos uma determinada palavra aparece
• A implementação usa um defaultdict no formato dict[str, dict[str, int]]
  • a chave externa é a palavra
  • a chave interna é a URL
  • o valor interno é o número de vezes que a palavra aparece no documento daquela URL
• A classe SearchEngine possui dois dicionários internos
  • _index: armazena a contagem de ocorrências por URL para cada palavra
  • _documents: armazena o conteúdo original por URL
• index(url, content) normaliza o conteúdo, divide por espaços e aumenta a contagem de ocorrências por URL de cada palavra
• bulk_index() recebe uma lista de URLs e conteúdos e indexa vários documentos de uma vez
• get_urls(keyword) normaliza a palavra-chave e retorna as URLs que contêm aquela palavra e sua contagem de ocorrências

Normalização de strings e busca básica

• A normalização de strings troca pontuação por espaços, organiza espaços duplicados e converte tudo para minúsculas
• Para reduzir diferenças entre maiúsculas e minúsculas, Foo e foo são tratados como a mesma palavra-chave
• Ao indexar dois documentos de exemplo, a busca por foo retorna ambos os documentos
  • Foo: Hello, World! My name is Foo!
  • Bar: Hello, World! My name is Bar, I'm not Foo!
• Nesta etapa, só é possível saber se um documento contém o termo pesquisado e quantas vezes ele aparece; por isso, é necessário um ranking separado para definir a ordem dos resultados

Rankeador BM25

• O BM25 é usado para ordenar os resultados da busca
• O PageRank ranqueia documentos com base em links, enquanto o BM25 calcula pontuações com base no conteúdo dos documentos
• O SearchEngine tem parâmetros padrão k1=1.5 e b=0.75 para o cálculo do BM25
• A classe fornece propriedades necessárias para o cálculo do ranking
  • posts: lista de URLs indexadas
  • number_of_documents: número total de documentos
  • avdl: comprimento médio dos documentos
• idf(kw) calcula a frequência inversa de documentos de uma palavra-chave específica
  • número total de documentos N
  • número de documentos que contêm a palavra-chave n_kw
  • usa a fórmula log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
• bm25(kw) calcula a pontuação BM25 para cada URL que contém a palavra-chave
• search(query) normaliza a consulta, divide em palavras e retorna a soma das pontuações BM25 de cada palavra por URL
• No exemplo, ao buscar apenas foo, o documento Foo recebe pontuação maior que Bar; ao buscar foo bar, o documento Bar recebe pontuação maior

Interface FastAPI

• O mecanismo de busca é exposto como um pequeno app FastAPI
• O app cria uma instância de SearchEngine e, na inicialização, lê URL e conteúdo dos dados Parquet para indexar com bulk_index()
• Há três rotas principais
  • /: renderiza a página de busca e envia a lista de posts indexados
  • /results/{query}: executa a busca da consulta e mostra as 5 URLs principais na página de resultados
  • /about: renderiza a página de apresentação
• Os resultados são ordenados por pontuação em ordem decrescente, e apenas as top-N URLs são selecionadas
• UI e UX ainda têm bastante espaço para melhorar, mas a busca funciona rápido e os resultados não são ruins

Recursos ausentes e limitações

• A implementação não tem vários recursos esperados de um mecanismo de busca real
• Não há operadores de consulta
  • por exemplo, não há suporte para excluir uma palavra específica como em how to build a search engine -solr no Google
• Não há indexação por n-gram
  • não há suporte a buscas como "search engine", que procuram apenas documentos em que duas palavras aparecem em uma ordem específica
• Não há expansão de consulta ou de documento
  • ao buscar engine, documentos com engines não são encontrados automaticamente
• Crawling e indexação estão separados
  • isso poderia ser integrado para indexar assim que o documento fosse recebido, e esse processo também poderia ser assíncrono

Próximos passos

• O projeto ajudou a desenvolver uma intuição melhor sobre como o Solr funciona internamente
• Também ficou claro que código assíncrono tem grande efeito em tarefas centradas em IO
• O próximo passo é adicionar busca semântica ao mecanismo de busca
• O autor vem experimentando com modelos de embeddings e ANN, e incorporar isso ao microsearch é a próxima tarefa

[GN⁺]

Opiniões no Hacker News

• Isso é realmente muito legal. Estou criando com Pandas um mecanismo de busca BM25 bem rápido para testes locais: https://github.com/softwaredoug/searcharray
  O motivo de usar Pandas é que BM25 sozinho não basta, e quero calcular e combinar facilmente outros fatores, como atualidade e popularidade, com pandas/numpy
  A propósito, busca por frases é a parte difícil. Correspondência de frases tem muitos casos de borda, e também é preciso considerar coisas como slop. As informações de posição também precisam ser compactadas usando o mínimo de memória possível: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

  • Já lidei com correspondência de frases em um projeto de brinquedo: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
    Acho que testei de forma bastante completa, mas gostaria de receber feedback. Codifiquei as informações de posição com delta encoding e depois em base36
  • Fico curioso se incluir análise de sentimento ajudou no processamento de frases ou se acabou atrapalhando. Frases são difíceis de lidar, e estou pensando no que poderia ser feito para melhorar o desempenho
  • Fico curioso para saber como você encontrou este post tão rápido e comentou. Queria saber se usa algum tipo de ferramenta de monitoramento de buscas que varre a primeira página procurando palavras-chave de interesse, ou se foi por acaso

• Está certo. A maior parte do que é difícil em busca está em lidar com a escala dos dados. A lógica em si pode ser surpreendentemente fácil, ou feita para ser fácil
  Claro que também dá para torná-la infinitamente complexa, mas este projeto removeu bem o que era desnecessário. Dá para ir bem longe se você abordar isso não como um problema de tornar o mecanismo de busca maior, mas de tornar os dados fisicamente menores ou aumentar a relação sinal-ruído

• Olhando src/microsearch/engine.py, há um código como SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), mas não faço ideia do que sejam k1 ou b, e não há um único comentário no arquivo inteiro
  Comentários não estão mais na moda hoje em dia? Imagino que _documents tenha URLs como chaves e o conteúdo dessas URLs como valores, mas posso estar errado. Poderia ter sido um material para aprender a criar e expandir um mecanismo de busca, mas a qualidade do código deixa a desejar por falta de documentação

  • Essa parte é explicada no texto, e o próprio texto serve como documentação do código. O link do BM25 leva ao contexto matemático, e se você pesquisar um pouco mais sobre os parâmetros do BM25, também encontra posts relacionados que tratam de como escolhê-los
  • Para deixar o título do post chamativo, era preciso reduzir ao máximo o número de linhas de código ;)
    Brincadeiras à parte, concordo que normalmente é melhor ter documentação e código juntos. Mas, neste caso, por ser um projeto educacional, a opção foi separar código e documentação e documentar o código no post do blog
  • Estou no celular, então não consigo olhar em detalhes, mas k1 e b são valores de ponderação padrão usados em TF-IDF ou BM25; aqui é o caso do BM25
    Comentários seriam úteis, mas para quem conhece esse problema também são nomes reconhecíveis de imediato
  • k1 e b são parâmetros de ajuste da função de ranqueamento BM25. Não são nomes inventados pelo autor do post original; quase todas as implementações e livros-texto usam esses nomes de variáveis
    Para alguém que conhece recuperação de informação, o correto é justamente chamá-los de k1 e b: https://en.wikipedia.org/wiki/Okapi_BM25
  • Quando vejo um fluxo como a: float, sempre lembro da palestra do Rich Hickey: “não é de tipos que você precisa, é de bons nomes”
    Detesto essa tendência, que parece vir de Go, de usar nomes de variáveis de uma letra sem explicação e abusar do sistema de tipos como se fosse uma ferramenta auxiliar de nomes. Nomes podem transmitir informação semântica sobre o que um programa faz, então deveriam ser bem usados

• Não entendo qual é o sentido de se gabar do número de linhas de código, e não do número total de \r\n, quando se usa dependências externas
  Não existe uma unidade SI para medir uma base de código, mas acho que a carga cognitiva precisa ser medida de alguma forma

  • Não é um critério oficial, mas na nossa equipe às vezes fazemos referência a https://grugbrain.dev e dizemos “este código não é grug” ou “este código é bem grug”
  • O mecanismo de busca de 80 linhas em si não usa dependências externas. Ele importa apenas collections, math e string, tudo da biblioteca padrão
    Mas talvez fosse mais correto chamá-lo de “engine do mecanismo de busca”. O crawler e a interface não estão incluídos nessas 80 linhas, mas são necessários de alguma forma, e a implementação apresentada aumenta bastante tanto o número de linhas quanto o de bibliotecas. Ainda assim, essas bibliotecas não têm relação com o mecanismo de busca em si. Se você começar a contar dependências genéricas como pandas ou fastapi, talvez também tenha que contar os milhões de linhas do sistema operacional, o firmware da placa de rede e a complexidade do hardware
  • Há algum motivo para não celebrar a conquista da indústria que tornou possível construir algo assim em 80 linhas?
  • Aqui faz sentido. Se fosse “um mecanismo de busca feito em 4000 linhas de Python”, a maioria simplesmente passaria direto, mas 80 linhas é curto o bastante para valer uma olhada
  • À moda antiga, existe a complexidade ciclomática

• Gostei. Também dá para fazer um mecanismo de recomendação com menos de 20 linhas para usar junto com o mecanismo de busca. Se você mantiver logs de sessão das URLs clicadas, pode olhar uma janela deslizante depois da URL atual em cada sessão e atribuir pesos maiores aos links mais próximos para criar uma lista de recomendações
  Ao ordenar os resultados recomendados e manter apenas os N primeiros, você obtém uma lista de URLs recomendadas para uma URL específica. Com alguns ajustes, também dá para misturar nos logs os termos de busca digitados e as URLs clicadas para extrair sugestões de ortografia

• Muito legal e educativo. Só não recomendo colocar em produção :-)
  Há algum tempo precisei de algo parecido, mas em escala um pouco maior, com dezenas de milhares de documentos, e a resposta, como sempre, foi sqlite. Estruturalmente é igual ao que está aqui, mas com a camada de persistência do índice invertido escrita por outra pessoa

  • Uso SQLite FTS em praticamente tudo, e ele nunca me decepcionou
  • De fato, tem até a mesma fórmula. Graças a este comentário, tive algo como um “arrepio de compreensão”

• Quando você pesquisa no Google com aspas, como "search engine", ele mostra apenas resultados em que as duas palavras aparecem nessa ordem
  Pelo menos em alguns casos é assim, mas infelizmente nem sempre. O que usuários avançados querem é um “grep para a web”, não “dizer o que o Google quer mostrar”

  • Posso garantir que quase ninguém quer de fato um “grep para a web”. Comparado até com um mecanismo de busca que faça só uma expansão de consulta mínima, um grep para a web é claramente pior
    É verdade que o Google exerce liberdade demais ao interpretar consultas, mas há muitos processamentos que qualquer mecanismo de busca faz e que certamente são melhores do que não fazer nada. O problema da busca do Google hoje é que é difícil inferir por que aqueles resultados aparecem, e parece ser porque ela depende demais de embeddings para comparação de strings. É frustrante quando "cat food" casa com "dog restaurant", por exemplo: resultados semanticamente próximos no espaço de embeddings, mas que não batem com o raciocínio humano

• Acho injusto dizer que é código de 80 linhas usando bibliotecas externas como feedparser, bs4 etc.

  • Eu concordaria se fosse construído em cima do elasticsearch, mas, se a parte de mecanismo de busca de fato está implementada nessas 80 linhas, acho justo. As bibliotecas importadas são do tipo que faz sentido não implementar por conta própria
    Às vezes artigos do tipo “faça seu próprio mecanismo de busca” na verdade são guias de instalação do searxng ou do yacy, mas este caso é diferente
  • Acho ok se essas dependências forem bem comuns e mainstream

• Bom. Não deve ser tão difícil adicionar um recurso de busca fuzzy aqui. Por exemplo, fazer uma busca por "hackrnew" casar com "hackernews", encontrando resultados cuja distância de edição de prefixo fique abaixo de certo limiar
  A ideia básica é manter mais um índice invertido, com as chaves sendo os n-gramas (normalmente 3-gramas) das palavras na coleção de documentos, e as postagens sendo as palavras, ou IDs de palavras, em que aquele n-grama aparece. Dá para usar o lema auxiliar de que, se PED(x, y) <= delta, então |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta. Você calcula os n-gramas da entrada x, busca as postagens de cada n-grama e combina as duplicatas, obtendo o número de n-gramas compartilhados com cada palavra candidata y. Se esse número for maior que o critério, só então calcula o PED real; se for menor, pula, reduzindo bastante o cálculo caro
  Depois é só consultar o índice existente com a lista de palavras obtida assim. Usei essa abordagem antes ao criar um mecanismo de busca fuzzy em JS do lado do cliente para https://dont.watch/. Olhando dentro do código JS, dá para ver que o índice invertido e o índice de n-gramas comprimido são entregues diretamente como um arquivo JS. O mecanismo de busca em si tem cerca de 300 linhas de JS, sem dependências externas, e inclui apenas heurísticas bem básicas para melhorar os resultados

  • Com esse método, quanto o tamanho do índice aumenta?