EP6 - Formato da saída da BW transform

EP6 - Formato da saída da BW transform

por Bruna Thalenberg -
Número de respostas: 6

A saída da transformada Burrows Wheeler precisa seguir algum formato específico ou basta ter coerência interna/compatibilidade com a nossa transformada inversa?

Por exemplo:

3
ARD!RCAAAABB

 

3ARD!RCAAAABB

 

3 ARD!RCAAAABB


seriam todos válidos? No vídeo de COS226 ele usa a segunda, mas na página aparece a primeira. (Estou tentando resolver aqui como manter as quebras de linha dos textos originais, se alguém tiver alguma dica pra me iluminar... Estou com problemas quando o índice de first tem mais de um dígito).

Em resposta à Bruna Thalenberg

Re: EP6 - Formato da saída da BW transform

por José Coelho de Pina -

Oi Bruna,

Legal!

A saída da transformada Burrows Wheeler precisa seguir algum formato específico

Sim. Vocês   devem seguir a especificação do enunciado:

[...] Notice how there are 4 consecutive As and 2 consecutive Bs—these clusters make the message easier to compress.

% java-algs4 BurrowsWheeler - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump  16
00 00 00 03 41 52 44 21 52 43 41 41 41 41 42 42
128 bits

Also, note that the integer 3 is represented using 4 bytes (00 00 00 03). The character 'A' is represented by hex 41, the character 'R' by 52, and so forth.

Em resposta à José Coelho de Pina

Re: EP6 - Formato da saída da BW transform

por José Coelho de Pina -

Oi,
Continuando....

Estou tentando resolver aqui como manter as quebras de linha dos textos originais,  

encode(), transform(), decode(),... codificam e decodificam fluxos de bits (stream of bits).
Não importa a semântica dos bits, se é que há alguma.
Não importa se os bytes represetam um caractere associado a um símbolo gráfico: 'A','ç','#',...
ou efeito não gráfico: '\n' (=LF), '\t' (=TAB), 0x7f (=DEL),...
.

Binary input and binary output. To enable your programs to work with binary data, you will use BinaryStdIn and BinaryStdOut, which are described in Algorithms, 4th edition. To display the binary output when debugging, you can use HexDump, which takes a command-line argument n, reads bytes from standard input and writes them to standard output in hexadecimal, n per line.

Em resposta à José Coelho de Pina

Re: EP6 - Formato da saída da BW transform

por Bruna Thalenberg -

mas hmmm..

se abra.txt tem um \n no final, isso não deveria se manter na saída?

java-algs4 BurrowsWheeler - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump 16
00 00 00 03 41 52 44 21 52 43 41 41 41 41 42 42
0a
136 bits

A minha opção foi fazer a leitura (e as transformadas) linha a linha.

A outra opção seria processar a quebra de linha dentro da transformada, mas isso altera muito os resultados (já que altera a ordenação dos sufixos):

java-algs4 BurrowsWheeler - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump 16

00 00 00 04 21 41 52 44 0a 52 43 41 41 41 41 42
42
136 bits




Em resposta à Bruna Thalenberg

Re: EP6 - Formato da saída da BW transform

por José Coelho de Pina -

Ois,


se abra.txt tem um \n no final, isso não deveria se manter na saída?

Sim.
Todos os bits da entrada devem ser codificados.

meu_prompt> more abra.txt 
ABRACADABRA!
meu_prompt> file abra.txt 
abra.txt: ASCII text, with no line terminators
meu_prompt> wc abra.txt 
 0  1 12 abra.txt
meu_prompt> java HexDump < abra.txt 
41 42 52 41 43 41 44 41 42 52 41 21
96 bits

meu_prompt> echo -n "Como é bom estudar MAC0323!" > algo.txt
meu_prompt> more algo.txt 
Como é bom estudar MAC0323!
meu_prompt> file algo.txt 
algo.txt: UTF-8 Unicode text, with no line terminators
meu_prompt> wc algo.txt 
 0  5 28 algo.txt
meu_prompt> java HexDump < algo.txt 
43 6f 6d 6f 20 c3 a9 20 62 6f 6d 20 65 73 74 75
64 61 72 20 4d 41 43 30 33 32 33 21
224 bits

meu_prompt> echo "Como é bom estudar MAC0323!" > ritmos.txt
meu_prompt> more ritmos.txt 
Como é bom estudar MAC0323!
meu_prompt> file ritmos.txt 
ritmos.txt: UTF-8 Unicode text
meu_prompt> wc ritmos.txt 
 1  5 29 ritmos.txt
meu_prompt> java HexDump < ritmos.txt 
43 6f 6d 6f 20 c3 a9 20 62 6f 6d 20 65 73 74 75
64 61 72 20 4d 41 43 30 33 32 33 21 0a
232 bits