Implementing Efficient Error-Tolerant Query Autocompletion Systems
Van Den Berg da Gama Ferreira, https://lattes.cnpq.br/9433225118102294, https://orcid.org/0000-0001-8985-5045 · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2024
Nesta tese, desenvolvemos algoritmos e estruturas de dados eficazes e eficientes para sistemas de autocompletar consultas tolerantes a erros (ETQAC). Esses sistemas sugerem consultas classificadas com base em um prefixo digitado, passando por duas fases principais: correspondência e classificação. A fase de correspondência seleciona sugestões que combinam com o prefixo, enquanto a fase de classificação organiza os resultados de acordo com uma função de pontuação que busca as sugestões mais relevantes. Discutimos o uso de uma abordagem de paralelismo de bits para calcular a distância de edição entre strings, adaptando-a para métodos de busca aproximada por prefixo. Propomos um método baseado em tries chamado BWBEV, que utiliza uma representação unária de vetores de edição e operações de bits para atualizá-los ao calcular distâncias de edição. Demonstramos também como aplicar essa técnica para computar distâncias de edição online sem uma estrutura de índice. Nossos experimentos mostram que o BWBEV melhora a velocidade de processamento em mais de 36% em comparação com métodos de ponta. Além disso, investigamos a otimização do cálculo dos resultados principais, combinando as fases de correspondência e classificação para eliminar resultados irrelevantes durante a correspondência, acelerando assim o processamento. Como ETQACs precisam apresentar apenas algumas das melhores sugestões, essa limitação é explorada para reduzir custos computacionais. Em relação à fase de correspondência, estudos anteriores utilizaram tries e variações como estruturas em memória. No entanto, esses métodos podem exigir muita memória. Exploramos o uso de burst tries, uma versão compacta de tries, como estrutura subjacente para métodos de busca de prefixo tolerante a erros. Burst tries constroem contêineres leves nos nós folha do índice, reduzindo custos de armazenamento sem comprometer o desempenho. Ao indexar o conjunto de dados JusBrasil, o uso de burst tries reduziu o consumo de memória para 26% de uma trie completa e aumentou o desempenho de tempo em 16%.