Um bom fim de semestre pro senhor tb ^^
Eu acho q o binário a ser decifrado tem alguns errinhos, mas ainda estou refazendo milhões de vezes antes de afirmar alguma coisa.
Aparentemente tem uns 3 bits errados =P
Nada q comprometa o entendimento da mensagem = P
Nada q comprometa o entendimento da mensagem = P
Já mataram. Tinha sim uns bits errados. A primeira a descobrir a mensagem foi a Nicoli, às 21:25 de ontem.
abraços,
--
carlinhos
abraços,
--
carlinhos
Respondi um otimo semestre pro senhor tb as 21:14 , mas td bem =P
Eu não consegui encontrar nenhum caso que dê problema na codificação do final do texto ( isso na forma q eu estou implementando). Mesmo se tais erros não ocorrerem, é necessário colocar os caracteres especiais?
Achei algo realmente util na net!!!
http://www.lysator.liu.se/c/ten-commandments.html
Espero q isso ajude alguem = P
http://www.lysator.liu.se/c/ten-commandments.html
Espero q isso ajude alguem = P
Caso canônico:
Seja o arquivo composto por um byte tal que esse byte seja nulo.
00000000
0|00|000|00 /* pedaço de um prefixo anterior */
Seja o arquivo composto por um byte tal que esse byte seja nulo.
00000000
0|00|000|00 /* pedaço de um prefixo anterior */
Sobre o exemplo de enunciado do EP:
Eu não entendi porque o resultado da compressão do primeiro pedaço é apenas o "0". Ele não é resultado da concatenação do pedaço de índice 0 (vazio) com o caractere '0'? O resultado não seria "00"?
Eu não entendi porque o resultado da compressão do primeiro pedaço é apenas o "0". Ele não é resultado da concatenação do pedaço de índice 0 (vazio) com o caractere '0'? O resultado não seria "00"?
Posso estar falando besteira, mas acho que é porque deve se usar o número de bits necessários para se escrever n - 1 (nesse caso o valor é 0), então 0 tem que ser escrito em 0 bits
correto.
--
carlinhos
--
carlinhos
A entrada será um arquivo já convertido para binário ou o EP deverá fazê-lo? (no caso da compactação)
Edit: Há alguma restrição de tempo ou de memória?
Edit: Há alguma restrição de tempo ou de memória?
o programa recebe um texto em binario e devolve um texto em binario!
Não deve receber um arquivo qualquer e lê-lo bit a bit? Isso faz mais sentido...
é isso mesmo. Deve funcionar como o gzip: você codifica o arquivo texto lendo bit a bit.
abraços,
--
carlinhos
abraços,
--
carlinhos
Droga!!! Maldito curso de alfabetização do instituto universal brasileiro!
Agora eu to vendo algum sentido no ep (ou naum =P).
Ah!! Perdi!!
Agora eu to vendo algum sentido no ep (ou naum =P).
Ah!! Perdi!!
Não entendi exatamente como tratar problema do último pedaço, alguém poderia me explicar?
Outro problema, se estamos lendo um arquivo de texto bit a bit, pode acontecer da compressão resultar em um número de bits não múltiplo de 8, e portanto um "grupo" de bits não teria um caractere correspondente. Como devemos tratar isso?
Outro problema, se estamos lendo um arquivo de texto bit a bit, pode acontecer da compressão resultar em um número de bits não múltiplo de 8, e portanto um "grupo" de bits não teria um caractere correspondente. Como devemos tratar isso?
Você quis dizer no final do texto, é isso?
Os caracteres do texto vão ser enxergados como uma sequência de bits. Por exemplo,
ABCD (acho que o ASCII do 'A' é 65):
01000001 01000010 01000011 01000100
a codificação pode combinar uns bits do 'A' com uns bits do 'B`, e assim por diante. O que pode acontecer é que quando o texto acaba a gente ainda não tinha completado um byte, e poderia dar confusão: Como o programa vai saber que terminou ali? Por isso a sugestão de incluir uma marca de fim de texto para seu programa saber que terminou a codificação.
(não sei se respondi sua pergunta)
--
carlinhos
Os caracteres do texto vão ser enxergados como uma sequência de bits. Por exemplo,
ABCD (acho que o ASCII do 'A' é 65):
01000001 01000010 01000011 01000100
a codificação pode combinar uns bits do 'A' com uns bits do 'B`, e assim por diante. O que pode acontecer é que quando o texto acaba a gente ainda não tinha completado um byte, e poderia dar confusão: Como o programa vai saber que terminou ali? Por isso a sugestão de incluir uma marca de fim de texto para seu programa saber que terminou a codificação.
(não sei se respondi sua pergunta)
--
carlinhos
O que você quer dizer com "marca de fim de texto"? Algum caractere? Uma sequência de bits que complete um byte?
Acho que eu não expliquei muito bem minha dúvida. Pelo que eu entendi, a saída deve ser um arquivo texto normal, impresso caractere a caractere, certo? Assim, a impressão da saída é byte a byte, apesar da leitura dos dados ser bit a bit.
Mas se no final do texto eu não conseguir completar um byte, qual caractere eu deveria imprimir? Uma marca de fim de texto? Mas se essa marca de fim de texto for um caractere, eu continuaria tendo um byte incompleto e se fosse uma sequência de bits que complete um byte, eu formaria um caractere válido, como qualquer outro.
Acho que eu não expliquei muito bem minha dúvida. Pelo que eu entendi, a saída deve ser um arquivo texto normal, impresso caractere a caractere, certo? Assim, a impressão da saída é byte a byte, apesar da leitura dos dados ser bit a bit.
Mas se no final do texto eu não conseguir completar um byte, qual caractere eu deveria imprimir? Uma marca de fim de texto? Mas se essa marca de fim de texto for um caractere, eu continuaria tendo um byte incompleto e se fosse uma sequência de bits que complete um byte, eu formaria um caractere válido, como qualquer outro.
Acho que seu problema é o mesmo que o meu.
Vou exemplificar:
Vou 'compactar' um arquivo de texto que contenha o caractere 'a'.
a = 01100001
separando: 0|1|10|00|01
Pelo algoritmo:
codificação final: 0011000100011
dividi-la-ei em bytes: 00110001|00011
Como completá-lo? Eu tentei fazer umas gambiarras, mas nenhuma funcionou.
Não entendi o porquê de jogar caracteres 'não interpretados', não sei provar que, caso eu os adicione, não haverá problemas no processo de compactar e descompactar.
Vou exemplificar:
Vou 'compactar' um arquivo de texto que contenha o caractere 'a'.
a = 01100001
separando: 0|1|10|00|01
Pelo algoritmo:
| 0 |
1 |
2 |
3 |
4 |
5 |
| (vazio) |
0 |
1 | 10 | 00 |
01 |
| 0 0 |
0 1 |
2 0 |
1 0 |
1 1 |
codificação final: 0011000100011
dividi-la-ei em bytes: 00110001|00011
Como completá-lo? Eu tentei fazer umas gambiarras, mas nenhuma funcionou.
Não entendi o porquê de jogar caracteres 'não interpretados', não sei provar que, caso eu os adicione, não haverá problemas no processo de compactar e descompactar.
No enunciado do EP diz prá incluir uma marca de fim de texto: um caractere que não ocorre no texto para marcar que acabou. E diz também que quando você está decodificando e encontra a marca de fim de texto, é porque acabou, mesmo que sigam alguns bits depois... Isso não resolve a pergunta de vocês?
--
carlinhos
--
carlinhos
Não resolve... A marca de fim de texto resolve a questão do final do texto ser um índice de algum pedaço anterior, não o nosso problema.
O problema o qual eu me refiro é outro: pode acontecer de faltar bits para poder imprimir um caractere no final do texto. No exemplo do William:
00110001|00011
O 00011 não equivale a nenhum caractere, então, como imprimiríamos na saída?
Se acrescentar um marca de fim de texto, digamos o 00000000, teríamos:
00011000|00000
E novamente aparecem bits sobrando que não teriam caractere que os representasse.
Isso tudo acontesse porque a leitura é bit a bit mas a saída é caractere a caractere... Ainda não achei uma solução razoável...
O problema o qual eu me refiro é outro: pode acontecer de faltar bits para poder imprimir um caractere no final do texto. No exemplo do William:
00110001|00011
O 00011 não equivale a nenhum caractere, então, como imprimiríamos na saída?
Se acrescentar um marca de fim de texto, digamos o 00000000, teríamos:
00011000|00000
E novamente aparecem bits sobrando que não teriam caractere que os representasse.
Isso tudo acontesse porque a leitura é bit a bit mas a saída é caractere a caractere... Ainda não achei uma solução razoável...
tente completar os bits, não sei se resolve pois não testei ainda:
00011000|00000 -> 00011000|00000000
e na hora de descompactar vc dá um jeitinho
00011000|00000 -> 00011000|00000000
e na hora de descompactar vc dá um jeitinho
esquece o q eu escrevi!
1) durante a codificação, codifique o EOF junto com o seu texto
2) complete o byte final incompleto como vc quizer
3) na hora de decodificar vc deve parar assim q decodificar o EOF q vc colocou e ignorar o resto, q foi só pra completar o byte
espero q tenha ficado claro (e correto...)
1) durante a codificação, codifique o EOF junto com o seu texto
2) complete o byte final incompleto como vc quizer
3) na hora de decodificar vc deve parar assim q decodificar o EOF q vc colocou e ignorar o resto, q foi só pra completar o byte
espero q tenha ficado claro (e correto...)
Eu pensei uma maneira diferente. Já que provavelmente vão sobrar até 7 bits(pq se for 8 já é uma nova codificação), reservei no arquivo compactado um primeiro inteiro (já que não sei escrever somente 3 bits) que diz quantos bits finais são realmente do arquivo original. Ainda não está pronto, vou testar assim que possível.
Até!
Até!
Marcos, acho que isso não vai funcionar. Você deve pegar a sequência de bits que é o resultado de sua codificação, e então agrupá-los de 8 em 8, escrevendo o caracter correspondente no arquivo de saída. Se sobrarem bits no final (ou, no caso faltarem para completar um byte), você não conseguirá escrever esse último pedaço no arquivo de saída.
Uma pergunta sobre a sequência ABCD dada pelo prof. Dividindo esta sequência de acordo com a regra e determinando seus respectivos pares
01000001 01000010 01000011 01000100
1 2 3 4 5 6 7 8 9 10 11 12?
0|1|00|000|10|100|001|0010|0001|101|00010|0
(0 0) (0 1) (1 0) (3 0) (2 0) (5 0) (3 1) (7 0) (4 1) (5 1) (9 0) (???)
O que fazer com último zero? Como poderia inseri-la na árvore?
Abcs
Você pode colocar o caractere de controle e, se necessário, preencher com qualquer porcaria.
Como o programa lerá somente até o caractere de controle, a porcaria que vier depois será sumariamente ignorada.
Como o programa lerá somente até o caractere de controle, a porcaria que vier depois será sumariamente ignorada.
Exatamente como o William respondeu, Fernando. Adicione um caracter de controle quantas vezes forem necessárias, até que você tenha um pedaço que não é prefixo de nenhum outro. Faça a compressão e, se na hora de escrever o último byte não tiver 8 bits, complete com qualquer coisa apenas para ter um byte para escrever.
@ Alguém poderia disponibilizar arquivos para teste? Entrada - codificado - decodificado?
@ E posso assumir que a linah de comando vai estra correta ou preciso pensar no usuário que vai digitar arquivo.x arquivo.y -w -k ?
@ E posso assumir que a linah de comando vai estra correta ou preciso pensar no usuário que vai digitar arquivo.x arquivo.y -w -k ?
gostaria de saber um jeito razoavel p/ ler os caracteres bit a bit no C... eu sou tão burrinho 
char c;
c = getchar();
A cada getchar(), ele pega o próximo caractere da entrada.
c = getchar();
A cada getchar(), ele pega o próximo caractere da entrada.
eu escrevi BIT A BIT não BYTE A BYTE!
Almir, um byte é um número, para tê-lo em bits é suficiente representá-lo em base 2 - acrescentando a quantia correta de zeros à esquerda, não? =P
Procure sobre os operadores << , >> , & , | , ^ ,
com eles é possível "mexer" nos bits de um char (1 byte).
Não sei se existe outra maneira mais esperta.
com eles é possível "mexer" nos bits de um char (1 byte).
Não sei se existe outra maneira mais esperta.
O jeito de se mexer com bits é esse mesmo, Ricardo!
Faltou o operador ~ (NOT).
Estudem e testem bastante esses operadores, podem parecer complicados no começo mas com o tempo vocês pegam o jeito.
Faltou o operador ~ (NOT).
Estudem e testem bastante esses operadores, podem parecer complicados no começo mas com o tempo vocês pegam o jeito.
Se você tem um byte(conjunto de 8 bits), faça o que você aprendeu em Algebool usando os operadores que o colega acima citou.
Até!
Até!
No enunciado está escrito:
"A seqüência de pares é então codificada em um arquivo binário."
Isso quer dizer que o arquivo comprimido deve ser um texto com 0's e 1's que consegui com o algoritmo (os pares em binário)?
Ou um arquivo com os caracteres respectivos a esses binários 8 a 8?
"A seqüência de pares é então codificada em um arquivo binário."
Isso quer dizer que o arquivo comprimido deve ser um texto com 0's e 1's que consegui com o algoritmo (os pares em binário)?
Ou um arquivo com os caracteres respectivos a esses binários 8 a 8?
Ricardo, a saída deve ser um arquivo com os caracteres obtidos ao agrupar os bits da codificação de 8 em 8.
Na prática, ao abrir seu arquivo codificado, ele estará completamente ilegível.
Na prática, ao abrir seu arquivo codificado, ele estará completamente ilegível.
Olá, nunca consegui fazer qualquer ep que fizesse manipulações bit a bit funcionar (para mim, este é o terceiro desse tipo...), e tenho várias dúvidas em relação a isso, mas as principais são:
- devo usar algo além de fputc e fgetc para fazer a leitura e as gravações no arquivo?
-se o número de bits do arquivo não for múltiplo de oito, o que o fgetc devolve quando faz a última leitura antes do EOF? Como devo fazer o tratamento desse último conjunto de bits?
-como não existe função que leia (ou grave) apenas 1 bit de (em) um arquivo, como a estrutura "campo de bit" do C (como a que está abaixo) poderia ser inicializada com um bit do arquivo(principalmente no caso da última leitura válida do fgetc)?
struct {
unsigned int campo : 1;
} bit;
bit.campo = ?
Obrigado.
- devo usar algo além de fputc e fgetc para fazer a leitura e as gravações no arquivo?
-se o número de bits do arquivo não for múltiplo de oito, o que o fgetc devolve quando faz a última leitura antes do EOF? Como devo fazer o tratamento desse último conjunto de bits?
-como não existe função que leia (ou grave) apenas 1 bit de (em) um arquivo, como a estrutura "campo de bit" do C (como a que está abaixo) poderia ser inicializada com um bit do arquivo(principalmente no caso da última leitura válida do fgetc)?
struct {
unsigned int campo : 1;
} bit;
bit.campo = ?
Obrigado.
- devo usar algo além de fputc e fgetc para fazer a leitura e as gravações no arquivo?
Creio que apenas com essas duas dê para fazer toda a leitura e escrita necessárias.
-se o número de bits do arquivo não for múltiplo de oito, o que o fgetc devolve quando faz a última leitura antes do EOF? Como devo fazer o tratamento desse último conjunto de bits?
Como dito, você fará a leitura e escrita com fgetc e fputc, que lêem e escrevem caracteres (bytes). Portanto, sempre no arquivo o número de bits será múltiplo de 8.
-como não existe função que leia (ou grave) apenas 1 bit de (em) um arquivo, como a estrutura "campo de bit" do C (como a que está abaixo) poderia ser inicializada com um bit do arquivo(principalmente no caso da última leitura válida do fgetc)?
Pedro, como você mesmo disse, não existe uma maneira de ler apenas um bit de um arquivo (ou escrevê-lo individualmente). Na hora da leitura, você tem que ler um byte, ai manipular seus 8 bits individualmente usando os operados bit-a-bit mostrados pelo Ricardo Oda neste mesmo tópico, e então escrever no arquivo novamente os 8 bits resultantes juntos, formando um byte.
Por exemplo, digamos que você leu um byte fazendo c = fgetc(arquivo). Aí, por exemplo, para saber qual o bit mais a esquerda desse byte, você faria algo como:
c & 128
Por que isso? Primeiramente, lembramos que 128 = 10000000 (chamamos esse valor de máscara). Ao fazer um &, todos os 7 bits mais a direita serão zerados. O bit totalmente a esquerda valerá 1 caso, em c, ele já valesse 1, e 0 caso contrário. Dessa forma, você descobriu o valor do bit mais a esquerda de c. Aí você vai deslocando o bit 1 da máscara para a direita, e descobrindo os outros bits.
Assim, você pode ir atribuindo os valores descobertos (1 ou 0) para os "bit fields" de uma determinada estrutura. Confesso, porém, que nunca usei esses chamados bit fields, e creio ser possível fazer o EP sem usá-los.
Entendeu a idéia?
Creio que apenas com essas duas dê para fazer toda a leitura e escrita necessárias.
-se o número de bits do arquivo não for múltiplo de oito, o que o fgetc devolve quando faz a última leitura antes do EOF? Como devo fazer o tratamento desse último conjunto de bits?
Como dito, você fará a leitura e escrita com fgetc e fputc, que lêem e escrevem caracteres (bytes). Portanto, sempre no arquivo o número de bits será múltiplo de 8.
-como não existe função que leia (ou grave) apenas 1 bit de (em) um arquivo, como a estrutura "campo de bit" do C (como a que está abaixo) poderia ser inicializada com um bit do arquivo(principalmente no caso da última leitura válida do fgetc)?
Pedro, como você mesmo disse, não existe uma maneira de ler apenas um bit de um arquivo (ou escrevê-lo individualmente). Na hora da leitura, você tem que ler um byte, ai manipular seus 8 bits individualmente usando os operados bit-a-bit mostrados pelo Ricardo Oda neste mesmo tópico, e então escrever no arquivo novamente os 8 bits resultantes juntos, formando um byte.
Por exemplo, digamos que você leu um byte fazendo c = fgetc(arquivo). Aí, por exemplo, para saber qual o bit mais a esquerda desse byte, você faria algo como:
c & 128
Por que isso? Primeiramente, lembramos que 128 = 10000000 (chamamos esse valor de máscara). Ao fazer um &, todos os 7 bits mais a direita serão zerados. O bit totalmente a esquerda valerá 1 caso, em c, ele já valesse 1, e 0 caso contrário. Dessa forma, você descobriu o valor do bit mais a esquerda de c. Aí você vai deslocando o bit 1 da máscara para a direita, e descobrindo os outros bits.
Assim, você pode ir atribuindo os valores descobertos (1 ou 0) para os "bit fields" de uma determinada estrutura. Confesso, porém, que nunca usei esses chamados bit fields, e creio ser possível fazer o EP sem usá-los.
Entendeu a idéia?
Acho que sim. Obrigado, Thiago.
Na hora de descompactar o arquivo, como é que podemos inserir um novo elemento na árvore trie se sabemos apenas o índice do pai e o bit do elemento? Isto é, eu não sei a partir da raiz se vou encontrar o pai dele à direita ou a esquerda, pois eu não sei a sequência de bits do pai.
Tem como disponibilizar testes de compressão e descompressão???
Também tenho dúvidas quanto a descompressão. Na verdade não entendi como, a partir do texto comprimido, chegar novamente na Trie e descomprimir o texto. Alguém pode ajudar?
Valeu!
Valeu!
Não sei se isso ajuda, mas...
Quando você comprime, o texto fica com um padrão...
O padrão de compressão é feito justamente quando você monta o arquivo final (dê uma olhada na tabela presente no enunciado no trecho que contém o 1,2,3,3,4,4,4...)
Vou 'compactar' o caractere 'a'.
código do a em ASCII: 01100001
Depois da 'compactação'.
0011000100011
0) |0
1) 0|1
2) 10|0
3) 01|0
4) 001|1
A localização (em binário) do prefixo é dada em vermelho. Em preto temos o termo total.
Ex: montando o termo 3)
O prefixo dele está na posição '01' em binário, ou seja, na posição 1) em decimal. O prefixo do 1) está na posição 0). O prefixo do 0) não existe (ele é a raiz da trie).
010 (esse é o termo da posição 3)).
Quando você comprime, o texto fica com um padrão...
O padrão de compressão é feito justamente quando você monta o arquivo final (dê uma olhada na tabela presente no enunciado no trecho que contém o 1,2,3,3,4,4,4...)
Vou 'compactar' o caractere 'a'.
código do a em ASCII: 01100001
Depois da 'compactação'.
0011000100011
0) |0
1) 0|1
2) 10|0
3) 01|0
4) 001|1
A localização (em binário) do prefixo é dada em vermelho. Em preto temos o termo total.
Ex: montando o termo 3)
O prefixo dele está na posição '01' em binário, ou seja, na posição 1) em decimal. O prefixo do 1) está na posição 0). O prefixo do 0) não existe (ele é a raiz da trie).
010 (esse é o termo da posição 3)).
Douglas, é como o William falou: ao receber o texto comprimido, você vai quebrá-lo em pedaços, e você sabe exatamente o tamanho de cada um desses pedaços. Isso vem do fato de você saber exatamente quantos bits foram usados pra comprimir cada par definido no texto inicial. Ao obter um pedaço, você sabe que todos os bits menos o último representam o índice do prefixo. Você então procura esse índice na trie, e coloca um novo nó, com o índice do pedaço atual, sendo a esquerda ou a direita dependendo do último bit.
William, só um detalhe quanto ao seu exemplo. Eu creio que, ao numerar os pedaços do texto comprimido, você deva começar a numeração por 1 e não 0. Dessa forma, o termo 3) do seu exemplo seria na verdade 4), e seria a concatenação do termo 1), que no caso seria apenas 0, com o bit 0. Portanto, esse termo 4) ficaria 00 e não 010.
Apesar de não ter implementado o EP, acho que é isso. Você confirma?
Nesse caso, vale lembrar que o termo 1), apesar de não trazer explicitamente o seu prefixo, tem obviamente como prefixo o termo 0), que é a cadeia vazia.
William, só um detalhe quanto ao seu exemplo. Eu creio que, ao numerar os pedaços do texto comprimido, você deva começar a numeração por 1 e não 0. Dessa forma, o termo 3) do seu exemplo seria na verdade 4), e seria a concatenação do termo 1), que no caso seria apenas 0, com o bit 0. Portanto, esse termo 4) ficaria 00 e não 010.
Apesar de não ter implementado o EP, acho que é isso. Você confirma?
Nesse caso, vale lembrar que o termo 1), apesar de não trazer explicitamente o seu prefixo, tem obviamente como prefixo o termo 0), que é a cadeia vazia.
Quando vamos descompactar o arquivo, é mesmo uma boa idéia remontar a trie?
Pois temos um par contituido por um índice e um bit, logo, para saber o pedaco nós teríamos que fazer uma busca na trie que estamos montando procurando o nó que tivesse o índice desse par para então inserir o novo nó na arvore, mas o único jeito que eu vejo de encontrar o nó com esse índice é percorrendo todos os nós já inseridos na trie... Isso não seria muito ineficiente?
Além disso, para imprimir o texto armazenado na trie, teríamos que procurar os nós com cada um dos índices para podermos imprimir os pedacos na ordem correta.
Talvez se a gente simplesmente armazenasse esses pedacos em um vetor, por exemplo, não seria melhor? Nesse caso conseguiríamos acessar o pedaco correspondente a determinado índice em tempo constante, além de conseguir imprimir esses pedacos na ordem certa muito mais facilmente.
Pois temos um par contituido por um índice e um bit, logo, para saber o pedaco nós teríamos que fazer uma busca na trie que estamos montando procurando o nó que tivesse o índice desse par para então inserir o novo nó na arvore, mas o único jeito que eu vejo de encontrar o nó com esse índice é percorrendo todos os nós já inseridos na trie... Isso não seria muito ineficiente?
Além disso, para imprimir o texto armazenado na trie, teríamos que procurar os nós com cada um dos índices para podermos imprimir os pedacos na ordem correta.
Talvez se a gente simplesmente armazenasse esses pedacos em um vetor, por exemplo, não seria melhor? Nesse caso conseguiríamos acessar o pedaco correspondente a determinado índice em tempo constante, além de conseguir imprimir esses pedacos na ordem certa muito mais facilmente.
Também estou com problemas para reconstruir a trie.... Dado um par (índice do prefixo; último bit do pedaço), como fazer para (a partir da raiz, se for possível, pois acho que isso facilitaria a descompressão) achar qual caminho deve ser seguido para chegar até o nó de chave "índice do prefixo"? Grato.
Pedro, você precisa primeiramente encontrar esse nó. Como já discutido, isso pode ser ineficiente se você tiver que procurar dentre todos os nós da trie. Mas, você também pode pensar numa maneira mais eficiente de buscar esse nó (possivelmente usando uma estrutura auxiliar).
A partir dele, você vai andando pra cima na trie até chegar à raiz. Chegando lá, basta "lembrar" o caminho que fez e refazê-lo, agora de cima pra baixo, concatenando os 0's e 1's dependendo de para qual lado você andou.
A partir dele, você vai andando pra cima na trie até chegar à raiz. Chegando lá, basta "lembrar" o caminho que fez e refazê-lo, agora de cima pra baixo, concatenando os 0's e 1's dependendo de para qual lado você andou.
Deve ser implementada obrigatoriamente uma maneira eficiente de se achar esse nó?
Bom Tiago, o enunciado não específica isso explicitamente, porém questões de eficiência sempre devem ser levadas em conta.
De toda forma, claro que isso, ainda que afetasse sua nota (ainda não pensei nem discuti com o outro monitor sobre critérios de correção), não seria de forma muito sensível, já que o foco principal do EP não são questões de eficiência.
Porém, vale ressaltar que é importante que sejam feitos testes para arquivos grandes, e que, mesmo que não seja implementada uma maneira eficiente de se achar os nós na descompressão, essa etapa não torne-se inviável de ser realizada por ser extremamente lenta (para arquivos grandes).
De toda forma, claro que isso, ainda que afetasse sua nota (ainda não pensei nem discuti com o outro monitor sobre critérios de correção), não seria de forma muito sensível, já que o foco principal do EP não são questões de eficiência.
Porém, vale ressaltar que é importante que sejam feitos testes para arquivos grandes, e que, mesmo que não seja implementada uma maneira eficiente de se achar os nós na descompressão, essa etapa não torne-se inviável de ser realizada por ser extremamente lenta (para arquivos grandes).
Pode ser meio noob mas vamo lá...
Sobre o problema de o último trecho ser um prefixo já existente: o enunciado do ep diz para "adicionar algumas cópias de um símbolo especial que não aparece no texto (por exemplo o símbolo fim de arquivo)".
O símbolo fim de arquivo que o enunciado faz referência é o EOF? (imagino que não... pois EOF é uma macro... certo?)
Refere-se então ao caracter ETX (0000 0011) da tabela ASC?
Em algum momento será escrito ETX (0000 0011) no arquivo .cod, isso não é problema na hora de decodificar (digo parar de ler no meio...)? ou então ETX não significa nada e o que vale mesmo é o EOF (indicado pelo SO)?
Obrigado.
Sobre o problema de o último trecho ser um prefixo já existente: o enunciado do ep diz para "adicionar algumas cópias de um símbolo especial que não aparece no texto (por exemplo o símbolo fim de arquivo)".
O símbolo fim de arquivo que o enunciado faz referência é o EOF? (imagino que não... pois EOF é uma macro... certo?)
Refere-se então ao caracter ETX (0000 0011) da tabela ASC?
Em algum momento será escrito ETX (0000 0011) no arquivo .cod, isso não é problema na hora de decodificar (digo parar de ler no meio...)? ou então ETX não significa nada e o que vale mesmo é o EOF (indicado pelo SO)?
Obrigado.
Olá André,
Creio não haver problemas em usar o símbolo de EOF mesmo.
Porém, veja que você não irá escrevê-lo diretamente no arquivo. Na verdade, ele será concatenado com o texto original e compactado normalmente, como se fosse parte do texto original.
Creio não haver problemas em usar o símbolo de EOF mesmo.
Porém, veja que você não irá escrevê-lo diretamente no arquivo. Na verdade, ele será concatenado com o texto original e compactado normalmente, como se fosse parte do texto original.
E qual a codificação binária do EOF?
http://www.idevelopment.info/data/Programming/ascii_table/PROGRAMMING_ascii_table.shtml
http://www.idevelopment.info/data/Programming/ascii_table/PROGRAMMING_ascii_table.shtml
Então André, como você disse, o EOF é uma macro, portanto sua codificação binária depende do valor que ele assume.
Acho que agora entendo melhor sua pergunta, onde realmente usar o EOF poderia acarretar numa falta de portabilidade. Em geral, até onde eu sei, o valor de EOF é definido como -1, mas isso não é obrigatório.
De toda forma, você poderia assumir, por exemplo, que o símbolo especial que irá adicionar no fim do seu texto seja o de valor -1 (o que, em geral, corresponderia ao próprio EOF).
Isso resolve sua dúvida?
Acho que agora entendo melhor sua pergunta, onde realmente usar o EOF poderia acarretar numa falta de portabilidade. Em geral, até onde eu sei, o valor de EOF é definido como -1, mas isso não é obrigatório.
De toda forma, você poderia assumir, por exemplo, que o símbolo especial que irá adicionar no fim do seu texto seja o de valor -1 (o que, em geral, corresponderia ao próprio EOF).
Isso resolve sua dúvida?
Não, não resolve.
Até onde eu penso que sei, EOF é um valor (número) definido pela stdio do C, este valor é retornado quando não foi possível ler mais nenhum byte.
Deste modo, não existe uma codificação para o EOF, visto que este não é de fato escrito no arquivo. É apenas uma forma de se ter controle sobre a leitura de arquivos (e.g. condição de parada).
É isso ou não?
(Supondo que sim) Estou buscando uma codificação válida para um caracter que nunca apareça no arquivo, ou pelo menos apenas no fim dele.
Obrigado.
Até onde eu penso que sei, EOF é um valor (número) definido pela stdio do C, este valor é retornado quando não foi possível ler mais nenhum byte.
Deste modo, não existe uma codificação para o EOF, visto que este não é de fato escrito no arquivo. É apenas uma forma de se ter controle sobre a leitura de arquivos (e.g. condição de parada).
É isso ou não?
(Supondo que sim) Estou buscando uma codificação válida para um caracter que nunca apareça no arquivo, ou pelo menos apenas no fim dele.
Obrigado.
De fato, o EOF não aparece no arquivo. Quando é atingido o final do arquivo, a forma de sinalizar isso ao programa é enviando um EOF.
Porém, como você mesmo disse, EOF é uma macro, um número. Logo, claro que existe uma codificação para o EOF. Basta pegar esse número que o representa e ver qual sua codificação binária.
Claro que aí caímos no problema de EOF não ter um valor definido, que seja sempre o mesmo. Mas, em geral, como dito anteriormente, ele assume valor -1.
Dessa forma, não vejo porque não usar esse valor para resolver seu problema.
Porém, como você mesmo disse, EOF é uma macro, um número. Logo, claro que existe uma codificação para o EOF. Basta pegar esse número que o representa e ver qual sua codificação binária.
Claro que aí caímos no problema de EOF não ter um valor definido, que seja sempre o mesmo. Mas, em geral, como dito anteriormente, ele assume valor -1.
Dessa forma, não vejo porque não usar esse valor para resolver seu problema.
Agora entendi.
Na decodificação, é como se estívessemos lendo um byte cuja codificação (ansi, digamos) fosse "-1". Mesmo ele não sendo o EOF "enviado" pelo SO interpretamos sua codificação como EOF.
Show!
Obrigado.
Na decodificação, é como se estívessemos lendo um byte cuja codificação (ansi, digamos) fosse "-1". Mesmo ele não sendo o EOF "enviado" pelo SO interpretamos sua codificação como EOF.
Show!
Obrigado.
Mas se o caractere cuja codificação é -1, ou 255 pois é um char, estiver presente no texto? Não dá para saber se é um caractere válido ou se está representando fim de arquivo
Nao eh qualquer -1, eh um usado analogamente ao EOF, portanto um int entre chars. Se o arquivo nao for de texto, e aceitar ints, outro valor teria que ser usado. (provavelmente atraves de algum outro truque)
Hmmm, não sei se entendi exatamente o que você quis dizer Denis. Na verdade o arquivo será de chars, sim, mas nada impede de aparecerem números lá, através de sua codificação ASCII. O -1 no caso não tem muito a ver com isso. Cada char tem sua codificação ASCII, e o caracter que marcará o fim do texto (segundo minha sugestão) seria o de codificação -1, ou 255.
eh que o EOF eh um int bem grande no meio de um monte de chars.
Entao pensei que o marcador teria que ter ou essa caracteristica, que eh dificil jah que a divisao eh de byte a byte (entao o int cairia numa sequencia de em torno de quatro chars), ou ser um char (ou uma sequencia), convencionado a nao aparecer (como eh o sugerido).
uma ideia que tive pra contornar isso seria achar um caracter (ou combinacao de caracteres, se necessario) que nao ha no texto, e depois de comprimir, adiciona-lo no inicio como um cabecalho pra o descompressor saber qual vai ser o marcador.
Quanto a aceitar ints, me referia ao fato de caracteres unicode superarem um byte, daih a historia de colocar algo grande jah fura.
Entao pensei que o marcador teria que ter ou essa caracteristica, que eh dificil jah que a divisao eh de byte a byte (entao o int cairia numa sequencia de em torno de quatro chars), ou ser um char (ou uma sequencia), convencionado a nao aparecer (como eh o sugerido).
uma ideia que tive pra contornar isso seria achar um caracter (ou combinacao de caracteres, se necessario) que nao ha no texto, e depois de comprimir, adiciona-lo no inicio como um cabecalho pra o descompressor saber qual vai ser o marcador.
Quanto a aceitar ints, me referia ao fato de caracteres unicode superarem um byte, daih a historia de colocar algo grande jah fura.
Então Tiago, isso a princípio seria de fato um problema.
Porém, acho que não tem muito jeito. Supondo que existem 256 caracteres válidos codificados como um char, caso todos apareçam no texto, você não teria como sinalizar o fim de arquivo.
Dessa forma, podem supor que o caracter de codificação -1, ou 255, não aparecerá no texto original.
Porém, acho que não tem muito jeito. Supondo que existem 256 caracteres válidos codificados como um char, caso todos apareçam no texto, você não teria como sinalizar o fim de arquivo.
Dessa forma, podem supor que o caracter de codificação -1, ou 255, não aparecerá no texto original.
Assim como nos outros eps, não precisamos nos preocupar se o usuário vai utilizar o programa de forma errada, né? Por exemplo, ele não colocará parâmetros desconhecidos, arquivos que não existem, etc...
Olá,
A entrada estará correta.
A entrada estará correta.
o prazo tá acabando e ainda não rolou uns exemplos de entrada e saida...
Acho no mínimo estranho os arquivos .cod ficarem maiores que os .dec mesmo para arquivos de entrada grandes e com caracteres aleatórios. Isso pode ser considerado "normal"?
Tiago, você testou para arquivos razoavelmente grandes?
Testei com certeza arquivos com 100000 caracteres. Com mais que isso eu não tenho certeza.
Bom, tente com arquivos maiores, da ordem de megabytes. Acredito que a partir daí a diferença comece a aparecer.
Então, testei o meu com um arquivo de +ou - 4 mega, e ele comprimiu para um de +ou - 1 mega.
Para arquivos pequenos realamente não rola.
Mas a descompressão esta lenta, tem algum problema nisso?
abss
Para arquivos pequenos realamente não rola.
Mas a descompressão esta lenta, tem algum problema nisso?
abss
Olá Geraldo, veja o que eu respondi ao Tiago um pouco acima.
Como eu disse, eficiência na manipulação das estruturas de dados é sempre algo a ser trabalhado, porém não é o foco principal do EP.
Porém, é importante que essa "lentidão" não seja algo exagerado, tornando os testes impossíveis.
Como eu disse, eficiência na manipulação das estruturas de dados é sempre algo a ser trabalhado, porém não é o foco principal do EP.
Porém, é importante que essa "lentidão" não seja algo exagerado, tornando os testes impossíveis.
Vocês encontrarão os arquivos bible.txt, constitution.txt, const.txt, random.txt, usa.txt, um.txt em http://www.ime.usp.br/~alvaro/textos/