next up previous


Busca por Frases em Bancos de Dados Textuais

Marcus Vinícios Rocha - Mateus Conrad B. da Costa - Pedro de Alcântara dos Santos Neto

mvrocha@dcc.ufmg.br - mcosta@dcc.ufmg.br - pasn@dcc.ufmg.br


Introdução

Encontrar a informação desejada na Web é uma atividade que depende do uso de máquinas de busca e, consequentemente, de sua eficiência e eficácia. Para permitir a busca por palavras chaves, frases ou consultas booleanas no conteúdo completo de textos (full text searching), as ferramentas de busca varrem a Web, fazendo o download dos textos, indexando seu conteúdo. Desde dezembro de 1997, a relação entre a cobertura relativa de índices de máquinas de busca e o número estimado de páginas públicas indexáveis na Web tem reduzido substancialmente. Em 1999 nenhum índice cobria mais do que 16% do tamanho estimado da Web indexável [9]. Neste mesmo ano, o número estimado de páginas públicas indexáveis era de 800 milhões, totalizando cerca de 15 terabytes de dados ou 6 terabytes de texto, após a remoção de rótulos HTML, comentários e espaços em branco [9].

Uma consequência do crescimento da Web, além da invisibilidade da maior parte deste conteúdo, é o aumento do esparsamento do mapeamento destes índices sobre o conteúdo público indexável, podendo tornar vagas, consultas feitas por palavras chave ou combinações booleanas [8]. Uma alternativa para aumentar a precisão na busca de informações na Web é a pesquisa por frases, na qual, o usuário especifica uma frase completa que deseja encontrar na base de dados.

Entretanto, para a realização de busca por frases, máquinas de busca devem incorporar métodos apropriados. Este artigo apresenta uma comparação entre os resultados obtidos em implementações de mecanismos de busca por frases utilizando índices de arquivos invertidos com contadores de posição e índices para a próxima palavra (Nextword Indexes)[8].

Técnicas de busca por frases em bancos de dados textuais

Um banco de dados textual é uma coleção de documentos, que pode também ser visto como um largo conjunto de registros, em que cada registro contém apenas uma lista de palavras de tamanho arbitrário. Os dois métodos principais de busca por frases em bancos de dados textuais de larga escala, utilizando indexação de textos, são os arquivos invertidos com contadores de posição e índices para a próxima palavra[12]. Um arquivo invertido possui duas partes principais: uma estrutura de busca, chamada de vocabulário, contendo todos os termos distintos existentes no texto indexados e, para cada termo, uma lista invertida que armazena os identificadores dos registros contendo o termo. Consultas são feitas tomando-se a lista invertida correspondente ao termo procurado. As consultas booleanas são feitas obtendo-se a conjunção ou disjunção entre as listas relativas ao termos presentes na consulta. Arquivos invertidos podem ser utilizados para busca de frases, através da adição de mais informações a lista invertida. Basicamente, adiciona-se os deslocamentos no texto em que ocorrem as palavras.

Os índices para a próxima palavra apresentam uma abordagem mais eficiente do que o uso de arquivos invertidos com contadores de posição. Nessa abordagem, para cada palavra existente no vocabulário é criado uma lista com as palavras que ocorrem em uma posição subsequente no texto, juntamente com apontadores de posição para essas ocorrências.

Este trabalho apresenta em detalhes essas 2 técnicas, com uma breve comparação entre elas. Na seção 2 detalhamos os índices invertidos com contadores de posição. Na seção 3 demonstramos os índices para a próxima palavra. Na seção 4, apresentamos algumas técnicas de compressão, em especial, técnicas a serem aplicadas para o índice para a próxima palavra. Finalizando, na seção 5 apresentamos nossas conclusões e, na seção 6, sugerimos alguns trabalhos futuros.

Índices Invertidos com Contadores de Posição

