Este trabalho é uma realização conjunta de Adriano Mitre, Helton Kishi e Igor Rascovsky.
O objetivo do trabalho foi implementar um sistema de compressão, descompressão e simulação de textos baseado em cadeias de Markov.
O conjunto de dados escolhido pelo grupo foi o linguístico.
O arquivo
O grupo optou por codificar o sistema na linguagem JavaScript. A decisão levou em conta diversos fatores, tais como facilidade e agilidade no desenvolvimento do sistema e de sua interface, a qual decidimos que deveria ser gráfica e amigável. Além disso, a portabilidade do sistema e legibilidade de seu código foram fatores decisivos na escolha da linguagem.
Adicionalmente, foi utilizada a linguagem Java na codificação do parser da árvore probabilística produzida pelo sistema R.
O enunciado do trabalho não esclarece se a estimação das probabilidades de transição deve ser estática (offline) ou adaptativa (online). Alguns dias após a publicação do enunciado o professor afirmou tratar-se do primeiro caso, por conta da maior dificuldade da estimação adaptativa.
Na ocasião do esclarecimento, contudo, o grupo já havia implementado grande parte do sistema utilizado estimação adaptativa. Assim, os integrantes optaram por concluir a implementação da versão adaptativa e posteriormente incluir, para efeitos de comparação, a versão estática.
Em aula, o Prof. Antonio Galves fez entender que os grupos implementassem a versão adaptativa teriam pontos de bonificação na nota. Não ficou acertado, no entanto, quantos pontos seriam.
Apesar de o enunciado exigir apenas cadeias de Markov de ordem 1 e 2, o sistema implementado suporta cadeias de qualquer ordem maior ou igual zero, lembrando que k = 0 é o modelo independente (ao longo do texto, k denotará o alcance).
A fim de não sobrecarregar a interface com o usuário o grupo optou por limitar a ordem do modelo em 10, que é o alcance da VLMC ótima para o texto escolhido (detalhes na seção Árvore Probabilística).
Convém notar que o grupo também realizou experimentos com cadeias de ordem diferente de 1 e 2. Além disso, para cada k foram realizados o dobro de testes: um para o compressor estático, outro para o dinâmico.
A estimação das probabilidades de transição é feita como descrito nas notas de aula sobre compressão com cadeias de Markov de alcance fixo, redigidas por Adriano Mitre.
Para a estimação estática, utilizou-se o estimador de máxima verossimilhança da Equação 6.
A função que trata disso é estProbMLE() do arquivo
Já para a estimação adaptativa, utilizou-se o estimador de máxima verossimilhança com a Regra da Sucessão
(Equação 7). A função que trata disso é estProb() do arquivo
O algoritmo de compressão utiliza as probabilidades de transição estimadas para produzir códigos que
seguem a prescrição de Shannon.
O arquivo
Convém destacar que a determinação dos códigos é feita sem a construção explícita da árvore de códigos.
As funções que tratam disso são getPrevSameLen() e getCode()
do arquivo
O algoritmo de descompressão implementado foi o adaptativo, que opera por meio da criação de um vetor
associativo que possui como valores os caracteres do alfabeto e cujas chaves são os códigos das mesmas.
O arquivo
Um modelo de ordem k só determina como se faz para simular caracteres a partir da (k+1)-ésimo. Em face disso, o grupo adotou a seguinte convenção: os k primeiros símbolos da simulação serão os k primeiros símbolos do texto de entrada.
As partições são geradas como uma matriz de transição cumulativa, que se baseia na matriz estimada ao final do processo de compressão. A função que trata disso écriaMatrizTransicaoCumulativa()
do arquivo
Depois disso, há um laço principal. A cada iteração do laço simula-se um caractere.
A função proximoPassoMarkov() determina a próximo caractere
dada um prefixo e a matriz de transição.
Convém notar que, para o caso de passados que não ocorreram no texto de entrada, a simulação será realizada com distribuição de probabilidade uniforme. Por conta disso, pode haver no texto simulado caracteres que não ocorreram no texto de entrada.
O arquivo
A árvore probabilística correspondente ao modelo de memória variável foi produzida no sitema R pela seguinte seqüência de comandos:
library(VLMC)
texto <- scan(file="Candido1_bin.txt", sep=" ", what="")
arvore <- vlmc(texto)
arvore
draw(arvore)
O comando arvore acima produz a seguinte saída:
`vlmc', a Variable Length Markov Chain;
alphabet '01234', |alphabet| = 5, n = 13615.
Call: vlmc(dts = txt); default cutoff = 4.744
-> extensions (= $size ) :
ord.MC context nr.leaves total
10 38 17 392
O comando draw(arvore), por sua vez, produz a saída abaixo:
[x]-( 6560 2955 2955 962 182| 13614)-F
+--[0]-( 1794 1880 2125 627 134| 6560) <603.23>
| +--[0]-( 559 987 186 48 14| 1794) <430.17>
| | +--[0]-( 163 396 0 0 0| 559) <89.29>
| | | `--[0]-( 28 135 0 0 0| 163) <6.28>-T
| | +--[1]-( 0 0 151 38 9| 198) <392.05>-T
| | +--[2]-( 396 591 0 0 0| 987) <150.15>-T
| | `--[3]-( 0 0 35 10 5| 50) <99.71>-T
| +--[1]-( 198 0 1481 393 106| 2178) <1221.90>
| | +--[0]-( 75 0 955 236 72| 1338) <11.89>
| | | +--[0]-( 19 0 472 115 41| 647) <5.62>
| | | | `--[0]-( 6 0 178 39 17| 240) <0.37>
| | | | `--[0]-( 2 0 46 10 10| 68) <2.40>
| | | | `--[2]-( 2 0 37 8 8| 55) <0.04>
| | | | `--[0]-( 2 0 22 6 5| 35) <0.31>
| | | | `--[0]-( 1 0 0 0 2| 3) <4.84>-T
| | | `--[2]-( 56 0 483 121 31| 691) <4.03>
| | | +--[0]-( 44 0 344 81 22| 491) <0.36>
| | | | `--[1]-( 36 0 239 61 16| 352) <0.49>
| | | | `--[0]-( 23 0 151 43 10| 227) <0.20>
| | | | `--[2]-( 14 0 79 14 7| 114) <2.18>
| | | | `--[0]-( 10 0 55 12 5| 82) <0.20>
| | | | `--[3]-( 5 0 10 0 0| 15) <4.97>-T
| | | `--[3]-( 0 0 26 12 1| 39) <4.97>-T
| | `--[2]-( 123 0 526 157 34| 840) <14.54>
| | +--[0]-( 86 0 372 105 24| 587) <0.13>
| | | `--[3]-( 7 0 100 23 6| 136) <6.71>-T
| | `--[4]-( 5 0 21 15 0| 41) <4.94>-T
| +--[2]-( 987 893 0 0 0| 1880) <1094.92>-T
| `--[3]-( 50 0 458 186 14| 708) <436.69>-T
+--[1]-( 2178 0 570 160 47| 2955) <823.98>
| +--[0]-( 1338 0 402 106 34| 1880) <3.25>
| | +--[0]-( 647 0 259 60 21| 987) <7.75>-T
| | `--[2]-( 691 0 143 46 13| 893) <9.47>-T
| `--[2]-( 840 0 168 54 13| 1075) <6.09>-T
+--[2]-( 1880 1075 0 0 0| 2955) <1077.57>
| `--[4]-( 45 49 0 0 0| 94) <4.83>-T
+--[3]-( 708 0 166 88 1| 963) <280.94>-T
`--[4]-( 0 0 94 87 0| 181) <248.81>-T
A árvore probabilística produzida corresponde à uma VLMC que atende ao critério de otimalidade apresentado no artigo A Universal Data Compression System de Jorma Rissanen.
No caso do texto utilizado (
A representação da árvore produzida pelo pacote VLMC do R é visualmente interessante (considerados os limites de uma representação ASCII), porém inadequada à leitura do programa desenvolvido pelo grupo.
Assim, os integrantes optaram por transformar a representação pelo R em outra mais conveniente.
A representação transformada consiste de seqüências como abc,d=1/2,
onde 1/2 é a probabilidade do caractere d dado o
contexto abc. Exemplo de representação transformada:
0,0=1/3
0,1=2/3
01,0=1/4
01,1=3/4
11,0=1/2
11,1=1/2
A fim de automatizar esta transformação, foi desenvolvido um programa em Java, que recebe um arquivo com a representação textual da árvore tal como produzida pelo R e gera as seqüências no formato acima descrito com suas respectivas probabilidades.
Infelizmente, o aplicativo desenvolvido acabou não sendo utilizado, porque, às vésperas da entrega deste
trabalho, divulgou-se que o arquivo que deveria ter sido utilizado era o
O alfabeto de entrada utilizado foi A={0,1,2,3,4}, apelidado de numérico restrito no sistema desenvolvido pelo grupo.
Apresentamos a seguir as taxas de compressão do texto original, em bits por símbolo (média).
| tipo/alcance | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Adaptativo | 2,645 | 1,899 | 1,632 | 1,590 | 1,628 | 1,690 | 1,782 | 1,911 | 2,054 | 2,218 | 2,384 |
| Estático | 2,642 | 1,891 | 1,613 | 1,536 | 1,544 | 1,527 | 1,491 | 1,459 | 1,413 | 1,347 | 1,270 |
Em acordo com o enunciado do trabalho, o texto simulado foi produzido por uma cadeia de ordem igual à utilizada na compressão.
Apresentamos a seguir as taxas de compressão do texto simulado, em bits por símbolo (média).
| tipo/alcance | 1 | 2 |
|---|---|---|
| Adaptativo | 1,893 | 1,614 |
| Estático | 1,883 | 1,602 |
Naturalmente, as taxas de compressão foram menores para o modelo adaptativo do que para o modelo estático, afinal o último utiliza o próprio estimador de máxima verossimilhança e não um outro que converge para este.
Isso, no entanto, não implica que a compressão efetiva seja sempre maior no caso estático, afinal neste último é necessário incluir no arquivo comprimido um preâmbulo com as probabilidades de transição.
Espera-se que um modelo markoviano de alcance maior permita comprimir tanto ou mais que um modelo de alcance menor, afinal uma cadeia de Markov de ordem k também é uma cadeia de Markov de ordem n > k.
É exatamente isso que acontece no caso estático. No caso adaptativo, entretanto, a situação é diferente. A compressão aumenta com o alcance até k = 3, mas quando k > 3 a compressão se torna inversamente proporcional ao alcance.
Esta situação aparentemente contraditória se deve ao fato de o modelo adaptativo utilizar uma distribuição a priori independente e uniforme (constantes somadas ao numerador e denominador na Equação 7 das notas de aula). Por conta disso, há uma "demora" na convergência para o estimador de máxima verossimilhança, a qual é proporcional ao alcance do modelo. Como se trata de um texto com comprimento finito, o efeito dessa demora é apreciável.
Em todos os casos, a compressão foi maior com os textos simulados. A razão para isto é o nível de ajuste do modelo à fonte.
O texto original não foi produzido por uma fonte markoviana de ordem k. Conseqüentemente, toda cadeia de Markov de ordem k será apenas uma aproximação da fonte.
No caso do texto simulado, por outro lado, a fonte é uma cadeia de Markov. Assim, há um perfeito ajuste entre modelo e fonte, resultando numa maior taxa de compressão.