Correção ortográfica com índice k-gram

Ao escrever uma consulta, o usuário pode cometer erros ortográficos durante a digitação. Esses erros podem ter duas formas: escrita incorreta da palavra (comesso ao invés de começo), contexto (no meu casa ao invés de na minha casa). Note que no primeiro exemplo, a palavra está incorreta; no segundo, as palavras estão corretas mas o contexto é errado. Nesse momento, a ideia é ver como é possível fazer a correção de erros de escrito (primeiro caso).... [Continue lendo]

Executando consultas por frases: Positional Index

Para realizar a consulta por frases (sequências de palavras) é necessário um índice k-gram. Porém, criar um índice todas as combinações de termos pode ocupar muito espaço em disco/memória. Principalmente se for necessário indexar combinações de 5 ou mais palavras, visto que muitas combinações podem aparecer apenas uma ou outra vez. Uma solução para esse problema é um positional index (índice de posições). Em um índice invertido, termos são mapeados para listas com ids de documentos.... [Continue lendo]

Compressão de índices: Variable Byte Encoding

Uma vez que o índice invertido está montado com postings lists, é necessário persistí-lo em disco. O detalhe é que, se o índice for persistido como texto em UTF-8, cada caractére vai requisitar ao menos 8 bytes. Portando, o id 4568912 requer 7 bytes para ser armazenado. A contrapartida é que, se for armazenado como um numérico (int por exemplo), precisa de apenas 4 bytes. Porém, é possível conseguir uma melhora na compressão ao considerar a estrutura de dados que será armazenada.... [Continue lendo]