o problema
Compressor de propósito geral trata a entrada como uma fita de bytes. A família do gzip procura repetição dentro de uma janela que desliza da esquerda para a direita: se a sequência de bytes que está passando agora já apareceu há pouco, o codificador aponta para trás em vez de repetir. Para texto em prosa isso funciona, porque a redundância da prosa mora mesmo ali, na vizinhança imediata.
Dado tokenizado não se comporta assim. Um log de servidor, um dump de tabela, um csv de milhões de linhas: a repetição está na vertical. O campo de data da linha novecentos mil se parece com o campo de data da primeira linha, e não com o user-agent que está três bytes ao lado dele. Um compressor que anda pela fita de bytes atravessa a estrutura na direção errada e gasta a janela guardando vizinhos que não ajudam. Em 2007, quando este trabalho foi para o VLDB, isso era um problema de conta a pagar: o volume que os sistemas de dados precisavam guardar, mover e replicar crescia mais rápido que o disco e que a rede, e o dado que mais crescia era justamente esse — registro delimitado, gerado por máquina, repetitivo por coluna.
a ideia
O título assume dois compromissos, e é o que se pode afirmar com honestidade a partir do material que sobrou da referência. O primeiro é a unidade: o objeto a comprimir é um fluxo de tokens, não de bytes. Quem sabe onde a linha termina e onde o campo começa pode reorganizar o dado antes de codificar, colocando junto o que se parece, em vez de aceitar a ordem em que o dado chegou. O segundo compromisso é o custo: tempo linear. Não é uma nota de rodapé. Compressão é um campo onde quase sempre dá para ganhar mais razão de compressão gastando mais tempo de busca; declarar linearidade no título é dizer que o alvo não é o melhor arquivo possível, é o melhor arquivo que ainda cabe num pipeline que processa terabytes.
O nome sugere uma transformação de rearranjo antes da codificação — mas o material que chegou aqui não traz o resumo do paper, muito menos o algoritmo. Como a transformação funciona, quanto ela ganha e contra o que foi medida: isso está no PDF do VLDB, e este verbete não vai inventar.
o que isso custou
O trade-off visível é o da linearidade. Um compressor que se recusa a gastar tempo superlinear aceita ficar atrás, em razão de compressão, de métodos que fazem busca mais cara. Esse é o negócio: ele existe para rodar em cima de um fluxo grande demais para dar ao luxo de pensar duas vezes sobre cada byte.
O segundo custo é a especialização. Assim que um compressor passa a raciocinar sobre tokens, ele para de ser universal. Alguém precisa informar onde estão os delimitadores, ou o sistema precisa inferi-los, e dado mal formado — campo com o separador dentro, linha truncada, esquema que muda no meio do arquivo — deixa de ser um detalhe e vira caminho de erro. Sobre texto em prosa, ou binário sem estrutura de registro, a premissa toda desaparece.
Existe um terceiro custo, e é deste verbete, não do paper: os autores certamente declaram limites e comparações, e nada disso chegou até aqui. Quem for usar isso numa decisão de arquitetura precisa ler o original.
onde isso aparece hoje
A tese de fundo — separe o dado por estrutura antes de comprimir, porque a redundância mora na coluna — é a mesma que organiza o armazenamento analítico moderno, e ela vinha ganhando terreno exatamente nesses anos. Dois anos antes, o C-Store já defendia guardar por coluna em vez de por linha, e a compressão era metade do argumento. Três anos depois, o Dremel levou a ideia para registros aninhados em escala de web. E o Gorilla mostrou, na série temporal, o quanto se ganha quando o codificador conhece a forma do valor que está codificando, em vez de tratá-lo como bytes.
Isso é vizinhança, não linhagem: não há nada no material recebido que ligue esses sistemas ao RadixZip. Vale registrar apenas que Gurmeet Singh Manku assina, no mesmo ano, o simhash — outro trabalho da mesma safra do Google sobre reduzir volume enorme de dado repetitivo a uma representação que dê para operar barato.