Recuperação de Informação em Dados Semi

Universidade Federal de Uberlândia
RENATO DE AQUINO LOPES
Recuperação de Informação em Dados Semiestruturados Utilizando o Modelo Vetorial
Uberlândia
2003
RENATO DE AQUINO LOPES
Recuperação de Informação em Dados Semi-estruturados
Utilizando o Modelo Vetorial
Dissertação apresentada ao programa de
pós-graduação em Ciência da Computação da
Universidade Federal de Uberlândia, como
requisito parcial para a obtenção do título de
mestre em Ciência da Computação.
Área de concentração: Banco de Dados
Orientador: Professor Dr. Ilmério Reis Silva
UBERLÂNDIA – MG
Universidade Federal de Uberlândia – UFU
2003
Renato de Aquino Lopes
Recuperação de Informação em Dados Semi-estruturados
Utilizando o Modelo Vetorial
Dissertação apresentada ao Programa
de Pós graduação em Ciência da Computação
da Universidade Federal de Uberlândia, para
obtenção do grau de Mestre em Ciência da
Computação.
Área de concentração: Banco de Dados
Banca Examinadora:
Uberlândia, 15 de Dezembro de 2003.
Prof. Dr. Ilmério Reis da Silva – Orientador – UFU
Prof. Dr. João Nunes de Souza Co-Orientador – UFU
Prof. Dr. Berthier Ribeiro de Araújo Neto – UFMG
Prof. Dr. Autran Macêdo – UFU
Aos meus pais, pelo apoio
dedicação, carinho e por
estarem sempre ao meu
lado.
AGRADECIMENTOS
A Deus pela vida.
À Universidade Federal de Uberlândia e à Faculdade de Computação pela
oportunidade de realizar este curso.
Aos meu pais pelo estímulo e companheirismo.
Ao grupo de Recuperação de Informação da Universidade Federal de
Uberlândia.
A todas as pessoas que direta ou indiretamente contribuíram para a
concretização dessa dissertação.
Resumo
A recuperação de informação tradicional propõe modelos que definem como representar
consultas e documentos sem estrutura e uma métrica para calcular a similaridade entre eles.
Dentre esses modelos, o modelo vetorial clássico é o mais popular da recuperação de
informação tradicional, em função de seu desempenho e fácil implementação. Por outro lado,
em coleções de documentos semi-estruturados, o uso da informação de estrutura dos
documentos no cálculo do ranking pode aumentar a precisão da resposta. Neste trabalho,
documentos semi-estruturados são documentos XML representados como árvores onde os nós
internos representam informação de estrutura e as folhas informação de conteúdo. Os modelos
clássicos da recuperação de informação não consideram essa informação de estrutura. Neste
sentido a motivação deste trabalho é aliar as vantagens de uma coleção de documentos semiestruturados à simplicidade de implementação e desempenho do modelo vetorial. Para atingir
esse objetivo, a proposta aqui apresentada é acrescentar informação de contexto ao domínio
de termos. Entretanto, o acréscimo desses termos pode levar a um crescimento exponencial na
quantidade de termos do vocabulário. Para evitar esse aumento de termos, são propostas
estratégias para diminuir a quantidade de termos a serem adicionados. Essas estratégias
consistem no descarte de alguns termos e na indexação de conjuntos de termos. Dessa
maneira, viabiliza-se a extensão do modelo vetorial para utilizar a informação de estrutura no
cálculo da similaridade entre documentos e consultas. Assim, a principal contribuição deste
trabalho é ampliar o domínio de termos do modelo vetorial, inserindo termos com informação
de contexto sem causar o aumento exponencial na quantidade de termos do vocabulário da
coleção.
Abstract
The models of traditional information retrieval define how to represent queries and documents
without structure and a metric to calculate the similarity among them. The classic vector space
model is the most popular one in traditional information retrieval because of its good
performance and easy implementation. On the other hand, in semi-structured document
collections the use of information obtained from the structure to calculate the ranking can
increase the precision of the answer set. In this work, semi-structured documents are XML
documents which are represented as trees. In these trees the internal nodes represent the
context information and the leaves nodes represent content information. The classical models
of information retrieval ignore this kind of information. The motivation of this work is to join
the advantages of semi-structured document collection to the simplicity and performance of
the vector space model. To reach this goal we propose to add terms with structured
information in the traditional information retrieval term domain. However, the addition of this
type of terms can lead to an exponential increase of the number of terms in the vocabulary. To
avoid this problem we propose strategies to decrease the number of terms that will be added
in the term domain. These strategies consist of discarding some terms and indexing sets of
terms instead of the terms themselves. So, it is viable to extend the vector model to use
information about the structure of documents to calculate the similarity among queries and
documents. Then, the main contribution of this work is to enlarge the terms domain of vector
space model, adding terms with context information without to produce an exponential
number of terms in the vocabulary of the collection.
Sumário
CAPÍTULO 1....................................................................................................................................................... 11
INTRODUÇÃO...................................................................................................................................................... 11
CAPÍTULO 2....................................................................................................................................................... 16
FUNDAMENTOS DE XML E RECUPERAÇÃO DE INFORMAÇÃO ............................................................................. 16
2.1 – Linguagens de Marcação ..................................................................................................................... 17
2.2 – Recuperação de Informação................................................................................................................. 20
2.2.1 – Conceitos Clássicos da Recuperação de Informação........................................................................................21
2.2.2 – Modelo Vetorial ...............................................................................................................................................22
2.3 – XML e Recuperação de Informação ..................................................................................................... 24
2.4 – Linguagens para Consulta a Documentos XML................................................................................... 26
2.5 –Árvores: Propriedades e Notação ......................................................................................................... 28
2.6 – Trabalhos Relacionados ....................................................................................................................... 30
CAPÍTULO 3....................................................................................................................................................... 36
UMA PROPOSTA PARA RECUPERAÇÃO DE INFORMAÇÃO EM DADOS SEMI-ESTRUTURADOS ............................... 36
3.1 – Extensão do Vocabulário da Recuperação de Informação Tradicional............................................... 37
3.2 – Aumento na Quantidade de Termos do Índice...................................................................................... 41
3.2.1 – Descarte de Termos Compostos sem Informação de Conteúdo .......................................................................42
3.2.2 – Descarte de Termos Derivados dos Termos Complexos que não são Sub-árvores ..........................................42
3.2.3 – Conjunto de Termos como Unidade de Indexação...........................................................................................45
CAPÍTULO 4....................................................................................................................................................... 49
APLICAÇÃO DO ALGORITMO CHARM EM DOCUMENTOS XML ........................................................................ 49
4.1 – Notação ................................................................................................................................................ 50
4.2 – Árvore de Pesquisa Termset-Tidset ...................................................................................................... 52
4.3 – Propriedades Básicas dos pares Termset-Tidset.................................................................................. 53
4.4 – Algoritmo CHARM na Recuperação de Informação em Dados Semi-estruturados ............................. 55
4.4 - Cálculo da Similaridade no Modelo Proposto ...................................................................................... 67
4.4.1 – Estruturas Necessárias para o Cálculo da Similaridade...................................................................................67
4.4.2 – Exemplo do Cálculo da Similaridade...............................................................................................................68
CAPÍTULO 5....................................................................................................................................................... 74
EXPERIMENTOS .................................................................................................................................................. 74
5.1 – Estrutura da Coleção de Documentos .................................................................................................. 75
5.2 – Cálculo dos Closed termsets................................................................................................................. 76
CAPÍTULO 6....................................................................................................................................................... 80
CONCLUSÃO ....................................................................................................................................................... 80
REFERÊNCIAS BIBLIOGRÁFICAS............................................................................................................... 82
Lista de Figuras
Figura 1: Estrutura Básica de um Documento XML................................................................ 19
Figura 2: Visualização de um Documento XML...................................................................... 19
Figura 3: Exemplo de uma Estrutura de Árvore....................................................................... 29
Figura 4: Termo Complexo ...................................................................................................... 39
Figura 5: Domínio dos Termos................................................................................................. 39
Figura 6: Relação entre os Conjunto de Termos Complexos, Compostos, Estendidos,
Complementares e Termos que não Possuem Informação de Conteúdo........................... 45
Figura 7: Coleção D de Documentos........................................................................................ 51
Figura 8: Árvore de Pesquisa Termset-Tidset do Exemplo 1................................................... 54
Figura 9: Pseudo Código do Algoritmo CHARM .................................................................... 56
Figura 10: Coleção o D de documentos Semi-estruturados do Exemplo 2. ............................. 59
Figura 11: Vocabulário do Exemplo 2 ..................................................................................... 60
Figura 12: Processo de Busca para o Exemplo 2 Usando Tidsets............................................ 62
Figura 13: Coleção D’ de documentos semi-estruturados do Exemplo 3 ................................ 64
Figura 14: Vocabulário do Exemplo 3 ..................................................................................... 65
Figura 15: Árvore Termset-Tidset para os termos da consulta q. ............................................ 69
Figura 16: Lista Invertida da Coleção de Documentos D’. ...................................................... 72
Figura 18: Estrutura da Coleção de Documentos do BDPT..................................................... 78
Figura 19: Estrutura Interna da Coleção de Documentos do BDPT......................................... 78
Figura 20: Esquema para o cálculo dos closed termsets para a coleção de documentos do
BDPT ................................................................................................................................. 79
Lista de Tabelas
Tabela 1: Diferenças Principais entre SQL e XQL .................................................................. 27
Tabela 2: Frequent, Closed e Maximal Termsets para a Coleção de Documentos .................. 51
Tabela 3: Comparação da Quantidade de Termos Indexados do Exemplo 2........................... 63
Tabela 4: Comparação da Quantidade de Termo Indexados do Exemplo 3 ............................ 66
Tabela 5: Índices dos termos da consulta q .............................................................................. 68
Tabela 6: Estatísticas da Aplicação do Algoritmo CHARM no BDPT.................................... 77
11
Capítulo 1
Introdução
Antes do surgimento da informática, em geral, os dados eram registrados em papel. Isto
acarretava grandes dificuldades de armazenamento, conservação e, principalmente, de
recuperação da informação. Com o desenvolvimento do computador e meios de
armazenamento modernos, as pessoas passam a ter a possibilidade de produzir documentos
digitais além de documentos em papel. Então, a quantidade de informação produzida pela
sociedade cresce de forma exponencial. A internet é um exemplo desse crescimento. Neste
cenário, a pesquisa pela informação em um grande volume de dados pode ser muito custosa
do ponto de vista computacional. Portanto, o aperfeiçoamento das técnicas de
armazenamento e pesquisa são pontos fundamentais para a disponibilizar informação de
forma eficaz.
Um dos objetivos da tecnologia de banco de dados é propor maneiras de estruturar,
pesquisar e gerenciar dados que se encontram no formato digital. Por exemplo, nos bancos de
dados relacionais os dados são gravadas em tabelas que possuem um relacionamento entre si.
A pesquisa é efetuada através de uma linguagem de consulta, por exemplo, o SQL. A resposta
dessas consultas é uma tabela. Por outro lado, um Sistema de Recuperação de Informação
(SRI) propõe a pesquisa por informação que não esteja estruturada. Estas informações são
textos sem estrutura armazenados em um formato digital que na recuperação de informação é
chamado documento.
Na área de recuperação de informação o objetivo é propor maneiras (modelos) de
pesquisar documentos e fornecer ao usuário, como resposta a suas consultas, uma lista de
12
documentos (ranking) que atendam a necessidade de informação do usuário. Um modelo de
recuperação de informação propõe uma representação e uma métrica para calcular a
similaridade entre documentos e consultas. Quanto maior a importância do documento para
uma dada consulta, maior será a sua medida de similaridade com relação a essa consulta. O
ranking é construído em ordem decrescente de similaridade.
A representação do documento em um SRI tradicional é feita de forma plana, ou seja,
sem informação de estrutura (contexto). Ele é representado por um conjunto de palavras
(termos). Este conjunto de palavras é o domínio de termos da recuperação de informação
tradicional. Portanto, um SRI tradicional não é capaz de utilizar a informação de estrutura de
uma consulta contextualizada no cálculo da similaridade. Neste trabalho, uma consulta
contextualizada é aquela na qual o usuário especifica em que parte da estrutura do documento
XML ele deseja que os termos consultados ocorram. Por exemplo, o usuário deseja pesquisar
por artigos que contenham os termos recuperação, informação e XML em seu título, em uma
coleção de documentos.
A utilização da informação de estrutura pelo SRI melhora a precisão do ranking,
conforme mostra o trabalho apresentado em [32]. Esta característica aliada ao crescente uso
da linguagem XML (eXtended Markup Language) têm direcionado os esforços na pesquisa da
recuperação de informação em dados semi-estruturados para a recuperação de informação em
documentos XML. Vário trabalhos estão sendo propostos nesta área [7, 18, 22, 31, 35, 37].
Há quatro tópicos de interesse na recuperação de informação em documentos XML [17]:
1. Modelos de Recuperação de Informação: O foco dos grupos classificados neste tópico é
a extensão de modelos de recuperação de informação tradicional para serem aplicados em
documentos XML. Essa extensão significa acrescentar a esses modelos a característica de
utilizar a informação de contexto dos documentos na resposta às consultas dos usuários;
2. Banco de Dados: Nesta área, há um crescente interesse em acrescentar aos gerenciadores
de banco de dados a característica de manipular dados semi-estruturados. Essa
característica consiste em
incorporar a pesquisa que considere a relevância entre
documentos e consulta para produzir um ranking;
3. XML Específico: Os grupos classificados neste tópico têm o objetivo de desenvolver
novos modelos e sistemas especificamente para XML;
4. Sistemas/Estrutura de Dados: Há vários grupos mais interessados nos aspectos
orientados a sistemas. Por exemplo, no desenvolvimento de novas estruturas de dados e
algoritmos para XML.
13
Este trabalho se insere no contexto do tópico 1, isto é, extensão do modelo vetorial
clássico para trabalhar coleções de documentos XML, empregando a informação de contexto
dos documentos para calcular o ranking.
Os SRI’s, em geral, utilizam estatísticas de ocorrência de termos nos documentos para
representá-los. Na recuperação de informação tradicional, estas estatísticas são pré-calculadas.
Dessa maneira, são construídos índices considerando todos os termos do vocabulário. Por
outro lado, quando se trabalha com documentos semi-estruturados, um dos problemas
encontrados é representar estas estatísticas de forma que elas considerem informação de
contexto. Esta representação pode levar ao crescimento exponencial de termos. Portanto,
existem duas linhas de pesquisa na recuperação de informação em dados semi-estruturados de
acordo com o momento em que esses cálculos são realizados. Na primeira, as abordagens
propostas geram as estatísticas necessárias para o cálculo da similaridade em tempo de
consulta. Assim, o conjunto de termos considerados para calcular as estatísticas é restringido,
observando a consulta do usuário. Na segunda, as estatísticas são geradas em uma fase de
pré-processamento, quando ocorre a indexação da coleção de documentos (como ocorre na
recuperação de informação tradicional). Nesta última linha de pesquisa são estudadas
estratégias para representar os termos com informação de estrutura e evitar seu aumento
exponencial. Apesar da vantagem de restringir o conjunto de termos durante o processamento
da consulta, em geral, esta estratégia apresenta um tempo de processamento da consulta
maior, se comparado com a segunda linha de pesquisa. A proposta apresentada nesta
dissertação calcula as estatísticas durante o pré-processamento da coleção de documentos.
O objetivo deste trabalho é propor uma metodologia para acrescentar termos com
informação de contexto ao domínio de termos da recuperação de informação tradicional e
aplicar o modelo vetorial considerando esse novo domínio de termos. Assim, o usuário poderá
utilizar a informação de contexto para melhorar a qualidade das respostas geradas pelo SRI.
Neste trabalho, os documentos são representados pela linguagem XML (eXtended Markup
Language). Esta representação possibilita que sejam criadas estruturas em forma de árvores
onde que cada nó identifica uma parte do documento. Na árvore, os nós internos representam
informação de estrutura e nós folha representam informação de conteúdo.
Os termos acrescentados ao domínio de termos da recuperação de informação
tradicional são derivados de forma a possuírem informação de contexto (representados como
nós internos das árvores) e informação de conteúdo (representados pelas folhas das árvores).
Assim, além de conseguir responder consultas sem contexto (como ocorre na recuperação de
14
informação tradicional) a abordagem aqui proposta possibilita o uso da informação de
contexto para responder as consultas.
A derivação dos termos com informação de contexto, representada pelos nós internos
das árvores XML, pode gerar uma quantidade exponencial de termos a serem acrescentados
ao domínio de termos. Para diminuir essa quantidade de termos, este trabalho propõe
descartar alguns desses termos de duas formas. A primeira considera aspectos referentes às
informações de contexto e de estrutura do termo, por exemplo, descartar termos que
representam apenas informação de contexto. A segunda consiste em indexar conjuntos de
termos em vez de termos.
A proposta de aumentar o domínio dos termos com novos termos que possuam
informação de contexto, tem o objetivo de aliar a contextualização oferecida por uma coleção
de documentos semi-estruturados com a simplicidade e eficiência do modelo vetorial clássico.
Assim, a contribuição central deste trabalho é definir um domínio de termos com informação
de contexto, aplicando o modelo vetorial neste domínio estendido sem gerar um aumento
exponencial na quantidade de termos do vocabulário.
Os artigos apresentados em [30] e [31] são originados desse trabalho. Em [31] é mostrado
como são gerados os termos com informação de contexto a partir dos documentos XML.
Além disso, discute o crescimento exponencial de termos causado pelo acréscimo dos termos
com informação de contexto. Em [30], além do exposto em [31], é apresentado um exemplo
para ilustrar a diferença entre a quantidade de termos e a quantidade de conjunto de termos a
serem indexados.
Esta dissertação está dividida da seguinte maneira: no Capitulo 2, é relatado um breve
histórico das linguagens de marcação e, depois, são descritos os conceitos básicos da
recuperação de informação e do modelo vetorial clássico. Também são descritas algumas
formas de aplicar a XML na recuperação de informação. Em seguida, são mostradas algumas
linguagens de consultas a documentos XML. Por fim, são apresentados alguns conceitos e
propriedades da estrutura de dados em árvores e alguns trabalhos relacionados ao tema dessa
dissertação que utilizam a informação de estrutura do documento no cálculo do ranking. No
Capítulo 3, é apresentada a proposta deste trabalho para incorporar a pesquisa contextualizada
ao modelo vetorial. Além disso, esse capítulo descreve estratégias para diminuir a quantidade
de termos a serem adicionados ao domínio dos termos. No Capítulo 4, é descrito como são
calculados os conjuntos de termos que são indexados ao invés dos termos. Em seguida são
apresentados dois exemplos que consideram pequenas coleções de documentos para ilustrar
como são obtidos esses conjuntos de termos. Também são mostradas tabelas comparando a
15
quantidade de conjunto de termos com a quantidade de termos da recuperação de informação
tradicional e com a quantidade de termos da recuperação de informação estruturada,
considerando a indexação de termos dos exemplos referidos no capítulo. Este capítulo
apresenta, ainda, uma proposta para o cálculo da similaridade entre documentos e consultas
utilizando os conjuntos de termos como unidades de indexação. O Capítulo 5, mostra os
experimentos realizados na coleção de peças teatrais da Universidade Federal de Uberlândia.
Por fim, o Capítulo 6 apresenta as conclusões.
Capítulo 2
Fundamentos de XML e Recuperação de Informação
A recuperação de informação tradicional não considera a estrutura dos textos para fazer a
pesquisa em documentos. Essa pesquisa é feita utilizando apenas termos contidos no texto
como apostila, tutorial, linguagem etc. Esses termos não possuem informações de contexto,
ou seja, informações sobre em que parte do documento eles estão localizados. Por outro lado,
a recuperação de informação em dados semi-estruturados emprega informações de contexto
para fazer a pesquisa em documentos. Uma das maneiras de estruturar um documento é por
meio de uma linguagem de marcação.
Este capítulo apresenta conceitos, notações e propriedades que são utilizados ao longo
desta dissertação. Considerando que neste trabalho é empregada a linguagem XML (eXtended
Markup Language) [2] para representar dados semi-estruturados, é mostrado um pequeno
histórico das linguagens de marcação e seus principais conceitos. Em seguida, mostra os
conceitos da recuperação de informação e do modelo vetorial. Além disso, mostra como a
XML pode ser empregada na recuperação de informação em dados semi-estruturados e
algumas linguagem de consulta a documentos XML. Por fim, apresenta conceitos sobre
árvores e alguns trabalhos que usam a informação de contexto na pesquisa a documentos
XML.
17
2.1 – Linguagens de Marcação
Quando é utilizado um editor de texto para produzir um documento, são armazenadas
informações adicionais, além das palavras digitadas. Essas informações são compostas de
instruções para controlar a aparência do documento e são conhecidas como marcação
(markup). Antes da existência dos documentos eletrônicos, os profissionais de editoração
escreviam nos textos instruções de marcação. Essas instruções tinham o objetivo de informar
a pessoa responsável pela impressão dos textos como ele desejava a aparência final do
documento impresso. Tais indicações eram do tipo “coloque esta palavra em itálico”,
“sublinhe esta frase” etc. Com o advento do mundo digital, essas marcas passaram a ser
gerenciadas pelos processadores de texto.
Uma marcação em um documento é tudo aquilo que não acrescenta conteúdo a ele. As
marcações utilizadas para informar ao digitador como o texto deve ser diagramado e que tipo
de letra ele deve usar é chamada de marcação de procedimentos. O outro tipo de marcação
existente é a marcação descritiva. Neste último tipo de marcação, o autor não se preocupa
com a aparência do texto, mas sim com as entidades que ele representa. Em um sistema de
marcação de procedimentos, define-se tamanho da letra, tipo de fonte etc, enquanto em um
sistema descritivo, identificam-se a parte do texto que representa o título do documento, a
parte do texto que representa um capítulo etc. Portanto, a marcação descritiva é a responsável
por fornecer meios para a estruturação de um texto.
Atualmente, não é necessário preocupar-se com o gerenciamento dessas marcações,
porque os editores de texto eletrônicos incorporaram essa funcionalidade. Algumas vezes, não
é possível abrir um documento em um editor diferente (tecnologia ou fabricantes diferentes)
daquele em que o documento foi editado. Um dos motivos pelos quais este fato ocorre é
porque os editores de texto usam padrões de marcação proprietários ou interpretam de forma
diferente as marcações do texto. Essas diversidades de marcações motivaram iniciativas de
padronização dessas marcações.
O SGML (Standard Generalized Markup Language) [2] é um padrão internacional
(ISO 8879), não proprietário e de código aberto, publicado em 1986. Ele apresenta um padrão
para o uso de marcações descritivas em um documento. Um dos objetivos do SGML é
garantir que documentos codificados de acordo com suas regras possam ser transportados de
um ambiente para outro sem perda de informação. A linguagem SGML pode ser chamada de
“linguagem mãe”, pois dela derivam outras linguagens de marcação como, HTML (Hypertext
Markup Language) [2] e XML (eXtended Markup Language) [2].
18
A linguagem HTML possui um grupo de marcações (tags) pré-definidas, tais como
títulos, cabeçalhos, parágrafos, listas, tabelas etc. A função dessas marcações é organizar a
informação a ser exposta por meio de páginas Web. O documento HTML contém em sua
estrutura informações que definem a apresentação e o conteúdo da página. Não há uma
separação ou estruturação precisa dessas informações. Quanto às suas limitações, a HTML
não permite que seus usuários determinem suas próprias marcações ou atributos. Portanto,
não pode ser classificada como uma linguagem extensível. Ela também não permite definir
estruturas de informações que representem hierarquia e não realiza validações de sua
estrutura.
A linguagem XML é o resultado do trabalho de um grupo de especialistas estabelecido
em 1996 pelo W3C (World Wide Web Consortium), com o objetivo de propor uma
simplificação do SGML que fosse voltada às necessidades específicas da Web. A XML é uma
versão simplificada do SGML. Um documento XML pode conter, simultaneamente, os dados
e a descrição de sua estrutura. A XML consiste em um padrão utilizado para a marcação de
documentos que contenham informações estruturadas, ou seja, documentos que contenham
uma estrutura clara e precisa da informação que é armazenada em seu conteúdo.
Os principais aspectos que diferenciam a XML da HTML são:
•
O programador pode definir seu próprio conjunto de elementos, marcações e atributos
utilizando a linguagem XML. Assim, ele não fica preso às marcações pré-definidas, como
ocorre na HTML;
•
A definição da estrutura do documento pode ser feita em documentos diferentes. Desta
maneira, o conteúdo e sua estrutura podem ser criados em arquivos separados, oferecendo
maior clareza no entendimento dos documentos XML;
•
A forma como o conteúdo do documento XML é apresentado pelo browser depende de
como a folha de estilo (XSL – eXtensible Stylesheet Language) do documento foi
definida. A preocupação principal da HTML é a exposição visual da informação enquanto
a XML, além da apresentação, possibilita a estruturação da informação.
Portanto, um documento XML é formado por três elementos básicos. Essa divisão é
feita considerando as funções de armazenamento, estruturação e apresentação do conteúdo de
um documento. A Figura 1 mostra a estrutura básica de um documento XML.
As DTDs (Document Type Definition) consistem nas definições das regras, hierarquias
e marcações criadas para caracterizar a estrutura das informações do documento. A validação
da estrutura de um documento XML é feita pela DTD, ou seja, é ela quem fornece as
19
informações de estrutura para serem verificadas. O SCHEME [] foi elaborado pela Microsoft
e possui a mesma função da DTD. Ela fornece mais recursos do que as DTDs.
XML
(conteúdo)
SCHEME
XSL
(apresentação)
DTD
(estrutura)
Figura 1: Estrutura Básica de um Documento XML
XML
(conteúdo)
XSL
HTML
XSL
.DOC
XSL
.PDF
Figura 2: Visualização de um Documento XML
A divisão do documento XML em três partes, separando conteúdo, estrutura e
apresentação permite, por exemplo, que um mesmo documento XML possa ser visualizado
em formatos diferentes. Observe-se a Figura 2, são construídas diferentes XSLs para um
mesmo documento XML. A primeira XSL apresenta o conteúdo do documento XML no
formato HTML, a segunda XSL no formato word, e a terceira no formato pdf.
As aplicações capazes de aproveitar as características oferecidas pela XMLpodem ser
definidas em quatro categorias [6]:
•
Aplicações em que o cliente Web tenha que obter informações de bases de dados
heterogêneas.
•
Aplicações que permitam a distribuição de parte do processamento de informações dos
servidores para os clientes.
20
•
Aplicações que requeiram a apresentação de uma mesma informação em diferentes formas
e para diferentes usuários,
•
Aplicações em que agentes inteligentes possam descobrir informações precisas e de
qualidade na Web.
A XML pode ser empregada nas mais variadas áreas do conhecimento, desde
computação à música, como também biblioteconomia, biologia, matemática etc. Em [25],
podem ser encontrados várias propostas e iniciativas da indústria com XML. Para esta
dissertação, a XML é utilizada para fornecer um meio de estruturar textos. Assim, essa
informação de estrutura pode ser usada para que o usuário de um sistema de recuperação de
informação contextualize suas consultas. A criação de estruturas em árvore a partir de
documentos XML é ideal para a representação de documentos que possuam informações de
estrutura como livros, relatórios, catálogos, roteiros etc.
A seguir, apresentam-se os fundamentos da recuperação de informação e, em seguida,
algumas iniciativas de recuperação de informação usando documentos XML.
2.2 – Recuperação de Informação
O usuário de um Sistema de Recuperação de Informação busca obter documentos que
atendam à sua necessidade de informação. Para isto, ele, geralmente, expressa sua
necessidade por meio de uma consulta. O sistema então realiza o casamento da consulta com
seus documentos por meio de um modelo de recuperação de informação. Um modelo para
recuperação de informação propõe uma representação para documentos e consultas e define
como calcular a similaridade entre os mesmos. O modelo, então, é capaz de quantificar a
relevância de cada documento da coleção em relação à consulta do usuário e, com base nesta
relevância, apresentar-lhe os documentos que melhor atendam à sua necessidade de
informação i.e., os mais similares à consulta. Por fim, o modelo apresenta um ranking de
documentos que aparecem em ordem decrescente de similaridade.
Para realizar a tarefa de recuperar documentos, um SRI trabalha com modelos de
representação de documentos e consultas. A seguir, são apresentados alguns conceitos usados
nestes modelos.
21
2.2.1 – Conceitos Clássicos da Recuperação de Informação
Esta seção descreve os principais conceitos da recuperação de informação que serão utilizados
ao longo deste trabalho.
Definição 2.1 (Documento).
Um documento d é um registro de dados armazenado em algum formato, mas, usualmente,
incluindo uma parte textual. O j-ésimo documento em uma coleção de documentos é
denotado por dj.
Definição 2.2 (Termo e Vocabulário).
Um termo é uma palavra que, semanticamente, contribui para definir o tema principal do
documento. O conjunto de termos presentes nos documentos de uma coleção é chamado
vocabulário. O i-ésimo termo do vocabulário é denotado por ki.
Definição 2.3 (Dimensão de uma Coleção de Documentos)
Seja C = {d1, ..., dz} uma coleção de documentos. A dimensão de C é o número de termos
(vocabulário) usados para definir todos os documentos na coleção de documentos. Então
K = {k1, ..., kt} é o conjunto de todos os termos de uma coleção de documentos com dimensão
t.
Definição 2.4 (Peso)
O peso associado com o par (ki, dj) quantifica a importância do termo ki para descrever a
semântica do conteúdo do documento dj. Este peso é denotado por wij.
Definição 2.5 (Representação de Documentos e Consultas).
Seja C uma coleção de documentos e K = {k1, ..., kt} seus termos. Neste caso, a dimensão de
C é t. Um documento em C é representado por um vetor em Rt,
d j = (w1 j , K , w tj )
onde wij é o peso associado com o par (ki, dj). Analogamente, uma consulta é representada por
um vetor em Rt,
q = (w1 q , K , w tq )
22
onde wiq é o peso associado com o par (ki, q).
Definição 2.6 (Função Peso).
Sejam C = {d1, ..., dz} uma coleção de documentos, K = {k1, ..., kt} um conjunto de termos.
A função peso
g : K ×{C ∪{q}} → R
é tal que g(ki, dj) retorna o peso associado com o par (ki, dj), e g(ki, q) retorna o peso associado
ao par (ki, q).
Por conveniência, é adotada, uma notação simplificada. Seja gj : K → R uma função
unária que retorna o peso de cada termo no documento dj. Então, gj(ki) retorna o peso
associado com o par (ki, dj). Analogamente, seja gq: K → R uma função unária que retorna o
peso na consulta q. Então, gq(ki) retorna o peso associado com o par (ki, q).
2.2.2 – Modelo Vetorial
Os modelos clássicos da recuperação de informação são o Modelo Probabilístico, o Modelo
Booleano e o Modelo Vetorial [3]. Neste trabalho, a recuperação de informação tradicional é
representada pelo modelo vetorial clássico. Esta seção apresenta os principais conceitos desse
modelo.
O modelo vetorial representa consultas e documentos como vetores em um espaço
t-dimensional onde t é o número de termos da coleção. Cada dimensão desse espaço é
associada com um vetor de termos kj distintos. Esses vetores de termos são ortogonais
entre si, assim:
i ≠ j ⇒ k i • k j = 0,
onde “•” é o produto interno entre os vetores ki e kj. Isto denota que os termos ocorrem
independentemente nos documentos e consultas. Além disso, o modelo vetorial assinala pesos
para termos em consultas e documentos. Uma abordagem comum para calcular esses pesos é
balancear a importância do termo intra e inter documentos.
23
Sejam N o número total de documentos na coleção, ni o número de documentos em
que o termo ki aparece e freqij a freqüência do termo ki no documento dj. O fator freqij
quantifica a importância do termo ki para o documento dj e, usualmente, é chamado de
freqüência do termo (tf). O fator
N
log 
 ni




