Marco Antonio Lemos Perna - M.Sc./IME

Projeto GIS/LAMPADA - FCM/UERJ

Universidade do Estado do Rio de Janeiro

Blv 28 de Setembro 87, fds., 2o andar. Vila Isabel

Rio de Janeiro, RJ, Brasil

e-mail : maperna@uerj.br

São propostas técnicas para a utilização da tecnologia de compactação/compressão em estruturas de arquivos e dados de um GIS. São enfocados arquivos seqüenciais de pontos com geocódigo e coordenadas, para facilitar a compreensão. Esse arquivo sequencial é codificado com tecnologia de compressão de dados (com perda) e em seguida é utilizada tecnologia de compactação de dados (sem perdas). Ao final é gerado um arquivo com essa codificação que pode ser lido pelo GIS que possuir a metodologia de decodificação. Esta tecnologia pode ser utilizada em outras estruturas de arquivos e dados, com algumas alterações.

Alternatives are proposed for the compression technology use in GIS files and data structures. Sequential files with coordinates and geocode are used to improve understanding. This sequential file is coded using lossy data compression techniques followed by an error-free data compression technique. In the final step, a coded file is generated, which can be used by GIS equipped with a decoder. This technology can be used in other data and file structures, with minor modifications.

1. INTRODUÇÃO

O presente trabalho versa sobre a codificação de arquivos seqüênciais, contendo contorno de áreas, com as coordenadas de cada ponto do contorno em latitude e longitude.

Os arquivos originais estão no formato texto, contendo a maior precisão possível, que no caso foi imposta pela fase de aquisição de dados. Segue o seguinte modelo :

código,latitude,longitude

código,latitude,longitude

..........................................

..........................................

onde,

código = código de nível de precisão do ponto.

latitude e longitude em graus decimais.

Exemplo :

5,-23.7854789,43.235468789

4,-24.6234,43.65234657

A metodologia de compressão (codificação) proposta consiste de duas etapas: (i) codificação com perda de precisão, denominada de compressão (BLAHUT, 1990) e (ii) codificação sem perda, denominada de compactação.

2. IMPLEMENTAÇÃO

(i) a primeira etapa consiste na utilização de uma codificação de dados para o código, a latitude e a longitude, de forma a levar em consideração a redução do volume de dados e aumento da velocidade de recuperação, admitindo perda de precisão.

Quanto a velocidade de recuperação, salienta-se que em um arquivo no formato texto que contém valores no campo dos Números Reais (números de ponto flutuante), a recuperação desses valores é lenta devido a dois fatores. O primeiro é justamente o tamanho ocupado pela codificação em ASCII, utilizada no formato texto, que faz com que o programa perca tempo durante a recuperação do arquivo para a memória principal. O segundo é a conversão da codificação em ASCII para o formato numérico binário utilizado pelo programa para efetuar cálculos.

Logo, reduzindo-se o volume de dados e utilizando diretamente o formato numérico binário no arquivo, a velocidade de recuperação de dados aumentará.

A codificação em formato numérico binário pode ser feita levando-se em consideração a precisão ou o volume de dados gerado nessa codificação. Porém, independentemente do formato escolhido para o armazenamento e recuperação em disco, o formato interno ao programa utilizado para armazenamento e cálculo das variáveis deve conter a maior precisão possível. Foi utilizado o formato numérico binário de ponto flutuante de 64 bits (oito bytes) normatizado pelo ANSI/IEEE 754, o tipo double da linguagem C. Os outros formatos utilizados a seguir, para armazenamento em disco, também seguem normas internacionais.

A codificação do código de nível não gerou dúvidas e foi escolhido o tipo unsigned char da Linguagem C, ou seja, um byte (oito bits sem sinal), que pode representar 256 valores inteiros diferentes, suficiente o bastante para os propósitos momentâneos.

No caso da latitude e longitude, que são números de ponto flutuante, foram testados vários formatos númericos binários: short int e long int, que são formatos de números inteiros com sinal e float e double, que são formatos de ponto flutuante com sinal. Em todos esses formatos pode haver perda de informação de acordo com a precisão requerida.

O short int ocupa dois bytes (65536 valores possíveis = 2 elevado a 16 bits). Antes da codificação ser efetuada, por comandos ou funções da linguagem de programação utilizada, o valor da coordenada foi multiplicado por 182.0, para que se preserve a maior precisão possível. Esse valor é utilizado para que a faixa de valores da coordenada possa ser distribuída na faixa de valores do short int.

Faixa de valores de latitude e longitude :

+/- 180 graus.

Faixa de valores do short int :

- 32768 até + 32767

Multiplicando-se o valor máximo (ou o mínimo) 180 graus por 182.0 (cento e oitenta e dois), obtém-se o valor 32760, que é representável pelo short int, o que mostra que podem ser codificadas latitudes e longitudes dessa forma, com precisão de cinco dígitos e aproximadamente vinte segundos de grau.

Pela precisão resultante dessa codificação, esse formato é indicado para coordenadas com precisão geográfica, ou seja, contorno de continentes, rios e contornos políticos de países, com precisão de aproximadamente vinte segundos.

O long int ocupa quatro bytes (2 elevado a 32 bits) e multiplicando-se a coordenada por 10000000.0 (dez milhões) obtém-se uma precisão de dez dígitos e aproximadamente um milésimo de segundo. Do ponto de vista de tipo de dado, é o mais indicado para o armazenamento em disco, de coordenadas em latitude e longitude, visto que são números que variam apenas de -180.0 graus à + 180.0 graus e uma precisão de milésimo de segundo atende a maioria da aplicações, é claro que para cálculos deve-se converter para double para diminuir a propagação de erros.

Faixa de valores do long int:

- 2147483648 até +2147483647