Arquivos invertidos são tradicionalmente usados para a implementação de índices lexicográficos, ou seja, de índices ordenados [7]. Aplicado ao contexto de pesquisas por frases, um arquivo invertido pode ser visto como uma lista ordenada de palavras-chave contendo, para cada palavra, um apontador para cada um dos documentos em que a palavra ocorre, juntamente com a posição da palavra nesse documento. Este tipo de índice torna uma busca bem mais eficiente, no entanto, ela possui um custo adicional. A dimensão de um arquivo invertido é da ordem de 10 a 100% do tamanho do texto original [7]. Além disso, a cada atualização dos documentos originais, é necessário atualizar o arquivo invertido. A figura 1 mostra esquematicamente um arquivo invertido onde $D1,D2,\ldots \, Dn$ são documentos indexados, e $O1,O2,\ldots \, On$são as localizações em que as palavras ocorrem nesses documentos.


  
Figura 1: Esquema de um arquivo invertido
\begin{figure}
\centering

\includegraphics [width=80mm]{figinv.eps}

\end{figure}

Em busca do compromisso adequado entre capacidade de pesquisa e uso efetivo de recursos, é comum impor certas restrições ao arquivo invertido e, consequentemente, à capacidade de pesquisa possibilitada. Restrições no vocabulário (remoção de palavras mais frequentes, artigos e preposições, por exemplo), tornam o arquivo invertido menor e aceleram as consultas, sob o risco de torná-las mais imprecisas (justamente pela remoção de palavras que podem ser relevantes).

Um arquivo invertido como o mostrado na figura 1, pode ser aplicado diretamente na busca por um termo único. Em uma busca por frases fazemos múltiplas pesquisas, procurando ocorrências sucessivas dos termos em um documento. O encadeamento das múltiplas pesquisas é feito do seguinte modo:

1.
O primeiro termo é pesquisado. Como resultado, temos uma lista temporária de documentos e posições do termo nos documentos.
2.
O próximo termo é pesquisado nos documentos existentes na lista temporária, sendo retirados dela, os documentos em que o termo não ocorre na posição adequada (posição subsequente ao termo anteriormente pesquisado).
3.
O processo se repete até que o último termo tenha sido encontrado, ou até que a lista temporária fique vazia, indicando que a frase não foi encontrada.
Se considerarmos que este processo que executamos é uma repetição de mesclagens (merge ) de listas, teremos custo linear para o processo de busca. O custo em espaço também será linear, uma vez que é alocada uma entrada na lista temporária para cada ocorrência de um termo. Fica claro que a ordem de busca dos termos da frase é de fundamental importância. A cada passo da pesquisa, a lista temporária sofre apenas remoções. Assim, devemos iniciar a busca pelo termo menos frequente (fazendo a pesquisa em ordem diferente da ordem de ocorrência de termos na frase). Com esta alteração na ordem, minimizamos tempo e espaço, já que a lista temporária será iniciada com o menor tamanho possível.

A pesquisa iniciando por palavras com muitas ocorrências no texto pode levar a lista temporária a uma dimensão intratável. Em nossos experimentos, pudemos constatar que, ao efetuar uma consulta na ordem direta, iniciando a busca com uma palavra muito frequente, o equipamento de testes entrou em thrash [*], inviabilizando a execução da consulta para conjuntos de documentos com tamanho acima de 20MB.

Diversas técnicas de otimização podem ser empregadas na consulta de frases com arquivos invertidos. Uma otimização importante é a compressão desses arquivos. Como as dimensões de um arquivo invertido (10 a 100% do espaço indexado) o tornam impróprio para uso em memória primária, é uma prática manter os vetores de pesquisa em memória secundária. A redução do tempo de acesso a estes vetores, advinda da redução de ocupação de disco que a compactação propicia, permite ganhos de desempenho significativos [2].


  
Figura: Frequência de palavras
\begin{figure}
\centering

\includegraphics [width=80mm]{g_freqpal.eps}

\end{figure}