quantifica a importância do termo ki como um fator discriminante em relação a todos os
documentos da coleção. Ele é denominado de freqüência inversa de documentos (idf).
Uma estratégia comum para calcular o peso do termo ki em relação ao documento dj,é
N
wij = freqij × log 
 ni 
que é, comumente, chamado de esquema de pesagem tf-idf. Este esquema balanceia as
características intra (tf) e inter (idf) documentos.
Para o cálculo do peso do termo ki,em relação à consulta q, pode ser adotado
N
wiq = freqiq × log 
 ni 
onde freqiq é a freqüência do termo ki associada com a consulta q.
Os vetores de pesos do documento dj e da consulta e q são representados
respectivamente por:
d j = (w1j , w2 j ,K, wij )
q = (w1q , w2q ,K, wiq )
onde t é o número total de termos na coleção. Usualmente, a similaridade entre um documento
dj e a consulta q é calculada como o coseno do ângulo θ entre os vetores do documento e da
consulta no espaço t-dimensional. A medida do coseno é dada por
24
sim(d j , q) =
d j •q
| d j |×| q |
∑
t
=
i =1
∑
t
i =1
w
2
ij
wij • wiq
•
∑
t
i =1
(Equação 1)
w
2
iq
A sim(dj, q) mostra a proximidade dos vetores dj e q .
2.3 – XML e Recuperação de Informação
Na recuperação de informação tradicional a busca por informações relevantes é feita em
textos sem considerar a sua estrutura. Uma busca é contextualizada quando o usuário de um
sistema de recuperação de informação expressa, em sua consulta, a preferência relativa à
localização da palavra pesquisada no documento. Os sistemas baseados na busca em textos
sem estrutura não conseguem lidar com a busca contextualizada com base na estrutura, pois
eles não possuem mecanismos capazes de incorporar essa característica no cálculo da
similaridade. Os modelos clássicos da recuperação de informação tradicional são utilizados
para pesquisar dados textuais sem estrutura. A representação e consulta em dados semiestruturados são desafios para a comunidade científica de recuperação de informação. A
linguagem XML surge como uma solução para permitir a representação de estrutura para
esses dados. A Integração da recuperação de informação e das técnicas de busca em XML
permitirá pesquisas mais sofisticadas tanto na estrutura como no conteúdo destes documentos
[11]. A recuperação de informação em documentos XML vem despertando um grande
interesse dos pesquisadores. Várias soluções têm sido propostas na literatura para trabalhar
nessa área, por exemplo [8, 18, 22, 32, 36, 38], . Este interesse é justificado porque a XML
vem se tornando um padrão para o armazenamento, troca e apresentação de dados [11].
Portanto, são necessários sistemas que possibilitem uma busca eficiente da informação em
documentos XML.
Uma pesquisa sobre várias técnicas de indexação e busca para documentos XML
permitiu a classificação de três abordagens [11]:
•
Abordagem Orientada a Banco de Dados – Os dados indexados derivados de banco de
dados são convertidos para documentos XML usando XSL. A abordagem orientada a
banco de dados revela as seguintes vantagens: (i) as relações dos dados e integridade
podem ser modeladas e verificadas; (ii) as operações padrões a banco de dados podem ser
usadas; (iii) a linguagem de consulta é similar à linguagem padrão de banco de dados
25
(SQL). A desvantagem está na dificuldade de exportar dados XML para um banco de
dados e fazer mudanças em seus schemas.
•
Abordagem Orientada à Recuperação de Informação – Nesta abordagem, técnicas de
recuperação de informação são diretamente aplicadas para processar e recuperar
documentos XML. Cada documento XML é considerado um documento texto com tags
adicionais. Vários métodos têm sido sugeridos para trabalhar com as tags XML [11].
Essas sugestões vão de simplesmente descartar todas as tags, selecionar algumas tags
importantes e inseri-las no índice, até indexar todas as tags como se elas fossem termos de
índice.
•
Abordagem Híbrida – Nesta abordagem, um método mais simples é usado para especificar
os elementos do documento XML. A idéia básica é indexar as listas invertidas de todos os
termos e seus caminhos. Assim, os resultados das buscas são mais satisfatórios, desde que
a especificação dos caminhos limite os casamentos possíveis. A desvantagem é a
necessidade do usuário possuir conhecimento adicional sobre a estrutura do documento
XML para obter melhores resultados.
Há dois tipos de abordagens em recuperação de informação que lidam com
documentos estruturados [16].
•
A abordagem estruturada – Esta abordagem enriquece a pesquisa no texto mediante
condições relativas à estrutura do documento. Por exemplo, procurar palavra que ocorre
em certas partes do documento.
•
Abordagem baseada em conteúdo – Esta abordagem tem o objetivo de recuperar a parte
mais relevante do documento que melhor satisfaça a consulta.
Uma diferença fundamental entre a recuperação de informação tradicional e a
recuperação de informação em XML é a unidade de recuperação. Na recuperação de
informação tradicional, a unidade de recuperação é fixa, ela é o documento completo. Na
recuperação de informação em XML, além de possibilitar a recuperação de todo o documento,
cada elemento do documento XML é uma unidade de recuperação em potencial. Em [21], é
mostrado um estudo comparativo entre essas duas abordagens. O trabalho apresentado nesta
dissertação utiliza o documento como unidade de recuperação e é classificado como uma
abordagem estruturada.
26
2.4 – Linguagens para Consulta a Documentos XML
O crescimento do emprego da XML motivou o aparecimento das linguagens de consulta a
documentos XML. Podem-se dividir essas linguagens em duas abordagens. Na primeira, as
linguagens são usadas para acessar elementos de dados XML, filtrar estes elementos baseados
em certos critérios ou transformar os elementos XML em novas estruturas. Essas linguagens
suportam a álgebra relacional e foram desenvolvidas pela comunidade de banco de dados. Na
segunda, as linguagens empregam os conceitos de recuperação de informação na busca em
documentos XML.
As linguagens XML-QL [15], XQL [28] e Lorel [1] são exemplos da primeira
abordagem. A XML-QL é apoiada pela W3C. Essa linguagem propõe uma solução para a
extração, transformação e integração de dados para documentos XML. Ela considera
documentos XML como um banco de dados e a DTD como esquema do banco de dados. Ela
propõe uma cláusula WHERE-CONSTRUCT similar à cláusula SELECT-WHERE da SQL.
Também possibilita a extração de partes de um documento XML. As principais características
da XML-QL são: (i) é uma linguagem declarativa; (ii) suporta as operações da álgebra
relacional e em particular possibilita joins; (iii) é simples, pois técnicas de banco de dados
conhecidas para otimização de consulta, estimativas de custo e re-escrita de consulta podem
ser estendidas à XML-QL; (iv) pode extrair dados de documentos XML existentes e construir
novos documentos XML e (v) pode suportar as visões em um documento XML.
A XQL é uma notação para endereçamento e filtragem dos elementos de documentos
XML. Ela é uma extensão natural da XSL. A XQL fornece uma notação para apontar
elementos específicos e buscar nós com características particulares [11]. Essa linguagem é
uma notação para recuperar a informação em um documento XML. Essa informação deve ser
um conjunto de nós ou informações sobre o relacionamento desses nós ou valores derivados.
A especificação não indica o formato de saída. O resultado da consulta pode ser um nó, uma
lista de nós, um documento XML, um array ou alguma outra estrutura. A XQL fornece
algumas funcionalidades, tais como: (i) funcionalidade equivalente à declaração SQL
SELECT; (ii) funcionalidade equivalente à declaração SQL WHERE; (iii) operadores lógicosbooleanos (and, or, not); (iv) operadores de comparação (maior que, menor que, igual a). As
principais diferenças entre SQL e XQL são apresentadas na Tabela 1.
A Lorel é uma linguagem desenvolvida para o protótipo de um sistema gerenciador de
banco de dados (SGBD) para dados XML do projeto Lore. Essa linguagem foi, originalmente,
27
desenvolvida para consultas em dados semi-estruturados e, posteriormente, estendida para
dados XML. O projeto Lore foca a definição de uma linguagem de consulta declarativa para
XML, o desenvolvimento de uma nova tecnologia para a interação das buscas em dados XML
e a construção de um processador de consultas XML eficientes.
Tabela 1: Diferenças Principais entre SQL e XQL
SQL
O banco de dados é um conjunto de tabelas.
XQL
O banco de dados é um conjunto de um ou mais
documentos XML.
As consultas são feitas em SQL, uma
Consultas são feitas em XQL, uma linguagem
linguagem de consulta que usa tabelas como um de consulta que usa a estrutura de XML como
modelo básico.
um modelo básico.
A cláusula FROM determina as tabelas que são Uma consulta é determinada como um conjunto
examinadas pela consulta.
de nós de entrada de um ou mais documentos.
O resultado de uma consulta é uma tabela que
O resultado de uma consulta é uma lista de nós
contém um conjunto de linhas. Essa tabela pode de documentos XML que podem ser utilizados
ser utilizada em outras consultas
em outras consultas.
As linguagens ELIXIR [12] e XIRQL [16] são exemplos das abordagens que usam
conceitos de recuperação de informação. A ELIXIR estende a XML-QL com o operador “~”
de similaridade textual, que gera as respostas em ordem decrescente de similaridade. Ela usa a
XML-QL para consultar os dados XML em sua forma nativa. O resultado dessa consulta é,
então, submetido ao WHIRL[13, 14] para avaliar os predicados de similaridade. Uma consulta
WHIRL é uma conjunção de relações, predicados relacionais e predicados de similaridade. A
definição de similaridade do WHIRL é baseada no modelo vetorial clássico. Uma das
contribuições da ELIXIR é a definição das junções dos predicados de similaridade entre
variáveis (variável ~ variável). Assim, por exemplo, é possível pesquisar por livros e CDs
com títulos similares. Portanto, o algoritmo para responder a uma consulta na ELIXIR
consiste em: (i) re-escrever as consultas originais da ELIXIR e uma série de consultas em
XML-QL, que, por sua vez, geram dados intermediários; (ii) técnicas de banco de dados
relacional são usadas para avaliar os operadores de similaridade no dados intermediários
produzindo um documento XML com um ranking de nós.
A XIRQL é uma linguagem de consulta para a recuperação de informação em
documentos XML. Ela utiliza as características do modelo probabilístico da recuperação de
informação combinadas com conceitos da área de banco de dados para integrar as
características de pesagem e ranking, busca orientada à relevância e tipo de dados com
predicados vagos. Além disso, para o processamento de consultas XIRQL, é definida uma
28
álgebra de caminho.
Existem várias outras linguagens de consulta como por exemplo, XML-GL, XSLT,
Quilt etc. Um estudo comparativo sobre estas linguagens pode ser encontrado em [5]. Os
trabalhos descritos nesta seção definem linguagem para consultas a dados XML. Algumas
dessas linguagens procuram fornecer características e funcionalidades semelhantes a
linguagem SQL. Outras linguagens empregam conceitos de recuperação de informação para a
pesquisa em documentos XML. O foco do trabalho apresentado nesta dissertação é diferente
do foco dos trabalhos descritos nesta seção. o trabalho aqui apresentado têm o objetivo de
propor uma maneira para o modelo vetorial incorporar a informação de estrutura do
documento no cálculo do ranking. A seção2.6 descreve trabalhos com abordagem semelhante
a deste trabalho
A próxima seção mostra propriedades e notação de árvores em virtude da XML propor
a estruturação dos documentos utilizando a estrutura de árvores. O objetivo é apresentar a
notação utilizada neste trabalho.
2.5 –Árvores: Propriedades e Notação
A estrutura dos documentos XML é baseada em árvores. Vários trabalhos na área de
recuperação de informação em dados semi-estruturados utilizam as propriedades e a notação
de árvores em suas abordagens. A proposta apresentada nesta dissertação está incluída nesses
trabalhos. Portanto, esta seção apresenta uma notação e algumas propriedades das árvores.
Os elementos em uma estrutura de árvores obedecem a uma relação de hierarquia que
pode ser empregada para estruturar textos. Esta é a característica principal utilizada na
recuperação de informação estruturada. A terminologia desse tipo de estrutura é intuitiva e se
baseia na nomenclatura utilizada nas famílias, como os termos "pai", "filho", "ascendentes" e
"descendentes". A árvore é um tipo abstrato de dados cujos elementos (nós) estão dispostos
hierarquicamente. Na representação gráfica de árvores, os nós são ligados por ramos, também
conhecidos como arcos ou arestas.
Com exceção do elemento do topo, cada elemento têm um elemento pai e zero ou mais
elementos filhos. O elemento de topo é chamado de raiz. Portanto, o elemento raiz não tem
elemento pai e nem ascendentes. Por sua vez, os elementos que não possuem filhos são
designados nós folhas. Os outros nós da árvore são denominados nós internos.
29
A ligação de um nó para os seus descendentes faz-se por um único caminho. Os
ascendentes de um nó X são todos os nós que existem no caminho, desde a raiz até o nó X. A
profundidade de um nó é o número de ramos existentes no caminho entre o nó e a raiz. A
altura de uma árvore é definida como a máxima profundidade apresentada pelos nós. O grau
de um nó é o número de filhos que esse nó tem e o grau de uma árvore, o máximo dos graus
dos seus nós.
Uma sub-árvore S de uma árvore A é uma árvore cujos nós pertencem ao conjunto de
nós da árvore A e que mantém as relações de descendência, ascendência, pai e filho da árvore
A. Uma árvore é ordenada, se existe uma ordem entre os filhos de cada nó, de tal maneira que
é possível identificar os filhos de um nó como sendo o primeiro, o segundo, o terceiro e assim
por diante. O rótulo de um nó é o nome que o identifica.
carro
fiat
chevrolet
uno
preço
cor
ano
2000
palio
exterior
azul
interior
acessorios
12.000
ano
sim
ford
ka
corsa
ano
km
preço
peso
1998 2001 50.000 120
azul
Figura 3: Exemplo de uma Estrutura de Árvore
A Figura 3 mostra um exemplo de árvore onde:
1) A raiz é o nó com o rótulo carro;
2) A sub-árvore com a raiz fiat possui dois nós filhos uno e palio;
3) A sub-árvore com raiz palio possui 3 nós folhas 12.000, sim e 1998;
4) A altura da árvore com raiz carro é 5;
5) O grau do nó cor é 2.
2
potencia
1.0
preço
15.000
30
2.6 – Trabalhos Relacionados
Esta seção descreve alguns trabalhos que propõem incorporar a informação de estrutura para
calcular a similaridade entre documentos e consultas no contexto de recuperação de
informação. Esses trabalhos consideram que os documentos semi-estruturados são
representados utilizando a linguagem XML.
O trabalho apresentado em [18] propõe a definição de um escopo para o cálculo dos
pesos dos termos. Esse escopo é definido pela consulta. Assim, as estatísticas para o cálculo
da similaridade entre documentos e consulta são obtidas em tempo de consulta. A idéia
principal deste trabalho é manter um índice apenas com termos que contenham a parte textual
(conteúdo). Esses elementos são chamados de elementos básicos. Quando são necessárias
outras informações para o cálculo da similaridade, elas são derivadas desses elementos
básicos em tempo de consulta. Essa derivação depende do tipo da consulta que pode ser:
single-category, multi-categories ou nested retrieval. Single-category é o tipo de consulta em
que o usuário deseja referenciar apenas parte de um documento. Por exemplo, considere-se a
árvore da Figura 3, se o usuário está interessado em consultar somente sobre os carros da
marca fiat, a sua consulta será do tipo single-category, pois ele faz referência a uma parte
(categoria) do documento XML. Por outro lado, se o usuário deseja consultar sobre carros da
marca fiat e ford, então, a sua consulta será do tipo multi-categories, pois ele faz referência a
mais de uma parte (categoria) do documento XML. Consultas do tipo nested retrieval são
aquelas em que importâncias diferentes são consideradas para cada nível da árvore XML.
Essa importância é maior, se o termo ocorre mais próximo da raiz da sub-árvore considerada
ou menor, caso contrário. Por exemplo, na sub-árvore com a raiz uno, o termo (folha) 2000 é
considerado mais importante do que o termo (folha) azul, pois o termo (folha) 2000 está mais
próximo da raiz uno. A flexibilidade na granularidade da recuperação de informação é
conseguida por meio dessas formas de derivação. Essa abordagem gera, dinamicamente, o
espaço vetorial apropriado para o escopo da consulta.
Em [18] não é apresentado
experimentos que utilizam a abordagem descrita. A flexibilidade na granularidade de
recuperação, a geração dinâmica do espaço vetorial e o cálculo das estatísticas em tempo de
consulta são as contribuições descritas em [18].
Um outro trabalho em que o escopo da consulta é definido pelo usuário em tempo de
consulta, é apresentado em [32]. Neste caso, os autores definem esse escopo como
documentos admissíveis. Essa abordagem propõe a representação de documentos e consultas
como árvores. Assim, a tarefa de recuperação de informação torna-se encontrar as árvores de
31
documentos que mais se aproximem da árvore de consulta informada pelo usuário. O escopo
considerado para calcular os pesos dos termos é definido pela raiz da árvore de consulta. A
técnica de indexação utilizada é inspirada em partial index, introduzida por Navarro [24]. O
modelo vetorial pode ser simulado, ajustando alguns parâmetros no processo de recuperação
de informação para que sejam consideradas apenas as folhas das árvores dos documentos.
Essa abordagem também possibilita que o usuário forneça pesos para os termos da consulta de
acordo com sua necessidade de informação. Em [32], são descritos experimentos feitos em
uma coleção com 22 documentos usando técnicas definidas em [24]. Esses experimentos
mostram a diferença do posicionamento no ranking dos documentos em relação às consultas
nas quais são feitas referências à estrutura dos documentos (consultas estruturadas) e
consultas em que essas referências não são feitas (consultas planas). Observa-se que há uma
melhora na precisão, quando são feitas referências à estrutura dos documentos.
Na abordagem apresentada em [38], os pesos dos termos são calculados em tempo de
indexação. A idéia principal é ter como unidade de recuperação os elementos lógicos de um
documento XML. Elementos lógicos são partes do documento XML, por exemplo: título,
parágrafo, resumo etc. Esses elementos são representados em um modelo de árvore ordenada.
Nesta árvore os nós filhos de um mesmo pai são ordenados ascendentemente. A técnica de
busca empregada é baseada em Proximity Seach [29]. O objetivo dessa técnica é gerar um
ranking por meio de um conjunto de objetos baseados no caminho mais curto entre esses
objetos (elementos lógicos). Um documento, ou um componente de um documento, é
considerado como melhor casamento, se os termos da consulta são vizinhos aos termos do
documento. Alguns mecanismos são necessários para armazenar informações para todos os
níveis dos nós no modelo de árvore ordenada. Dessa maneira, é possível recuperar
componentes de documentos com várias granularidades. Para isso, é criado um índice cuja
entrada é definida como <term, frequency, position>, onde position é uma estrutura do tipo
<Section_ID, Para_ID>, usada para localizar um componente em um documento. São
descritos experimentos em uma coleção com cerca de 40.000 documentos e com um índice de
500MB. Uma das conclusões dos autores desse trabalho é que essa abordagem gera um índice
que pode consumir mais recursos de tempo e espaço, se comparado à indexação tradicional
por arquivos invertidos. Não é apresentada uma estratégia para melhorar a eficiência dessa
abordagem
Em [8], a idéia principal é permitir que o usuário formule consultas simples ou
complexas, dependendo do conhecimento que ele possua da estrutura do documento XML.
Para isso, é proposto que a consulta seja feita utilizando partes dos documentos XML
32
(fragmentos XML). Essa abordagem estende o modelo vetorial, usando como unidade de
indexação pares da forma (ti, ci), onde ti é o i-ésimo termo do vocabulário e ci é o contexto em
que ti aparece. Por exemplo, na Figura 3, tem-se o par (2000, ano/uno/fiat/carro), na qual
ano/uno/fiat/carro é o contexto em que o termo 2000 ocorre. Assim, os termos são
qualificados pelo contexto no qual aparecem. A relevância do termo é incrementada, quando
o mesmo par (ti, ci) é encontrado na consulta e no documento ou quando ti aparece em um
contexto relacionado cj. Portanto, no cálculo da similaridade, é introduzida a característica cr
para quantificar o relacionamento entre os contextos. Por exemplo, na Figura 3, o termo 2000
ocorre nos contextos ano/uno/fiat/carro e ano/palio/fiat/carro. A característica cr quantifica a
relação entre os contextos onde o termo 2000 aparece. A estratégia de indexação utilizada em
[8] cria um perfil contendo um vetor dos pares (t, c) para cada documento. O sistema de
recuperação de informação em texto completo, chamado Juru [10], foi estendido para
armazenar esse esquema de indexação. Em [8], são descritos experimentos utilizando o Juru e
a coleção de documentos INEX [19]. Os autores de [10] comentam que os experimentos
preliminares são bons para consultas simples e que o próximo passo é verificar o impacto da
característica cr na qualidade do ranking. Para alguns usuários, a sintaxe de um documento
XML pode não ser simples. Portanto, a idéia de utilizar esta sintaxe para fazer a consulta pode
dificultar o uso dessa abordagem. Por exemplo, se o usuário deseja consultar por documentos
que possuam os termos XML e tutorial no título de um capítulo, a sintaxe dessa consulta
nessa abordagem seria <capitulo><titulo> XML tutorial </titulo></chapter>.
O trabalho apresentado em [36] aproveita a estrutura de árvore dos documentos XML
e propõe um relaxamento no casamento de padrão entre árvores de consultas e documentos.
Esse relaxamento é no sentido de procurar, por exemplo, um livro que tenha o elemento isbn
como descendente e não como filho. Essa abordagem emprega os conceitos de pesos e
ranking da recuperação de informação. Entretanto, deixa em aberto o método para o cálculo
da similaridade entre documentos e consulta. Uma possível métrica para o cálculo do ranking,
sugerida em [36], é baseada no número de relaxamentos aplicados na consulta. Dada uma
consulta q, é obtida uma consulta q’ por meio das aplicações de um ou mais relaxamentos
definidos em [36]. Nessa abordagem, a consulta é uma árvore onde cada nó e arco, que liga
um nó pai a um nó filho, ao qual é associado com um número inteiro não negativo (peso).
Esse número pode ser definido pelo usuário ou automaticamente. As duas principais
contribuições dessa abordagem são: uma representação algébrica em que todos os
relaxamentos podem ser codificados usando junções em uma estrutura binária e o
desenvolvimento de um algoritmo que elimina respostas irrelevantes (o quanto antes possível)
33
durante a avaliação da consulta. Em [36], não são apresentados experimentos em relação ao
cálculo do ranking, pois este não é seu foco principal. O trabalho explora e propõe algoritmos
para casamento de padrões em árvores segundo algumas considerações (relaxamentos).
Portanto, o trabalho pode ser utilizado na recuperação de informação em dados semiestruturados como uma solução para o casamento de padrão entre árvores.
A abordagem apresentada em [22] emprega uma classe de consultas que suporta
expressões de caminho e utiliza um índice que combina arquivo invertido com índice de
estrutura. Para construir o índice dos documentos XML, é criada uma árvore de resumo XML,
que, em geral, é menor do que o documento XML original. A árvore de resumo é construída
especificando qual termo deve ser indexado nos documentos XML. Após essa especificação,
devem ser removidas as stop words e calculadas as estimativas de distribuição de todos os
termos (literais e tags). Quaisquer caminhos ou termos repetidos são removidos. A árvore
resumo é a entrada para a construção da estrutura do índice. Depois da construção da árvore
resumo, o próximo passo é separar os dados de conteúdo e estrutura. Desta maneira, é gerado
o índice de estrutura e o arquivo invertido. A pesquisa no índice consiste em duas etapas: uma
pesquisa para identificar os documentos XML que possuam o caminho do termo da consulta e
uma pesquisa para identificar os documentos XML que contenham o texto (conteúdo) dos
termos da consulta. Na primeira pesquisa, é identificada uma lista de candidatos A de
documentos e uma lista de candidatos T de termos do vocabulário. Esses termos são as folhas
dos caminhos (ramos) da árvore XML. Os termos da consulta são comparados com a lista T e
quando houver o casamento, os documentos são recuperados da lista invertida. Nessa
abordagem, o ranking combina os pesos dos termos baseados na distribuição dos termos (tf e
itf) e a posição do termo na estrutura do documento. Por exemplo, um literal que se encontra
no caminho jornal/topico/artigo/titulo, provavelmente, deve ter um coeficiente maior do que
o literal que se encontra no caminho jornal/topico/artigo/resumo. Isso mostra que o literal que
aparece no título é mais importante do que o literal que aparece no resumo. O peso final de
um termo i em um documento j é dado pela multiplicação desses dois componentes. Em [22]
são descritos experimentos em uma coleção com 1239 documentos com um índice de 2.5MB.
Segundo o autor de [22], a precisão conseguida é alta. Uma limitação dessa abordagem é que
o usuário deve informar o caminho completo, desde a raiz até a folha, na sua consulta. Por
exemplo, para uma árvore que possua o ramo jornal/topico/artigo/titulo, o usuário não pode
informar em sua consulta apenas o contexto artigo/titulo Além disso, o coeficiente que
especifica a importância do contexto em que o termo ocorre pode não refletir a vontade do
usuário. Por exemplo, para um determinado usuário o termo que aparece em
34
jornal/topico/artigo/resumo pode ser mais importante do que o termo que aparece em
jornal/topico/artigo/titulo. Um problema identificado pelo autor de [22] é que documentos
XML diferentes podem utilizar tags diferentes para descrever a mesma parte da informação,
como, por exemplo, revista e periódicos.
A abordagem proposta nesta dissertação diferencia-se de [18] e [32] em relação à
estratégia para o cálculo das estatísticas, pois, aqui, elas são calculadas em tempo de
indexação. Os trabalhos [18] e [32] propõem definir um escopo em tempo de consulta para o
cálculo das estatísticas utilizadas para produzir o ranking. Esta estratégia possui um overhead
maior, se comparada às estratégias que fazem esses cálculos em tempo de consulta [18]. Os
trabalho [18], [38] e [8] propõem que a granularidade na unidade de recuperação de
informação seja baseada nos elementos do documento XML em vez do documento inteiro,
como acontece na recuperação de informação tradicional. Nesta dissertação, a granularidade é
o documento inteiro. Isto ocorre para evitar a indexação de estatísticas adicionais dos
elementos dos documentos XML. Assim, considerando esta granularidade descarta-se um
fator que poderia aumentar significativamente o tamanho do índice. As características da
estrutura de árvore, dos documentos XML, são aproveitadas pelos trabalhos [32], [36] e [38]
para utilizar o casamento em árvores no cálculo da similaridade entre documentos e consultas.
Na abordagem proposta nesta dissertação, os termos da coleção de documentos XML contêm
informações de estrutura, porém são tratados como os termos da recuperação de informação
tradicional. A estrutura de árvore dos documentos XML é usada para a derivação de termos.
A forma de indexação utilizada nos diferentes trabalhos descritos nesta seção depende das
abordagens propostas. Por exemplo, as abordagens que permitem a recuperação de parte de
um documento utilizam índices com estatísticas dos elementos do documento XML, como se
observa em [18]. Alguns trabalhos propõem índices separados para a informação de conteúdo
e de contexto, como ocorre em [22]. Em [38], é adicionada a informação da posição do
elemento XML na indexação tradicional com arquivos invertidos. Em [32], é utilizada uma
estrutura de indexação que considera as características da estrutura em árvores dos
documentos XML. A abordagem proposta nesta dissertação usa a estrutura de indexação da
recuperação de informação tradicional. Entretanto, a unidade de indexação é um conjunto de
termos. A unidade de indexação também é um diferencial entre esta dissertação e o trabalho
apresentado em [8], pois a unidade de indexação em [8] é o par (t, c), como já foi descrito.
Outro diferencial importante entre o trabalho apresentado nesta dissertação dos
trabalhos descritos nesta seção é a motivação. A motivação desses trabalhos é propor uma
forma para trabalhar a recuperação de informação em dados semi-estruturados. A motivação
35
da proposta desta dissertação é inserir a característica de contextualização da recuperação de
informação estruturada ao modelo vetorial. Por exemplo, em [32], o modelo vetorial pode ser
simulado ajustando algumas restrições no processo de recuperação de informação. Em [8], o
espaço vetorial pode ser obtido, se a pesquisa for feita em um mesmo contexto. Em [18], o
espaço vetorial é gerado em tempo de consulta. Isso mostra que o modelo vetorial é uma
consequência e não o objetivo final. Em resumo, as principais contribuições são:
•
Estender o modelo vetorial para utilizar a informação de contexto no cálculo da
similaridade entre documentos e consultas.
•
Propor estratégias para diminuir a quantidade de termos a serem acrescentados ao domínio
de termos da recuperação de informação tradicional.
O Capítulo 3 apresenta a proposta desta dissertação para inserir a pesquisa
contextualizada no modelo vetorial clássico.
Capítulo 3
Uma Proposta para Recuperação de Informação em
Dados Semi-estruturados
A recuperação de informação em dados semi-estruturados vem recebendo uma atenção
crescente por parte da comunidade científica. Várias abordagens foram propostas na literatura
para trabalhar a recuperação de informação em dados semi-estruturados. Essas abordagens
podem ser divididas em duas categorias distintas: abordagens onde o cálculo das freqüências e
pesos dos termos é realizado em tempo de consulta e abordagens nas quais estes cálculos são
realizados em tempo de indexação. A primeira abordagem apresenta um tempo de resposta
durante o processamento da consulta maior, se comparado com a segunda e, em geral, os
métodos de indexação e pesquisa são mais complexos. O trabalho descrito nesta dissertação
calcula as freqüências e os pesos dos termos durante a indexação da coleção de documentos.
Em recuperação de informação, uma das vantagens de se trabalhar com dados semiestruturados em vez de dados não estruturados é fornecer ao usuário condições de
contextualizar a sua necessidade de informação. Por outro lado, é necessário que o usuário
tenha um certo conhecimento da estrutura da coleção para aproveitar esta vantagem. Essa
contextualização é conseguida por meio da estrutura dos documentos. Assim, por exemplo, o
usuário pode preferir documentos que possuam a palavra XML em seu título a documentos
que contenham a palavra XML na conclusão. Na recuperação de informação tradicional, essa
contextualização não é usada. Por outro lado, o modelo vetorial clássico apresenta uma
solução simples, eficiente e de fácil implementação para recuperar informação em dados não
estruturados [3]. Ao fazer o modelo vetorial clássico utilizar informações de estrutura
37
(informação de contexto) dos dados semi-estruturados, combina-se essa característica de
contextualização às vantagens do modelo vetorial. Dessa maneira, o usuário pode
contextualizar a sua necessidade de informação nas consultas a coleções de documentos semiestruturados mediante um sistema de recuperação de informação que implemente o modelo
vetorial. A motivação principal deste trabalho é aproveitar a simplicidade de implementação
e o desempenho do modelo vetorial para o cálculo do ranking, em coleções de documentos
semi-estruturados, preservando a noção de contextualização fornecida pela estrutura dos
documentos.
Este capítulo apresenta o modelo proposto nesta dissertação para acrescentar a
pesquisa contextualizada ao modelo vetorial. Em seguida, discute o problema do crescimento
do índice causado pelo aumento do domínio de termos da recuperação de informação
tradicional. Por fim, descreve estratégias para lidar com esse problema.
3.1 – Extensão do Vocabulário da Recuperação de Informação Tradicional
Os termos que formam o vocabulário da recuperação de informação tradicional não possuem
informação de estrutura. Por outro lado, a estrutura em árvores dos documentos XML
possibilita a estruturação de um texto, como foi visto no Capítulo 2. As folhas das árvores de
um documento XML são os termos que não possuem estrutura. A contextualização desses
termos (folhas) é fornecida pelos ramos das árvores das quais fazem parte. Portanto, as folhas
das árvores XML representam os termos da recuperação de informação tradicional e esses
termos, associados aos seus respectivos ramos, são os termos que contêm informação de
estrutura. Considere-se por exemplo, a sub-árvore com raiz uno da árvore mostrada na Figura
3, o termo 2000 apresenta apenas informação de conteúdo (folha da árvore). O termo
uno[ano[2000]] contém informação de contexto (uno[ano[]]) e de conteúdo (2000). A idéia
principal para inserir a noção de contextualização ao modelo vetorial é aumentar o seu
domínio com termos que possuam informação de estrutura. Assim, essa informação de
contexto poderá ser utilizada pelo SRI no cálculo da similaridade entre documentos e
consultas.
Para um melhor entendimento da proposta descrita neste capítulo, são apresentadas a
seguir, algumas definições de termos. Estas definições consideram os aspectos dos termos
terem ou não estrutura e como podem ser derivados das sub-árvores dos documentos XML.
38
As notações Termo Complexo e Termo Atômico foram inspiradas na notação utilizada em
[32].
Definição 3.1 (Termo Complexo).
Um termo complexo Tx é uma sub-árvore que possui informação de estrutura, ou seja, têm
grau maior ou igual a um. As folhas das árvores XML não são consideradas termos
complexos, visto que não possuem informação de estrutura (o grau da folha de uma árvore é
zero). O termo da Figura 4 é um exemplo de termo complexo. Um documento XML também
pode ser considerado como um termo complexo.
Definição 3.2 (Termo Composto).
Um termo composto Ts é uma string produzida com base nos rótulos do termo complexo
correspondente. O termo complexo apresentado na Figura 4, por exemplo, é associado ao
termo composto Livro[Titulo[Consulta, XML]].
Definição 3.3 (Termo Atômico).
Um termo atômico Ta é um termo derivado dos rótulos das folhas dos termos complexos. Os
termos XML e Consulta são termos atômicos derivados do termo complexo mostrado na
Figura 4.
Definição 3.4 (Termo Plano).
Um termo plano Tp é um termo que não contém informação de estrutura. É a definição de
termo comumente usada na recuperação de informação tradicional.
A Figura 5 mostra a relação entre os termos atômicos, planos, complexos e compostos.
Observa-se que o Domínio A é dividido em dois subconjuntos: conjunto dos termos atômicos
e o conjunto dos termos complexos. O Domínio B também é dividido em dois subconjuntos:
conjunto dos termos planos e conjunto dos termos compostos. Além disso, existe uma relação
biunívoca entre os elementos do Domínio A e os elementos do Domínio B.
O conjunto dos termos planos é o domínio da recuperação de informação tradicional,
pois os termos planos não apresentam estrutura. Os conjuntos dos termos atômicos e termos
complexos formam o domínio da recuperação de informação em dados semi-estruturados
(Domínio A). Para simular o modelo vetorial, o trabalho descrito em [32] restringe, em tempo
de consulta, o seu domínio de atuação para o conjunto dos termos atômicos. Os termos
39
atômicos não possuem estrutura e têm um termo plano correspondente. Portanto, essa
restrição possibilita à abordagem descrita em [32] trabalhar em um domínio equivalente ao
domínio da recuperação de informação tradicional.
A Figura 5 mostra, ainda, que os termos compostos são os correspondentes aos termos
complexos no Domínio B. O conjunto de termos complexos é composto por termos que
possuem estrutura (Definição 3.1). Portanto, ao se estender o domínio dos modelos de
recuperação de informação tradicional com termos que possuam informação de estrutura
(termos compostos), obtém-se o Domínio B = {termos planos} ∪ {termos compostos}. Dessa
maneira, é possível fazer o modelo vetorial utilizar a informação de estrutura no cálculo do
ranking.
Livro
Titulo
Consulta
XML
Figura 4: Termo Complexo
Ta1
Ta2
.
.
.
Taz
Tp1
Tp2
.
.
.
Tpz
Termos atômicos
Txz+1
Txz+2
.
.
.
Txn
Tsz+1
Tsz+2
.
.
.
Tsn
Termos planos
Termos compostos
Termos complexos
Domínio A
Domínio B
Figura 5: Domínio dos Termos
Os termos pertencentes ao conjunto de termos compostos fornecem a contextualização
da informação para o modelo vetorial. A necessidade de informação de um usuário é chamada
40
de topic pela TREC. Nesta dissertação, é adotada a mesma notação da TREC. Portanto,
considere-se o tópico.
TC 1 = “Livros que possuem as palavras Consulta e XML em seu título”.
Neste caso, o usuário está procurando por documentos (livros) que possuam a ocorrência do
termo composto Livro[Titulo[Consulta, XML]]. Se o tópico mudar para
TC 2 = “Documentos que possuam as palavras Consultas e XML em seu título”,
para satisfazer este segundo tópico, o usuário procura por documentos com o termo composto
Titulo[Consulta, XML], que pode ser derivado do termo composto Livro[Titulo[Consulta,
XML]]. Para um terceiro tópico,
TC 3 = “Documentos que possuem as palavras Consultas e XML”,
basta que as palavras procuradas ocorram em qualquer parte do documento. Os termos
Consulta e XML também podem ser derivados do termo composto Livro[Titulo[Consulta,
XML]]. Observando esses três exemplos de tópicos, nota-se que, nos dois primeiros
exemplos, o usuário necessita de um sistema de recuperação de informação em que ele possa
expressar um contexto para a sua pesquisa. Por outro lado, o terceiro tópico pode ser satisfeito
por um sistema de recuperação de informação tradicional, pois o usuário está interessado
apenas na ocorrência das palavras sem se preocupar com o contexto na qual elas apareçam.
Na abordagem aqui proposta, a flexibilidade de responder TC 1, TC 2 e TC 3 é conseguida,
porque o Domínio B (ver Figura 5) possui termos sem estrutura (termos planos) e termos
com estrutura (termos compostos).
A quantidade de termos complexos de um documento é igual a quantidade de subárvores, com grau maior ou igual a um, possíveis de serem derivadas desse documento (não
são consideradas as folhas). Para uma coleção de documentos D, a quantidade de termos
complexos é igual a soma de todas as sub-árvores distintas de todos os documentos. Cada
termo composto possui um termo complexo correspondente. Portanto, a quantidade de
termos compostos acrescentadas ao domínio de termos da recuperação de informação
tradicional é igual a quantidade de sub-árvores distintas com grau maior ou igual a um da
coleção de documentos considerada. Esse acréscimo de termos pode causar um aumento
41
exponencial de termos do índice. Por exemplo, considere-se o termo complexo da Figura 5
como sendo um documento XML, suas possíveis sub-árvores são: Livro[Titulo[Consulta,
XML]],
Livro,
Titulo,
Consulta,
XML,
Livro[Titulo],
Livro[Titulo[Consulta]],
Livro[Titulo[XML]], Titulo[Consulta], Titulo[XML], Titulo[Consulta, XML]. Os termos
Consulta e XML são termos que não possuem estrutura (termos planos). Os demais termos
(termos compostos) correspondem aos termos que contêm informação de estrutura. Portanto,
são acrescentados ao domínio da recuperação de informação tradicional nove termos
compostos. Se o termo complexo deste exemplo fosse considerado como um documento, ele
seria representado por dois termos na recuperação de informação tradicional e onze termos na
recuperação de informação em que o domínio de termos é acrescido com os termos
compostos.
3.2 – Aumento na Quantidade de Termos do Índice
A inclusão de termos compostos ao conjunto de palavras-chave no vocabulário da coleção é
uma estratégia simples e intuitiva, se comparada às abordagens propostas na seção 2.4.
Entretanto, ela pode provocar um aumento exponencial de termos no índice em virtude da
combinação dos elementos do documento XML. Este aumento é gerado pelo mapeamento dos
termos complexos para os termos compostos e está relacionado à profundidade da árvore
XML. Observe-se que a quantidade de ramos de uma árvore XML, que representa um
documento, é igual à quantidade de termos planos desse documento. Por exemplo, um
documento que é representado na recuperação de informação tradicional por dez termos
planos, ao ser estruturado por uma árvore XML, a quantidade de ramos dessa árvore também
é dez. Isto ocorre porque é associado a cada termo plano um contexto (ramo da árvore XML).
A quantidade de níveis de uma árvore XML é definida pelo usuário e pelo tipo de informação.
A linguagem XML não restringe uma
quantidade máxima de níveis. Quanto maior a
profundidade e ramificação maior a quantidade de termos compostos. Assim, dependendo da
profundidade da árvore XML, pode ser gerada uma quantidade de termos que torne essa
abordagem computacionalmente inviável.
Para lidar com esse problema, são propostas, nesta dissertação, três estratégias. A
primeira é descartar os termos compostos sem informação de conteúdo. A segunda é descartar
os termos que não obedeçam a hierarquia das árvores dos documentos XML, por exemplo, o
termo Livro[XML] não obedece a hierarquia da árvore do apresentada na Figura 4, pois entre
42
o nó Livro e XML existe o nó Titulo. A terceira é adotar uma estratégia de indexação que
minimize o tamanho do índice.
3.2.1 – Descarte de Termos Compostos sem Informação de Conteúdo
Em um documento XML, a informação de conteúdo está armazenada nas folhas da árvore que
o representa e a informação de contexto é todo caminho da raiz até o último nó não folha. Por
exemplo, no termo complexo mostrado na Figura 4, as informações de conteúdo, Consulta e
XML, estão armazenadas nas folhas e a informação de contexto é o caminho Livro[Titulo].
Quando é feito o mapeamento das sub-árvores desse termo complexo, observa-se que algumas
de suas sub-árvores não apresentam utilidade para o usuário de um sistema de recuperação de
informação. Por exemplo, os termos Livro, Titulo, Livro[Titulo] contêm apenas informação de
estrutura (contexto).
Os termos que possuem apenas informação de contexto não têm utilidade na
recuperação de informação, pois, em geral, o usuário expressa sua necessidade de informação
mediante termos que conjugam informação de contexto e de conteúdo
ou apenas de
conteúdo. Além disso, uma coleção pode ter uma mesma estrutura para todos os seus
documentos. Neste caso, os termos derivados que representarem apenas informação de
contexto podem ser descartados sem causar prejuízo à contextualização oferecida ao usuário.
Na prática, um termo complexo é mapeado para um termo composto somente se estiver
associado a um termo plano (folha da árvore XML).
3.2.2 – Descarte de Termos Derivados dos Termos Complexos que não são Sub-árvores
Observa-se que, ao mapear o termo complexo da Figura 4, não foram considerados os termos
Livro[Consulta], Livro[XML], Livro[Consulta, XML]. Esses termos possuem a característica
de não obedecerem à hierarquia do termo complexo. A Figura 4 mostra que, entre o nó Livro
e Consulta, existe o nó Titulo. Apesar desses termos conterem informações de contexto e de
conteúdo, eles não são sub-árvores de seu respectivo termo complexo. Esta é uma restrição
imposta pela definição de termos complexo (Definição 3.1), pois ela está associada ao
conceito de sub-árvore. Essa restrição causa um prejuízo para a contextualização da
43
necessidade de informação do usuário. Por exemplo, considere-se uma coleção cujos
documentos possuam a estrutura do termo complexo da Figura 4, o tópico
NI 4 = “Livros que possuam a palavra XML”
não pode ser contextualizado, pois o termo Livro[XML] não está indexado. Para este caso, o
usuário pode considerar duas alternativas. A primeira é fazer uma pesquisa mais restrita
considerando
os
livros
que
possuam
a
palavra
XML
em
seu
título
(termo
Livro[Titulo[XML]]). A segunda é fazer uma pesquisa mais ampla considerando todos os
documentos que contenham a palavra XML (termo XML). A decisão de não indexar os termos
compostos que possuam informações de contexto e de conteúdo, mas que não sejam
derivados de uma sub-árvore de seu respectivo termo complexo, pode levar em consideração
a coleção de documentos. Por exemplo, se uma coleção contém documentos com uma
estrutura igual à árvore mostrada na Figura 3(pg 28) e documentos com estrutura igual ao
termo complexo da Figura 4(pg 38), acrescentando um filho com o rótulo ano ao nó livro,
então, para esse tipo de coleção, a indexação dos termos que diferenciam esses dois tipos de
documentos facilita a pesquisa do usuário. Considere-se os tópicos
TC 5 = “Carros com ano de fabricação 2000”
TC 6 = “Livros publicados em 2000”,
usuários com os tópicos TC 5 e TC 6, ao fazerem uma consulta pelo termo plano 2000, obtêm
como resposta documentos referentes a livros publicados no ano 2000 e carros fabricados no
ano 2000. Neste caso, a indexação dos termos livro[2000] e carro[2000] diferenciaria TC 5 e
TC 6. Portanto, a indexação dos termos planos associados ao rótulo da raiz da árvore XML
diferencia os tipos de documentos existentes na coleção. Essa estratégia de redução do
número de termos pode ser adotada de forma parcial, ou seja, descartar apenas os termos que,
após um estudo prévio da estrutura da coleção e do perfil do usuário, não representem uma
perda importante na contextualização das consultas do usuário. Este estudo pode ser realizado
considerando quais são os termos complexos que são potencialmente relevantes para os
usuários e as características da coleção (homogênea ou heterogênea).
Após a discussão apresentada nas seções 3.2.1 e .3.2.2, nota-se que existe um
subconjunto dos termos compostos (termos que possuem apenas informação de contexto) que
44
podem ser descartados e um subconjunto derivado dos termos compostos (termos que não são
sub-árvores dos seus respectivos termos complexos) que pode ou não ser descartado. Para
uma melhor identificação desses termos, são definidos a seguir os termos estendidos e termos
complementares.
Definição 3.5 (Termo Estendido).
Um termo estendido é um termo derivado de um termo composto que possui informação de
contexto e de conteúdo e é obtido de uma sub-árvore de seu respectivo termo complexo. Por
exemplo, considerando o termo complexo da Figura 4 e seu termo composto correspondente
Livro[Titulo[Consulta, XML]], os termos estendidos derivados são: Livro[Titulo[Consulta]],
Livro[Titulo[XML]],
Titulo[Consulta],
Titulo[XML],
Titulo[Consulta,
XML],
Livro[Titulo[Consulta, XML]].
Definição 3.6 (Termo Complementar).
Um termo complementar é um termo que contém informação de estrutura e de conteúdo e não
é sub-árvore de seu respectivo termo complexo. Por exemplo, os termos Livro[Consulta],
Livro[XML], Livro[Consulta, XML] são termos complementares derivados do termo
complexo da Figura 4.
A abordagem proposta nesta dissertação possibilita uma flexibilidade na escolha dos
termos que serão indexados. Caso sejam adotadas as estratégias de descartar os termos que
não possuam informação de conteúdo e termos que não sejam sub-árvores de seus respectivos
termos complexos, então, os termos indexados serão os termos estendidos e os termos planos.
Caso seja adotada apenas a estratégia de descartar os termos que não contenham informação
de conteúdo, então, os termos indexados serão os termos estendidos, termos planos e os
termos complementares. Existe, também, a possibilidade de indexar os termos estendidos,
termos planos e alguns termos complementares, e, por fim, indexar apenas os termos
complementares. Esta última escolha pode deixar de considerar vários termos relevantes para
a consulta contextualizada do usuário. A escolha dos termos a serem indexados, como já foi
dito, pode ser feita em função de um estudo prévio da estrutura da coleção e do perfil do
usuário. Nesta dissertação, é considerada a indexação dos termos estendidos e termos planos.
A Figura 6 mostra que os conjuntos de termos compostos, estendidos, complementares
e os termos que não possuem informação de conteúdo são derivados dos termos complexos.
45
Além disso, mostra que o conjunto de termos compostos é a união dos conjuntos de termos
estendidos e termos que não contêm informação de conteúdo. Os termos estendidos são
obtidos dos termos complexos pela Derivação 1. Essa derivação considera que apenas as subárvores do conjunto dos termos complexos, com informação de conteúdo e contexto, ou
somente de conteúdo (folhas), são mapeadas para o conjunto dos termos estendidos. Os
termos que não possuem informação de conteúdo são obtidos dos termos complexos pela
Derivação 2. Esta derivação considera que somente as sub-árvores com informação de
contexto são mapeadas. Os termos complementares são obtidos dos termos complexos pela
Derivação 3. Esta derivação considera que apenas termos que não contêm uma sub-árvore
correspondente no conjunto dos termos complexos e que possuem informação de contexto e
de conteúdo são mapeados para o conjunto dos termos complementares.
Conjunto dos
Termos Compostos
Derivação 1
Conjunto dos
Termos Estendidos
Derivação 2
Derivação 3
Conjunto dos
Termos Complexos
Conjunto dos termos
que não possui
informação de
conteúdo
Conjunto dos Termos
Complementares
Figura 6: Relação entre os Conjunto de Termos Complexos, Compostos, Estendidos, Complementares e Termos
que não Possuem Informação de Conteúdo.
3.2.3 – Conjunto de Termos como Unidade de Indexação
Após o descarte dos termos compostos, conforme descrito nas seções 3.2.1 e 3.2.2, há uma
redução na quantidade de termos. Esses descartes devem ser considerados como estratégias de
projeto do SRI, de acordo com a coleção de documentos e perfil do usuário. Empregando
46
essas duas estratégias no termo complexo da Figura 4, obtém-se uma redução de seis termos
(considerando o descarte dos termos complementares), restando, ainda, oito termos para
serem indexados. A estratégia proposta nesta seção consiste em indexar termos de forma a
diminuir a quantidade de termos a serem indexados. Observe-se que esses termos podem ser
qualquer uma das variações descritas na seção 3.2.2. Várias técnicas para indexar documentos
semi-estruturados são apresentadas na literatura. Estas técnicas
enfatizam minimizar o
tamanho do índice e otimizar a pesquisa.
Algumas dessas estratégias de indexação usam banco de dados para armazenar os
índices. Assim, elas utilizam as funcionalidade do banco de dados para auxiliar na construção
e pesquisa do índice. São exemplos dessa estratégia os trabalhos apresentados em [4], [20]e
[37]. Em [20], a idéia principal é oferecer um mecanismo eficiente, que permita a atualização
do índice, quando o conteúdo do documento muda. Essa abordagem é indicada para coleções
de documentos cujo conteúdo sofre mudanças freqüentes. Ela cria várias tabelas de índices
organizadas essencialmente para o emprego da estratégia BUS (Bottom Up Scheme). Além
disso, os autores de [20] sugerem a implementação da estratégia BUS em um sistema
gerenciador de banco de dados relacional para facilitar a atualização incremental do índice.
Em [4], também é apresentada uma estratégia de indexação que permite a atualização do
índice. Essa abordagem propõe esquemas de codificação e compressão que possibilitam a
construção do índice para a implementação da busca por proximidade (proximity search).
Essa técnica de indexação é voltada para banco de dados nativos XML (foi testada em Soda2
– banco de dados nativo XML). Em [37], são propostas a integração da pesquisa em texto
completo e a tecnologia de banco de dados para armazenar e recuperar documentos XML.
Para a pesquisa em texto completo, essa abordagem utiliza um índice para a estrutura e outro
para o texto. A principal idéia dessa técnica de indexação é alocar um campo ID para cada
item texto de um elemento XML e registrá-lo no índice de estrutura e no índice de texto. O
índice de estrutura gerencia a hierarquia de cada campo e o índice de texto gerencia o ID do
campo e o ID do documento nos quais as palavras da consulta aparecem.
Existem também estratégias que empregam a hierarquia proveniente da estrutura em
árvores do documento XML e das linguagens de navegação nessa estrutura. Por exemplo, em
[7], são apresentadas novas estruturas de indexação baseadas nos PIDs (Path Identifiers). PID
é um esquema de identificação de nós usado em dois índices diferentes. Essa técnica de
indexação utiliza um índice para dados e outro para estrutura. Em [23], é proposto um
sistema de indexação e armazenamento de dados XML baseado em um esquema de
numeração para elementos. Este esquema determina a relação antecessor-descendente entre
47
elementos pertencentes à hierarquia dos dados XML. Além disso, propõe algoritmos para
processar consultas XML por meio de expressões regulares.
A técnica de indexação descrita em [9] propõe reduzir o tamanho do índice por meio
da eliminação de entradas do índice. Ela é baseada em dois métodos de poda: static index e
term-based. No primeiro, todas as entradas do índice, cujas contribuições para o score da
relevância estejam abaixo de um dado limite, são removidas do índice. No segundo, o limite
para a poda depende do termo. A idéia é remover as entradas do índice cujas contribuições
para o score da relevância de um documento sejam tão pequenas, que o efeito na precisão do
sistema não seja relevante. Essa técnica é baseada na abordagem de compressão com perdas
(lossy compression approach). Nessa abordagem, algumas informações são descartadas. Este
descarte reduz o tamanho do índice do sistema de busca, removendo as entradas menos
importantes do índice. Além disso, é apresentada, em [9], uma simulação em que é mostrado
que essa abordagem é capaz de atingir 35% de diminuição do índice com um decréscimo
médio da precisão de 7% e com efeito algum na precisão dos 10 primeiros resultados. Essa
técnica de indexação é utilizada por Juru [10], que é um mecanismo de pesquisa em texto
completo desenvolvido em java. O Juru, por sua vez, é adaptado e empregado para indexação
em [8].
Em [26], é proposta uma nova técnica para calcular pesos de termos chamada Set
Based Model. A idéia principal é agrupar os termos que aparecem em um mesmo conjunto de
documentos. Assim, a unidade de indexação passa de termo para conjunto de termos (closed
termsets). Esses conjuntos de termos são calculados utilizando o algoritmo chamado CHARM
[39]. Essa abordagem descreve experimentos que mostram a sua eficiência, se comparada ao
modelo vetorial clássico e ao modelo vetorial generalizado. Essa nova estratégia para calcular
pesos de termos, apresentada em [26], é empregada na recuperação de informação tradicional.
Uma das principais contribuições em [26] é propor um modelo em que o custo computacional
de considerar a correlação de termos é viável para grandes coleções de documentos. Vários
modelos que consideram a correlação de termos não podem ser aplicados nem mesmo a
coleções de médio porte devido ao aumento exponencial do vocabulário.
A proposta desta dissertação, de aumentar o domínio dos termos, tem como objetivo
inserir a característica de contextualização em um modelo de recuperação de informação
tradicional (modelo vetorial). Entretanto, a idéia de indexar conjuntos de termos em vez de
termos pode ser utilizada para lidar com o problema de crescimento da quantidade de termos
do índice.
48
As características que contribuíram para a escolha da idéia de indexar conjunto de
termos apresentada em [26] são:
•
Trata o termo estendido como um termo plano;
•
Possui eficiência comprovada na recuperação de informação tradicional;
•
Diminui o tamanho do índice em virtude da indexação dos conjuntos de termos;
Os termos estendidos, que representam as sub-árvores de um termo complexo,
possuem a característica de, geralmente, estar em um mesmo conjunto de termos. Essa
característica é aproveitada para minimizar o crescimento da quantidade de termos,
agrupando-os em um mesmo conjunto de termos. As técnicas de indexação que separam
informação de contexto e conteúdo são descartadas porque nos termos estendidos, essas
informações estão juntas.
O Capítulo 4 apresenta algumas propriedades desses conjuntos de termos utilizados
pelo algoritmo CHARM. Além disse, descreve o algoritmo e mostra, por meio de exemplos,
como ocorre a redução na quantidade de termos a serem indexados.
Capítulo 4
Aplicação do Algoritmo CHARM em Documentos
XML
A estratégia de redução de termos descrita na Seção 3.2.3, é indexar conjunto de termos em
vez de termos. Esta abordagem é apresentada em [26], como uma técnica para calcular pesos
dos termos, baseada na teoria de conjuntos. Os experimentos realizados em [26] comparam o
modelo vetorial, o modelo vetorial generalizado e o set-based model. Os resultados obtidos
mostram que o set-based model melhora a precisão média do ranking se comparado com os
outros dois modelos. Para calcular os conjuntos de termos a serem indexados, é utilizado o
algoritmo CHARM [39]. Este algoritmo tem origem na área de mineração de dados. O seu
objetivo é agrupar os itens que ocorram em um mesmo conjunto de transações. Além disso, a
teoria de regras de associação proporciona a semântica da co-ocorrência de termos que, às
vezes, não está presente na abordagem tf x idf [26].
Após aplicar os descartes de termos propostos nas seções 3.2.1 e 3.2.2, a unidade de
indexação considerada são os termos estendidos e os termos planos. Vale lembrar que a
estratégia descrita em 3.2.2 pode ser empregada de forma total ou parcial, portanto, a unidade
de indexação pode também incluir os termos complementares. Essa variação depende de
como essa estratégia é aplicada. O algoritmo CHARM é aqui empregado para agrupar os
termos (estendidos, planos e/ou complementares) que ocorrem em um mesmo conjunto de
documentos. O objetivo de indexar conjunto de termos é diminuir a quantidade de termos a
serem indexados.
Este capítulo mostra o algoritmo CHARM e uma notação para descrever seus
conceitos. Em seguida, mostra como o algoritmo CHARM realiza o agrupamento dos termos
50
segundo algumas propriedades. Por fim, é apresentado como ele é empregado na recuperação
de informação em dados semi-estruturados mediante dois exemplos.
4.1 – Notação
Para adaptar a notação empregada em [39] ao contexto da recuperação de informação, as
referências a itens e transações foram substituídas em [26] por termos e documentos,
respectivamente. A notação aqui utilizada é:
•
D uma coleção de documentos onde cada documento tem um identificador chamado tid;
•
I o conjunto de termos de uma coleção D;
•
T o conjunto de todos os tids;
•
Um conjunto X ⊆ I é chamado termset;
•
Um conjunto Y ⊆ T é chamado tidset;
•
Um termset com k itens é chamado k-termset;
•
Para um tidset Y, i(Y) corresponde aos termos presentes em todos os documentos do
conjunto Y;
•
Para um termset X, t(X) corresponde aos documentos onde os termos presentes em X
ocorrem;
•
X x t(X) representa o par termset x tidset;
•
σ(X) é o número de documentos em que X ocorre como um subconjunto. Por
exemplo, σ(X) = |t(X)|;
•
O suporte de um termset X é o número de documentos em que ele está presente.
•
sup_min (suporte mínimo) de um termset X é o número mínimo de documentos em que
X deve ocorrer para ser considerado freqüente.
Definição 4.1 (Frequent Termset).
Um termset X é freqüente se sua freqüência é maior ou igual ao sup_min especificado pelo
usuário, ou seja, σ(X) ≥ sup_min.
Definição 4.2 (Maximal Termset).
Um termset X é máximo quando ele não é subconjunto de nenhum outro frequent termset.
51
Definição 4.3 (Closed Termset).
Um closed termset X é um frequent termset, se não existe um super conjunto Y ⊃ X com
σ(X) = σ(Y). A notação utilizada é c(X).
Para exemplificar os conceitos de frequent, maximal e closed termsets, é apresentado
um exemplo adaptado de [39] e [26].
Exemplo 1 (Gerando closed termsets à partir de uma coleção de documentos): Considerese um vocabulário de cinco termos I = {a, t, c, d, w} e uma coleção D de seis documentos dj,
1 ≤ j ≤ 6. A distribuição dos termos nos documentos da coleção D ocorre da seguinte maneira,
D = {(a, t, c, w), (c, d, w), (a, t, c, w), (a, c, d, w), (a, t, c, d, w), (t, c, d)}, como mostra a
Figura 7. O suporte mínimo considerado é de 50%, o que significa que um termset é
freqüente, se ele aparece em pelo menos três dos seis documentos. A Tabela 2 mostra todos os
frequent, closed e maximal termsets para a coleção de documentos D.
d1
d3
d2
at
cw
d4
cd
w
d5
ac
dw
at
cw
d6
tc
d
atc
dw
Figura 7: Coleção D de Documentos
Tabela 2: Frequent, Closed e Maximal Termsets para a Coleção de Documentos
Freqüência
100%
83%
67%
67%
67%
50%
50%
Frequent Termset
c
w, cw
a, ac, aw, acw
t, tc
d, cd
at, atc atw, tw, tcw
atcw
dw, cdw
Closed Termset
Maximal Termset
c
cw
acw
tc
cd
atcw
atcw
cdw
cdw
52
A Tabela 2 mostra os frequent, closed, maximal termsets e suas respectivas
freqüências na coleção de documentos apresentada na Figura 7. Por exemplo, a primeira
coluna da primeira linha denota que o conjunto {c} ocorre em todos os documentos da
coleção. A segunda coluna da primeira linha aponta que o conjunto {c} é freqüente, pois seu
suporte (número de documentos que ele ocorre) e maior do que o suporte mínimo (neste
exemplo é igual a três). A terceira coluna da primeira linha indica que o termo c é um closed
termset uma vez ele é freqüente e não existe um conjunto Y tal que, Y ⊃ {c} e σ(Y) = σ({c}).
Observe-se que o conjunto {c} é subconjunto de vários outros conjuntos, entretanto, os
suportes destes conjuntos são diferentes. Portanto, pode-se afirmar que {c} é um closed
termset. A quarta coluna da sexta linha mostra que o conjunto {atcw} é um maximal termset,
pois ele não é subconjunto de nenhum frequent termset. Em [26], é apresentado uma
discussão sobre a escolha dos closed termsets como unidade de indexação em detrimento aos
frequent e maximal termsets. Essa escolha é justificada, porque, se comparado aos frequent
termsets, os closed termsets são gerados em menor número como mostra a Tabela 2. No
Exemplo 1, há dezenove frequent termsets e apenas sete closed termsets. Por outro lado, os
maximal termsets não possuem a mesma quantidade de informação que os closed termsets, o
que torna difícil sua utilização para encontrar co-ocorrênca de termos. Isto acontece porque
ocorrências de padrões de cada termset são descartadas. Assim como em [26], aqui também
são considerados os closed termsets como unidades de indexação.
Para calcular os closed termsets de uma coleção de documentos é, empregado um
algoritmo para mineração de dados chamado CHARM. Ele é basicamente um algoritmo de
enumeração que usa uma árvore de pesquisa chamada itemset-tidset. Ele evita várias
comparações na pesquisa, produzindo, assim, uma estratégia eficiente de poda. Este algoritmo
é aqui adaptado para trabalhar com termos e documentos.
A seção 4.2 descreve como é construída a árvore Termset-Tidset na qual o algoritmo
CHARM realiza a pesquisa pelos closed termsets. Em seguida, a seção 4.3 descreve o pseudo
código do algoritmo CHARM e as propriedades utilizadas para otimizar o agrupamento de
termos.
4.2 – Árvore de Pesquisa Termset-Tidset
Os nós da árvore de pesquisa Termset-Tidset representam as combinações dos termos
da coleção de documentos segundo uma relação de equivalência (Definição 4.5). O Algoritmo
53
CHARM realiza a busca por closed itemsets na árvore de pesquisa Itemset-Tidset. Com a
adaptação para o contexto da recuperação de informação essa árvore passa a ser chamada
Temset-Tidset. Para facilitar a notação, um termset {a, b, c} é denotado por abc e um tiset {2,
4, 5} por 245.
Definição 4.4 (Função Prefixo).
Uma função prefixo p é definida como p(X, k) = X[1:k] onde k é o comprimento do prefixo
do termset X. Por exemplo, considere-se o termset X = abcd, então, p(X, 2) = ab.
Definição 4.5 (Relação de Equivalência).
A relação de equivalência θk entre dois termsets X e Y é definida como:
∀X, Y ⊆ I, X ≡θk Y ⇔ p(X, k) = p(Y, k),
ou seja, dois termsets pertencem a mesma classe se eles possuem um prefixo de comprimento
k em comum. Por exemplo, considere-se X = abcd e Y = abef, então, X ≡θ2 Y pois
p(X,2) = p(Y,2). Entretanto, X ≡θ3 Y, pois p(X,3) ≠ p(Y,3).
A Figura 8 é a árvore de pesquisa Termset-Tidset do Exemplo 1. Cada nó na árvore
Termset-Tidset é representado pelo par termset-tidset (X x t(X)). Todos os filhos de um dado
nó (X x t(X)) pertencem à classe de equivalência de X, pois todos eles compartilham do
mesmo prefixo de X. Uma classe de equivalência P é denotada por [P] = {l1, l2, ..., ln},
onde P é o nó pai (prefixo) e cada li é um termo, assim, um nó da árvore Termset-Tidset pode
ser representado por Pli x t(Pli). Por exemplo, a raiz da árvore da Figura 8 corresponde à
classe [] = {a, c, d, t, w}, e o filho mais à esquerda desta árvore representa a classe [a] de
todos os termos que contêm o termo “a” como prefixo.
4.3 – Propriedades Básicas dos pares Termset-Tidset
Para encontrar o closed termset de um termset X, são executados dois passos:
1 – Calcular a imagem no espaço dos documentos para obter t(X) – Conforme especificado na
seção 4.1 t(X) representa os documentos em que o termset X ocorre. Portanto, nesse passo,
são calculados os documentos nos quais X ocorre. Esses documentos formam uma imagem no
espaço dos documentos.
54
2 – Mapear t(X) para a sua imagem no espaço dos termos a fim de obter i(t(X)) – Uma vez
calculado t(X), o segundo passo consiste em calcular os termsets que ocorrem nos
documentos representados por t(X), ou seja, aplicar a função i( ) nos documentos que
compõem a imagem calculada no primeiro passo por t(X).
Desse modo, c(X) = i(t(X)). Um termset X é closed se, e somente se, X = c(X). Por
exemplo, o termset acw do Exemplo 1, é closed, porque c(acw) = i(t(acw)) = i(1345) = acw.
O suporte de um termset X é igual ao suporte de seu fecho, ou seja, σ(X) = σ(c(X)).
Para quaisquer dois nós da árvore Termset-Tidset, Xi x t(Xi) e Xj x t(Xj), se Xi ⊆ Xj
então t(Xi) ⊆ t(Xj). Por exemplo, para acw ⊆ actw, t(acw) = 1345 ⊇ 135 = t(actw).
[ ]x123456
a x1345
ac x1345
acd x45
act x135
acdt x5 acdw x45
c x123456
ad x45 at x135 aw x1345
acw x1345
actw x135
adw x45
adtw x5
cd x2456 ct x1356
adt x5 atw x135
d x2456
t x1356
cw x12345 dt x56
dw x245
w x12345
tw x135
cdt x56 cdw x245 ctw x135 dtw x5
cdtwt x5
acdtw x45
Figura 8: Árvore de Pesquisa Termset-Tidset do Exemplo 1
Definição 4.6 (Função Ordenação).
Seja f : ρ (I) → N um mapeamento um-para-um dos termsets para os inteiros. Dado dois
termsets Xi e Xj, então Xi ≤f Xj se, e somente se, f(Xi) ≤ f(Xj). A função f define uma ordem
sobre todos os elementos do conjunto de todos os termsets.
Neste trabalho, f representa
a ordem lexicográfica para os termos. Há quatro
propriedades básicas do par termset-tidset, que são exploradas pelo algoritmo CHARM para
55
promover uma busca eficiente dos closed termsets. Sejam Xi x t(Xi) e Xj x t(Xj) quaisquer dois
membros de uma classe [P], com Xi ≤f Xj onde f é a ordem adotada entre os termos. As
propriedades são:
1 – Se t(Xi) = t(Xj) então c(Xi) = c(Xj) = c(Xi ∪Xj);
2 – Se t(Xi) ⊂ t(Xj) então c(Xi) ≠ c(Xj), mas c(Xi) = c(Xi ∪Xj);
3 – Se t(Xi) ⊃ t(Xj) então c(Xi) ≠ c(Xj), mas c(Xj) = c(Xi ∪Xj);
4 – Se t(Xi) ≠ t(Xj) então c(Xi) ≠ c(Xj) ≠ c(Xi ∪Xj).
Estas propriedades comparam os documentos em que Xi e Xj aparecem. Desta
maneira, são obtidas informações sobre seus closed termsets. Por exemplo, se a propriedade 1
é verificada, isto significa que os Xi e Xj aparecem no mesmo conjunto de documentos,
portanto, eles podem ser agrupados (união entre esses dois conjuntos) em um mesmo
conjunto. Observe-se que a rotina CHARM-PROPERTY, apresentada a seguir, utiliza essa
propriedade para excluir Xj e, assim, evitar uma comparação com Xj nas próxima iterações do
algoritmo.
Essas propriedades são provadas e discutidas em [39]. O pseudo código do algoritmo
CHARM é apresentado na Figura 9. Ele está dividido em 3 rotinas. A primeira (CHARM) é
responsável por iniciar a classe [P], retirando os pares termset-tidset que possuam um suporte
menor que o mínimo e, em seguida, chamando a rotina CHARM-EXTEND. A segunda rotina
(CHARM-EXTEND) é responsável por comparar cada par termset-tidset presente em [P] com
os demais elementos de [P] para calcular os closed termsets. A terceira rotina (CHARMPROPERTY) é responsável por testar as propriedades descritas neste capítulo. Dependendo
da propriedade verificada, é executada uma operação para otimizar o cálculo dos closed
termsets.
4.4 – Algoritmo CHARM na Recuperação de Informação em Dados Semiestruturados
O índice tende a aumentar de forma exponencial ao considerar os termos estendidos no
modelo vetorial. Para lidar com esse problema, a proposta aqui é indexar os closed termsets
em vez de termos como apresentado em [26]. O algoritmo CHARM é usado para obter os
closed termsets.
56
CHARM (D, sup_min):
1.
[P] = {Xi x t(Xi) : Xi ∈I ∧ σ(Xi) ≥ sup_min}
2.
CHARM-EXTEND ([P], C = ∅)
3.
return C // all closed sets
CHARM-EXTEND ([P], C):
4.
for each Xi x t(Xi) in [P]
5.
[Pi] = ∅ and X = Xi
6.
for each Xj x t(Xj) em [P], with Xj ≥f Xi
7.
X = X ∪ Xj and Y = t(Xi) ∩ t(Xj)
8.
CHARM-PROPERTY ([P], [Pi])
9.
if ([Pi] ≠∅) then CHARM-EXTEND ([Pi], C)
10.
delete [Pi]
11.
C=C∪X
// if X is not subsumed
CHARM-PROPERTY ([P], [Pi]):
12.
13.
if (σ(X) ≥ sup_min) then
if t(Xi) = t(Xj) then // Property 1
14.
Remove Xj from [P]
15.
Replace all Xi with X
16.
else if t(Xi) ⊂ t(Xj) then
17.
Replace all Xi with X
18.
else if t(Xi) ⊃ t(Xj) then // Property 3
19.
Remove Xj from [P]
20.
Add X xY to [Pi]
21.
22.
// Property 2
// Use ordering f
else if t(Xi) ≠ t(Xj) then // Property 4
Add X xY to [Pi]
// Use ordering f
Figura 9: Pseudo Código do Algoritmo CHARM
Para que os termos estendidos possam ser ordenados segundo a ordem lexicográfica
das folhas de seus termos complexos correspondentes, é adotada uma notação simplificada.
Considere-se o termo composto Livro[Titulo[Consulta, XML]] e o seu termo complexo
correspondente (Figura 4), as sub-árvores deste termo complexo são representadas pelos
seguintes termos estendidos e termos planos: Livro[Titulo[Consulta]], Livro[Titulo[XML]],
Titulo[Consulta], Titulo[XML], Titulo[Consulta, XML], Livro[Titulo[Consulta, XML]],
Consulta, XML. Observe-se que o termo estendido Titulo[Consulta, XML] denota que os
57
termos Consulta e XML ocorrem no título do documento. Essa notação pode ser simplificada
invertendo o sentido dos elementos que compõem o termo estendido. Assim, o termo
estendido passa a iniciar sempre com a folha do termo complexo correspondente. Por
exemplo, a notação simplificada dos termos estendidos acima é: Consulta, XML,
Consulta\Titulo\Livro, XML\Titulo\Livro, Consulta\Titulo, XML\Titulo. Note-se que a
quantidade de termos diminuiu de oito para seis. A semântica do termo Titulo[Consulta,
XML] é obtida consultando os termos Consulta\Titulo e XML\Titulo, por isso, ele é
desconsiderado nessa notação simplificada. Analogamente, a semântica do termo
Livro[Titulo[Consulta, XML]] é obtida consultando os termos Consulta\Titulo\Livro e
XML\Titulo\Livro. Observe-se que, ao aplicar as estratégias para redução de termos descritas
nas seções 3.2.1 e 3.2.2 e a adoção da notação simplificada, o documento XML, representado
pelo termo complexo da Figura 4, passa a gerar seis termos em vez de onze termos, como
inicialmente (sem considerar os termos complementares). Uma redução de quase 50%.
Para um melhor entendimento do algoritmo CHARM e de sua aplicação na
recuperação de informação em dados semi-estruturados, são descritas, a seguir, dois
exemplos. Esses exemplos consideram pequenas coleções de documentos, para que seja
possível explicar passo a passo a execução do algoritmo CHARM na obtenção dos closed
termsets.
Uma coleção de documentos estruturada em uma árvore XML possui algumas
características que influenciam na quantidade de termos estendidos. Apresentam-se a seguir
as definições de nível de um documento e de uma coleção, coleção homogênea e macro
contexto para estabelecer uma relação entre essas propriedades e a quantidade de termos
estendidos acrescentados ao domínio de termos do modelo vetorial.
Definição 4.7 (Nível de um Documento).
O nível de um documento XML é dado pelo somatório dos nós pertencentes ao maior
caminho entre o nó raiz e o nó folha, ou seja, é a profunidade da árvore XML mais 1. Por
exemplo, todos os documentos da coleção D (ver Figura 10) possuem o mesmo nível, que é
igual a 3.
Definição 4.8 (Nível de uma Coleção). O nível de uma coleção de documentos é igual ao
nível do documento que possui o maior nível dentre os documentos da coleção. Por exemplo,
o nível da coleção de documento D
documentos tem o mesmo nível.
(ver Figura 10) é igual a 3, pois todos os seus
58
Definição 4.9 (Coleção Homogênea).
Um coleção de documentos é homogênea, se todas as raízes de seus documentos possuem o
mesmo rótulo. Por exemplo, a coleção D (ver Figura 10) é homogênea, porque todos os
documentos possuem o rótulo livro em sua raízes.
Definição 4.9 (Macro Contexto).
Um macro contexto é definido pelo rótulo da raiz de um documento. Por exemplo, na coleção
D (ver Figura 10), todos dos documentos possuem os rótulos da raízes iguais, então, a
coleção D tem um macro contexto. A coleção de documentos D’ (ver Figura 13) possui 2
macro contextos visto que seus documentos possuem raízes com dois diferentes rótulos.
Exemplo 2 (Gerando closed termsets de uma coleção homogênea de documentos):
Considere-se uma coleção de documentos semi-estruturados D com cinco documentos
D = {d1, d2, d3, d4, d5}. As árvores XML dos documentos são apresentadas na Figura 10.
A Figura 10 mostra as árvores XML de uma coleção de livros. Nota-se que é uma
coleção de livros, porque a raiz de todos os documentos têm o rótulo livro. Ela está
estruturada da seguinte forma:
•
Cada documento da coleção tem um nó em sua árvore, que possui o rótulo título. As
folhas deste nó correspondem ao título do livro.
•
Cada documento da coleção tem uma nó em sua árvore, que possui o rótulo autor. As
folhas deste nó correspondem ao autor do livro.
•
Cada documento da coleção tem um nó em sua árvore, que possui o rótulo anoP. As
folhas deste nó correspondem ao ano de publicação do livro.
A Figura 11 mostra o vocabulário da coleção de documentos D. Observa-se que o
conjunto de termos Tp = {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49} são os
termos correspondentes às folhas das árvores XML dos documentos da coleção D (termos
planos). Estes são os termos que contêm apenas a informação de conteúdo. Eles representam
o vocabulário dessa coleção de documentos para a recuperação de informação tradicional. Os
termos que não estão presentes no conjunto Tp possuem informação de contexto e de
conteúdo (termos estendidos). Observe-se que eles são representados em uma notação
simplificada e seguem as regras de derivação descritas no Capitulo 3. O vocabulário da
coleção de documentos D possui 17 termos planos e 34 termos estendidos em um total de 51
termos. Os termos planos são utilizados na recuperação de informação tradicional. Os termos
59
estendidos representam o aumento do domínio dos termos proposto neste trabalho para
permitir a contextualização da consulta do usuário.
d1
titulo
homem
anoP
autor
calculava
d3
titulo
crise
d2
livro
malba
tahan
d4
anoP
d5
titulo
tabagismo
1985 crise
malba
tahan
anoP
autor
maxismo
perry
livro
anoP
autor
jose
rosemberg
1962
livro
titulo
anderson
perry
anoP
autor
matematica
1998 didatica
livro
autor
maxismo
titulo
livro
1985
Figura 10: Coleção o D de documentos Semi-estruturados do Exemplo 2.
anderson
1988
60
1 – 1962
2 – 1962\anoP
3 – 1962\anoP\livro
4 – 1985
5 – 1985\anoP
6 – 1985\anoP\livro
7 – 1988
8 – 1988\anoP
9 – 1988\anoP\livro
10 – 1998
11 – 1998\anoP
12 – 1998\anoP\livro
13 – anderson
14 – anderson\autor
15 – anderson\autor\livro
16 – calculava
17 – calculava\titulo
18 – calculava\titulo\livro
19 – crise
20 – crise\titulo
21 – crise\titulo\livro
22 – didatica
23 – didatica\titulo
24 – didatica\titulo\livro
25 – homem
26 – home\titulo
27 – homem\titulo\livro
28 – jose
29 – jose\autor
30 – jose\autor\livro
31 – malba
32 – malba\autor
33 – malba\autor\livro
34 – matematica
35 – matematica\titulo
36 – matematica\titulo\livro
37 – maxismo
38 – maxismo\titulo
39 – maxismo\titulo\livro
40 – perry
41 – perry\autor
42 – perry\autor\livro
43 – rosemberg
44 – rosemberg\autor
45 – rosemberg\autor\livro
46 – tabagismo
47 – tabagismo\titulo
48 – tabagismo\titulo\livro
49 – tahan
50 – tahan\autor
51 – tahan\autor\livro
Figura 11: Vocabulário do Exemplo 2
Portanto, para o Exemplo 2, o domínio seria aumentado de 34 termos. Pode-se
verificar que, para cada termo plano, são derivados 2 termos estendidos (34 = 17 × 2) e a
quantidade total de termos do vocabulário é 3 vezes a quantidade de termos estendidos
(51 = 17 × 3). A coleção de documentos D apresenta duas características que permitem
estabelecer essa proporção. Primeiro, todas as árvores de documentos XML possuem o
mesmo nível. Segundo, a coleção de documentos D é uma coleção homogênea.
As proporções identificadas para a coleção de documentos desse exemplo podem ser
generalizadas para a × n (quantidade de termos da coleção de documentos) e a × (n-1)
(quantidade de termos estendidos) onde a é a quantidade de termos planos e n é o nível da
coleção de documentos. Essa generalização é possível, pois um termo estendido deve,
necessariamente, conter informação de conteúdo (folha da árvore) e ser sub-árvore de seu
respectivo termo complexo (Definição 3.5). Se a coleção de documentos é homogênea e
possui documentos com níveis diferentes, então, a quantidade de termos estendidos
acrescentados ao domínio da recuperação de informação tradicional é menor do que a × (n-1).
Por exemplo, a coleção D de documentos, mostrada na Figura 10, possui todos os documentos
com nível igual a três, suponha-se que um ou mais de seus documentos tenha nível menor que
três. Neste caso, o número de termos da coleção seria menor do que 51, pois a quantidade de
termos estendidos gerados é menor. Portanto, se a coleção de documentos for homogênea, no
pior caso, é gerado a × (n-1) termos estendidos para cada termo plano da coleção.
Para gerar os closed termsets do Exemplo 2, é considerado um suporte mínimo de
40%, ou seja, para que o termo seja considerado pelo algoritmo CHARM, é necessário que ele
61
ocorra em pelo menos 2 documentos da coleção D. A escolha do suporte mínimo é um
ponto crítico, pois, se o suporte mínimo for alto, termos relevantes para o processo de
recuperação de informação podem ser descartados. Em [26], é apresentado um gráfico que
mostra o impacto da variação do suporte mínimo em relação a precisão na TreC-3. Os termos
do conjunto de termos TD = {1, 2, 3, 7, 8, 9, 10, 11, 12, 16, 17, 18, 22, 23, 24, 25, 26, 27,
28, 29, 30, 34, 35, 36, 43, 44, 45, 46, 47, 48} possuem um suporte mínimo menor que 40%,
por isso, não são considerados pelo algoritmo. O suporte mínimo de 40% foi escolhido para
exemplificar esse descarte de termos. O conjunto de termos submetido ao algoritmo
CHARM é TR = {4, 5, 6, 13, 14, 15, 19, 20, 21, 31, 32, 33, 37, 38, 39, 40, 41, 42, 49, 50, 51}.
Na primeira linha do algoritmo CHARM, o vocabulário é reduzido aos termos do
conjunto TR. A rotina CHARM-EXTEND faz as combinações entre os termos e verifica se o
resultado é um closed termset por meio da rotina CHARM-PROPERTY. O primeiro termo a
ser considerado é o termo 4. O laço da linha 6 é responsável por combinar todos os outros
termos do conjunto TR com o termo 4. Dentro desse laço, existe uma chamada à rotina
CHARM-EXTEND, na linha 8, que verifica se o resultado da combinação é um close termset
e aponta que ação deve ser executada. O termo 4 é, assim, combinado com o termo 5. O
resultado dessa combinação é o par termset-tidset 4,5xd3d5. Essa notação denota que os
termos 4 e 5 ocorrem nos documentos d3 e d5. A rotina CHARM-EXTEND verifica que o
termset-tidset 4,5xd3d5 satisfaz a primeira propriedade. Portanto, o termo 5 é removido e todas
as ocorrências do termset-tidset 4xd3d5 são substituídas pelo termset-tidset 4,5xd3d5. Voltando
para o laço da linha 6, o próximo termo a ser considerado é o termo 6 (o termos 5 foi
descartado). O termo 5 é descartado, porque ele ocorre no mesmo conjunto de documentos
que o termset-tidset 4,5xd3d5. O termset-tidset gerado, então, é o 4,5,6xd3d5. Também é
verificada a propriedade 1 para o termset-tidset 4,5,6xd3d5. O próximo termo é o 13, logo, o
termset-tidset gerado é 4,5,6,13xd3. Neste, o teste da linha 12 falha por o termset-tidset
4,5,6,13xd3 esta presente apenas no documento d3, ou seja, em menos de dois documentos o
que é abaixo do suporte mínimo exigido. O suporte é reduzido, por que, na linha 7, é feita a
interseção dos documentos onde o termo 13 (d3, d4) e o termset-tidset 4,5,6x d3d5 ocorrem.
Portanto, o termo 13 não é incorporado ao termset 4,5,6xd3d5. Todos os demais termos, ao
serem combinados com o termset-tidset 4,5,6xd3d5, também terão suporte menor que o
mínimo. O primeiro closed termset é C1 = {4, 5, 6xd3d5}.
O próximo termo é o 13, porque o 5 e 6 foram descartados conforme descrito no
parágrafo anterior. O termo 13 é combinado como o termo 14, gerando o termset-tidset
62
13,14xd3d4. É verificada a primeira propriedade para esse termset-tidset. Então, é descartado
o termo 14 e todas as ocorrências do termset-tidset 13xd3d4 são substituídas pelo termsettidset 13,14xd3d4. Este fato repete-se para os termos 15, 16, 19, 20, 21, 38, 39, 40, 41 e 42.
Para os termos 31, 32, 33, 49, 50 e 51, o suporte do termset-tidset gerado é menor do que o
mínimo. Portanto, o segundo closed termset é C2 = {13, 14, 15, 16, 19, 20, 21, 38, 39, 40, 41,
42x d3d4}. O próximo é o termo 31, que será comparado com os termos 32, 33, 49, 50 e 51. É
verificada a propriedade 1 para as combinações com esses termos. O terceiro e último
closed termset é C3 = {31, 32, 33, 49, 50, 51x d1d2}. A Figura 12 mostra como o Algoritmo
CHARM é executado para o Exemplo 2.
{}
4xd3d5
13xd3d4
31xd1d2
4,5xd3d5
13,14xd3d4
31,32xd1d2
4,5,6xd3d5
13,14,15xd3d4
31,32,33xd1d2
13,14,15,19xd3d4
31,32,33,49xd1d2
13,14,15,19,20xd3d4
31,32,33,49,50xd1d2
13,14,15,19,20,21xd3d4
31,32,33,49,50,51xd1d2
13,14,15,19,20,21,37xd3d4
13,14,15,19,20,21,37,38xd3d4
13,14,15,19,20,21,37,38,39xd3d4
13,14,15,19,20,21,37,38,39,40xd3d4
13,14,15,19,20,21,37,38,39,40,41xd3d4
13,14,15,19,20,21,37,38,39,40,41,42xd3d4
Figura 12: Processo de Busca para o Exemplo 2 Usando Tidsets
Após aplicar o algoritmo CHARM ao conjunto de termos TR, são gerados três closed
termsets C1, C2 e C3. A Tabela 3 mostra uma comparação entre a quantidade de termos na
recuperação de informação tradicional, na recuperação de informação considerando o domínio
aumentado dos termos ({termos planos} ∪ {termos estendidos}) e empregando o conceito de
closed termsets.
A quantidade de termos estendidos nos closed termsets é o número de termos do
vocabulário menos os termos que não possuem suporte mínimo maior do que o determinado
(conjunto TD). Entretanto, como a unidade de indexação é o closed termset, então, o índice
63
para a coleção de documentos D tem apenas 3 entradas a saber C1 = {4, 5, 6xd3d5}, C2 = {13,
14, 15, 16, 19, 20, 21, 38, 39, 40, 41, 42x d3d4} e C3 = {31, 32, 33, 49, 50, 51x d1d2}.
Tabela 3: Comparação da Quantidade de Termos Indexados do Exemplo 2
Abordagens
Recuperação de Informação tradicional
Recuperação de informação com o domínio aumentado
Recuperação de informação com o domínio aumentado empregando o
conceito de conjunto de termos
Quantidade de termos
indexados
17
51
3
Conclui-se que a indexação dos closed termsets diminui consideravelmente a
quantidade de termos a serem indexados. Observando no Exemplo 2, verifica-se que os
termos estendidos que contêm um determinado termo plano como sua
informação de
conteúdo estão no mesmo closed termset. Por exemplo, o termo 4 é um termo plano, pois não
contém informação de contexto, os termos estendidos 5 e 6 são termos que possuem
informação de contexto e de conteúdo. A informação de conteúdo dos termos estendidos 5 e 6
é exatamente o termo 4. Os termos 4, 5, 6 estão no mesmo closed termset. Esta é uma
tendência natural, pois esses termos, geralmente, estão presentes em um mesmo conjunto de
documentos. A explicação para este fato é simples, o termo 4 (termo plano) ocorre nos
documentos d3 e d5. Além disso, a estrutura (\anop\livro) que contextualiza o termo 4 é a
mesma para os dois documentos. Por isso, os termos 4, 5 e 6 estão no mesmo closed termset.
Essa característica faz com que seja gerado um número menor de closed termsets. Isto ocorre,
porque os termos que possuem informação de contexto e conteúdo tendem a ser agrupados no
mesmo conjunto no qual está o termo que representa a sua informação de conteúdo.
A quantidade de closed termsets é menor do que a quantidade de termos planos (ver
Tabela 3). Portanto, para o Exemplo 2, o número de termos planos indexados na recuperação
de informação tradicional, para a coleção de documentos D, é maior do que o número de
closed termsets. Isso quer dizer que, neste caso, é possível acrescentar a contextualização à
consulta do usuário e, ainda, construir um índice menor do que na recuperação de informação
tradicional. Assim, a estratégia de indexar conjunto de termos em vez de termos mostra-se
eficiente para lidar com o problema de crescimento do índice. Vale lembrar que
características com nível da coleção de documentos, ramificação das árvores XML e
quantidade de macro contextos da coleção influenciam no número de
gerados.
closed termsets
64
Exemplo 3 (Gerando closed termsets de uma coleção não homogênia de documentos):
Considere-se uma coleção de documentos semi-estruturados D’ com 3 documentos D’ = {d1,
d2, d3}. As árvores XML dos documentos são apresentadas na Figura 13.
A Figura 13 mostra as árvores XML de uma coleção de documentos D’. Esta coleção
de documentos possui a mesma estrutura da coleção D. Entretanto, D’ é uma coleção de livros
e CDs, ou seja, D’ não é homogênea. A Figura 14 mostra o vocabulário da coleção D’.
Para gerar os closed termsets do Exemplo 3, é considerado um suporte mínimo de
33,33%. Assim, todos os termos do vocabulário do Exemplo 3 são iguais ou estão acima do
suporte mínimo. No Exemplo 2, foi considerado um suporte de 40%, que limitou os termos da
coleção de documentos D que foram processados pelo algoritmo CHARM para o conjunto de
termos de TR. Portanto, dependendo do suporte mínimo escolhido, termos do vocabulário
podem ser descartados. A execução do algoritmo CHARM inicia-se pelo termo 1. Ao entrar
no laço da linha 6, o termo 1 é combinado com o termo 2, gerando o termset-tidset 1,2xd1d2.
É verificada a primeira propriedade para este termset-tidset, assim, o termo 2 é descartado e o
termo termset-tidset 1xd1d2 é substituído pelo termset-tidset 1,2xd1d2.
d1
titulo
1980
livro
d2
anoP
autor
marcos
titulo
jesus
1980
d3
titulo
futuro
futuro
anoP
autor
computador
silva
1980
livro
anoP
autor
computador
CD
silva
1990
Figura 13: Coleção D’ de documentos semi-estruturados do Exemplo 3
A próxima combinação é com o termo 3, gerando o termset-tidset 1,2,3xd2. É
verificada a terceira propriedade, então, o termo 3 é apagado e o termset-tidset 1,2,3xd2 é
65
acrescentado a P1. Este processo ser repete para os termos 4, 5, 6, 10, 11, 12, 14, 15, 16 18,
19, 20, 21, 22, 23, 24, 25 e 26. Para os termos 7, 8, 9, 13, 17, 27, o teste da linha 12 falha. Ao
final da combinação do termo 1 com os demais termos do vocabulário, é encontrado o
primeiro closed termset C’1 = {1, 2xd1d2}. O próximo passo é chamar recursivamente a rotina
CHARM-EXTEND para P1 ={1,2,3xd2; 1,2,4xd1; 1,2,5xd1; 1,2,6xd1; 1,2,10xd2; 1,2,11xd2;
1,2,12xd2; 1,2,14xd2; 1,2,15xd2; 1,2,16xd2; 1,2,18xd1; 1,2,19xd1; 1,2,20xd1; 1,2,21xd1;
1,2,22xd1; 1,2,23xd1; 1,2,24xd2; 1,2,25xd2; 1,2,226xd2;}. Ao combinar 1,2,3xd2 com os
termset-tidset de P1 que está presente apenas em d1, a condição da linha 12 falha. Quando a
combinação é feita com os termset-tidset, que também ocorrem em d2, a propriedade 1 é
verificada e, então, é obtido o segundo closed termset C’2 = {1, 2, 3, 10, 11, 12, 14, 15, 16,
24, 25, 26xd2}.
1 – 1980
2 – 1980 \anoP
3 – 1980 \anoP\CD
4 – 1980 \anoP\livro
5 – 1980 \titulo
6 – 1980 \titulo\livro
7 – 1990
8 – 1990\anoP
9 – 1990\anoP\livro
10 – computador
11 – computador\titulo
12 – computador\titulo\CD
13 – computador\titulo\livro
14 – futuro
15 – futuro\titulo
16 – futuro\titulo\CD
17 – futuro\titulo\livro
18 – jesus
19 – jesus\autor
20 – jesus\autor\livro
21 – marcos
22 – marcos\autor
23 – marcos\autor\livro
24 – silva
25 – silva\autor
26 – silva\autor\CD
27 – silva\autor\livro
Figura 14: Vocabulário do Exemplo 3
O próximo passo é combinar o termset-tidset 1,2,4xd1 com os demais termos. Ao
combinar 1,2,4xd1 com os termset-tidset de P1 que está presente apenas em d2, a condição da
linha 12 falha. Quando a combinação é feita com os termset-tidset, que também ocorrem em
d1, a propriedade 1 é verificada e é obtido o terceiro closed termset C’3 = {1, 2, 4, 5, 6, 18,
19,20, 21, 22, 23xd1}. O termo 7 é o próximo termo a ser combinado com os termos restantes
de P. Ao combinar o termo 7 com o termo 8, a propriedade 1 é verificada, gerando o termsettidset 7,8xd3. Este processo repete-se para os termos 9, 13, 17 e 27. Para a combinação do
termo 7 com os termos 10, 11, 14, 15, 24, 25, é verificada a propriedade 2. Ao final das
combinações com o termo 7, é encontrado o quarto closed termset C’4 = {7, 8, 9, 10, 11, 13,
66
14, 15, 17, 24, 25, 27xd3}. O termo 10 é o próximo termo a ser combinado. Ele é combinado
com o termo 11 e é verificada a propriedade 1. O processo repente-se para os termos 14, 15,
24, 25. Ao final das combinações com o termo 10 é encontrado o quinto closed termset
C’5 = {10, 11, 14, 15, 24, 25xd2d3}.A Figura 15 mostra como o Algoritmo CHARM é
executado para o Exemplo 3.
As proporções a × n e a × (n – 1) verificadas no Exemplo 2 não acontecem no
Exemplo 3. A quantidade total de termos é 27 e 7 × 3 = 21, onde 7 é a quantidade de termos
planos e 3 o nível da coleção de documentos D’. A quantidade de termos estendidos gerados é
igual a 20 e 7 × 2 = 14, onde 7 é a quantidade de termos planos e 2 o nível da coleção de
documentos menos 1. Esse fato, ocorre porque a coleção D’ não é homogênea (livros e CDs).
Portanto, para coleções de documentos heterogêneas, a quantidade de termos estendidos
obtidos é maior do que n - 1 vezes a quantidade de termos planos. Entretanto, pode-se
observar que a quantidade de closed termsets gerada ainda é menor do que a quantidade de
termos planos. Observa-se, também, que, apesar da coleção D ter um número maior de
documentos (5) do que a coleção D’ (3), a quantidade closed termsets de D é menor do que
D’. Coleções homogêneas produzem um número menor de closed termsets, uma vez que
contêm uma quantidade menor de macro contextos. Por exemplo, a coleção D possui apenas o
macro contexto livro e a coleção D’ os macros contextos livro e CD. A comparação entre a
quantidade de termos a serem indexados do Exemplo 2 é apresentada na Tabela 3.
Tabela 4: Comparação da Quantidade de Termo Indexados do Exemplo 3
Abordagens
Recuperação de Informação tradicional
Recuperação de informação com o domínio aumentado
Recuperação de informação com o domínio aumentado empregando
o conceito de conjunto de termos
Quantidade de termos
indexados
7
27
5
Como pode ser observado nos Exemplo 2 e Exemplo 3 a quantidade de closed
termsets é menor do que a quantidade de termos planos. Portanto, nesses dois exemplos, a
quantidade de closed termsets é menor do que a quantidade de termos indexados na
recuperação de informação tradicional. Isso mostra que a proposta de indexar conjunto de
termos em vez de termos é uma estratégia capaz de diminuir a quantidade de termos do
índice. Em [26] foram realizados experimentos para calcular os closed termsets para algumas
coleções de documentos. Dentre essas coleções, encontra-se a Trec-3 com, aproximadamente,
67
1 milhão de termos e um milhão de documentos. O resultado desse cálculo mostra que foram
obtidos aproximadamente, quatro mil closed termsets, isto é, 0,4%. Além disso, os termos
derivados de um mesmo ramo de uma árvore XML, por exemplo, os termos jose, jose/autor e
jose/autor/livro tendem a permanecer em um mesmo closed termset. Esta característica é
importante, porque, na abordagem proposta nesta dissertação, os termos que possuem
informação de estrutura e de conteúdo são derivados do mesmo ramo em que a sua
informação de conteúdo (folha) está localizado. Assim, esses termos geralmente são
agrupados em um mesmo conjunto.
A próxima seção apresenta uma proposta de como o modelo vetorial pode ser aplicado
no cálculo da similaridade entre documentos e consultas, considerando os closed termsets
como unidade de indexação
4.4 - Cálculo da Similaridade no Modelo Proposto
No modelo vetorial clássico, os documentos e consultas são representados por vetores e a
medida de similaridade mais empregada é o coseno do ângulo entre os vetores do documento
e da consulta (ver Equação 1 Capítulo 2). A proposta apresentada neste trabalho é utilizar o
mesmo cálculo da similaridade do modelo vetorial, aumentando o domínio dos termos da
recuperação de informação tradicional com os termos estendidos para possibilitar a pesquisa
contextualizada. Para lidar com o crescimento na quantidade de termos, são propostas três
estratégias conforme discutido na seção 3.2. A primeira é descartar termos estendidos com
informação apenas de contexto, entendendo que o usuário pesquisará por pelo menos uma
informação de conteúdo. A segunda é descartar os termos complementares porque se fossem
considerados a quantidade de termos cresceria de forma exponencial, embora este descarte
limite a representatividade da semântica do documento. A terceira é mudar a unidade de
indexação de termos para conjunto de termos, pois considerando conjunto de termos a
quantidade de unidades de indexação é menor e, conforme apresentado em [26], há um ganho
de qualidade na resposta. Esta seção apresenta uma proposta baseada em [26] para calcular a
similaridade entre documentos e consultas considerando os closed termsets.
4.4.1 – Estruturas Necessárias para o Cálculo da Similaridade
Para calcular a similaridade entre documentos e consultas indexando closed termsets, são
usadas as seguintes estruturas de dados:
68
1- Vocabulário: O vocabulário é o conjunto de termos estendidos
e termos planos(na
notação simplificada) distintos que estão presentes nos documentos da coleção. Esses
termos são armazenadas em ordem lexicográfica. A Figura 11 (pg. 59) e a Figura 14 (pg.
64), são exemplos de vocabulários;
2- Lista Invertida de Termos: Armazena, para cada termo plano e estruturado, um vetor de
documentos e a freqüência do termo no documento para cada termo da coleção;
3- Lista Invertida de Closed Termsets: Armazena, para cada closed termset os documentos e
a freqüência do closed termset no documento;
4- Vetor de Norma: Armazena a norma de cada documento;
4.4.2 – Exemplo do Cálculo da Similaridade
Para exemplificar o cálculo da similaridade, considere-se a coleção de documentos da Figura
13 (pg. 63), o vocabulário da Figura 14 (pg. 64) e o seguinte tópico
TC 7: “Documentos que tenham o nome Marcos como autor, a palavra computador no título e
a número 1980 em qualquer parte do documento.”
O TC 7 pode ser representado por q = (1980, marcos\autor, computador\titulo)1. A
consulta q representa a necessidade de informação do usuário relativo a TC7.
Primeiro passo:
Verificar os índices dos termos procurados no vocabulário, q = {1, 11, 22}.
Tabela 5: Índices dos termos da consulta q
Termo Estendido
1980
Computador\titulo
Marcos\autor
Índice no Vocabulário
1
11
22
Segundo Passo:
1
As estratégias para transformação de TC 7 em q não são discutidas neste trabalho.
69
Calcular os closed termsets dos termos da consulta. Cada termo da consulta é
considerado 1-termset, ou seja, um
conjunto com
apenas
1 termo. Verificar se
σ(termsets) ≥ sup_mim. Considerando sup_mim = 1 (33,33%), então se o termo está no
vocabulário, ele tem um suporte maior ou igual a sup_mim. Observe-se que os termos que não
estão no vocabulário não são processados pelo algoritmo CHARM. Por exemplo, considere-se
que a consulta q tenha o termo “flores”, como este termo não pertence ao vocabulário da
coleção de documentos o seu suporte é menor do que o suporte mínimo, portanto, o termo
“flores” não é analisado pelo algoritmo CHARM. A Figura 16 apresenta a árvore TermsetTidset dos termos da consulta gerada pelo CHARM.
Os closed termsets cq1 ={1xd1d2}, cq2 ={1,11xd2}, cq3 ={1,22xd1} e cq4 = {11xd3}
são gerados conforme descrito no Capítulo 4. Portanto, a consulta q = Cq = (cq1, cq2, cq3,
cq4).
[]
1xd1d2
1,11xd2
11xd3
1,22xd2
Figura 15: Árvore Termset-Tidset para os termos da consulta q.
Terceiro Passo:
Calcular a similaridade. No modelo vetorial clássico, a similaridade entre documentos
e consulta é dada pela Equação 1. Considerando o conjunto de termos ao invés de termos, a
Equação 1 pode ser escrita
sim(d j , q) =
dj • q
| dj | × | q |
=
∑c∈C
t
∑i=1 w
q
wc, j • wc,q
2
i, j
•
t
(Equação 2)
∑i=1 w
2
i ,q
onde wc,j é o peso associado com o closed termset c no documento dj, wc,q é o peso associado
com o closed termset c na consulta q, Cq é o conjunto de todos os closed termsets c ⊆ q, wi,j é
o peso do termo i no documento dj e wi,q é o peso do termo i na consulta q. Observe-se que
70
como em [26], neste trabalho, a normalização é feita usando as normas do documento e da
consulta ao invés de closed termsets. Isto é feito para reduzir o custo computacional de
calcular a norma de um documento d, usando os closed termsets. A Equação 2 é a mesma
utilizada em [26]. Os vetores da coleção dos documentos e da consulta são:
q = (c1 , c 2 , c3 , c 4 ,0)
d 1 = (c1 ,0, c3 ,0,0)
d 2 = (c1 , c 2 ,0,0, c5 )
d 3 = (0,0,0, c 4 , c5 )
Observe-se que os closed termsets da consulta são subconjuntos dos closed termsets
indexados da coleção de documentos D’ (ver Figura 15). Por exemplo, cq1 = {1xd1d2} o termo
estendido de índice 1 é subconjunto de C’1, C’2 e C’3. Entretanto, apenas C’1 ocorre no
mesmo conjunto de documentos d1d2, então, cq1 corresponde à C’1. Logo, a frequência do
closed termset cq1 no documento j da consulta q é a mesma freqüência do closed termset C’1
no documento j que está armazenada no índice. Para calcular o peso de um closed termset c
associado a um documento j, tem-se
 N
