Armazenamento, Indexação e Recuperação de Informação

Departamento de Eletrónica,

Telecomunicações e Informática

Armazenamento, Indexação e Recuperação de Informação

Trabalho Prático 2

Mestrado em Sistemas de Informação

Docente: Prof. José Luís Oliveira Discentes: Emanuel Pires – 77994

Prof. Sérgio Matos Mário Monteiro – 77910

Armazenamento, Indexação e Recuperação de Informação – MSI – 2015/2016

Mário Monteiro - 77910 || Emanuel Pires - 77994

2

Índice

INTRODUÇÃO......................................................................................................................... 3

PARTE 1 – ARQUITETURA E MODELAÇÃO ............................................................................. 5

PARTE 2 – CORPUS READ ..................................................................................................... 10

PARTE 3 – TOKENIZER ............................................................................................................ 11

PARTE 4 - INDEXAÇÃO ............................................................................................................ 12

PARTE 5 – RESPOSTAS AS QUESTÕES .................................................................................. 13

PARTE 6 – EXECUÇÃO DO ALGORITMO INDEXAÇÃO ............................................................ 19

PARTE 6 – CONSIDERAÇÕES FINAIS..................................................................................... 23



3

INTRODUÇÃO

Este relatório realiza-se no âmbito da unidade curricular da disciplina Armazenamento

Indexação e Recuperação de Informação do Mestrado em Sistemas de Informação da

Universidade de Aveiro, com o intuito de fazer uma readaptação do algoritmo do trabalho

prático 1 com os seguintes requisitos básicos:

Criar um algoritmo de índice invertido utilizando o corpus do trabalho 1, que permite

realizar pesquisa por um texto (Exemplo: Ambiente, politica Ambiental);

Criar corpus com base em capítulos e speakers fornecidos em cada um dos documentos

em ficheiros corpus.

Implementar o método rank retrieval baseado no modelo vector-space e utilizar o

sistema de ponderação tf-idf;

Disponibilizar um relatório;

Adaptar o método indexing/retrieval pesquisa por frase (Exemplo: “fishing quota”) e

pesquisa de proximidade (Exemplo:”fishing quota”~10);

Adaptar método indexing/retrieval para suportar múltiplos termos e combinação de

termos no querie.

Será apresentado com grande nível de detalhes a arquitetura, diagrama de classes, bem como a

descrição para cada uma das classes. Encontra-se também um tutorial em anexo a mostrar como

se interagir com o algoritmo.



4

DESENVOLVIMENTO

Para o desenvolvimento do algoritmo foi sugerido pelo professor a utilização da tecnologia

Java.

Java - Uma linguagem de programação e plataforma computacional lançada pela Sun

Microsystems em 1995. Esta linguagem está presente desde, laptops a datacenters, consolas de

jogos a supercomputadores científicos, telemóveis e muito mais. Ela encontra-se disponível de

forma gratuita na Internet no site java.com.

Como IDE de desenvolvimento, foi escolhido o Netbeans 8.0.2. Este oferece-nos assistentes e

modelos que permitem a criação de aplicações Java EE, Java SE e Java ME.

Teve-se a necessidade de incorporar algumas bibliotecas externas para o desenvolvimento deste

algoritmo como:

Jsoup-1.8.3.jar1 - Biblioteca feito em Java para trabalhar com serialização de objetos

Json.

Json-simple-1.1.1.jar2 – Biblioteca que faz parser (serialização) de objetos em Json.

Guava-18.0.jar3 - Biblioteca da Google utilizado para fazer tratamento de: coleções,

caching, apoio primitivas, processamento de string, I/O, no nosso caso ela é utilizado

para fazer o Join do texto Corpus.

1Http://jsoup.org/packages/jsoup-1.8.3.jar

2 Http://www.java2s.com/Code/Jar/j/Downloadjsonsimple111jar.htm 3 Http://search.maven.org/remotecontent?filepath=com/google/guava/guava/18.0/guava -18.0.jar



5

Libstemmer.jar 4 - Algoritmo Porter Stemmer, um processo comum para normalização

morfológicas de palavras em português. Seu principal objetivo é fazer normalização de