A questão das palavras mais comuns e do dicionário negativo [*] também têm fundamental importância. Se não incluirmos em um arquivo invertido as palavras constantes em um dicionário negativo, ou as palavras muito frequentes, porém pouco significativas, podemos reduzir a dimensão desses arquivos, com ganhos em espaço e tempo de processamento das consultas. Em nossos experimentos pudemos verificar a redução de espaço nos arquivos invertidos, conforme mostrado no gráfico 4. Também contatamos uma diminuição no tempo de indexação, conforme o demonstrado no gráfico 3.


  
Figura: Tamanho do índice
\begin{figure}
\centering

\includegraphics [width=80mm]{g_taminx.ps}

\end{figure}

Para a construção dos índices foram eliminadas as 10 palavras mais comuns, que correspondem a cerca de 20% do total de palavras nos documentos. Os ganhos em espaço são mais significativos se considerarmos que a operação de consulta é mais frequente que a de indexação. A principal perda é justamente a eliminação de termos que podem se tornar relevantes em alguma situação particular. Um exemplo clássico é uma frase composta apenas por palavras comuns, que não poderá ser respondida pela consulta ao arquivo invertido, caso tenhamos ignorado essas palavras na consutrução do índice.


  
Figura: Tempo de indexação
\begin{figure}
\centering

\includegraphics [width=80mm]{g_tempoinx.eps}

\end{figure}

Implementação

Implementamos um esquema simplificado de listas invertidas para permitir o levantamento de algumas informações características deste tipo de índice e sua comparação com outros tipos de indexação. Nesta implementação todo o índice foi mantido em memória primária. Para a criação do vocabulário foi usada uma árvore binária. Cada nó da árvore contém uma lista de ocorrências da palavra indexada. Cada nó da lista contém uma lista de ocorrências da palavra no documento. Para a medição de espaço foram considerados os campos da estrutura que seriam armazenados em um arquivo no disco: palavras do vocabulário, nomes de arquivos e localização das palavras nesses arquivos. Nenhum esquema de compactação foi considerado. As medições efetuadas permitiram confirmar os resultados previstos pela lieratura com relação a complexidade de tempo e espaço e importância da eliminação de palavras comuns.

Índices para Próxima Palavra

Arquivos invertidos permitem a avaliação de consultas por frases, mas as abordagens orientadas a indexação de frases são mais eficientes. Uma dessas abordagens é conhecida como índice para próxima palavra [8].

Um índice para a próxima palavra consiste de um vocabulário de palavras distintas e, para cada uma dessas palavras w, uma lista com as próximas palavras que a sucedem. A lista de próximas palavras consiste de todas as palavras s que sucedem w em algum local da base de documentos. Para cada par ws existe uma seqüência de localidades, determinando o documento e a posição em que esse par ocorreu [8].


  
Figura: Exemplo de índices para a próxima palavra.
\begin{figure}
\centering

\includegraphics [width=80mm]{nextex.ps}

\end{figure}

Na figura 5 temos um exemplo desses índices. No primeiro nível deles temos as palavras do vocabulário. Essas palavras correspondem às palavras existentes na base de dados que possuem uma palavra sucessora. No segundo nível temos o índice para a próxima palavra. Os dois primeiros níveis são implementados como árvores binárias. Cada palavra no primeiro nível contém um ponteiro para uma árvore de próximas palavras. Essa árvore contém o endereço de início de uma lista de documentos em que o par de palavras ocorre. Cada documento dessa lista possui o endereço de uma outra lista contendo as posições em que ocorreram esses pares. Através dessas posições podemos testar a ocorrência de frases.

Para a recuperação da frase ``the man who is'', inicialmente devemos determinar os pares a serem pesquisados. Uma vez que o número de palavras na frase é par, podemos agrupar em $\frac{n}{2}$ pesquisas ao índice de próxima palavra. Dessa forma, realizamos a recuperação do par ``the man'', juntamente com a recuperação do par ``who is''. Analisando a figura 5, notamos que o par ``the man'' ocorre no documento 5, na posição 235. Fazendo o mesmo para o par ``who is'', podemos constatar sua ocorrência no mesmo documento 2 posições subseqüentes. Isso significa que os pares se sucedem no texto. Pares distintos são sucessivos se ocorrem com diferença de 2 posições. Pares compostos são sucessivos se possuem diferença de 1 posição. Se a consulta desejada fosse a frase ``the man who'', estaríamos impossibilitados de dividir a frase em pares distintos. Nesse caso, teríamos que procurar o par ``the man'' e o par ``man who''. Esses pares, para serem considerado sucessivos, devem ocorrer com uma diferença de 1 posição nos índices. Existem diversas técnicas para otimizar a pesquisa por frases. Na seção 3.2 discutimos essas alternativas.

