Compressão de Índice

A compressão de índice codifica as listas de ocorrências de um índice invertido de forma compacta para que um sistema de busca armazene menos dados e responda a consultas mais rapidamente.

Definition

A compressão de índice é a aplicação de métodos de codificação de inteiros e strings ao dicionário e às ocorrências de um índice invertido, a fim de reduzir sua pegada de armazenamento, mantendo as ocorrências rapidamente decodificáveis durante o processamento de consultas.

Scope

Este tópico abrange técnicas para comprimir índices invertidos, especialmente a codificação de lacunas de identificadores de documentos e frequências de termos com códigos inteiros de comprimento variável e alinhados por palavra. Ele trata da compressão de dicionário, codificação de lacunas (delta), códigos clássicos como unário, gama e Golomb-Rice, esquemas alinhados por byte e baseados em blocos, como byte-variável e PForDelta, e a relação de troca entre taxa de compressão e velocidade de decodificação. Exclui a construção do próprio índice e a estratégia de avaliação de consulta que o consome.

Core questions

• Por que a codificação de lacunas entre identificadores de documentos comprime as ocorrências de forma eficaz?
• Quais códigos inteiros são usados e como eles equilibram a taxa de compressão com a velocidade de decodificação?
• Como o próprio dicionário de termos é comprimido?
• Como as ocorrências comprimidas podem ser decodificadas rápido o suficiente para manter a latência da consulta baixa?
• Como a compressão interage com o comportamento do cache e o custo de entrada/saída?

Key concepts

• codificação de lacunas (delta)
• codificação de byte variável
• códigos gama e Golomb-Rice
• PForDelta e códigos baseados em blocos
• compressão de dicionário
• taxa de compressão
• taxa de transferência de decodificação
• decodificação SIMD / vetorizada

Key theories

Codificação de lacunas de ocorrências

Como os identificadores de documentos em uma lista de ocorrências são crescentes, armazenar as diferenças (lacunas) entre identificadores consecutivos produz números pequenos que se comprimem bem, especialmente para termos frequentes com ocorrências densas.

Relação de troca entre compressão e velocidade

Códigos alinhados por bit, como gama e Golomb, maximizam a compressão, mas decodificam lentamente, enquanto códigos alinhados por byte e baseados em blocos, como byte-variável e PForDelta, sacrificam alguma taxa por uma decodificação muito mais rápida e vetorizável, o que frequentemente resulta em melhor desempenho geral da consulta.

Clinical relevance

A compressão é essencial para operar buscas em escala: ela encolhe os índices para que caibam na memória ou em armazenamento menor, reduz a entrada/saída e melhora a localidade do cache, diminuindo assim a latência da consulta e o custo de hardware. Motores de busca de produção e bibliotecas de busca de código aberto dependem todos de ocorrências comprimidas.

History

A codificação compacta de índices de texto foi desenvolvida juntamente com arquivos invertidos, com códigos clássicos alinhados por bit (unário, gama, Golomb) sistematizados no trabalho Managing Gigabytes dos anos 1990. À medida que a busca em escala web exigia decodificação cada vez mais rápida, esquemas alinhados por byte e baseados em blocos, como byte-variável e PForDelta, e posteriormente decodificadores vetorizados capazes de bilhões de inteiros por segundo, mudaram a ênfase para a velocidade.

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

Como um índice comprimido pode ser mais rápido do que um não comprimido?

A compressão reduz a quantidade de dados lidos do disco ou da memória, o que frequentemente é o gargalo. Códigos inteiros modernos decodificam muito rapidamente, frequentemente usando instruções vetoriais, então o tempo economizado na entrada/saída e o melhor comportamento do cache mais do que compensam o trabalho de decodificação.

Por que armazenar lacunas em vez de identificadores de documentos brutos?

Os identificadores de documentos em uma lista de ocorrências são classificados e crescentes, então os consecutivos diferem por pequenas quantidades. Armazenar essas pequenas lacunas em vez de grandes identificadores absolutos produz valores que códigos compactos podem representar em muito poucos bits.