palavras em sistemas de recuperação de informação.

PARTE 1 – ARQUITETURA E MODELAÇÃO

Foi dotado o modelo de classes Orientado a Objetos, para o desenvolvimento deste algoritmo .

O algoritmo foi desenvolvido com implementação de threads de forma realizar operações

diversas em paralelo ou seja, os trabalhos são executados em espaços próprios na memória e no

processador, de realçar ainda que as estruturas de dados mais utilizado para desenvolvimento

deste algoritmo são:

Map, HashMap e TreeMap.

Para uma melhor compreensão da estrutura de classes, é apresentado uma breve discrição dos

mesmos:

Library – Classe que incorpora um conjunto de métodos auxiliares que ajudam no

desenvolvimento do algoritmo;

Policy – Classe que faz toda gestão de politicas, como por exemplo:

o Definir o tamanho máximo de memória a ser utilizada;

o Definir quantidade de corpus a ser lido pelas threads;

o Definir o limite de memória;

Thread – Classe mãe para as threds, pois é nesta classe que todas threads são criados

em que posteriormente irão ser instanciados em outras classes;

4 (http://snowball.tartarus.org/)



6

CorpusRead – Classe responsável por fazer a leitura dos corpus, separar os CHAPTER

e SPEAKER, com finalidade de obter um corpus, de forma como foi especificado nos

requisitos do trabalho. Cada corpus pode conter um ou mais CHAPTER e cada

CHAPTER pode conter um ou mais SPEAKER. Quando processado um SPEAKER, a

classe tem a responsabilidade de fazer limpeza dos dados aplicando o algoritmo remove

StopWords, Steamer e guarda assim a referência de cada corpus numa estrutura de

HasMap, este recebe um id que é sequencial e um valor que contém a data que se

encontra em cada ficheiro concatenado com o id do CHAPTER e o id do SPEAKER,

nome do SPEAKER e referida Lingua. De realçar ainda que para proceder com limpeza

dos dados, foi criada ainda, um ficheiro com StopWords complexo, onde será removido

alguns outros termos que o stopWords simples ignorava.

Token – Classe responsável pelo tratamento e contabilização dos termos individuais;

OperateWhitThread – classe onde é criado todas operações que utiliza Thread;

Ranking – Classe onde realiza as operações relativamente ao ranking retrieval;

ListaRanking – Representa uma estrutura responsável por fazer armazenamento dos

corpus e a relativa classificação de ranking, de notar que esta estrutura apresenta os

dados ordenados.

Indexer – Classe responsável por fazer indexação final, executado todos os métodos das

outras classes descritas acima.



7

A estrutura das classes é apresentada na figura 1.

Figura 1 - Diagrama de Classes



8

Assim como foi descrito acima, acerca da classe CorpusRead, Indexer e Token podemos ver na

figura 2 o modelo descrevendo como é que essas classes trabalham para organizar os Corpus.

Para realizar a operação de indexação foi fornecido um conjunto de documentos (corpus). O

algoritmo desenvolvido aplica sobre esses corpus o princípio de divisão para que seja utilizado

menos memória possível e com menor quantidade de dados para processar a velocidade do

mesmo é maior.

Imaginemos numa fábrica onde dois funcionários trabalham na mesma linha de produção: isso

seria o equivalente a um processador dual-core. Caso o gerente tiver que mandar uma tarefa

Figura 2 – Modo de leitura dos Corpus



9

apenas para o primeiro operário, o segundo fica sem ter o que fazer. Desta forma só o primeiro

operário fica a trabalhar.

Para resolver esse problema, o gerente pode dividir a tarefa em duas partes e mandado ordenado

assim que cada um fizesse uma parte do trabalho. Dessa maneira, o processo seria concluído em

menos tempo e com maior eficácia.

Onde queremos chegar com esse exemplo? Simples: o algoritmo desenvolvido segue o mesmo

modelo que o gerente deve tomar para dividir tarefas aos seus operários.

Neste caso o que o algoritmo foi treinado a fazer é a repartição de dados em vários blocos, de

acordo com a definição na configuração, cada bloco ainda é subdividido de forma a partilhar os

mesmos aos várias threads tornando os mais eficientes, não sobrecarrega-los com grande

quantidade de dados na memória. Em java cada thread tem uma quantidade de memória limitada

e uma instanciação de processador reservado, permitindo assim a sua execução em paralelo e

independente de qualquer outro processo.

Depois de realizar toda a operação de divisão dos ficheiros em blocos, os blocos são tratados

pelas Threads, assim como foi descrito na descrição da classe CorpusRead, de forma que no

final cada speaker dentro dos Chapter, virá a ser um Corpus.

Depois de já ter um Corpus, as threads encarregam de fazer o tratamento dos mesmos (aplicação

do StopWords e Steamer) e armazena-os numa estrutura em HashMap, cada uma desta estrutura

é armazenado no disco de forma a libertar o espaço de memória, de mesmo modo as threads

são liberadas forma estarem prontos para executarem novas tarefas.

Os dados armazenados em disco são processados por uma outra thread para realizar a

tokenização, cada bloco no disco é carregado e um outro processo faz a contagem dos termos

para cada corpus devolvendo-os na estrutura de índice invertido 5.

5 Ver figura 4



10

Para melhor compreender todo o processo foi criada o seguinte diagrama de fluxo de dados que

representa todo o algoritmo.

Figura 3 – Diagrama de fluxo de dados da indexação invertida

PARTE 2 – CORPUS READ

Um dos requisitos do trabalho é criar uma classe capaz de fazer leitura de corpus e devolver o

conteúdo dos mesmos, analisando a estrutura do mesmo e removendo os caracteres especiais

existentes (tags HTML etc…).

A leitura dos ficheiros é feita através da divisão de corpus em segmentos, definida na

configuração, de forma a realizar toda as operações de leitura e tratamento dos conteúdos dos

ficheiros em paralelo entre as várias Threads. Para que o processo seja eficiente na utilização

do processador e da memória.

Cada corpus físico é dividido em vários corpus, conforme o número de speakers de cada corpus,

proporcionando como resultado um corpus com menor quantidade de informação, mais em

maior numero, cada um desses speakers são processados por uma Thead em paralela.



11

A leitura de corpus é armazenada em N estruturas de memória (HashMap), definida na

configuração de forma a facilitar o acesso do mesmo pelas Threads que realizam a operação de

tokenização. Essas estruturas são armazenadas em disco a cada iteração, com vista a melhorar

a performance do algoritmo. Após isso existe as threads auxiliares para carregar um a um, e

realizar o tratamento em memória. Ficam a trabalhar em paralelo com a leitura de corpus.

PARTE 3 – TOKENIZER

Tokenizer tem como objetivo, criar uma classe Token que devolve os tokens de um dado corpus,

sabendo que deve ignorar os caracteres especiais ('.', ',', '-', etc.) como também entidades HTML

e/ou XML (‘ ’ e outros).

Para o efeito, foi desenvolvido no algoritmo uma classe que executa o processo de leitura no

disco, dos corpus armazenados temporariamente, carregar cada um deles e realizar operação de

contagem de ocorrências dos mesmos dentro de cada corpus.

Sabendo que os corpos compõem uma grande quantidade de termos, processa-los de uma vez

só tornaria o algoritmo pouco eficiente, o consumo de memória e o acesso ao processador pode

ser excessivo. Por isso esses termos são divididos em vários segmentos e distribuídos em várias

Threads conforme o número de segmento criado, proporcionando assim uma maior velocidade

no processamento.

Como resultado, o processo irá retornar os termos e o número de vezes que estas ocorrem para

cada corpus. O mesmo será enviado para outras threads com finalidade de criar uma estrutura

de índice invertido.



12

PARTE 4 - INDEXAÇÃO

O objectivo principal de todo o algoritmo é criar indexação de índice invertido. Para o feito foi

criado uma classe de Index que executa todas as classes anteriores e armazena em disco a

indexação realizada.

A figura 4 apresenta a estrutura do índice invertido.

.

Figura 4 – Estrutura do índice Invertido



13

A filosofia adotada foi de utilizar o menos possível na estrutura do índice invertido o HashMap,

pois este consome muita memória.

Foi criada um índice com uma Lista da classe InvertIndex, onde cada índice é armazena a

informação para um determinado termo, e estes estão mapeadas num HashMap com Termo

e índice do ArrayList, pois tornaria o acesso muito mais rápido no processo de indexação e

pesquisa do mesmo.

Classe InvertIndex com os atributos frequênciaTermos (Numero de ocorrência do termo em

todos os corpus), elementos (Lista de classe No). A classe No é utilizada para armazenar

informações do corpus em que cada termo ocorre. Temos Para a classe No os atributos

idCorpus (id correspondente ao corpus), tF (term Frequency), WT (Calculo do Peso), nLize

(Normalização) e idPosicao (Link para uma lista de posição de cada termo dentro de um

Corpus), pois esta lista como consome muita memoria é armazenada no disco (Estrutura

HashMap) e guardado no índice apenas um id que refere ao mesmo.

PARTE 5 – RESPOSTAS AS QUESTÕES

O algoritmo realiza a limpeza de dados através de remoção de alguns termos (palavras) que são

encontrados na lista de StopWords e utilizando ainda o algoritmo de Steamer, de forma a

normalizar os termos. Foi combinado diferentes formas de execução do algoritmo com

finalidade de criar estatísticas acerca do desempenho e quantidade de termos indexados através

do algoritmo. Isto Pode ser analisado na tabela que se segue, com os resultados obtidos através

da combinação da limpeza dos Stop Words e a inclusão ou não do algoritmo Steamer.

Modo Execução Tempo

(Minuto) Número de

Termos Tempo Inicial Tempo Final

Com remoção do Stop

Words e Steamer

8.53 88778 11:18:54 11:27:26

Sem remoção do Stop

Words e com Steamer

8.43 88806 11:29:50 11:38:17

Com remoção do Stop

Words sem execução do

Steamer

8.1 162187 11:48:12 11:56:19



14

Sem remoção do Stop

Words e sem execução

do Steamer

8.33 162349 12:01:30 12:09:50

Tabela I - Tabela estatística de indexação com remoção do StopWords e aplicação do algoritmo Steamer.

O tempo inicial referido na tabela acima representa o tempo em que o algoritmo foi iniciado e

o tempo final, representa o tempo em que o algoritmo termina execução.

Uma dos requisitos também é criar novo corpus a partir das informações de cada Speaker dentro

dos Chapters, ou seja o nome do corpus devem ser além das datas, ter o chapter ID, o speaker

ID, O nome do Speaker e a língua. Para isso foi criado a seguinte estrutura para o nome do

corpus:

D:00-03-14 C:10 S:167 N:Antonios L:SL

o D – data do corpus

o C – Chapter ID

o S – Speaker ID

o N – Nome do Speaker

o L – língua do speaker (o Speaker que não tem língua é atribuída SL)

Para responder as questões é necessário criar o algoritmo que realiza o ranking dos termos por

cada corpus utilizando o processo tf-idf. A figura 5 apresenta a forma como é realizada todo o

processo de cálculo do ranking.



15

Figura 5 - Calculo do Ranking

O processo começa com a indexação onde é calculado o peso de termos por corpus que é 1+

log10 (TF) para tf maior que zero, 0 caso contrario, durante esse processo é calculado o DF e

armazenada num HashMap (termo, DF), calculado também o doc lenght (raiz quadrada do

somatório ao quadrado de cada WT dos termos) e armazenada numa Estrutura HashMap

(corpus, dc lenght), foi utilizado o HashMap pois facilita a inserção e a pesquisa do mesmo.

Após terminar a indexação é realizado o calculo do IDF sobre a estrutura de HashMap do DF,

onde o IDF é log10(N/DF), terminando o calculo do IDF é calculado o N’Lize para cada termo

por Corpus. Para isso é realizada uma iteração pela estrutura do Índice invertido onde a cada

relação Termo/Corpus é aplicado a normalização (WT/docLenght). E essas informações podem

ser guardadas no disco conforme a opção do utilizador, permanecendo na memória.

Quando o utilizador pretende processar a query, parte da informação (lista de posições) é lida

do disco antes de inserir a query. Com essa inserção é calculada o WT da query ((1+log(tf-wt)

para tf-wt > 0, 0 caso contrario) * IDF), a normalização do mesmo (WTquery/docLenghtquery )

e obtido a normalização do Termo/Corpus. Com essas informações disponíveis é calculado o

score e disponibilizada a informação no Output.



16

Os dados calculados da score por cada termo/corpus é adicionado numa estrutura em lista de

forma ordenada por ordem decrescente ou seja a instancia com maior score fica no início da

fila, e depois a mesma é apresentada no output ordenada. Para isso é utilizada a classe

ListaRanking com Atributos:

String NomeCorpus – Nome atribuído ao corpus;

int idCorpus – identificação dos corpus;

double score – o score calculado para os corpus;

HashMap cálculos – os cálculos efetuados (WT, IDF, N’Lize);

ListaRanking próximo – apontado para o próximo elemento da lista.

PESQUISA SIMPLES (3 - PARTE A)

Para a realização desta pesquisa é criado uma lista de corpus, são corpus onde os termos

aparecem, isto para realizar a operação de ranking apenas nos corpus/termos da query. Para

isso é realizada a operação de união dos corpus onde os termos introduzidos ocorrem (vide

figura 6).

Figura 6 – Cálculo do ranking para pesquisa simples

Apos a inserção dos termos é aplicado a limpeza dos stopwords e aplicado o steamers, e

realizada uma união de todos os corpus onde os termos aparecem e depois diss o é calculado

o ranking para cada um dos corpus/termos.



17

PESQUISA DE FRASES E DE PROXIMIDADE E COM QUOTAS K (4 – PARTE B)

A pesquisa de frases e de proximidade é utilizada o mesmo algoritmo, pois a pesquisa de frase

utiliza a proximidade igual a 1, enquanto a pesquisa de proximidade utiliza uma quota igual a

K, introduzida pelo utilizado na query.

Para a realização desta pesquisa é criado uma lista de corpus, são corpus onde os todos os

termos aparecem, isto para realizar a operação de ranking apenas nos corpus/termos da query

aparecem todos ao mesmo tempo.

Para isso é realizada a operação de interseção dos corpus onde os termos introduzidos

ocorrem (vide figura 7), apos isso é aplicado o processo de proximidade apenas nos N

primeiros corpus do Ranking, proporcionado maior rapidez, pois não será preciso realizar o

cálculo de proximidade em grande número de corpus, visto que já tenhamos o corpus com

maior probabilidade dos termos aparecerem juntos.

Figura 7 – pesquisa de Proximidade

PESQUISA POR COMBINAÇÃO DE CAMPOS (5 – PARTE B)



18

A pesquisa por combinação dos campos é suposto ao utilizador inserir determinado campo a

pesquisar e proporcionar resultados conforme o campo escolhido, por exemplo pesquisar

todos os corpus onde aparece o speaker com o nome Marques.

Para isso foi utilizado um filtro baseado no nome do corpus mapeado durante a indexação,

pois o nome do corpus já tem o nome para cada speaker. Além disso tem todos os outros

campos que podem ser utilizados na pesquisa, como língua e data (vide figura 8).

Figura 8 - Pesquisa por campos no corpus



19

PARTE 6 – EXECUÇÃO DO ALGORITMO INDEXAÇÃO

Figura 9 - Escolher a configuração

Ao iniciar o algoritmo, questionado ao utilizador sobre a configuração do mesmo, onde pode

adicionar um novo endereço para a configuração ou pressionar um Enter para aceitar a

configuração por defeito.

Apos isso é apresentado um menu, com opções a fim de ajudar-nos na execução do algoritmo.

Opções como: Executar a indexação e apresentar os relatórios, Queries, Configuração, Load a

Save Data, vide a figura 10.



20

Figura 10 - Menu inicial

A configuração é muito importante, pois a partir desta é possível determinar o número de corpus

a processar por cada threads, por defeito é aplicado uma configuração com um threads para cada

corpus para quantidade de corpus até 50, a partir desta os corpus são processados em grupos de

50 e criado 50 HashMaps e 50 Threads para processar respetivos corpus. Esta configuração

pode ser alterada pelo utilizador antes de executar a indexação. Vide figura 11.

Figura 11 - Opção de configuração



21

Definir o número de blocos de memória a processar tem a ver com a quantidade de HasHMap

a ser utilizado para armazenar informação durante o processo de corpus Read e de

Tokenização, os mesmos são armazenados no disco para continuação do processo de

indexação, visto a sua permanência na memória, irá sobrecarregar a mesma.

Definir o número de Blocos de Corpus, tem a ver com o número de corpus a ser carregado e

processado por cada threads que é criada conforme a configuração do número de blocos de

memória, vide figura 2.

Definir o limite de memória que a aplicação deve chegar tem a ver com o ultimo limite que a

aplicação deve suportar durante o processo de indexação.

Todas essas configurações são carregadas e armazenadas num ficheiro de configuração por

isso o utilizador pode aceitar ou não a configuração por defeito.

Após escolher a opção executar Indexação é apresentada as opções de execução.

Opção 1 - é para arrancar com a execução em si. Durante a execução aparece no output o tempo

de início e os números de grupos de corpus em execução, ao terminar a indexação aprece o

tempo final.

Opção 2 [Desativar] Stopwords, significa que o algoritmo vai ser executado removendo do

corpus todos os Stopwords, caso se pretenda deixar os Stopwords nos corpos deve ser escolhida

esta opção, o utilizador pode ativar ou desativar execução de Stopwords.

Opção 3 [Desativar] Steamer, significa que o algoritmo vai ser executado aplicando algoritmo

de Steamer sobre os termos, caso se pretenda deixar os termos sem aplicar o Steamer deve ser

escolhida esta opção.

Opção 4 pode ser escolhida os dois modos de execução ao mesmo tempo. Vide a figura 12.



22

Figura 12 - Menu execução da indexação

No menu inicial, na figura 8 se escolher a opção 3 é proporcionado um outro menu de forma a realizar as diversas pesquisas sugeridas no trabalho ver figura 13.

Figura 13 - Opção de queries



23

A opção 1 é para realizar as queries da parte A em 3, na opção 2 e 3 para realizar as pesquisas

por frases de proximidade na parte B em 4 e a opção 4 para realizar a pesquisa proposta em

parte B em 5.

PARTE 6 – CONSIDERAÇÕES FINAIS

Este trabalho propôs-se como objetivo geral criar uma estrutura de indexação invertida em

java, para que o trabalho não se limitasse a um simples algoritmo de indexação pouco eficiente

em termos de recursos e tempos, foi realizado um conjunto de pesquisa e ações de forma a

torna-lo num algoritmo eficiente na utilização dos recursos e com um tempo de execução

razoável.

Este tempo pode ser melhorado muito ainda mais com um uma unidade de processamento e

memória maior, aumentando o número de corpos a processar a cada bloco de corpos.

Filosofia de segmentação e multiprocessamento adotada pode se dizer que em termos de

performance do algoritmo o ganho foi brutal, visto que com o multiprocessamento dos corpos

em segmentos teremos pouca utilização da memória e uma melhor eficiência no uso do

processador, bem como a operação de pesquisa sobre o Índice invertido criado.

A nível de eficiência o maior ganho em termos de eficiência do algoritmo foi conseguido nos

seguintes pontos:

Segmentação dos corpos e grupos pequenos, num tamanho razoável para permitir que

não seja sobrecarregada o processador e a memória;

Construção do índice invertido utilizado Listas em Array para uma estrutura em classes,

pois a inserção e pesquisa é muito rápido bem como o consumo de memória é menor,

pois é utilizada menos HashMaps.

Não utilização de colectores de lixo (Garbage colector, System.gc() no Java) da memoria

varias vezes, pois o mesmo tende a tornar pouco eficiente o algoritmo, pois executa

varias operações para o efeito.

Aplicação de uma classe policy, que determina a quantidade de memória em uso e o

limite a ser utilizada durante a indexação e processamento d algoritmo, permite que

não haja uma sobrecarga da memória.

Data & Analytics

Armazenamento, Indexação e Recuperação de Informação