A técnica de índice para a próxima palavra pode auxiliar não apenas na pesquisa por frases. Dentre suas outras utilidades destacamos [8]:

Abordagem combinada

Os logs do Excite de 1997 a 1999, tendo retirado as consultas de teor pornográfico, apresentaram 1.583.922 consultas, incluindo as consultas duplicadas. Nessas consultas, 132.276 eram consultas explícitas a frases. Do conjunto total de consultas, apenas 5% possuía uma palavra que não existia no texto. De todas as consultas que não eram frases, 41% possuíam frases encontradas na base de dados (contendo 21.9 Gb de informações). Em 8,4% das consultas realizadas existia uma das 3 palavras mais comuns da língua inglesa.

Baseado nesse grande número de ocorrências de palavras comuns foi proposto uma abordagem híbrida, combinando arquivos invertidos e índices para a próxima palavra [3]. Esta técnica tem como objetivo manter a eficiência das consultas, ao mesmo tempo que se propõe a diminuir o tamanho dos índices gerados.

Nesse esquema, denominado esquema baseado na freqüência máxima (top frequency), é utilizado o fato das palavras comuns existirem em grande parte das consultas para melhorar o tempo de resposta. Nesse caso, apenas as palavras mais comuns são utilizadas como índice para a próxima palavra. O restante das palavras é indexado normalmente, na forma de índices invertidos. As palavras comuns também são indexadas como índices invertidos, uma vez que elas podem ocorrer em final de frases.


  
Figura: Exemplo de índice utilizando a abordagem combinada.
\begin{figure}
\centering

\includegraphics [width=80mm]{nextinv.ps}

\end{figure}

Na figura 6 temos um exemplo dessa abordagem. Nela, temos um vocabulário com 5 palavras, sendo duas palavras comuns (the, who). No caso de uma consulta pela frase ``the man who is very tall'', iniciamos pelos pares que começam por palavras comuns. Assim, realizamos a busca dos índices para ``the man'' e ``who is''. Como as palavras very e tall não são palavras comuns, devemos recuperar seus índices invertidos, para posterior combinação dos resultados, descobrindo assim, onde eles se sucedem. No caso dos dois pares com palavras comuns, encontramos no documento 5 uma sucessão. Precisamos realizar a pesquisa na lista dos dois outros vocábulos para descobrir se eles também aparecem no documento 5.

A pesquisa nos índices para a próxima palavra propicia uma redução na quantidade de elementos a pesquisar. Este é o ponto chave para melhoria no desempenho. Com menos itens a verificar, serão necessários menos acessos ao disco, reduzindo o tempo de resposta.

 
 
Tabela: Tempo de Consulta
Número de Tempo Total Consultas Consultas
Palavras Comuns   com 2 palavras com 5 palavras
  1,56 0,49 6,41
3 0,76 0,31 2,28
6 0,57 0,31 2,28
10 0,53 0,30 2,10
20 0,50 0,30 1,98
254 0,46 0,27 1,83

Na tabela 1, temos uma comparação entre consultas a frases utilizando arquivos invertidos e a abordagem combinada [3]. Nela podemos visualizar o ganho de desempenho obtido com a introdução de poucas palavras comuns em um índice para a próxima palavra. Na tabela 2 temos o tamanho do índice para a próxima palavra, utilizado na abordagem híbrida, com diferentes quantidades de palavras comuns utilizadas na sua construção [3]. Nessa tabela temos ainda uma comparação desse tamanho, em relação ao tamanho total do índice invertido.

