Døtrenes forlovelser i Heimskringla

O modelo de predição gera um novo símbolo para adicionar à cadeia. Independentemente da probabilidade de a predição estar ou não correcta, o sistema de codificação deverá sempre comportar códigos para corrigir a predição caso esta divirja da sequência original. Manter a sequência correcta é fundamental para actualizar os modelos de predição locais.

No trabalho desenvolvido criou-se um sistema de codificação que tira o máximo proveito da capacidade de predição do modelo e também da capacidade de predição aproximada, algo que dentro do nosso conhecimento é inovador. De facto, confiando na capacidade do nosso sistema de predição poder-se-ía pensar que mais tarde aquando da compressão da bitstream fornecida ao codificador aritmético, na descrição das probabilidades dos símbolos da fonte, o intervalo mais provável, logo maior, seria o que corresponde às predições do modelo. Com esta nova filosofia, o modelo até poderia errar boa parte dos símbolos e ainda assim conseguir boa compressão, isto obviamente se esses erros fossem maioritariamente mínimos.

Para sistematizar este conceito de predição aproximada há a necessidade de introduzir a noção de modelo adaptativo para a codificação aritmética. É sabido que a codificação aritmética pode ser realizada com base em modelos estáticos ou dinâmicos. Os modelos estáticos assumem que a sequência a comprimir é homogénea em termos de composição e como tal as probabilidades não apresentam variação significativa considerando diversos segmentos para a sequência total. Por outro lado, os modelos adaptativos procuram aproveitar as diferenças acentuadas de distribuição das probabilidades nos diferentes segmentos. Por exemplo, se determinada porção da sequência apresentar uma predominância GC muito acentuada, pode ser vantajoso fornecer dois modelos mais as localizações onde alternar a sua aplicação na compressão. Mais intensivo seria adaptar constantemente o modelo a cada símbolo adicionado. Esta última situação acarretaria a necessidade de um processamento intensivo para recalcular o modelo em função dos caracteres passados.

Retomando o conceito de predição aproximada e do seu aproveitamento, consideremos que o modelo probabilístico realiza uma determinada predição para um símbolo baseado nas seguintes probabilidades de ocorrência:

A: 34%; C: 30%; T: 20%; G: 16%.

Neste caso, o modelo irá prever a base A como símbolo seguinte. Para o caso de a predição estar errada, e se o modelo dispusesse de uma segunda tentativa então prediria a base C, e assim por diante. É crível que as probabilidades apresentadas pelo modelo sejam minimamente fiáveis e sustentadas pelo que, se num caso hipotético se quisesse codificar o próximo símbolo com base nestas probabilidades, então ter-se-ía de optar por compressão aritmética acompanhada de um modelo dinâmico, pois a cada novo caracter as probabilidades serão distintas. Este caso, porém, implica um ónus acrescido em relação ao modelo dinâmico convencional, que reutiliza os símbolos passados para actualizar o modelo, e como tal não necessita de informação explicitamente fornecida de forma suplementar para esse efeito, ou seja a sobrecarga resultante é funcional e não devida a informação adicional. Note-se que esta informação adicional representa um custo que pode por em causa o desiderato principal que é a compressão. Para obviar esta situação e ainda assim tirar algum partido das segundas escolhas, a estratégia de codificação seguida utiliza os pressupostos descritos a seguir.

Considerando um esquema como o representado na Figura 5.7, e considerando como estado principal o correspondente à predição do modelo, sempre que a predição do modelo resultar acertada então adiciona-se o símbolo zero “0” à bitstream. Caso a predição esteja errada então codificam-se as transições necessárias para corrigir a predição. Supondo que o símbolo correcto fosse o “T”, o símbolo que dava entrada na

bitstream seria o dois “2”, já que são necessárias duas transições até chegar ao 3º

Figura 5.7 – Representação dos acertos ou desacertos predictivos para adicionar à bitstream.

