Alguem me poderia disponibilizar o codigo que faz o seguinte:
Realize um par de programas para compressão/descompressão de documentos de texto em formato txt. O programa que realiza compressão (com ponto de entrada na classe Compress) lê o texto a compactar do standard input e produz no standard output o resultado da compressão, doravante designado de texto compactado. O programa que realiza descompressão (com ponto de entrada na classe Uncompress) lê o texto compactado do standard input e produz no standard output o resultado da descompressão, idêntico ao texto inicialmente submetido ao programa de compressão.
Para a leitura e escrita de ficheiros redireccione o standard input e o standard output do programa para os respectivos ficheiros. Para o efeito considere as seguintes linhas de comando:
c:\> java Compress < input.txt > compressed.txt
c:\> java Uncompress < compressed.txt > output.txt
A primeira promove a execução do programa de compressão (Compress) redireccionando o standard input (símbolo <) para o ficheiro input.txt e o standard output (símbolo >) para o ficheiro compressed.txt, que irá conter o texto compactado.
A segunda promove a execução do programa de descompressão (Uncompress) que realiza a operação inversa, colocando no standard output (redireccionado para o ficheiro output.txt) o texto não compactado, que se pretende igual ao originalmente contido em input.txt.
Algoritmo de compressão:
O algoritmo de compressão opera sobre o texto de entrada (no exemplo, conteúdo de input.txt) aplicando duas transformações em cascata: A primeira é designada de Burrows-Wheeler Transform (BWT); a segunda de Run-Length Encoding (RLE). A descrição de ambas as transformadas (assim como das transformadas inversas) encontra-se em apêndice. A figura seguinte ilustra o processo.
Algoritmo de descompressão:
O algoritmo de descompressão opera sobre o texto compactado (no exemplo, conteúdo de compressed.txt) aplicando as transformações inversas das usadas na compressão. O resultado (no exemplo, conteúdo de output.txt) é o texto original. A figura seguinte ilustra o processo.
A transformação BWT opera sobre blocos de dados (no contexto deste trabalho, sequências de caracteres) e produz blocos da mesma dimensão mas com formato mais adequado à compressão. Após a transformação, a sequência de caracteres de saída contém exactamente os mesmos caracteres da sequência original, diferindo apenas na sua ordem (a sequência de saída é uma rotação da sequência de entrada).
Esta transformação é reversível, ou seja, a ordem original dos caracteres é recuperável a partir da sequência de saída. A sua utilidade na compressão resulta da observação que, se a sequência de caracteres original contiver repetições de subsequências, então a sequência de saída irá conter várias repetições consecutivas dos mesmos caracteres. Nestas condições, a utilização do algoritmo Run-Length Encoding (RLE) produz a informação contida na sequência original mas usando uma codificação mais compacta, resultando na compressão dos dados. Abaixo encontra-se um exemplo da aplicação da transformada:
entrada:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
saida:
TEXYDST.E.IXIXIXXSSMPPS.B…E.S.EUSFXDIIOIIIT
Transformada directa:
A transformada é realizada ordenando todas as rotações da sequência de caracteres de entrada, e tomando como sequência de saída a formada pela última coluna da matriz resultante. Por exemplo, o texto ?^BANANA@? é transformado em ?BNN^AA@A? (o símbolo @ indica fim de bloco, EOB ? End Of Block[1]) através dos seguintes passos: criação da matriz composta por todas as rotações da sequência de entrada; ordenação lexicográfica das linhas da matriz; produção na saída da última coluna da matriz ordenada.
RLE
O algoritmo RLE é eficaz na compressão quando aplicado a sequências com repetições consecutivas do mesmo símbolo (designados de runs). Para o efeito, essas sequências são representadas por um único símbolo, seguido do número de ocorrências, em vez da sequência original. Por exemplo, considere-se a seguinte sequência:
AAAAAAAAAAAABAAAAAAAAAAAABBBAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAA
A representação resultante da aplicação do algoritmo é:
12A1B12A3B24A1B14A
Esta sequência é formada por doze A’s, um B, doze A’s, três B’s, etc. O algoritmo produziu a partir da sequência original (com 67 caracteres) uma representação com apenas 18 caracteres.
O algoritmo da transformação inversa (RLE-1) é imediato. Basta reproduzir, na saída, o carácter o número vezes indicado pela dimensão do run.