A utilização exclusiva dos índices para a próxima palavra tem o incoveniente de duplicar o tamanho dos índices, além de dificultar a pesquisa por ordem (rank). A abordagem combinada reduz o tamanho dos índices e mantem uma estrutura mais adequada para a pesquisa por ordem.

 

 
Tabela: Tamanho dos índices
Número de Tamanho % em Relação ao
Palavras Comuns do Índice Índice Invertido
3 254 10,81%
6 427 18,17%
10 520 22,13%
20 657 27,46 %
254 1366 58,13%


Planejamento de consultas

A utilização de consultas com índices para a próxima palavra traz mais eficiência às pesquisas. Essa eficiência pode ainda ser melhorada através de um melhor planejamento das consultas a serem realizadas. Esse planejamento refere-se à forma como os pares são selecionados para a pesquisa [2].

Como exemplo, suponha a realização da pesquisa pela frase ``1980 year of the Tiger''. Quando possuímos uma quantidade par de palavras, podemos simplesmente combiná-las duas a duas para montar a consulta. No caso de um número ímpar de palavras, podemos apenas agrupar os itens 2 a 2 e, no caso do último item, realizarmos uma combinação com a penúltima palavra. Nesse caso teremos $\frac{n}{2}+1$ pares para consulta. No caso da frase acima, selecionamos os pares ``1980 year'', ``of the'' e ``the Tiger''.

Essa abordagem de simplesmente agrupar os pares, sem levar em consideração a quantidade de ocorrências desses pares, é chamada de estratégia descuidada (naive) [2]. Essa abordagem usa o mínimo possível de pares para a consulta. Uma outra abordagem, denominada abordagem mínima, usa também o mínimo possível de pares, no entanto, todos os possíveis agrupamentos são analisados à busca dos pares que possuem menos ocorrências, facilitando assim o conjunto total a ser pesquisado. Em uma outra estratégia, chamada de estratégia ordenada, realizamos todas as possíveis combinações permitidas entre os pares de palavras, buscando uma combinação que minimize o conjunto de pesquisa. Nessa procura, podemos encontrar um número de pares maior que o mínimo exigido, diferentemente das técnicas anteriores.

As abordagens descuidada e mínima ainda podem ser otimizadas através de uma ordenação na ordem de avaliação dos pares. Nesse caso, iniciamos a consulta pelo par com maior raridade de ocorrência, continuando o casamento pelos pares restantes (ordenados por raridade), até que todo o conjunto de pares tenha sido pesquisado.

Na figura 7 temos uma comparação entre os tempos de resposta para essas abordagens [2]. Nela podemos constatar que o planejamento das consultas traz ganho de desempenho. As consultas utilizando a abordagem ordenada obtiveram melhor desempenho, seguido pela abordagem mínima ordenada e a abordagem descuidade ordenada. Embora teoricamente a abordagem descuidada ordenada devesse sempre obter tempos melhores que a abordagem sem ordenação, o gasto proveniente com essa ordenação influencia no resultado final, uma vez que ela não consegue ganhos significativos na pesquisa. Os ganhos obtidos com a abordagem ordenada justificam a introdução de pares adicionais, uma vez que seu tempo de resposta foi quase sempre o melhor dentre todas as abordagens.


  
Figura: Comparação do tempo de execução das diferentes estratégias de planejamento.
\begin{figure}
\centering

\includegraphics [width=80mm]{planquery2.ps}

\end{figure}

Experimentos realizados

Realizamos a implementação de um algoritmo para a indexação e busca utilizando arquivo invertido, e um algoritmo para indexação e busca utilizando índices para próxima palavra. Esses programas não foram otimizados, sendo utilizados apenas para constatar a grande diferença de desempenho entre as técnicas.

Para a realização das comparações, utilizamos arquivos com diversos documentos do Wall Street Journal, disponíveis na rede interna do DCC. Os testes consistiram na utilização de 3 arquivos com 2, 10 e 20Mb de tamanho. Nas figuras 3 e 4 temos uma comparação entre os tamanhos dos índices e o tempo gasto na indexação das palavras por cada uma das abordagens.

