![[*]](foot_motif.gif){kind=small}
Universidade Federal de Minas Gerais - UFMG
Departamento de Ciência da Computação - DCC
26 de Setembro de 2002
Em [3] são propostos métodos que mostram que a busca feita diretamente em arquivos comprimidos é mais veloz do que a busca feita nos arquivos originais. Além disso, os sistemas de RI podem acessar uma determinada palavra em um arquivo comprimido sem que o texto seja totalmente descomprimido.
Em relação à compressão, algumas métricas são especialmente interessantes. A primeira é a taxa de compressão que representa o tamanho do arquivo comprimido como uma porcentagem do tamanho do arquivo não comprimido. Outras duas métricas são definidas como a velocidade de compressão e de descompressão. Em bases textuais grandes a velocidade de descompressão torna-se mais importante do que a velocidade de compressão. Isto se deve ao fato de que normalmente o texto é comprimido uma única vez e lido várias vezes.
Para o casamento de padrão, uma técnica relevante é fazer a busca diretamente sobre o arquivo comprimido sem que este seja descomprimido. Neste caso, ao invés de descomprimir o texto, o padrão é comprimido para então ser realizada a busca no texto comprimido. Conseqüentemente, como tanto o padrão quanto o texto estão comprimidos, uma quantidade menor de bytes são comparados durante a busca.
não são vantajosas para o cenário de RI por dois motivos.
Primeiro, o acesso aleatório é caro pois a descompressão
precisa ser iniciada no começo dos arquivos. Segundo, a busca em
arquivos comprimidos com estes métodos necessitam a sua descompressão.
A codificação aritmética apresentada em [6] que codifica os símbolos em frações de bits é outro exemplo que apresenta restrições semelhantes às dos métodos da família Ziv-Lampel.
O método de codificação de Huffman utiliza códigos menores aos símbolos (tipicamente caracteres) de maior freqüência de um texto [7]. Em sistemas de RI esta codificação é melhor aproveitada quando as palavras são tratados como símbolos ao invés de caracteres, conforme proposto por Bentley et al. [8]. A esta abordagem dá-se o nome de Compressão de Huffman Baseada em Palavras.
A compressão é feita em duas fases distintas. Primeiro, é obtida a freqüência de cada palavra do texto. A seguir, é feita a compressão propriamente dita.
Melhorias podem ainda ser alcançadas utilizando um modelo que considera o fato de que os textos possuem, além das palavras, separadores. Uma forma eficiente de tratar palavras e separadores é a utilização do modelo sem espaços proposto por Moura et al. [3].
![\begin{figure} \centering \includegraphics [scale=.9]{images/huffman-word-space-less}\end{figure}](img1.gif) |
A Figura 1 mostra a codificação de texto utilizando o método sem espaços da codificação de Huffman baseada em palavras. Nesta figura, o texto ``para cada rosa, uma rosa é uma rosa" foi codificado em ``0110 0100 1 0101 00 1 0111 00 1". Note que toda ocorrência de separadores compostos de um único espaço são ignoradas.
Durante a decodificação, um espaço em branco é acrescentado entre todas as ocorrências de duas palavras que não possuírem um separador entre elas.
Como os bytes são unidades básicas de armazenamento, as operações de leitura/escrita, aritméticas e lógicas são mais eficientes quando executadas sobre bytes do que quando executadas sobre bits. Por este motivo, a codificação em bytes torna-se interessante para sistemas de RI.
A codificação de Huffman em bytes proposta por Moura et al. [3] é uma variação chamada Byte-Huffman (BH) que associa uma seqüência de bytes ao invés de bits para cada palavra do texto.
Em [1] Moura propõe outra variação chamada de Byte-Huffman Sincronizado (BHS). O método BHS utiliza códigos de Huffman com dígitos de 7 bits e adiciona um bit extra de sincronização para cada dígito do código comprimido. Este bit sinaliza qual é o primeiro byte de cada código. Assim, utilizando o BH, suponha que a codificação para a palavra ``olá'' seja ``3 29 15'', utilizando o BHS a codificação seria ``131 29 15'' pois 3 + 128 = 131.
Segundo Ziviani et al. [2], a utilização de bytes ao invés de bits na codificação de Huffman apresenta uma degradação pequena na taxa de compressão. Seus experimentos mostram que o BHS possui uma taxa de compressão três pontos percentuais maior do que o BH. Uma grande vantagem dos métodos BH e BHS é o tempo de descompressão que é mais do que 20 por cento mais rápido do que o utilitários como o Gzip e o Unix Compress.
Outra vantagem do BH e BHS é a possibilidade de executar uma busca rápida diretamente no texto comprimido utilizando qualquer algoritmo de busca seqüencial baseada em casamento de padrão.
Para a procura de palavras simples em um texto comprimido, o algoritmo inicialmente realiza a operação de busca binária do padrão no vocabulário, obtendo em seguida o código comprimido da palavra. Se esta palavra for encontrada a folha correspondente a ela na Árvore de Huffman é marcada. O segundo passo é utilizar um algoritmo de busca seqüencial sobre o texto comprimido utilizando o código encontrado.
É importante salientar que para a codificação BH, como não há marcação de inicio de palavras, o código pode ser encontrado no texto comprimido, mas pode não representar a palavra e sim uma concatenação dos códigos de outras palavras. Este problema é contornado utilizando-se na compressão a codificação BHS.
Considerando as exigências dos sistemas de informação atuais, os algoritmos de busca devem ser flexíveis, o que significa realizar busca para padrões complexos, que incluem buscas ignorando letras maiúsculas e minúsculas, buscas que permitam erros (buscas aproximadas) e buscas de frases compostas por padrões complexos.
Considere um padrão que possui L palavras. Para cada uma
destas palavras é criada uma máscara de L bits. A
frase passa por um pré-processamento, onde o i-ésimo
bit da palavra x recebe valor 1 se ela aparecer como o i-ésimo
elemento do padrão. O algoritmo então busca seqüencialmente
cada elemento i da frase no vocabulário e coloca em 1 o valor
do i-ésimo bit das palavras que casam como o elemento i
da frase. A Figura 2 ilustra
esta situação.
![\begin{figure} \centering \includegraphics [scale=.8]{images/search-scheme}\end{figure}](img2.gif) |
Após esta fase, o texto comprimido é verificado como descrito para palavras simples. Um autômato não-determinístico é responsável pelo controle dos estados do padrão, onde o estado 0 está sempre ativo e toda vez que o estado i é ativado o algoritmo informa que houve uma ocorrência.
A transição do estado i para o estado i+1 ocorre quando o elemento i do padrão foi encontrado no texto. O autômato é não determinístico por que permite a ativação de dois estados no mesmo intervalo de tempo.
O algoritmo lê os bytes do texto comprimido e percorre a árvore de Huffman, até chegar em uma folha, quando irá enviar para o autômato a mascara de bits da folha. A ativação do estado i está condicionada ao estado i-1 estar ativo e ao bit i da máscara de i estar em 1.
Este procedimento é implementado pelos algoritmos Shift-OR [10] e Shift-AND [11], que permitem a simulação de um autômato com até w+1 estados, onde w é tamanho em bits da palavra do computador.
Estes algoritmos executam uma transição no autômato para cada palavra do texto utilizando apenas duas operações por transição. Somente para os estados que casam com a palavra do texto ocorrem transições, neste caso é realizada uma operação AND (Shift-AND) ou OR (Shift-OR) bit a bit com a mascará encontrada na folha da árvore de Huffman. Uma operação shift e uma operação AND a cada palavra do texto atualizam o estado da busca (Shif-AND).
Nesta operação podem ser ignorados separadores de texto e palavras como artigos e preposições tornando a busca mais flexível.
O autômato da Figura 3
representa uma busca por frase, com quatro palavras e permitindo 2 erros,
entre eles inserções, remoções e/ou substituições
de palavras.
![\begin{figure} \centering \includegraphics [scale=.7]{images/quatro-palavras-dois-erros}\end{figure}](img3.gif) |
Utilizando-se extensões do algoritmo Shift-AND este autômato pode ser implementado para a busca aproximada de frases e definitivamente tornar a busca em textos comprimidos cada vez mais atrativa.
Em [2] são apresentados três tipos distintos de índices. O primeiro é o índice invertido completo, que guarda a posição exata de cada palavra no texto, e pode ser utilizado com qualquer método de compressão, pois a busca é feita utilizando a lista, e a descompressão é utilizada somente na apresentação do resultado. O segundo é o índice de arquivo invertido, que guarda o documento onde há a ocorrência de cada palavra, e apresenta dificuldades quando a busca desejada envolve uma frase, pois duas palavras podem estar em um documento sem que façam parte da mesma frase. O último é o índice de endereçamento de bloco, que divide o texto em blocos de tamanho fixo, o qual pode conter parte de ou vários documentos, ou ainda a sobreposição de limites de documentos, guardando apenas os blocos onde cada palavra possui ocorrência, servindo como um filtro que elimina os blocos que não contém a ocorrência.
Nestes últimos dois casos, é necessário que a técnica de busca com compressão seja eficiente quando o texto tiver que ser comprimido, permitindo uma busca rápida em tempo real.
É possível combinar qualquer um dos três tipos de índices invertidos com índice comprimido, o que reduz bastante o tamanho deste último devido às características de seqüencia das listas de ocorrências. As listas podem, entretanto, ser construídas já no formato comprimido, reduzindo o uso de memória principal do sistema. A construção do índice de um texto comprimido é mais rápida que a construção do índice de um texto não comprimido [2]. Uma das características da codificação de Huffman baseada em palavras é a sua fácil integração com índice invertido, pois a tabela de símbolos de Huffman é exatamente o vocabulário do texto, permitindo integrar as estruturas de dados do compressor e do índice.
Em [4] Scholer et al. também utilizam uma codificação em bytes ao invés de bits aplicada a índices invertidos. Como resultado, Scholer et al. também concluíram que a codificação em bytes dos índices comprimidos produz pesquisas mais rápidas quando comparadas com índices não comprimidos e com índices comprimidos utilizando a codificação em bits (mesmo quando estes cabem inteiramente na memória).
Pode-se, entretanto, aplicar uma heurística que consiste em adicionar
uma palavra vazia com freqüência zero ao vocabulário,
e esta irá sinalizar as novas palavras adicionadas ao texto, ou
seja, toda vez que uma nova palavra for adicionada, esta irá ser
codificada com o código da palavra vazia. Quando o texto comprimido
é grande, o uso do código corrente pode tornar-se ótimo,
e as novas palavras podem ter uma perda, que entretanto será desprezível.
Faz-se necessário adaptar o algoritmo de busca quando se pretende
obter essas novas palavras.
![\begin{figure} \centering \includegraphics [scale=.55]{images/taxa}\end{figure}](img4.gif) |
Os testes oferecem um estudo comparativo entre as técnicas de
compressão utilizadas pelos aplicativos Gzip, Compress, Pack do
Unix e o BH mostrado na seção 2.1.2.
As métricas utilizadas são: taxa de compressão, tempo
de compressão e tempo de descompressão.
![\begin{figure} \centering \includegraphics [scale=.55]{images/compressao}\end{figure}](img5.gif) |
![\begin{figure} \centering \includegraphics [scale=.55]{images/descompressao}\end{figure}](img6.gif) |
Os experimentos (Figura 4) mostram que os aplicativos Gzip, Compress e Pack do Unix apresentam uma taxa de compressão constante independente do tamanho do arquivo texto. Para o BH, a taxa de compressão diminui de acordo com o crescimento do texto original. A Figura 4 nos permite observar também que, para arquivos grandes (mais de 20MB), o BH é capaz de comprimir mais do que os demais aplicativos de compactação. Isto ocorre porque para arquivos grandes as palavras mais comuns apresentam uma grande repetição de maneira que o BH utiliza códigos menores para palavras de grande ocorrência. Além disso, espaços em branco não são codificados pelo BH.
Na Figura 5 podemos analisar o tempo de compressão gasto pelos BH e os outros aplicativos de compactação. Obviamente, o tempo de compactação cresce de acordo com o tamanho do texto. É importante observar que o BH é mais eficiente do que o Gzip perdendo para o Compress e para Pack cujas taxas de compressão são, respectivamente, aproximadamente 30 e 10 pontos percentuais pior do que a taxa do BH (Figura 4).
Conforme observado anteriormente mais importante do que o tempo de compressão
é o tempo de descompressão. Na Figura 6
podemos verificar que os melhores tempos de descompressão são
alcançados pelo BH e pelo Gzip. Contudo, o BH supera o Gzip, principalmente
quando o tamanho do arquivo a ser descompactado cresce.
![\begin{figure} \centering \includegraphics [scale=.55]{images/tempo-medio}\end{figure}](img7.gif) |
Para a busca exata, foi utilizado o Shift-OR em textos comprimidos com
o método BH. Esta busca é comparada com os aplicativos Grep,
Agrep e uma implementação do BMH (Boyer-Moore-Hospool). As
buscas foram executadas com padrões de tamanhos entre 2 e 18 em
um texto de 100MB. A Figura 7
e a Tabela 1 mostram os valores médios
dessas buscas. Note que o Shift-OR sobre o arquivo comprimido foi, na média,
6 segundos mais rápido do que o Agrep.
| Algoritmo | Tempo médio (s) |
| busca comprimida | |
| com Shift-OR | 3.94 |
| Agrep | 10.28 |
| Grep | 10.86 |
| bmh | 16.69 |
Para a busca permitindo erros, é utilizado o Shift-AND sobre
o arquivo comprimido com o BH. Em [2]
é mostrado que a busca permitindo erros em arquivos comprimidos
é bem mais eficiente do que o Agrep quando o número de erros
cresce (Tabela 2) chegando a ser até
7 vezes mais rápido. Outros resultados apresentados em [1]
mostram que este ganho de velocidade pode ser de até 8 vezes.
| Algoritmo | k=1 | k=2 | k=3 |
| busca comprimida | |||
| com Shift-AND | 23.10 | 24.70 | 25.00 |
| Agrep | 117.90 | 146.10 | 174.60 |
As técnicas de compressão como o BH e BHS são capazes de obter melhores taxas de compressão, velocidade de compressão e de descompressão quando comparado aos aplicativos Gzip, Compress e Pack.
Os algoritmos para busca em texto comprimido podem ser tão flexíveis quanto qualquer sistema de busca em textos não comprimidos permitindo diferentes maneiras de realizar busca exata e aproximada. Isto se deve ao fato de que o BH e o BHS permitem o acesso aleatório aos arquivos comprimidos. Além disso, para a pesquisa não é necessário que o texto seja descomprimido como é o caso dos algoritmos da família Ziv-Lempel.
Outras aplicações para técnicas de compressão incluem a melhoria do desempenho de algoritmos distribuídos utilizados na construção de arquivos invertidos e a compressão de arquivos de histórico utilizados em máquinas de busca modernas.