MAC 499- TRABALHO DE FORMATURA
SUPERVISIONADO
MONOGRAFIA
Professor
supervisor : Yoshiharu Kohayakawa e-mail:yoshi@ime.usp.br
Professor
responsável : Carlos Eduardo Ferreira e-mail:cef@ime.usp.br
Aluno : Ulisses Kendi Hayashida e-mail:ulisses@ime.usp.br
Tipo de trabalho: Iniciação Científica
ÍNDICE
1. Introdução
4. Compressão, descompressão e indexação
4.1 Modelos
5. Tópicos/teorias/sistemas
estudados ou desenvolvidos
5.2
LZ77
5.3
Índices
5.3.1
Indexação de arquivo invertido
6. O MG
8. Conclusão ou resultados obtidos
10. Desafios e frustrações encontradas
11. Lista das disciplinas cursadas no BCC mais relevantes para a Iniciação Científica
12. Interação com
colegas ou professores que tenham agido como mentores do trabalho
14. Pretende continuar
estudando o tema, ou tema correlato em uma pós-graduação ?
PRIMEIRA PARTE
1. Introdução
O tradicional método de armazenar dados em papel é muito custoso em relação a espaço de armazenamento e, mais importante, o tempo levado para localizar e recuperar informações. Portanto torna-se cada vez mais atrativo armazenar e acessar documentos eletronicamente. Para ter uma melhor noção, os textos de centenas de livros que ocupariam um espaço considerável podem ser mantidos em apenas um disco rígido. Ainda mais importante, a informação pode ser acessada usando palavras chave tiradas do próprio texto, muito melhor os esquemas manuais de catalogar livros, por exemplo, fornecendo flexibilidade, pois todas as palavras de um texto podem ser palavras chave, e segurança, pois a indexação é realizada sem interpretação ou intervenção humana. Além do mais, hoje em dia existem diversas fontes de informação eletrônica, como arquivos de computador, fac-símiles e documentos digitalizados. Todos esses podem ser armazenados e acessados eficientemente usando mídias eletrônicas, dispensado o uso de papéis.
O assunto sobre o qual estou estudando na minha
Iniciação Científica, com supervisão do professor Yoshiharu Kohayakawa (Yoshi), irá tratar
portanto da compressão, gerenciamento e indexação de dados eletrônicos (textos
e figuras).
2. Objetivos do trabalho
O objetivo desta Iniciação Científica é estudar métodos para gerenciar dados digitais de forma eficiente e eficaz, de modo que dados pertinentes possam ser localizados e extraídos sem grandes custos ou inconveniências.
O trabalho visa principalmente a compressão, gerenciamento e indexação de grandes quantidades de dados (textos e figuras).
3. Metodologia empregada
Inicialmente, para fazer o trabalho consultei meu supervisor sobre algum assunto que ele teria interesse, e entre os vários propostos, optei pelo de gerenciamento de dados. No primeiro semestre minha metodologia de trabalho foi ficar lendo , em média 6 horas por semana, parte do livro Managing Gygabytes [1], o qual contém uma série de algoritmos de compressão e indexação de textos e imagens. No segundo semestre, minha metodologia de trabalho foi mais voltada para tentar instalar alguns softwares de compressão e indexação indicados pelo livro. Para isso, dediquei as sextas-feiras para ficar tentando instalar esses softwares e conseqüentemente um pouco mais sobre o sistema Unix.
4. Compressão, descompressão e indexação
Compressão é a mudança de
representação de um arquivo para que ocupe menos espaço de armazenamento ou
menos tempo para transmitir, com o arquivo original podendo ser reconstruído
exatamente a partir da representação.
4.1 Modelos
Compressão
é obtida formando-se modelos dos dados a serem comprimidos. Um modelo provê a distribuição
de probabilidade dos símbolos contidos nos dados. O conjunto de todos os
símbolos é chamando alfabeto.
Tanto o
codificador como o decodificador devem usar o mesmo modelo.
O número
de bits para codificar um símbolo ,s, é chamado de conteúdo de informação.
O conteúdo de informação, I(s), esta diretamente relacionado com
a probabilidade do símbolo, Pr[s], pela
função I(s) = -log Pr[s] bits. A quantidade média de informação por
símbolo sobre um alfabeto é conhecido
como a entropia da distribuição de probabilidade, denotada por H,
e é dada por:
H = å P[s].I(s) = å -P[s].log Pr[s], para todos s
pertencente ao alfabeto
Desde
que os símbolos apareçam independentemente e com probabilidades já definidas, H
é um limite inferior para compressão, medido em bits por símbolo. Esse
limite inferior foi provado por Claude Shannon, cientista da Bell Labs.
Portanto
um bom algoritmo de compressão deve fornecer compressão o mais perto possível
da entropia.
A
fórmula acima indica que baixas probabilidades resultam em alta entropia e
vice-versa. No caso extremo, quando a probabilidade de um símbolo s é 1, apenas
um símbolo é possível, e I(s) = 0, indicando que nenhum bit é necessário
para transmiti-lo , ou seja, se um símbolo é certo para ocorrer, não precisa
ser transmitido. Por outro lado, I(s) torna-se muito grande quando Pr[s]
aproxima-se de zero, e um símbolo com probabilidade zero não poderia ser
codificado. Portanto, na prática é dada uma probabilidade diferente de zero a
todos os símbolos, pois pode ser que por azar apareça tal símbolo.
Para
melhorar o resultado da fórmula acima, a probabilidade para o próximo símbolo
pode ser tomada levando em conta o símbolo anterior. Por exemplo, se o símbolo q
acabou de ser encontrado, a probabilidade do próximo ser u deve ser bem
grande, baseado na freqüência em que um q é seguido por um u. É
claro que os outros símbolos terão probabilidades menores para compensar, e se
a predição estiver incorreta, o próximo símbolo será codificado com mais bits.
Modelos
que tomam em conta o conjunto dos símbolos imediatamente precedentes para fazer
uma predição das probabilidades são chamados modelos de contexto finito de
ordem m, onde m é o número de símbolos prévios usados para fazer a
predição. Esse modelo é efetivo em uma variedade de aplicações de compressão, e
os melhores métodos conhecidos são baseados nele. Uma variação desse modelo é
usar um modelo de estado finito, em que cada estado de uma máquina de
estados finito armazena uma probabilidade de distribuição diferente para o
próximo símbolo. Para explicar melhor, a figura abaixo serve para modelar
strings em que o símbolo a é esperado para ocorrer em pares. A codificação
começa no estado 1, onde a e b são esperados com igual
probabilidade ½.
Usando
a fórmula acima, resultará que cada símbolo usará em média 1 bit. Vê-se
claramente na figura acima que depois de uma letra primeira letra a
tem-se probabilidade bem grande para que o próximo símbolo seja a
também.
5. Tópicos/teorias/sistemas
estudados ou desenvolvidos
Entre
os algoritmos que estudei, os principais são:
Código de
Huffman:
Codificação
aritmética
Decodificação
aritmética
Codificação
e decodificação usando a transformação de Burrows-Wheeler
O método
DMC
Codificação
usando DMC
Compressão
e descompressão usando LZ77
Para
não escrever muito, irei explicar um pouco dois deles: Código de Huffman e
Compressão de descompressão usando LZ77.
5.1 Código de Huffman
Codificação
é a tarefa de determinar a representação de um símbolo, baseado na distribuição
de probabilidade suprido por um modelo. A idéia geral é que o codificador
deveria dar como saída, representações mais curtas para símbolos mais prováveis
e mais compridas para símbolos menos prováveis. Uma consideração importante é a
velocidade do codificador, pois pode haver um grande overhead se for requerida
uma compressão ótima. Pode-se sacrificar um pouco da performance da compressão
para reduzir o overhead.
Dado um
texto cujos símbolos em ordem decrescente de probabilidade sejam :
t,e,s,n,a,o,l, uma possível representação para os símbolos seria:
símbolo |
representação |
Probabilidades |
|
T |
00 |
0,3 |
|
E |
10 |
0,2 |
|
S |
010 |
0,2 |
|
N |
110 |
0,1 |
|
A |
111 |
0,1 |
|
O |
0110 |
0,05 |
|
L |
0111 |
0,05 |
Colocando
a tabela acima em uma árvore, temos a figura abaixo, que pode ser usada para a
decodificação. Para decodificar um símbolo, a árvore é percorrida transversalmente,
começando da raiz até alguma folha. O
caminho percorrido corresponde a uma representação na tabela acima.
O
algoritmo de Huffman constrói a árvore de decodificação de baixo para cima. Como
exemplo, sabendo as probabilidades dos símbolos, primeiro o algoritmo constrói
um nó para cada símbolo. Depois os dois nós com menor probabilidade tornam-se
irmãos na árvore, criando-se para isso um nó pai que tenha como probabilidade a
soma dos seus dois filhos. A operação de combinação é repetida, escolhendo-se
novamente os dois nós com menor probabilidade e ignorando-se os nós que já são
filhos.
Exemplo: combinação
dos nós O e L
O código de Huffman é geralmente
rápido tanto para codificação como para decodificação, visto que as
probabilidades são estáticas. Também há versões em que as probabilidades são
adaptativas, o que diminui a velocidade devido a um maior overhead para a computação
das probabilidades.
5.2 LZ77
O
LZ77 (Ziv and Lempel 1977) é um algoritmo fácil de implementar e a
decodificação pode ser feita de maneira extremamente rápida usando pouca
memória. Por estas razões é ajustável quando os recursos são mínimos. A melhor
maneira de explicar o funcionamento do LZ77 é em termos de sua decodificação. A
figura abaixo mostra uma saída do codificador LZ77, supondo para propósitos de
exemplo que o alfabeto consiste apenas de a’s e
b’s. A saída consiste de uma de triplas. O primeiro componente de uma tripla indica quanto
voltar no texto já decodificado para encontrar a próxima frase, o segundo
componente armazena o comprimento dessa frase, e o terceiro dá o próximo
caracter da entrada.Os dois primeiros itens constituem um ponteiro de volta no
texto. Na figura os caracteres abaabab já foram decodificados, e os
próximos caracteres para ser decodificados são representados pela tripla
<5,3,b>.Portanto o decodificador volta cinco caracteres no texto
decodificado e copia três caracteres, produzindo a frase aab. A próxima
tripla, <1,10,a>, é uma referencia recursiva. Para decodifica-la, o
decodificador começa copiando um caracter anterior (b) e copia os próximos dez
caracteres. Isso produzirá 10 b’s consecutivos.
O LZ77 limita quanto um ponteiro
pode voltar em um texto, e o tamanho máximo de uma frase.
Para codificar então, o LZ77 vai
percorrendo o texto e vai produzindo triplas para partes já percorridas do
texto. As triplas <0,0,a> e <0,0,b> iniciais contém zeros porque
são os primeiros a’s e b’s a aparecerem, portanto não se volta
nada no texto e apenas se copia o terceiro item da tripla.
5.3 Índices
Apesar do uso de compressão salvar muito
espaço, isso não ajuda quanto a questão de como a informação deveria ser
organizada de modo que consultas possam ser feitas e porções relevantes de
dados sejam localizados e extraídos. Índices são cruciais para um acesso
eficiente.
5.3.1 Indexação de arquivo invertido
Em aplicações envolvendo texto, o
método mais ajustável é o uso de um arquivo invertido. Um arquivo invertido
contém, para cada termo de um dicionário, uma lista invertida que armazena uma
lista de ponteiros para todas as ocorrências daquele termo no texto, onde cada
ponteiro é, em efeito, o número de um documento no qual esse termo aparece. Um
índice de arquivo invertido requer um lexicon, ou seja, uma lista de
todos os termos que aparecem na base de dados. O léxico faz um
mapeamento dos termos para suas correspondentes listas invertidas e a sua forma
mais simples é uma lista de strings e endereços de disco. Como exemplo, podemos
tomar cada linha de um texto para ser um documento. O arquivo invertido gerado
seria uma lista com cada célula tendo uma palavra do texto e uma lista com as
linhas em que essa palavra aparece. As listas invertidas são geralmente
armazenadas em ordem crescente de documento, facilitando operações de merge
entre listas.
6 O MG
O mg é um software de domínio público que usa os melhores algoritmos de compressão e indexação. O MG esta coberto pelo GNU public licence. A versão corrente do MG esta disponível via ftp em http://www.cs.mu.oz.au/mg/.
O mg
demonstra os vários tipos de compressões possíveis com diferentes tipos de
documentos, e também de velocidade de indexação e recuperação.
Um bom
exemplo que tirei do livro mostra as performances para compressão dos textos da
Bíblia,das bibliotecas do GNU e do Comact e do TREC, sendo que não sei bem do
que se tratam os dois últimos. Na tabela abaixo os números indicam a
porcentagem de tamanho sobre o texto normal. O melhor método, o ppm (predição
por emparelhamento parcial) usa o modelo de contexto finito discutido
anteriormente, assim como os outros melhores métodos.
|
Método |
Bíblia |
GNUlib |
Comact |
TREC |
Média |
|
Pack |
57,5 |
64,5 |
63,2 |
63,0 |
62,0 |
|
Char |
57,2 |
64,2 |
62,8 |
62,4 |
61,6 |
|
Lzrw1 |
52,0 |
44,7 |
42,1 |
59,3 |
49,5 |
|
Compress |
34,2 |
31,6 |
32,3 |
40,4 |
34,6 |
|
Gzip-f |
36,8 |
26,6 |
25,3 |
39,9 |
31,9 |
|
Huffword |
27,1 |
26,6 |
26,2 |
29,4 |
27,3 |
|
Gzip-b |
28,8 |
22,3 |
19,2 |
33,3 |
25,9 |
|
Dmc |
22,1 |
17,6 |
16,6 |
27,1 |
20,9 |
|
Bzip |
20,5 |
15,9 |
14,2 |
24,8 |
18,8 |
|
Ppm |
19,0 |
14,0 |
14,2 |
23,0 |
17,6 |
Maiores informações sobre o software (incluindo exemplos e man pages) estão disponíveis em http://www.mds.rmit.edu.au/mg/;
7. Atividades realizadas
Durante o primeiro semestre, leitura do livro Managing Gygabytes[1], análise dos algoritmos de compressão e indexação, estudo de exemplos.
Durante o segundo semestre, instalação do software mg, estudo de parte do código do software, e alguns testes usando o software. Como o software é todo escrito em linguagem C, consultei também o livro do Kerninghan e Richie. No começo do mês de novembro, comecei a escrever esta monografia,
8. Conclusão ou resultados obtidos
A conclusão a que cheguei é que com o aumento cada vez maior da quantidade de informação, principalmente devido a internet, a tendência é de que haverá uma maior necessidade de espaço para armazenamento. Portanto a compactação ira se tornar cada vez mais comum, como já é comum quando fazemos o download de um arquivo (geralmente já esta comprimido). Nos últimos anos tem havido um aumento no número de sites especializados em fazer buscas (google, yahoo, altavista ), o que é reflexo do maior número de pessoas querendo fazer consultas via internet. Uma rápida busca torna-se então necessária. Os índices estão aí para ajudar nessa busca. Como dito anteriormente, atualmente o principal foco esta na indexação eficiente dos dados, e não mais na compressão, devido ao aviltamento dos discos rígidos e maior poder de processamento para produzir os índices.
9. Bibliografia utilizada
[1] Ian H. Witten, Alistair Moffat, Timothy C. Bell Managing Gygabytes
– Compressing and Indexing Documents and Images, Second Edition, Ed. Morgan
Kaufman 1999
[2] Kernigan & Ritchie, Linguagem C
SEGUNDA PARTE
10. Desafios e frustrações encontrados
O maior desafio e frustração encontrado foi a parte de instalação do software greenstone na rede do IME, pois sempre falhava, e por mais que eu tentasse achar onde estava o problema, não conseguia resolver. Isso fui muito frustrante, pois além de perder meia hora em cada tentativa de instalação, que foram várias, esse software seria o que mais se aproximaria do objetivo da Iniciação Científica, ou seja, um programa com interfaces gráficas adequado para a web, software esse que seria alterado para talvez ser instalado na rede do IME para fazer buscas.
11. Lista das disciplinas cursadas no BCC mais relevantes para a Iniciação Científica
As disciplinas que mais me ajudaram na Iniciação Científica foram:
Mac 110 : Introdução a computação
Foi
em Mac 110 que tive as primeiras noções sobre como funciona uma compactação,
sendo que foi em Mac 110 que fiz pela primeira vez um código (em Pascal) que
compactava textos.
Mac 122 : Princípio de
desenvolvimento de algoritmos
Foi
em Mac 122 que vi pela primeira vez o código de Huffman, e foi nessa disciplina
que aprendi a linguagem C, que como já
foi dito, é a linguagem usada no mg, e foi nela que aprendi sobre os algoritmos
mais conhecidos de busca, reconhecimento de padrões, ordenação, inserção, etc,
que são a base para desenvolver e entender um software.
Mac 323: Estrutura de dados
Sem
dúvida, estruturas de dados estão presentes em todos os softwares de maior
complexidade, como o mg, e as noções que aprendi de filas, pilhas e árvores me
ajudaram muito.
Mac 338: Análise de Algoritmos
Em
Análise de Algoritmos pude rever as principais estruturas de dados e algoritmos
em Mac 122 e Mac 323, mas com ênfase em calcular a melhor ou pior eficiência de
cada um.
Mac: 330: Algoritmos Algébricos
Como
na verdade essa matéria trata de Criptografia, foram estudados vários
algoritmos que transformavam um texto em algo totalmente diferente, e depois
recuperar o texto anterior, o que se assemelha muito com compressão e
descompressão, e aprendi também sobre entropia das palavras, que tem a ver com
compressão.
12. Interação com colegas ou professores que tenham agido como mentores do trabalho
Optei fazer a Iniciação Científica individualmente, pois o meu horário de aulas não coincidia muito bem com o dos meus colegas. Quanto ao meu supervisor, Yoshiharu Kohayakawa, sempre dispôs-se a me atender quando de uma dúvida, requisição de um livro ou aumento de cota de disco na rede do IME. Ajudou-me também a resolver os problemas de configuração que tive na rede ao tentar instalar o software greenstone.
13. Diferenças notadas entre a forma de cooperação com colegas do BCC nas tarefas em grupo das disciplinas e a forma de trabalho da iniciação
Como fiz individualmente, acho que essa questão não se aplica, mas acredito que não haveria grandes diferenças.
14. Pretende continuar estudando o tema, ou tema correlato em uma pós-graduação?
Certamente que sim, pois o tema é bem amplo, e tem a ver com banco de dados, um dos assuntos que pretendo estudar numa pós-graduação.
15. Se o aluno fosse continuar pesquisando na área, que passos tomaria para aprimorar os conhecimentos técnicos/metodológicos/cientificos/etc relevantes para esta atividade ?
Primeiro iria estudar mais profundamente os algoritmos de compressão, descompressão e indexação, analisando a eficiência de cada um, os casos em um é melhor que o outro, os casos médios e qual seria a pior e a melhor eficiência da cada um deles. Daria ênfase nos algoritmos de indexação, pois acho que é o de maior importância atualmente, pois com o preço cada vez menor dos dispositivos de armazenamento, não há mais tanto interesse com a economia de espaço. Hoje os interesses estão voltados mais para a rápida busca de informações.
Depois, com um maior conhecimento desses algoritmos, pretenderia criar novos algoritmos, alguns talvez voltados especialmente para a nossa língua.