Criamos um conjunto de 150 consultas aleatórias para cada um dos arquivos. Essas consultas possuíam 50 frases com 2 palavras, 50 com 4 palavras e 50 com 6 palavras. Essas consultas foram submetidas aos 2 programas, realizando a contabilização do tempo gasto para cada resposta.

A diferença de desempenho obtida foi muito grande. O índice para a próxima palavra conseguiu respostas, em média, 3 ordens de grandeza mais rápidas que as respostas utilizando arquivos invertidos. Na tabela 3 temos uma comparação nos desempenhos dos programas. Essa tabela mostra a média de tempo das consultas realizadas no arquivo de 10Mb para frases com 2, 4 e 6 palavras.


 

 
Tabela: Tempos de resposta
Palavras Tempo médio Tempo médio
  em arquivos invertidos em Nextword
2 0,150 0,00005
4 0,271 0,00011
6 0,267 0,00036


Compressão de Índices

O objetivo principal do uso de qualquer estrutura de índices é aumentar a velocidade de recuperação da informação indexada. Como pudemos observar nos experimentos, o tamanho das listas de arquivos invertidos e índices para próxima palavra assumem proporções grandes com relação ao texto indexado. Este problema tem sido abordado sob dois pontos de vista: A aplicação direta de algoritmos de compactação de números inteiros (convenientes para listas invertidas), tais como os códigos delta e gama de Elias, a codificação Golomb-Rice[10] orientados a bits (bitwise) e esquemas orientados a Bytes (Bytewise). Uma outra abordagem é a busca por esquemas de representação de listas que facilitem a compactação[2].

O uso de compressão reduz tanto o tamanho dos arquivos de índices quanto o tempo necessário para avaliação de consultas[10]. Sem o uso de compressão, o custo de recuperação de listas invertidas é a soma entre o tempo gasto na procura e recuperação da lista no disco, aliado ao tempo gasto para transferir a lista para o cache da CPU, antes desta ser processada. Usando listas compactadas, a velocidade de acesso às listas invertidas fica em função dos requisitos computacionais para a decodificação dos dados e o tempo necessário para recuperá-la do disco e disponibiliza-la no cache da CPU, para posterior processamento.

Para que um esquema de compressão permita acesso relativo rápido a listas invertidas, a soma do tempo de recuperação das listas e o processamento adicional de decodificação deve ser menor que o tempo de recuperação de listas não comprimidas. Um aspecto que torna o uso de compactação ainda mais atrativo é ela aumenta o número de listas invertidas presentes no cache da memória, reduzindo o número de acessos a disco[10].

Algoritmos de compactação

Algoritmos de compactação podem usar combinações adequadas para cada classe de informação armazenada. Na compactação de índices invertidos com deslocamento, utilizados na busca por frases, pode-se usar os esquemas orientados a bits (códigos de Elias e Golomb-Rice) e esquemas orientados a Bytes (Bytewise) para representar identificadores de documentos, juntamente com a frequência do termo no documento e os deslocamentos existentes.

Melhores resultados podem ser obtidos com a compressão orientada a Bytes[10]. Nesta, um inteiro k é representado em uma sequência de blocos de 8 bits, onde os 7 bits menos significativos são usados para representar o valor e o bit remanescente é usado para indicar se o respectivo bloco é o último ou se existe um próximo bloco. Por exemplo, para os números inteiros entre 27 e 214, dois blocos são necessários para obter todas as representações. O primeiro bloco contém os 7 bits menos significativos do número e o oitavo bit é usado para indicar que existe um próximo bloco. O segundo bloco contém os bits mais significativos restantes e o oitavo bit indica que o bloco é o último.

Representação eficiente de índices para próxima palavra

O principal objetivo dos esquemas alternativos de deslocamentos é prover informação suficiente para a localização de elementos dentro de um conjunto, minimizando o espaço necessário para armazená-los. Isso pode ser alcançado através do uso de algoritmos especializados de compressão [4] [6] [11], ou através de formas alternativas de otimização no armazenamento dos deslocamentos.