Como se descreveu, os símbolos que constituem a bitstream são símbolos de indicação do aproveitamento das predições do modelo e não correspondem directamente a símbolos. Pode parecer estranho mas, são esses símbolos que constituem o grosso do ficheiro compactado, e em rigor os símbolos reais só serão recuperados na fase de descodificação.

Aquando da descodificação, e justificado pelo facto da mecânica ser idêntica na descompressão e os modelos usados estarem igualmente disponíveis, será possível redescobrir a ordenação dos símbolos usada para uma determinada predição. Em suma e por paradoxal que possa parecer, na realidade o ficheiro codificado não contém a sequência correcta mas apenas indicações de como atingir essa sequência correcta. Numa antevisão do que poderá ser o conteúdo do ficheiro comprimido resultante da sub-sequência extra-dicionário, no sentido de obter uma compressão substantiva, estima-se que poderá conter uma distribuição percentual dos símbolos correctivos (0, 1, 2 e 3) com a seguinte conformação média: 0-35%; 1-30%; 2-25% e 3-10%. Ou seja, o modelo predictivo não só terá de acertar cerca de um terço das predições como terá de errar apenas por uma transição praticamente a mesma percentagem de predições. Algum optimismo advém do facto de serem apenas quatro símbolos que constituem o alfabeto genómico e que numa predição ao acaso há 25% de probabilidades de acertar, e outras tantas de acertar com uma transição. Assim, o que o modelo necessita fazer é desequilibrar estas probabilidades para um pouco mais de acertos. Nas sequências mais repetitivas isso é, obviamente, mais fácil de atingir.

G T C A 1 2 3 Predição do modelo

Adicionalmente é possível efectuar para estes valores uma simulação aproximada da compressão obtida por codificação aritmética recorrendo à fórmula da Equação (5.3), a qual nos permite saber o número de bits necessários para codificar um símbolo sabendo a sua probabilidade de ocorrência na sequência.

símbolos os todos de ade probabilid símbolo do ade probabilid p= (5.3) símbolo bits p) / log( = −

Na Tabela 5.5 estão reunidos os cálculos para as taxas de compressão a esperar perante a distribuição percentual dos palpites produzidos pelo modelo predictivo. Na estratégia seguida não é forçoso que os acertos sejam a maioria, no caso hipotético de se falharem 90% das predições também seria positivo pois a distribuição percentual resultaria semelhante e a codificação aritmética é baseada no desequilíbrio das probabilidades. O facto é que é tão difícil errar sempre da mesma forma como acertar. Acresce que todo o trabalho foi realizado para dotar o modelo que qualidade predictiva para acertar, assim sendo, o desequilíbrio que se pretende atingir é por via do aumento dos acertos ou, em alternativa, dos falhos com desvio mínimo. Sempre que esses dois grupos somem mais que 50% ter-se-á obtido compressão, no exemplo apresentado esses dois grupos somam 65%.

Símbolo Percentagem Bits/símbolo

0 – Acerto 35% –log(0,35)=1,515 bits

1 – Desvio 1 30% –log(0,3)=1,737 bits

2 – Desvio 2 25% –log(0,25)=2 bits

3 – Desvio 3 10% –log(0,1)=3,322 bits

Tabela 5.5 – Previsão das taxas de compressão obtidas por codificação aritmética.

A previsão total corresponderia a:

Sabe-se que a codificação aritmética convencional permite, para a informação genómica natural, taxas médias de compressão entre os 1,90 e 1,98 bits por base de média. O valor alcançado pela incorporação do modelo probabilístico de linguagem é significativamente mais baixo. O factor diferenciador decisivo foi o aproveitamento da capacidade probabilística do modelo e também a capacidade de aproximação.

A taxa de compressão média de 1,88 não constitui, por si só, um desempenho suficiente para ombrear com os melhores algoritmos de compressão de ADN mas, importa referir, em defesa do trabalho desenvolvido, que a porção mais repetitiva já tinha sido excisada da sequência antes desta ser submetida ao modelo probabilístico. No final a compressão é melhorada pela contribuição do dicionário.