wc , j = cf i , j × ids i = cf i , j × log
 dsi



(Equação 3)
onde N é o número de documentos na coleção, sfi,j é o número de ocorrências do closed
termset i no documento j (sfi,j tem a mesma semântica de tfi,j), idsi é a freqüência inversa das
ocorrências dos closed termsets na coleção (idsi tem a mesma semântica de idfi). A sfi,j é dada
pela menor freqüência dos termos pertencentes ao closed termset i no documento j. Por
exemplo, sf1,1 = 2 pois é a menor freqüência dentre os termos do closed termset C1 associado
ao documento d1 (Figura 17). A idsi é dada pela lista invertida de closed termsets. Por
exemplo, o closed termset C1 ocorre em 2 documentos da coleção D’ (Figura 13).
Efetuando-se os cálculos conforme descrito nesta seção, obtém-se o seguinte ranking:
1° - d1
2° - d2
71
3° - d3
O documento d1 é o mais similar à consulta q. Observe-se que o documento d1 possui
dois dos três termos da consulta, 1980 e marcos/titulo. O documento d2 têm os termos 1980,
computador/titulo e o documento d3 possui computador/titulo. A diferença dos pesos dos
closed termsets é que determina que d1 esteja em primeiro lugar no ranking.
A estratégia de indexação e de cálculo do ranking proposta em [26] pode ser aplicada
utilizando a abordagem proposta nesta dissertação. Isto acontece porque os termos estendidos
são tratados como os termos planos da recuperação de informação tradicional.
72
1
d1 3
d2 4
2
d1 2
d2 1
3
d2 1
4
d1 2
5
d1 1
6
d1 1
7
d3 6
8
d3 2
9
d3 1
10
d2 18
d3 20
11
d2 2
d3 2
12
d2 1
13
d3 1
14
d2 7
d3 10
15
d2 1
d3 1
16
d2 1
17
d3 1
18
d1 3
19
d1 1
20
d1 1
21
d1 4
22
d1 1
23
d1 1
24
d2 2
d3 3
25
d2 1
d3 1
26
d2 1
27
d3 1
Figura 16: Lista Invertida da Coleção de Documentos D’.
73
[]
1 xd1d2
1,2 xd1d2
1,2,3xd
1,2,4xd 1,2,5xd 1,2,6xd1 1,2,10xd 1,2,11xd 1,2,12xd2 1,2,14xd2 1,2,15xd2 1,2,16xd2 1,2,18xd1 1,2,19xd 1,2,20xd 1,2,21xd 1,2,22xd 1,2,23xd1 1,2,24xd2 1,2,25xd2 1,2,26xd2
2
1,2,3,10xd2
1,2,3,10,11xd
1,2,310,11,12xd2
1,2,310,11,12,14xd2
1,2,3,10,11,12,14,15xd2
1,2,3,10,11,12,14,15,16xd2
1,2,3,10,11,12,14,15,16,24xd2
1,2,3,11,12,14,15,16,24,25x
d
2
1,2,3,11,12,14,15,16,24,25,26xd
2
1
1
1,2,4,5xd1
1,2,4,5,6xd1
1,2,4,5,6,18xd1
1,2,4,5,6,18,19xd1
1,2,4,5,6,18,19,20xd1
1,2,4,5,6,18,19,20,21xd1
1,2,4,5,6,18,19,20,21,22xd1
1,2,4,5,6,18,19,20,21,22,23xd1
[]
7 xd3
10,11 x
d d xdd
10,11
2 3
7,8 xd3
7,8,9xd3
10,11,14 x d2d3
7,8,9,10 xd3
10,11,14,15 x d2d3
7,8,9,10,11 xd3
10,11,14,15,24 x d2d3
7,8,9,10,11,12 xd3
7,8,9,10,11,12,13 xd3
10,11,14,15,24,25 x d2d3
7,8,9,10,11,12,13,14 xd3
7,8,9,10,11,12,13,14,15
xd
7,8,9,10,11,12,13,14,15,17 xd3
7,8,9,10,11,12,13,14,15,17,24 xd3
7,8,9,10,11,12,13,14,15,17,24,25 xd3
7,8,9,10,11,12,13,14,15,17,24,25,27 xd3
Figura 17: Processo de Busca para o Exemplo 3 Usando Tidsets
Capítulo 5
Experimentos
Existem algumas iniciativas com o objetivo de dar suporte às pesquisas realizadas pela
comunidade de recuperação de informação, provendo uma estrutura necessária para a
avaliação em larga escala de suas metodologias. A TREC [34] (Text REtrieval Conference) é
um exemplo para a recuperação de informação tradicional. A INEX [19] (Initiative for the
Evaluation of XML retrieval) apresenta um papel semelhante a TREC para a recuperação de
informação em dados semi-estruturados. Ela é uma iniciativa recente (2002), que foi motivada
pelo crescente uso da XML na área de recuperação de informação.
Além da coleção de documentos XML, a INEX também possui um conjunto de
consultas (tarefas) para que os usuários possam ser capazes de julgar a qualidade das
respostas retornadas pelos sistemas de recuperação de informação. No início de 2002, a
coleção de documentos da INEX era composta por textos completos da IEEE Computer
Society de 1995 até o início de 2002. A coleção inclui os artigos de 12 volumes de revistas e 6
transactions. Detalhes da coleção INEX podem ser encontrados em [17].
Em virtude do grupo de recuperação de informação da Universidade Federal de
Uberlândia – UFU – não fazer parte da INEX, optou-se por uma coleção de documentos XML
local para realizar os experimentos, empregando a abordagem proposta nesta dissertação. O
objetivo desses experimentos é mostrar que a quantidade de closed termsets é menor do que a
quantidade de termos do vocabulário estendido (termos planos e termos estendidos) proposto
neste trabalho.
75
A Universidade Federal de Uberlândia possui uma coleção de peças teatrais em sua
Biblioteca Central. Esta coleção é constituída de 778 textos de peças teatrais. Para possibilitar
a conservação e pesquisa desse acervo por meio de um sistema informatizado, está sendo
desenvolvido um projeto para a construção de uma Biblioteca Digital de Peças Teatrais
(BDPT), conjuntamente pelo Sistema de Bibliotecas da Universidade Federal de Uberlândia,
Faculdade de Computação e o curso de Artes Cênicas. No momento da execução dos
experimentos haviam 72 peças digitalizadas e formatadas.
A forma de armazenamento e estruturação dessa coleção é XML. A escolha da coleção
de peças teatrais para a realização dos experimentos da abordagem proposta nesta dissertação
foi motivada, principalmente, pela complexidade de sua estrutura e pela disponibilidade da
mesma.
5.1 – Estrutura da Coleção de Documentos
Uma das primeiras dificuldades no projeto do BDPT foi encontrar uma estrutura
genérica que atendesse a todo o acervo de peças. Para essa definição, foram necessários os
conhecimentos específicos dos professores do curso de artes cênicas e dos funcionários da
biblioteca. A estrutura básica da peça é dividia em duas partes:
•
Registro Marc: Marc é um padrão usado na biblioteconomia para a catalogação de acervos
bibliográficos. Dentro desse padrão, foram escolhidas algumas informações para formar
um padrão específico para a catalogação de peças teatrais.
•
Texto da Peça: Nesta parte da estrutura do BDPT, foi definida uma estrutura genérica para
peças teatrais. Portanto, todo conteúdo da peça é armazenado nessa estrutura definida.
A informação contida no registo MARC tem uma estrutura bem definida. Por
exemplo, autores da peça, gênero, idioma etc. Para esse tipo de informação, a solução
oferecida por
um sistema gerenciador de banco de dados atende às necessidades de
informação do usuário. Portanto, foi definido que esta parte seria armazenada em um banco
de dados (MySQL). Por outro lado, o conteúdo da peça não possui uma estrutura bem
definida. A XML foi o padrão escolhido para armazenar e estruturar o conteúdo dessas peças.
As Figura 18 e Figura 19 mostram a estrutura definida para o conteúdo das peças
teatrais. Na Figura 18, observa-se que a peça é dividida em duas partes o registro-marc e
76
texto_peca. O resgisto_marc é armazenado em um banco de dados, e o texto_peca é
estruturado e armazenado utilizando a XML, conforme descrito anteriormente. O texto_peca
também está dividido em duas partes, divisao e prologo. No prologo, é armazenado todo texto
que não faz parte da dramatização da peça. O nó divisao tem os filhos ato, episodio, parte,
cena, outro. Esses nós representam a estrutura básica de uma peça. Cada uma dessas
estruturas são divididas em cena, monologo, dialogo, letra_musica, poesia, outro_texto. Esses
elementos possuem duas divisões texto e rubrica. No elemento texto, é armazenado o texto
referente ao ramo da árvore de que ele faz parte. Na rubrica, é armazenado o texto que indica
a interferência direta do autor na dramatização da peça. Observa-se que o elemento
outro_texto e outro foram definidos para armazenar as informações que não são classificadas
nos outros elementos. Cada elemento do nó divisao, com exceção do elemento cena, possui
uma estrutura conforme mostra a Figura 19. O elemento cena possui a estrutura mostrada na
Figura 19 sem o nó cena (referência recursiva).
5.2 – Cálculo dos Closed termsets
O BDPT encontra-se no início da fase em que as peças estão sendo digitadas. Os
experimentos realizados para o cálculo dos closed termsets dessa coleção foram realizados em
72 peças. A derivação dos termos estendidos foi feita seguindo 4 passos:
•
Passo 1: Com base nos documentos XML digitados são gerados novos documentos
filtrando as stopwords apresentadas em [33] e [27] Este filtro realizado, utilizando XSL e
JAVA;
•
Passo 2: A partir dos documentos filtrados do Passo 1, é construído o vocabulário
utilizando JAVA. Este vocabulário contém os termos planos (folhas) e os termos
estendidos segundo a notação simplificada definida no Capítulo 4.
•
Passo 3: Neste passo, é gerado, a lista invertida de termos para a coleção de documentos
de peças teatrais.
•
Passo 4: Com base nesta lista invertida, é aplicado o algoritmo CHARM para obter os
closed termosets.
A Figura 20 mostra o esquema descrito nos passos 1 à 4.
77
No Passo 1, também são tratadas acentuação e letras em maiúsculo. O Algoritmo
CHARM foi implementado empregando a linguagem C no ambiente windows. Em [39], são
descritas duas estratégias para melhorar a performance do algoritmo CHARM, são elas:
•
A utilização de diffsets: Um diffset é a diferença entre dois termsets, ou seja,
d(PXY) = t(PX) – t(PY), onde P é a classe de equivalência (prefixo) dos termsets X e Y
(ver Capítulo 4). A idéia é armazenar a diferença entre dois termsets em vez de sua
intercessão (t(X) ∩ t(Y)). Segundo [39], essa estratégia reduz a quantidade de memória
necessária para armazenar resultados intermediários.
•
Combinar dois termsets Xi e Xj somente se Xi Xj for freqüente: Isto é feito calculando o
conjunto de termsets de tamanho 2 para verificar se eles são freqüentes. Essa otimização
baseia-se no fato de que muitos termsets de tamanho 2 não são freqüentes.
A implementação do algoritmo proposto nesta dissertação não considerou estas duas
estratégias para melhoria de performance em decorrência do tamanho da coleção de
documentos. O algoritmo utilizado foi o CHARM descrito na Figura 9 O resultado do
algoritmo CHARM aplicado a 72 documentos da coleção de peças teatrais é mostrado na
Tabela 6. O suporte mínimo utilizado foi de 1,38%, ou seja, todos os termos da coleção foram
considerados.
Tabela 6: Estatísticas da Aplicação do Algoritmo CHARM no BDPT
Nro. Documentos
Nro. de termos do vocabulário
(termos planos e termos
estendidos)
Nro. de closed termsets
72
300.870
264
Observa-se que há uma grande diferença entre a quantidade de termos do vocabulário
e a quantidade de closed termsets. Assim, o problema do tamanho do índice gerado pela
quantidade de termos inseridos no vocabulário (termos estendidos), pode ser tratado
utilizando a estratégia de indexar conjunto de termos (closed termsets). Este trabalho não
abordou a eficácia do uso de closed termsets, pois segundo os experimentos apresentados em
[26], a indexação dos closed termsets provê uma maior precisão na recuperação de
informação se comparado com a indexação tradicional.
78
peca
texto _peca
registro
marc
divisao
outro
cena
prologo
parte
episodio
campo
ato
subcampo
Figura 18: Estrutura da Coleção de Documentos do BDPT
ato/episodio/parte/outro
outro_texto
texto
rubrica
texto
poesia
rubrica
letra_musica
texto
rubrica
diálogo
texto
monologo
rubrica
Figura 19: Estrutura Interna da Coleção de Documentos do BDPT
texto
cena
rubrica
texto
rubrica
lider
79
XSL
+
JAVA
documentos
XML
digitados
JAVA
documentos
XML
filtrados
Vocabulário
JAVA
Algoritmo
CHARM
Closed
Termsets
Lista
Invertida de
termos
Figura 20: Esquema para o cálculo dos closed termsets para a coleção de documentos do BDPT
Capítulo 6
Conclusão
A recuperação de informação em documentos semi-estruturados tem recebido uma crescente
atenção desde o surgimento da linguagem XML. Várias abordagens propostas pela literatura
utilizam a informação de contexto dos documentos no cálculo do ranking. Esta dissertação
apresentou uma extensão ao modelo vetorial com o objetivo de se utilizar a informação de
contexto no cálculo da similaridade entre documentos e consultas. Dessa maneira, foi possível
aliar a simplicidade e desempenho do modelo vetorial às vantagens da consulta
contextualizada. A abordagem para se atingir esse objetivo, foi acrescentar ao domínio de
termos da recuperação de informação tradicional os termos estendidos.
A derivação dos termos complexos é feita observando as possíveis sub-árvores desde a
raiz até os nós folhas da árvore do documento XML. A quantidade de termos compostos
derivado dos termos complexos é exponencial. Portanto, um domínio de termos onde fosse
acrescentado os termos compostos torna-se computacionalmente inviável. Para evitar este
problema alguns trabalhos calculam as estatísticas necessárias para calcular o ranking durante
a consulta.
A contribuição central desta dissertação é definir um domínio de termos com
informação de contexto onde o cálculo das estatísticas é feito durante a indexação da coleção
de documentos. Para lidar com o problema do aumento exponencial de termos, foi proposto
descartar os termos que possuem somente informação de contexto e indexar conjunto de
termos em vez de termos. Essas duas estratégias não oferecem prejuízo à contextualização
oferecida ao usuário. Por outro lado, o descarte dos termos complementares traz prejuízo a
81
essa contextualização. Portanto, o descarte dos termos complementares pode ser feito de
forma parcial ou total, dependendo das características da coleção de documentos.
Ao considerar apenas os termos estendidos, nota-se que a quantidade de termos
acrescentados ao domínio da recuperação de informação tradicional é a × (n – 1), onde a é a
quantidade de termos planos da coleção de documentos (folhas das árvores XML), e n é o
nível da coleção de documentos. A quantidade total de termos do vocabulário é a × n. A
quantificação desses termos é possível pelo fato dos termos estendidos necessariamente
estarem associados a um termo plano e também serem sub-árvores de seus respectivos termos
complexos. Assim, considerando termos planos e termos estendidos a quantidade de termos
adicionados ao domínio de termos da recuperação de informação tradicional deixa de ser
exponencial.
A principal diferença entre a recuperação de informação em dados semi-estruturados
e a recuperação de informação tradicional é a utilização da informação de estrutura no cálculo
da similaridade entre documentos e consultas. Esta informação de contexto é utilizada para
aumentar a precisão do ranking. Entretanto, para que o usuário de um SRI tire proveito dessa
vantagem, é desejável que ele tenha noções de como os documentos, da coleção pesquisada,
estão estruturados. Assim, os SRI’s de coleções de documentos específicas, tais como
coleções jurídicas, médicas e etc, são os mais indicados a usarem a informação de contexto no
cálculo do ranking. Isto porque seus usuários geralmente conhecem a coleção de documentos
que estão pesquisando.
Os trabalhos futuros concentram-se na implementação do modelo proposto em uma
coleção de documentos maior para avaliação dos resultados e comparar com outras
abordagens que utilizam a informação de contexto dos documentos no cálculo do ranking.
82
Referências Bibliográficas
[1]
ABTEBOUL, S.; QUASS, D.; McHUGH, J.; WIDOM, J.; WIENER, J. The Lorel
Query Language for Semistrucutred Data. International Journal on Digital Libraries,
v. 1, n.1, p.68-88, Apr. 1997.
[2]
ALMEIDA, M. B. Uma introdução ao XML, sua utilização na Internet e alguns
conceitos complemetares. CIÊNCIA DA INFORMAÇÃO, Brasília, v.31, n.2, p. 5-13,
maio/agosto. 2002.
[3]
BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern Information retrieval. New york:
ACM Press, 1999.
[4]
BARG, M.; WONG, R. K. Structural Proximity Searching for Large Collections of
Semi-Structured Data. In: ACM CONFERENCE ON INFORMATION AND
KNOWLEDGE MANAGEMENT (CIKM), 2001, Atlanta. Proceedings... Atlanta:
ACM, p. 175-182, 2001.
[5]
BONIFATI, A.; LEE, D. Technical Survey of XML Schema and Query Languages.
January, 2001. Disponível em: < http://www.icar.cnr.it/angela/publications.shtml>.
Acesso em: Jun. 2003.
[6]
BOSAK, J. XML. Java, and the future of the Web, USA, 1997. Disponível em:
<http://www.ibiblio.org/pub/sun- info/standards/ xml/why /xmlapps.htm>. Acesso em: Mar. 2003.
[7]
BREMER, J. M.; GERTZ, M. An Efficient XML Node Identification and Indexing
Scheme. California: Department of Computer Science, University of California,
January 2003. Technical Report CSE-2003-04. Disponível em:
< http://www.db.cs.ucdavis.edu/~bremer/TR_CSE-2003-04_BremerGertz.pdf >.
Acesso em: Fev. 2003.
83
[8]
CARMEL, D.; EFRATY, N.; LANDAU, G. M.; MAAREK, Y. S.; MASS, Y. An
extension of the Vector Space Model for Querying XML Documents via XML
Fragments. In: ACM SIGIR, 2002, Finland. Workshop on XML and IR. Finland:
ACM, 2002.
[9]
CARMEL, D.; COHEN, D.; FAGIN, R.; FARCHI, E.; HERSCOVICI, M.;
MAAREK, Y. S.; SOFFER, A. Static Index Pruning for Information Retrieval
Systems. In: ACM SIGIR, p. 43-50, 2001, Louisiana. Proceedings... Lousiana, 2001.
[10]
CARMEL, D.; AMITAY, E.; HERSCOVICI, M.; MAAREK, Y.; PETRUSCHKA, Y.
Juru at TREC 10 - Experiments with Index Pruning. In: TEXT RETRIEVAL
CONFERENCE (TREC), 10., 2001. Proceedings..., 2001.
[11]
CERQUEIRA, A. G.; SILVA, G. B.; CARDOSO, O. N. P. Uma visão Geral de XML
em Recuperação de Informação. Revista eletrônica de iniciação científica, v.2, n.2,
jun.2002. Disponível em: < http://www.sbc.org.br/reic/edicoes/2002e2/>. Acesso em:
Mar. 2003.
[12]
CHINENYANGA, T. T.; KUSHMERICK, N. Expressive Retrieval from XML
Document. In: SIGIR, 2001, New Orleans. Proceedings... New orleans, 2001.
[13]
COHEN, W. WHIRL: A Word-Based Information Representation Language. J.
Artificial Intelligence, v. 118, p.163-196, 2000.
[14]
COHEN, W. Integration of heterogeneous databases without common domains using
queries based on textual similarity. In: SIGMOD, 1998, Proceedings..., 1998. p.201211.
84
[15]
DEUTSCH, A.; FERNANDEZ, M.; FLORESCU, D.; LEVY, A.; SUCIU, D. XMLQL: A Query Language for XML. In: INT. WORLD WIDE WEB CONF., 8. p. 1116,1999, Proceedings..., 1999.
[16]
FUHR, N.; GROBJOHANN, K. XIRQL: A Query Language for Information
Retrieval in XML Documents. In: SIGIR, p.172-180, 2001, Lousiana.
Proceedings...Lousiana, 2001.
[17]
FUHR, N.; GOVERT, N.; KAZAI, G.; LALMAS, M. INEX: Intitiative for the
Evaluation of XML Retrieval. In: ACM SIGIR WORKSHOP ON XML AND
INFORMATION RETRIEVAL, 2002, Tampere. Proceedings..., Tampere, editor,
2002.
[18]
GRABS, T.; SCHEK, H.-J. Generating Vector Spaces On-the-fly for Flexible XML
Retrieval. XML and Information Retrieval Workshop. In: ANNUAL
INTERNATIONAL ACM SIGIR CONFERENCE ON RESEARCH AND
DEVELOPMENT IN INFORMATION RETRIEVAL, 25., 2002, Finland.
Proceedings... Finland: ACM, 2002.
[19]
INEX (Initiative for the Evaluation of XML Retrieval). Disponível em:
<http://qmir.dcs.qmw.ac.uk/INEX>. Acesso em: Out. 2003.
[20]
JANG, H.; KIM, Y.; SHIN, D. An Effective Mechanism for Index Update in
Structured Documents. In: ACM CONFERENCE ON INFORMATION AND
KNOWLEDGE
MANAGEMENT
(CIKM),
p.383-390,
1999,
Kansas
City.
Proceedings... Kansas City: ACM, 1999.
[21]
KAMPS, J.; MARX, M.; RIJKE, M.; SIGURBJORNSSON, B. XML Retrieaval: What
to Retrieve?. In: SIGIR, 2003, Toronto. Proceedings...Toronto: ACM, p. 409-410
2003.
85
[22]
KOTSAKIS, E. Structured Information Retrieval in XML Documents. In
Proceedings of the seventeenth. In: ACM SYMPOSIUM ON APPLIED
COMPUTING (SAC), 2002, Madrid. Proceedings... Madrid: ACM, 2002. p. 663-667
[23]
LI, Q.; MOON, B. Indexing and Querying XML Data for Regular Path Expressions.
In: VLDB CONFERENCE, 27., p. 351-360, 2001, Roma. Proceedings... Roma, 2001.
Disponível em: < http://www.cs.arizona.edu/~bkmoon/papers/vldb01.pdf >. Acesso
em: Jan. 2003.
[24]
NAVARRO, G. A Language for Queries for Structure and Contents of Textual
Databases. Master’s Thesis - Department of Computer Science, University of Chile.
[25]
Online
Resource
for
Markup
Language
Technologies.
Disponível
em:
<http://www.oasis-open.org/cover/xml.html#applications>. Acesso em: Fev. 2003.
[26]
PÔSSAS, B.; MEIRA, W. J.; ZIVIANI, N.; RIBEIRO-NETO, B. Set-Based Model: A
New Approach for information Retrieval. In: ACM SIGIR CONFERENCE ON
RESEARCH AND DEVELOPMENT IN INFORMATION RETRIEVA, 2002,
Tampere. Proceedings... Tempere: ACM, 2002.
[27]
RANKS.nl Portuguese Stopwords. Disponível em:
<http://www.ranks.nl/stopwords/portugese.html>. Acesso em Set. de 2003.
[28]
ROBIE, J. XQL(XML Query Language). Aug. 1999. Disponível em:
<http://www.ibiblio.org/xql/xql-proposal.html>. Acesso em: Jun. 2003.
[29]
ROY, G.; NARAYANAN, S.; SURESH, V.; HECTOR, G. Proximity Search in
Databases. In: VLDB CONFERENCE, 24, p. 26-37,1998, local. Proceedings...Local,
1998.
86
[30]
SILVA, I. R. SOUZA, J. N. LOPES, R. A. Recuperação de informação em dados
semi-estruturados utilizando o modelo vetorial. In: INTERNATIONAL
INFORMATION AND TELECOMMUNICATION TECHNOLOGIES
SYMPOSIUM, 2., 2003, Florianópolis. Proceedings...Florianópolis: Faculdades
Barddal, 2003. 1 CD-ROM.
[31]
SILVA, I. R. SOUZA, J. N. LOPES, R. A. Information Retrieval in Semi-Structured
Data Using Vector Space Model. In: INFORMATION RESOURCES
MANAGEMENT ASSOCIATION (IRMA) INTERNATIONAL CONFERENCE,
15., 2004, Louisiana, New Orleans, USA, 2004. To appear.
[32]
SCHLIEDER, T.; MEUSS, H. Querying and Ranking XML Documents. Journal of
the American Society for Informations Systems, v.53, n.6, p.489-503, Apr. 2002.
[33]
Tribunal de Contas da União: Tabela de Palavras Reservadas. Disponível em:
<http://www.tcu.gov.br/Consultas/BRS/stdstop.html>. Acesso em Set. de 2003.
[34]
TREC (Text REtrieval Conference). Disponível em: <http://trec.nist.gov>. Acesso em:
Abr. 2003.
[35]
XML SCHEMA. Disponível em <http://www.w3.org/XML/Schema>. Acesso em Jan.
de 2003.
[36]
YAHIA-AMER, S.; CHO, S.; SRIVASTAVA, D. Tree Pattern Relaxion, In
International Conference on Extending Database Technology (EDBT), 2002,
Proceedings ... 2002. p. 496-513.
[37]
YAMANE, Y.; IGATA, N.; NAMBA, I. High-performance XML Storage/Retrieval
System. Fujitsu Scientific & Technical Journal(Fstj), v. 36, n. 2, p. 185-192, Dec.
2000.
87
[38]
WANG, X.-L.; DONG, Y.-S.; WEN, J.-R.; YIN, L. W. Enhancive Index for
Structured Document Retrieval. In: INTERNATIONAL WORKSHOP ON
RESEARCH ISSUES IN DATA ENGINEERING: ENGINEERING ECOMMERCE/E-BUSINESS SYSTEMS (RIDE), 12., p. 256-264, 2002, Califórnia.
Proceedings... California, 2002.
[39]
ZAKI, M. J.; HSIAO, C. Charm: An efficient algorithm for closed association rule
mining. In: SIAM INTERNATIONAL CONFERENCE ON DATA MINING, 2., p.
457-473, 2002, Arlington. Proceedings... Arlington, 2002.