Baseando-se na premissa que em consultas por frases não é necessário saber a posição absoluta de uma palavra dentro de um documento, técnicas alternativas de cálculo do deslocamento de palavras podem ser desenvolvidas [2], utilizando as posições relativas das palavras nas frases, causando uma redução no tamanho dos números armazenados, e, propiciando assim, uma diminuição no tamanho total dos índices.

Indicadores compostos

Os indicadores de posição nos índices para a próxima palavra são grandes, tipicamente em torno de 50% do tamanho do texto indexado [8]. Eles devem ser suficientemente eficientes para identificar se as palavras ocorrem de forma sucessiva em um texto, não importando aonde essas palavras ocorrem.

A técnica de indicadores compostos é baseada nessa idéia. Nesse caso, cada ocorrência de uma palavra w em um texto tem um número associado. Esse número é n se a ocorrência em questão é a enésima no texto. Na tabela 4 temos um exemplo dessa forma de cálculo dos deslocamentos.

Nesse exemplo, para testarmos a ocorrência de uma frase w1w2w3, devemos descobrir se existe um índice composto para w1w2 e para w2w3 no documento. Se esses índices existirem e, os índices para w2 forem os mesmos, então as palavras w1, w2 e w3 se sucedem dentro do documento, existindo a frase em questão. Para a pesquisa pela frase ``time the red'', encontramos os índices compostos para ``time the'' e para ``the red''. Como o índice para a palavra the é o mesmo (tabela 4), a frase ocorre no texto.


 

 
Tabela: Cálculo do deslocamento utilizando indicadores compostos
Texto the first time the red dog saw the cat
Desl. 1 1 1 2 1 1 1 3 1



 

 
Tabela: Cálculo do deslocamento baseado em palavras repetidas
Texto the first time the red dog saw the cat
Desl 1 1 2 3 3 3 4 5 6


Deslocamento baseado em palavras repetidas

Deslocamentos que nos permitam distinguir entre ocorrências repetidas de uma mesma palavra em um texto são suficientes para a avaliação de consultas por frases.

Uma outra alternativa para representação dos deslocamentos é a representação baseada em palavras repetidas. Nesse caso, uitilizamos um contador para o deslocamento que somente é incrementado quando uma palavra se repete. Para eliminar a possibilidade de casamentos falsos, esse contador é incrementado por 2 em 2 passos. Devemos incrementar a ocorrência de 1, uma palavra antes da nova ocorrência do termo, e mais uma vez de 1 quando realmente o termo ocorre novamente. Na tabela 5 temos um exemplo dessa forma de cálculo do deslocamento.

Na tabela 6 temos uma comparação do tamanho dos índices obtidos com as técnicas de compactação citadas anteriormente. Podemos notar que os índices compostos apresentam um melhor aproveitamento do espaço, obtendo maiores reduções no tamanho total dos índices (medidos em Gb).


 

 
Tabela: Comparativo do tamanho do índice para próxima palavra com compactação
Tamanho do Índices Web WSJ
Normal 4,37 0,25
Composto 3,81 0,21
Palavras Repetidas 3,99 0,22


Conclusão

Analisando os resultados dos experimentos realizados, foi possível constatar a superioridade do índice para próxima palavra. Os resultados obtidos demonstraram que o tempo de resposta utilizando esse índice chegou a ser ordens de grandeza superior ao índice invertido. Apesar desses resultados estarem de acordo com o previsto na literatura, a enorme discrepância entre eles sugere que seja necessário realizar um estudo mais detalhado das implementações.

Apesar da superioridade de desempenho do índice para a próxima palavra, o índice invertido é superior em alguns aspectos. O tempo necessário para indexação de uma base de dados foi, em média, dez vezes menor que o tempo exigido pelo índice para próxima palavra (figura 4). Alem disso, o tamanho do índice para próxima palavra fica em torno de 2 vezes o tamanho dos índices invertidos (figura 3). Essas limitações sugerem a utilização dos índices para próxima palavra juntamente com técnicas de compactação, reduzindo assim suas fraquezas.