Nesses dois casos de codificação em números inteiros, deve-se dividir pelo mesmo valor multiplicado no início da codificação para decodificar a coordenada para utilização pelo programa.

Também deve-se levar em consideração que a ordem dos bytes que formam os tipos inteiros depende do hardware utilizado. Se, por exemplo, estiver sendo utilizado um micro-computador com processador da linha PC-80x86, os bytes menos significativos são armazenados primeiro, já com o processador Motorola e máquinas RISC (e.g. RISC 6000, SUN) os bytes mais significativos são armazenados primeiro. Essa forma de armazenamento na memória principal é refletida no armazenamento em disco, logo deve-se especificar na documentação do lay-out do arquivo de dados o hardware utilizado.

O double possui uma precisão de quinze dígitos e ocupa 8 bytes ou 64 bits, como mostra a Figura 1. Não necessita de nenhum multiplicador e possui precisão suficiente para a maioria dos cálculos em geodésia. Apesar de ocupar oito bytes, ainda consegue reduzir o volume ocupado pelas coordenadas no formato texto.

O tipo double é dividido em três campos, como mostrado na Figura 1 a seguir.

Fig. 1 - Diagrama do formato double

onde

s = sinal,

e = expoente,

f = mantissa,

msb = more significative bit

(bit mais significativo),

lsb = less significative bit

(bit menos significativo).

o valor numérico v é determinado por

Se (0 < e < 2047)

Então v = (-1)^s * 2^(e-1023) * (1.f)

Se (e = 0) & (f <> 0)

Então v = (-1)^s * 2^(-1022) * (1.f)

Se (e = 0) & (f = 0)

Então v = (-1)^s * 0

Se (e = 2047) & (f = 0)

Então v = (-1)^s * infinito

Se (e = 2047) & (f <> 0)

Então v não possui valor numérico

O float possui uma precisão de sete dígitos e ocupa quatro bytes. Não foi testado devido possuir precisão menor que o long int apesar de ter o mesmo tamanho.

A relação de tamanho dos arquivos codificados com esses formatos é diretamente proporcional ao tamanho unitário de cada tipo de dado como mostra a Tabela 1, deixando a decisão de qual formato utilizar para a etapa posterior.

Resultados da codificação

(ii) a segunda etapa utiliza algoritmos de compactação conhecidos levando em consideração a relação da taxa de compactação com a velocidade de descompactação (a recuperação dos dados é muito mais freqüente do que a sua criação). Foram realizados testes das quatro formas de codificação propostas na etapa anterior.

Foram utilizados os algoritmos de Huffman estático (HUFFMAN, 1951) e o dinâmico (KNUTH, 1985), Código Aritmético ordem 1 (ELIAS, 1963), o PKZIP de Phil Katz, o LZW (WELCH, 1984) e o algoritmo RLE (Run Lenght Enconding) de oito bits. Todos comentados e testados também em (PERNA, 1994).

Do gráfico da relação entre tempo e compactação, na Figura 2, verifica-se que o algoritmo LZW possui uma boa relação entre velocidade e taxa de compactação para os propósitos desse trabalho, perdendo apenas para o PKZIP 2.04 de Phil Katz, que é um programa comercial e não fornece o fonte do programa para compactação.

Fig. 2 - Relação compactação X velocidade

Os resultados finais, como mostrado nas Tabela 2 e 3, e na Figura 3, foram considerados bons com a utilização do formato double sem perda de precisão e com os formatos inteiros com precisão reduzida, o resultado foi considerado ruim. Pelo fato dos arquivos codificados em formato inteiro binário possuirem símbolos (bytes) estatísticamente independentes e com histograma sem grandes concentrações, todos os algoritmos de compactação tiveram um baixo desempenho em relação a taxa de compactação para os formatos inteiros, como mostra a Figura 3. O que indica que nesse caso deve-se utilizar somente a etapa anterior. O long int gerou um arquivo compactado maior que o gerado com o double.

Resultados da Compactação em kbytes

Resultados da Compactação em UNIDADES DE TEMPO

No programa gerenciador (GIS) foi acoplado o algoritmo de descompactação LZW, que efetua a descompactação no momento da recuperação dos dados do arquivo em disco para a memória principal, caso haja memória disponível pode-se carregar o arquivo todo para a memória e descompactar diretamente dela, essa técnica é útil caso se acesse os dados seqüenciais mais de uma vez, já que acessos a disco são mais lentos que acessos a memória principal.

Fig.3- Comparação das taxas de compactação

3. CONCLUSÃO

Para informações de caráter geográfico, com precisão aproximada de vinte segundos, deve-se utilizar somente a primeira etapa com a codificação em short int, com o código de nível indicando a precisão e conseqüentemente o uso do short int.

Caso se necessite de maior precisão o formato indicado é o double com o uso da compactação LZW, que gera um arquivo maior que o caso de caráter geográfico, mas carrega maior precisão. Como o algoritmo LZW é patenteado pela UNISYS, é aconselhável licenciar seu uso, ou a utilização de algum algoritmo sem copyright. O uso de programas comerciais também pode ser feito, o ARJ de Robert K. Jung, fornece o fonte do algoritmo de descompactação para uso em outros programas, ou ainda o PKZIP 2.04 de Phil Katz, que também fornece o fonte de descompactação. Possuir o fonte da compactação não é relevante e essa pode ser uma solução.

Um estudo em cima de arquivos seqüenciais indexados e arquivos de acesso aleatório (imagens raster e arquivos de dados convencionais, como os DBF) deverá ser realizado. Em (PERNA, 1994) é feito um estudo em compactação de imagens raster, porém não foi levado em consideração o acesso aleatório à pixels da imagem compactada.

4. REFERÊNCIAS BIBLIOGRÁFICAS