A abordagem combinada incorpora as características de desempenho do índice para a proxima palavra, ao mesmo tempo que permite a decisão sobre quanto a mais de espaço estamos dispostos a gastar. Isso é um fator atrativo, diante dos ganhos possibilitados.

Trabalhos Futuros

Para uma análise mais detalhada das abordagens, sugerimos como trabalhos futuros a otimização das implementações, juntamente com a implementação da abordagem combinada, submetendo-as a consultas reais geradas por uma máquina de busca. Com isso, teremos uma análise mais precisa do comportamento das abordagens em casos reais. Alternativamente, poderíamos utilizar a abordagem combinada, utilizando como palavras comuns as palavras que mais ocorrerem nas consultas. Nesse caso, os índices deveriam ser refeitos a cada intervalo de tempo predefinido, após a ordenação das palavras mais utilizadas, para que o ganho com desempenho se torne o máximo.

Também sugerimos a utilização de alguma técnica de compactação para testar os ganhos produzidos com desempenho e tamanho dos índices, no caso específico dos índices para a próxima palavra.

Bibliografia

1
BAHLE D., WILLIAMS H. E., ZOBEL J. Efficient phrase querying with an auxiliary index. Proceeding of the twenty-fifth annual international conference on Research and development in information retrieval, August 2002. Tampere, Finland.

2
BAHLE D. WILLIAMS H. E. ZOBEL J. Compactation Technics for Nextword Indexes. In Proc. 8th International Symposium on String Processing and Information Retrieval (SPIRE2001), 2001.

3
BAHLE D. WILLIAMS H. E. ZOBEL J.Optimised Phrase Querying and Browsing of Large Text Database. Proceedings of the Australasian Computer Science Conference, M. Oudshoorn (ed), Gold Coast, Australia, January, 2001, pp. 11-19.

4
ELIAS P. Universal codeword sets and representation of integers. IEEE Transaction on Information Theory, IT 21(2):194-203, Mar. 1975.

5
GLOVER E. J. , LAWRENCE S. ,GORDON M. D., BIRMINGHAN W. P., GILES C. L. Web Search - Your Way. Communications of the ACM. December 2001, Volume 44 Issue 12.

6
GOLOMB S. Run-Length encodings. IEEE Transaction on Information Theory, IT-12(3):399-401, july 1966.

7
HARMAN, D., FOX, E., BAEZA-YATES, R., Lee, W., Inverted Files , in Information Retrieval - Data Structures & Algorithms, Prentice Hall, 1992.

8
HUGH E. W., ZOBEL J., ANDERSON P. What's Next? Index Structures for efficient phrases quieryng. Proceedings of the Tenth Australasian Database Conference, Auckland, New Zeland, January 18-21, 1999.

9
LAWRENCE S., GILES C. L. Accessibility and Distribution of Information on the Web. Nature, Vol. 400, pp. 107-109, 1999.

10
SCHOLER F. WILLIAMS H. E. ZOBEL J. Compression of Inverted Index For fast query evaluation. ACM SIGIR'02, August, 11-15, 2002. Tampere, Finland.

11
WITTEN I. MOFFAT A., BELL T. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers, Los Altos, CA - USA, 1999.

12
ZOBEL J.Inverted files versus signatures files for text indexing. ACM Transaction on Database Systems, Vol. 23, No. 4, December, 1998, Pages 453-490.

About this document ...

Busca por Frases em Bancos de Dados Textuais

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 s.

The translation was initiated by pedro de alcantara dos santos neto on 9/25/2002


Footnotes

...thrash
Dizemos que o sistema operacional entra em thrash quando o acesso à memória virtual tem baixa localidade, e exige que se efetuem repaginações constantes, de tal forma que a maior parte dos recursos é usado nesta paginação, e não na execução de programas de usuários.

...negativo
Dicionário negativo é um conjunto de palavras que são pouco significativas na formação de expressões de busca.


next up previous
pedro de alcantara dos santos neto
9/25/2002