[Powered by Google Translate] [Passo a passo - Conjunto de Problemas 6] [Zamyla Chan - Harvard University] [Esta é CS50. - CS50.TV] 

Olá, todos, e bem vindo ao Passo a passo 6: Puff Huff'n. Em Puff Huff'n o que estamos fazendo vai estar lidando com um arquivo compactado Huffman e depois soprando-lo de volta, para descompactá-lo, para que possamos traduzir do 0s e 1s que o usuário envia-nos e convertê-lo de volta para o texto original. Pset 6 vai ser muito legal, porque você está indo para ver algumas das ferramentas que você usou na pset 4 e 5 e pset tipo de combiná-los em um conceito muito arrumado quando você chegou a pensar sobre isso. 

Além disso, sem dúvida, pset 4 e 5 foram os mais desafiadores Série de Exercícios que tínhamos para oferecer. Então, a partir de agora, temos essa pset um mais em C, e depois disso que estamos diante de programação web. Então felicitar-vos para ficar mais a mais difícil corcova na CS50. 

Passando para Puff Huff'n, a nossa caixa de ferramentas para este pset vão ser árvores Huffman, de modo a compreensão não só como trabalho árvores binárias, mas também árvores especificamente Huffman, como eles são construídos. E então nós vamos ter um monte de código distribuição neste pset, e nós vamos chegar a ver que, na verdade, parte do código podemos não ser capazes de compreender plenamente ainda, e assim esses serão os arquivos. C, mas depois os seus acompanhantes. arquivos h nos dará o suficiente compreensão de que precisamos para que possamos saber como essas funções funcionam ou pelo menos o que é suposto fazer - suas entradas e saídas - mesmo se não sabemos o que está acontecendo na caixa preta ou não entendem o que está acontecendo na caixa preta dentro. E então, finalmente, como de costume, estamos a lidar com estruturas de dados novos, tipos específicos de nós que apontam para certas coisas, e por isso aqui ter uma caneta e um papel não apenas para o processo de design e quando você está tentando descobrir como o seu pset deve funcionar mas também durante a depuração. Você pode ter GDB ao lado de sua caneta e papel, enquanto você toma para baixo o que os valores são, onde suas setas estão apontando, e coisas assim. 

Primeiro, vamos olhar para as árvores Huffman. Árvores Huffman são árvores binárias, o que significa que cada nó só tem 2 filhos. Em árvores Huffman a característica é a de que os valores mais frequentes são representados por o menor número de bits. Nós vimos nos exemplos de palestras do Código Morse, que tipo de consolidada algumas letras. Se você está tentando traduzir um A ou um E, por exemplo, você está traduzindo que, muitas vezes, então ao invés de ter que usar todo o conjunto de bits alocados para esse tipo de dados de costume, comprimi-lo para baixo, para menos, e depois as cartas que são representados com menos frequência são representados com pedaços mais longos porque você pode pagar que quando você pesar as freqüências que essas letras aparecem. Nós temos a mesma idéia aqui em árvores Huffman onde estamos fazendo uma corrente, uma espécie de caminho para chegar aos personagens certas. E então os personagens que têm mais freqüência vai ser representado com o menor número de bits. 

O jeito que você construir uma árvore de Huffman é a colocação de todos os personagens que aparecem no texto e calcular a sua freqüência, quantas vezes eles aparecem. Isto poderia ser uma contagem de quantas vezes as letras aparecem ou talvez uma porcentagem de fora de todos os personagens quantos cada um aparece. E então o que você faz é quando você tem tudo isso para fora mapeado, então você olha para as duas freqüências mais baixas e depois juntá-los como irmãos onde, então, o nó pai tem uma freqüência que é a soma de seus dois filhos. E então você por convenção dizer que o nó esquerdo, você segue que, seguindo o ramo 0, e depois o nó mais à direita é o ramo 1. Como vimos em código Morse, a única pegadinha é que, se você tivesse apenas um bip eo bip era ambígua. Poderia ser uma letra ou pode ser uma sequência de duas letras. E então o que Huffman árvores faz é porque, por natureza dos personagens ou finais nossos personagens reais, sendo os nós últimos no ramo - nos referimos aos que como as folhas - em virtude de que não pode haver qualquer ambiguidade em termos de qual a letra que você está tentando codificar com a série de bits porque em nenhum lugar ao longo dos bits que representam uma carta você vai encontrar outra carta inteira, e não haverá nenhuma confusão lá. Mas vamos entrar em exemplos que vocês podem realmente ver que em vez de nós simplesmente dizendo que isso é verdade. 

Vejamos um exemplo simples de uma árvore de Huffman. Eu tenho uma seqüência aqui que é de 12 caracteres. Eu tenho 4 Como, 6 Bs, Cs e 2. Meu primeiro passo seria contar. Quantas vezes é que um parecer? Ele aparece quatro vezes na seqüência. B aparece 6 vezes, e C é exibida duas vezes. Naturalmente, eu vou dizer que estou usando B na maioria das vezes, assim que eu quero representar B com o menor número de bits, o menor número de 0s e 1s. E então eu também vou esperar C para exigir a maior quantidade de 0s e 1s também. Primeiro o que eu fiz aqui é que eu colocava em ordem crescente em termos de frequência. Vemos que o C e A, essas são as nossas duas frequências mais baixas. Criamos um nó pai, e que o nó pai não tem uma carta a ela associados, mas tem uma frequência, que é a soma. A soma torna-se 2 + 4, o qual é 6. Então, seguimos o ramo esquerdo. Se estivéssemos naquele nó 6, então poderíamos seguir 0 para chegar a C e, em seguida, 1 para obter a A. Portanto, agora temos dois nós. Nós temos o valor 6 e depois também temos outro nó com o valor 6. E assim os dois não são apenas o menor 2, mas também a apenas 2 que sobraram, para que se juntar aos que por outro pai, com a soma sendo 12. Portanto, temos aqui a nossa árvore de Huffman onde para chegar a B, que seria apenas o bit 1 e, em seguida, para chegar a um teríamos 01 e, em seguida, C com 00. Então aqui nós vemos que, basicamente, estamos representando estes chars com 1 ou 2 bits em que a B, como previsto, tem pelo menos. E então esperávamos C para ter mais, mas já que é tal uma árvore de Huffman pequeno, então o A é também representada por 2 bits em vez de algures no meio. 

Só para passar por cima de outro exemplo simples da árvore de Huffman, dizer que você tem a string "Olá". O que você é primeiro você diria quantas vezes H aparecer nessa? H aparece uma vez e em seguida e aparece uma vez e então temos l aparecendo duas vezes e o aparecimento vez. E então nós esperamos que carta a ser representado pelo menor número de bits? [Aluno] l. L. >> Sim. l é certo. Esperamos l ser representado por pelo menos o número de bits porque eu é usado mais na string "Olá". O que eu vou fazer agora é tirar esses nós. I ter 1, que é H, e, em seguida, um outro 1, que é o e, em seguida, um 1, que é o - agora eu estou colocando-os em ordem - e, em seguida, 2, que é l. Então eu digo a maneira que eu construir uma árvore de Huffman é encontrar os dois nós com as menores freqüências e torná-los irmãos criando um nó pai. Aqui temos três nós com a menor freqüência. Eles são todos um. Então aqui nós escolher qual vamos ligar primeiro. Vamos dizer que eu escolher o H eo e. A soma de 1 + 1 é 2, mas este nó não tiver uma carta a ela associados. Ele só tem o valor. Agora vamos olhar para os próximos 2 frequências mais baixas. Isso é 2 e 1. Isso poderia ser um desses dois, mas eu vou escolher um presente. A soma é 3. E então, finalmente, eu só tenho 2 esquerda, de modo que se torna então 5. Então, aqui, como esperado, se eu preencher a codificação para que, 1s são sempre o braço direito e 0s são a esquerda. Então nós temos l representadas por apenas um pouco e depois o o por 2 e, em seguida, o e por 2 e, em seguida, o H cai para 3 bits. Então você pode transmitir esta mensagem "Olá" em vez de realmente usando os personagens por apenas 0s e 1s. No entanto, lembre-se que em vários casos que tinham laços com a nossa frequência. Poderíamos ter ou juntou o H eo O primeiro talvez. Ou então, mais tarde, quando tivemos a l representada por 2 bem como a que se juntou um representado por 2, pode-se ter ligado um ou outro. 

E assim, quando você envia os 0s e 1s, que na verdade não garante que o destinatário pode inteiramente ler sua mensagem logo de cara porque eles podem não saber que a decisão que você fez. Então, quando estamos lidando com compressão Huffman, de alguma forma, temos de dizer o destinatário da nossa mensagem como decidimos - Eles precisam saber algum tipo de informação extra para além da mensagem comprimida. Eles precisam entender o que a árvore realmente se parece, como realmente fez essas decisões. 

Aqui foram apenas fazendo exemplos baseados na contagem real, mas às vezes você pode ter também uma árvore de Huffman com base na freqüência em que as letras aparecem, e é exatamente o mesmo processo. Aqui eu estou expressando-a em termos de percentagens ou fração, e por isso aqui exatamente a mesma coisa. Acho o menor 2, somá-los, o 2 menor seguinte, somá-los, até eu ter uma árvore cheia. Mesmo que pudéssemos fazê-lo de qualquer forma, quando estamos lidando com percentagens, isso significa que estamos dividindo as coisas e lidar com decimais ou melhor, flutua se estamos pensando em estruturas de dados de uma cabeça. O que sabemos sobre carros alegóricos? O que é um problema comum quando estamos lidando com carros alegóricos? [Aluno] aritmética imprecisa. Sim >>. Imprecisão. Por causa da imprecisão de ponto flutuante, para este pset para que certifique-se que não perdemos nenhum valor, então estamos realmente vai ser lidar com a contagem. Então, se você pensar em um nó Huffman, se você olhar para trás, para a estrutura aqui, se você olhar para os verdes que tem uma freqüência associada a ele assim como ele aponta para um nó para o seu lado esquerdo, assim como um nó à direita. E, em seguida, as tintas têm também um carácter que lhes estão associados. Nós não vamos fazer os separados para os pais e, em seguida, os nós finais, a que nos referimos como as folhas, mas sim aqueles que só têm valores nulos. Para cada nó teremos um personagem, o símbolo que representa esse nó, em seguida, a frequência, bem como um indicador para o seu filho esquerdo, bem como a sua criança direita. As folhas, que são bem no fundo, também teria ponteiros nó à sua esquerda e à sua direita, mas desde que esses valores não estão apontando para nós reais, o que seria o seu valor ser? >> [Aluno] NULL. NULL. >> Exatamente. Aqui está um exemplo de como você pode representar a freqüência em carros alegóricos, mas vamos estar lidando com isso com números inteiros, então tudo que eu fiz é mudar o tipo de dados lá. 

Vamos a um pouco mais de um exemplo complexo. Mas agora que temos feito as mais simples, é apenas o mesmo processo. Você encontra as duas frequências mais baixas, somar as freqüências e essa é a nova freqüência de seu nó pai, que, então, aponta para a sua esquerda com o ramo do direito 0 e com o ramo 1. Se temos a string "Este é CS50," então nós contar quantas vezes é mencionado T, h mencionado, i, s, c, 5, 0. Então o que eu fiz aqui é com os nós vermelhos eu só plantadas, Eu disse que eu vou ter esses personagens, eventualmente, na parte inferior da minha árvore. Aqueles vão ser todas as folhas. Então o que eu fiz é que eu classificados los pela frequência em ordem crescente, e esta é realmente a maneira que o código faz pset é ele classifica-lo por freqüência e, em seguida, em ordem alfabética. Por isso, tem os números primeiro e depois em ordem alfabética pela freqüência. Então o que eu gostaria de fazer é que eu iria encontrar a menor 2. Isso é 0 e 5. Gostaria de somá-los, e isso é 2. Então gostaria de continuar, encontrar o próximo 2 menor. Esses são os 1s dois, e, em seguida, os dois se tornam também. Agora eu sei que o meu próximo passo vai ser juntar o menor número, que é o T, a 1, e em seguida, escolher um dos nós que tem 2 como a freqüência. Portanto, temos aqui três opções. O que eu vou fazer para o slide é apenas visualmente reorganizá-los para você de modo que você pode ver como eu estou construindo-o. O que o código eo código de distribuição vai fazer seria juntar a uma T com o nó 0 e 5. Então que resume a 3, e então continuar o processo. O 2 a 2 e agora são os mais baixos, de modo então aqueles soma a 4. Todos seguindo até agora? Okay. Em seguida, depois de que temos a 3 e 3 que necessitam de ser adicionados, assim outra vez eu estou apenas ligá-lo de modo que você pode ver visualmente, de modo que ele não fique muito confuso. Então nós temos um 6, e então o nosso passo final é agora que temos apenas 2 nós somamos aqueles para tornar a base da nossa árvore, que é 10. E o número 10 faz sentido, porque cada nó representado, seu valor, o seu número de freqüência, era quantas vezes eles apareceram na seqüência, e então temos 5 personagens em nossa string, de modo que faz sentido. Se olhar para como nós, na verdade, codificá-lo, como esperado, o i eo s, que aparecem com mais freqüência são representados pelo número mínimo de bits. 

Tenha cuidado aqui. Em árvores Huffman o caso realmente importa. Um S maiúsculo é diferente de um s minúsculo. Se tivéssemos "Este é CS50" com letras maiúsculas, o s minúsculo só aparecem duas vezes, Seria um nó com 2 como o seu valor e, em seguida, S maiúsculo seria apenas uma vez. Então sua árvore mudaria as estruturas, porque você realmente tem uma folha extra aqui. Mas a soma ainda seria 10. Isso é o que estamos realmente vai ser chamar o checksum, a adição de todas as contagens. 

Agora que nós cobrimos árvores Huffman, podemos mergulhar em Huff'n Puff, o pset. Nós vamos começar com uma seção de perguntas, e isso vai levá-lo acostumado com árvores binárias e como operar em torno de que: nós desenho, criando a sua própria estrutura typedef para um nó, e ver como você pode inserir em uma árvore binária, um que está classificado, atravessando, e coisas assim. Esse conhecimento é definitivamente vai ajudar você quando você mergulha na porção Puff Huff'n do pset. Na edição padrão do pset, sua tarefa é implementar Puff, e na versão pirata sua tarefa é implementar Huff. O Huff faz é que leva o texto e então o traduz para os 0s e 1s, assim o processo que fizemos acima, onde contamos as freqüências e em seguida, fez a árvore e, em seguida, disse: "Como posso obter T?" T é representado por 100, coisas assim, Huff e depois levaria o texto e, em seguida, saída que binário. Mas também porque sabemos que nós queremos permitir que o nosso destinatário da mensagem para recriar a mesma árvore que, também inclui informações sobre as contagens de freqüência. Então, com Puff nos é dado um arquivo binário de 0s e 1s e atendendo também à informação sobre as frequências. Traduzimos todos os 0s e 1s de volta para a mensagem original que foi, por isso estamos descompactando isso. Se você está fazendo a edição padrão, você não precisa implementar Huff, , então você pode simplesmente usar a implementação equipe de Huff. Há instruções na especificação de como fazer isso. Você pode executar a implementação equipe de Huff em cima de um arquivo de texto certa e depois usar essa saída como a sua entrada para Puff. 

Como eu mencionei antes, nós temos um monte de código de distribuição para este. Eu vou começar a passar por isso. Eu vou passar a maior parte do tempo no. Arquivos h porque nos arquivos. c, porque temos o h. e que nos fornece os protótipos das funções, não é totalmente precisa entender exatamente - Se você não entende o que está acontecendo nos arquivos. C, então não se preocupe muito, mas definitivamente tentar dar uma olhada porque pode dar algumas dicas e é útil para se acostumar com leitura de código de outras pessoas. 

Olhando huffile.h, nos comentários que declara uma camada de abstração para Huffman codificados arquivos. Se descermos, vemos que há um máximo de 256 símbolos que podemos precisar de códigos para. Isto inclui todas as letras do alfabeto - maiúsculas e minúsculas - e, em seguida, os símbolos e números, etc Então aqui nós temos um número mágico identificar um arquivo Huffman-codificado. Dentro de um código de Huffman eles vão ter um número de certa magia associados com o cabeçalho. Isso pode parecer apenas um número mágico aleatório, mas se você realmente traduzi-lo em ASCII, então ele realmente explicita Huff. Aqui temos uma estrutura para um arquivo Huffman-codificado. Há todas essas características associadas a um arquivo Huff. Então aqui temos o cabeçalho de um arquivo de Huff, por isso nós dizemos que Huffeader em vez de adicionar o h extra porque parece o mesmo de qualquer maneira. Bonito. Nós temos um número mágico associado a ele. Se for um arquivo de Huff real, que vai ser o número acima, esta magia. E então ele vai ter uma matriz. Assim, para cada símbolo, dos quais existem 256, ele vai listar o que a frequência desses símbolos estão dentro do arquivo de Huff. E então, finalmente, temos uma soma de verificação para as freqüências, qual deve ser a soma dessas frequências. Então é isso que um Huffeader é. Então, temos algumas funções que retornam o próximo bit no arquivo Huff bem como escreve um pouco para o arquivo de Huff, e então esta função aqui, hfclose, que realmente fecha o arquivo Huff. Antes, estávamos lidando com reta apenas fclose, mas quando você tem um arquivo de Huff, em vez de se fclosing o que na verdade você está indo fazer é hfclose e hfopen-lo. Essas são funções específicas para os arquivos de Huff que nós vamos tratar. Então aqui nós lemos no cabeçalho e em seguida, escrever o cabeçalho. 

Só lendo o. Arquivo h podemos tipo de obter uma noção do que um arquivo pode ser Huff, quais as características que tem, sem realmente ir para o huffile.c, que, se mergulhar, vai ser um pouco mais complexa. Ele tem todo o arquivo I / O lidando aqui com ponteiros. Aqui vemos que quando chamamos hfread, por exemplo, que ainda está lidando com fread. Nós não vai se livrar dessas funções totalmente, mas estamos enviando as medidas a tomar conta de dentro do arquivo Huff em vez de fazer tudo nós mesmos. Você pode se sentir livre para fazer a varredura através deste se você está curioso e ir descascar a camada de volta um pouco. 

O próximo arquivo que vamos olhar é tree.h. Antes do passo a passo desliza dissemos que esperar um nó Huffman e fizemos um nó typedef struct. Esperamos que tem um símbolo, uma frequência, e depois duas estrelas nó. Neste caso, o que estamos fazendo é que este é essencialmente o mesmo exceto em vez de nó vamos chamá-los de árvores. Nós temos uma função que quando você chamar fazer árvore que retorna um ponteiro de árvore. Fazer a Speller, quando você estava fazendo um novo nó você disse nó palavra * novo = malloc (sizeof) e coisas assim. Basicamente, mktree vai ser lidar com isso para você. Da mesma forma, quando você quiser remover uma árvore, de modo que é essencialmente libertar a árvore quando terminar com ele, em vez de chamar explicitamente livre em que, na verdade você está indo só para usar a função rmtree onde você passar o ponteiro para a árvore e, em seguida, tree.c vai cuidar disso para você. 

Olhamos para tree.c. Esperamos que as mesmas funções, exceto para ver a execução também. Como esperávamos, quando você chama-lo mktree mallocs do tamanho de uma árvore em um ponteiro, inicializa todos os valores para o valor NULL, assim 0s ou nulos, e retorna o ponteiro para a árvore que você acabou de malloc'd para você. Aqui quando você chamar remover árvore primeiro garante que você não está liberando dupla. Ele garante que você realmente tem uma árvore que você deseja remover. Aqui porque uma árvore também inclui os seus filhos, o que isto significa é que chama recursivamente remover árvore no nó esquerdo da árvore bem como o nó direito. Antes que liberta o pai, ele precisa libertar os filhos também. Pai também é intercambiável com raiz. O primeiro pai nunca, assim como o grande-grande-grande-grande-avô ou árvore avó, primeiro temos que libertar-se os primeiros níveis. Então, atravessar para o fundo, sem aqueles, e em seguida, voltar-se, livre daqueles, etc Então, isso é árvore. 

Agora vamos olhar para floresta. Floresta é onde você coloca todas suas árvores de Huffman. Ele está dizendo que nós vamos ter uma coisa chamada trama que contém um apontador para uma árvore, assim como um indicador para uma trama chamada seguinte. Que estrutura faz esse tipo de olhar como? É o tipo de diz por lá. Bem aqui. Uma lista ligada. Vemos que, quando temos uma trama que é como uma lista ligada de parcelas. A floresta é definida como uma lista ligada de parcelas, e assim a estrutura da floresta é que estamos indo só para ter um ponteiro para o nosso primeiro lote e que a trama tem uma árvore dentro dele, ou melhor aponta para uma árvore e, em seguida, aponta para o lote seguinte, assim por diante e assim por diante. Para fazer uma floresta que chamamos mkforest. Então, temos algumas funções muito úteis aqui. Temos escolher onde você passa em uma floresta e, em seguida, o valor de retorno é um * Árvore, um ponteiro para uma árvore. O que vai fazer é escolher ele vai para a floresta que você está apontando para em seguida, remover uma árvore com a menor freqüência do que a floresta e depois dar-lhe o ponteiro para essa árvore. Uma vez que você chama de escolher, a árvore não vai existir na floresta mais, mas o valor de retorno é o ponteiro para a árvore. Então você tem planta. Desde que você passar em um ponteiro para uma árvore que tem uma frequência não-0, que planta vai fazer é que vai demorar a floresta, tomar a árvore, e planta que árvore dentro da floresta. Aqui temos rmforest. Similar para remover árvore, que, basicamente, libertou todos os nossos árvores para nós, remover floresta vai tudo livre contida na floresta. 

Se olharmos para forest.c, vamos esperar para ver pelo menos um comando rmtree lá, porque a memória livre na floresta se uma floresta tem árvores em que, depois, eventualmente, você vai ter que remover as árvores também. Se olharmos para forest.c, temos a nossa mkforest, que é como nós esperamos. Nós malloc coisas. Nós inicializar a primeira parcela na floresta como NULL porque ele está vazio, para começar, então vemos picareta, que retorna a árvore com o menor peso, a menor freqüência, e então se livrar desse nó especial que aponta para que a árvore eo próximo, por isso é preciso que fora da lista vinculada da floresta. E então aqui temos planta, que insere uma árvore para a lista ligada. O que mata não é bem mantém classificados para nós. E, em seguida, finalmente, temos rmforest e, como esperado, temos chamado rmtree lá. 

Olhando para o código de distribuição, até agora, huffile.c foi provavelmente, de longe, o mais difícil de entender, enquanto que os outros arquivos em si eram bem simples de seguir. Com o nosso conhecimento de ponteiros e listas ligadas e tal, fomos capazes de acompanhar muito bem. Mas tudo o que precisamos para realmente ter certeza de que compreendemos plenamente. São os arquivos h porque você precisa estar chamando essas funções, lidar com esses valores de retorno, para se certificar que você entendeu o que a ação vai ser realizada sempre que você chamar uma dessas funções. Mas, na verdade, o entendimento dentro do que não é absolutamente necessário, porque temos aqueles. Arquivos h. Temos mais dois arquivos deixados em nosso código de distribuição. 

Vamos olhar para despejo. Despejo por seu comentário aqui leva um arquivo Huffman-comprimido e, em seguida, traduz e depósitos de todo o seu conteúdo para fora. Aqui, vemos que ele está chamando hfopen. Esta é uma espécie de espelhamento para arquivo de entrada * = fopen, e então você passa a informação. É quase idêntico, exceto em vez de um * arquivo que você está passando em um Huffile; em vez de fopen você está passando em hfopen. Aqui lemos no cabeçalho do primeiro, que é uma espécie de similar a como se lê no cabeçalho para um arquivo bitmap. O que estamos fazendo aqui é verificar para ver se as informações de cabeçalho contém o número mágico direito que indica que é um arquivo de Huff real, em seguida, todas essas verificações para certificar-se de que o arquivo que é aberto um arquivo real xingou ou não. O que isto significa é que gera as freqüências de todos os símbolos que podemos ver dentro de um terminal para uma tabela gráfica. Esta parte vai ser útil. Ele tem um pouco e lê pouco a pouco para o pouco variável e imprime-o. Então, se eu fosse chamar despejo em hth.bin, que é o resultado de um arquivo huffing utilizando a solução pessoal, gostaria de obter isso. É a saída de todos esses personagens e depois colocar a freqüência em que eles aparecem. Se olharmos, a maioria deles são 0s exceto para isso: H, que aparece duas vezes, T e, em seguida, uma vez que aparece. E aqui temos a verdadeira mensagem em 0s e 1s. Se olharmos para hth.txt, que é provavelmente a mensagem original que foi bufou, esperamos ver alguns Hs e Ts lá. Especificamente, nós esperamos ver apenas 1 T e 2 hs. Aqui estamos em hth.txt. De fato, tem HTH. Incluído em, embora não possamos vê-lo, é um caractere de nova linha. O hth.bin arquivo Huff também é a codificação de caracteres de nova linha também. Aqui porque sabemos que a ordem é HTH e depois de nova linha, podemos ver que, provavelmente, o H é representado por apenas um único 1 e, em seguida, o T é provavelmente 01 e, em seguida, o seguinte é um H, bem e então temos uma nova linha indicada por dois 0s. Cool. 

E então, finalmente, arquivos, porque estamos lidando com múltiplas. C e. H, nós vamos ter um argumento muito complexo para o compilador, e aqui temos um Makefile que faz despejo para você. Mas, na verdade, você tem que ir sobre como fazer seu próprio arquivo puff.c. O Makefile na verdade, não se trata de fazer puff.c para você. Estamos deixando isso para você editar o Makefile. Quando você digita um comando como fazer tudo, por exemplo, ele vai fazer todos eles para você. Sinta-se livre para olhar para os exemplos de Makefile das pset passado bem como sair de um presente para ver como você pode ser capaz de fazer o seu arquivo Puff editando este Makefile. É sobre isso para o nosso código de distribuição. 

Uma vez que temos obtido através disso, então aqui é só mais um lembrete de como vamos estar lidando com os nós Huffman. Nós não vamos estar chamando-os de nós mais, nós vamos estar chamando-os de árvores onde vamos estar representando seu símbolo com um char, a sua frequência, o número de ocorrências, com um número inteiro. Nós estamos usando isso porque é mais preciso do que um carro alegórico. E então nós temos um outro ponteiro para o filho esquerdo, bem como o direito da criança. Uma floresta, como vimos, é apenas uma lista encadeada de árvores. Por fim, quando estamos construindo o nosso arquivo Huff, queremos que a nossa floresta para conter apenas uma árvore 1 - Uma árvore, uma raiz com vários filhos. No início de quando estávamos fazendo nossas árvores de Huffman, começamos por colocar todos os nós em nossa tela e dizendo que nós vamos ter esses nós, eventualmente, eles vão ser as folhas, e este é o seu símbolo, esta é a sua freqüência. Em nossa floresta se só temos 3 letras, que é uma floresta de três árvores. E então, como vamos, quando adicionamos o primeiro pai, fizemos uma floresta de duas árvores. Nós removemos 2 das crianças da nossa floresta e, em seguida, substituí-lo com um nó pai que tinha esses dois nós como filhos. E então, finalmente, o nosso último passo com fazer o nosso exemplo, com o As, Bs e Cs seria tornar o progenitor final, e assim, então, que iria trazer a nossa contagem total de árvores na floresta para 1. Será que todo mundo ver como você começa com várias árvores em sua floresta e acabar com um? Okay. Cool. 

O que precisamos fazer para Puff? O que precisamos fazer é garantir que, como sempre, eles nos dão o direito tipo de entrada para que possamos realmente executar o programa. Neste caso, eles vão estar dando-nos após seu argumento de linha de comando primeiro 2 mais: o arquivo que queremos descomprimir e a saída do arquivo descompactado. Mas uma vez que nós temos certeza que eles passam-nos a quantidade certa de valores, queremos garantir que a entrada é um arquivo Huff ou não. E então, uma vez que garante que é um arquivo de Huff, então nós queremos construir a nossa árvore, construir a árvore de tal forma que ele corresponda a árvore que a pessoa que enviou a mensagem construída. Em seguida, depois de construir a árvore, então podemos lidar com o, 0s e 1s que eles passaram em seguir aqueles ao longo da nossa árvore porque é idêntico, e em seguida, escrever essa mensagem, interpretar os bits de volta para chars. E então, no final, porque estamos lidando com ponteiros aqui, nós queremos ter certeza de que não temos quaisquer vazamentos de memória e que tudo livre. 

Garantir o uso adequado é velho chapéu para nós agora. Nós levamos em uma entrada, que vai ser o nome do arquivo a soprar, e, então, especificar uma saída, de modo que o nome do ficheiro de saída para o tufado, que será o ficheiro de texto. Isso é uso. E agora queremos garantir que a entrada é xingou ou não. Pensando bem, estava lá nada no código de distribuição que pode nos ajudar a com a compreensão se um arquivo é xingou ou não? Houve informações sobre o huffile.c Huffeader. Nós sabemos que cada arquivo tem um Huff Huffeader associada com um número mágico , bem como uma matriz de as frequências para cada símbolo , bem como uma soma de verificação. Nós sabemos disso, mas nós também levou uma olhada em dump.c, no qual se lê em um arquivo Huff. E assim, para fazer isso, tinha que verificar se ele realmente foi xingou ou não. Então, talvez pudéssemos usar dump.c como uma estrutura para o nosso puff.c. Voltar ao pset 4, quando tivemos a copy.c arquivo que copiou no triplica RGB e interpretamos que para Whodunit e Redimensionar, Da mesma forma, o que você poderia fazer é executar o comando como cp dump.c puff.c e usar parte do código lá. No entanto, não vai ser tão simples de um processo para traduzir o seu dump.c em puff.c, mas pelo menos ele dá-lhe um lugar para começar sobre a forma de garantir que a entrada é efectivamente ou não bufou bem como algumas outras coisas. Temos assegurado o uso adequado e garantiu que a entrada é bufou. Toda vez que fizemos o que fizemos nossa verificação de erro adequada, para retornar e encerrar a função se alguma falha ocorre, se há um problema. 

Agora, o que nós queremos fazer é construir a árvore real. Se olharmos em Floresta, há duas principais funções que vamos querer tornar-se muito familiarizado. Há a planta função booleana que planta uma árvore de freqüência não-0 dentro de nossa floresta. E assim, lá você passar em um ponteiro para uma floresta e um ponteiro para uma árvore. Pergunta rápida: Quantos florestas que você tem quando você está construindo uma árvore de Huffman? A nossa floresta é como a nossa tela, certo? Então, nós estamos indo só para ter uma floresta, mas vamos ter várias árvores. Então, antes de chamar planta, você está provavelmente vai querer fazer sua floresta. Há um comando para que, se você olhar para forest.h de como você pode fazer uma floresta. Você pode plantar uma árvore. Nós sabemos como fazer isso. E então você também pode escolher uma árvore da floresta, remoção de uma árvore com o menor peso e dando-lhe o ponteiro para isso. Pensando quando estávamos fazendo os exemplos de nós mesmos, quando estávamos desenhando-o para fora, nós simplesmente acabou de adicionar os links. Mas aqui, em vez de apenas adicionar os links, pensar mais como você está removendo dois desses nós e, em seguida, substituí-lo por outro. Para expressar isso em termos de colheita e plantio, você está escolhendo duas árvores e plantar outra árvore que tenha essas duas árvores que você escolheu como crianças. Para construir árvore de Huffman, você pode ler nos símbolos e freqüências em ordem porque o que Huffeader dá para você, dá-lhe um conjunto de frequências. Então você pode ir em frente e simplesmente ignorar qualquer coisa com a 0 nele porque não queremos 256 folhas no final do mesmo. Nós só queremos o número de folhas que são personagens que são realmente utilizados no arquivo. Você pode ler nesses símbolos, e cada um desses símbolos que têm freqüências não-0, aqueles vão ser árvores. O que você pode fazer é toda vez que você ler em um símbolo de frequências não-0, você pode plantar a árvore na floresta. Depois de plantar as árvores na floresta, você pode juntar essas árvores como irmãos, Então, voltando ao plantio e escolher onde você escolhe 2 e depois planta 1, onde que uma planta que você é o pai das duas crianças que você escolheu. Então o resultado final vai ser uma única árvore na floresta. É como você construir a sua árvore. 

Há várias coisas que podem dar errado aqui porque estamos lidando com fazer novas árvores e lidar com ponteiros e coisas assim. Antes, quando estávamos lidando com ponteiros, sempre que malloc'd nós queríamos ter certeza de que não nos devolver um valor de ponteiro NULL. Então, em vários passos dentro deste processo não vão ser vários casos onde o programa poderia falhar. O que você quer fazer é que você quer ter certeza de que você lida com esses erros, e na especificação diz para segurá-los graciosamente, assim como imprimir uma mensagem para o usuário dizendo-lhes por isso que o programa tem para sair e então prontamente sair dela. Para fazer isso o tratamento de erros, lembre-se que você quer verificar se cada vez que pode haver uma falha. Toda vez que você está fazendo um novo ponteiro você quer ter certeza de que isso é sucesso. Antes que estamos acostumados a fazer é fazer um novo ponteiro e malloc-lo, e então nós verificar se esse ponteiro é NULL. Portanto, não vão ser alguns casos em que você só pode fazer isso, mas às vezes você realmente está chamando uma função e dentro dessa função, que é a única que está fazendo a mallocing. Nesse caso, se olharmos para algumas das funções dentro do código, alguns deles são funções booleanas. No caso abstrato, se temos uma função booleana chamada foo, Basicamente, podemos supor que, além de fazer o que faz foo, já que é uma função booleana, ele retorna verdadeiro ou falso - verdadeiro caso de sucesso, false se não. Então, queremos verificar se o valor de retorno de foo é verdadeira ou falsa. Se é falso, o que significa que nós vamos querer imprimir algum tipo de mensagem e feche o programa. O que queremos fazer é verificar o valor de retorno de foo. Se foo retorna falso, então sabemos que encontramos algum tipo de erro e nós precisamos parar de nosso programa. Uma maneira de fazer isso é ter uma condição onde a função em si é a sua condição. Diga foo leva em x. Podemos ter como condição if (foo (x)). Basicamente, isso significa que se no final da execução de foo ele retorna true, então podemos fazer isso porque a função tem que avaliar foo , a fim de avaliar a condição geral. Então é assim que você pode fazer alguma coisa, se a função retornará verdadeiro e é bem sucedido. Mas quando você está a verificação de erros, você só quer sair se a sua função retorna falso. O que você poderia fazer é apenas adicionar um == false ou apenas adicionar um estrondo na frente dele e então você tem if (! foo). Dentro desse corpo de que condição você teria todo o tratamento de erros, assim como, "Não foi possível criar esta árvore" e, em seguida, retornar 1 ou algo assim. O que faz, porém, é que mesmo que foo retornou falso - Diga foo retorna true. Então você não tem que chamar foo novamente. Isso é um equívoco comum. Porque ele estava em sua condição, ele já está avaliado, Então você já tem o resultado, se você estiver usando tornar árvore ou algo assim ou planta ou picareta ou algo assim. Ela já tem esse valor. Ele já está executado. Por isso, é útil usar funções booleanas como condição porque se está ou não efectivamente executar o corpo do loop, ele executa a função de qualquer maneira. 

Nosso segundo a última etapa é escrever a mensagem para o arquivo. Uma vez que vamos construir a árvore de Huffman, em seguida, escrever a mensagem para o arquivo é bastante simples. É muito simples agora para apenas seguir os 0s e 1s. E assim por convenção, sabemos que em uma árvore Huffman os 0s indicam que deixaram e os 1s indicam certo. Então, se você ler em pouco a pouco, cada vez que você receber um 0 você vai seguir o ramo da esquerda, e depois a cada vez que você ler em um 1 você vai seguir o ramo direito. E então você vai continuar até que você bata uma folha porque as folhas vão ser no final dos ramos. Como podemos dizer se nós batemos uma folha ou não? Nós dissemos isso antes. [Aluno] Se os ponteiros são NULL. Sim >>. Podemos dizer se nós batemos uma folha se os ponteiros para árvores, tanto a esquerda e direita são NULL. Perfeito. Sabemos que queremos ler pouco a pouco em nosso arquivo Huff. Como vimos antes, em dump.c, o que eles fizeram é que lêem pouco a pouco para o arquivo Huff e apenas impressos que esses fragmentos eram. Nós não vamos estar fazendo isso. Nós estamos indo fazer algo que é um pouco mais complexa. Mas o que podemos fazer é que podemos tomar aquele pedaço de código que lê para o bit. Aqui nós temos o bit inteiro representando o bit atual que estamos no. Este cuida de iteração todos os bits no arquivo até chegar ao final do arquivo. Com base nisso, então você vai querer ter algum tipo de iterador para atravessar a sua árvore. E, em seguida, com base em se o bit é 0 ou 1, você vai querer quer mover esse iterador para a esquerda ou movê-lo para a direita todo o caminho até que você bata uma folha, assim todo o caminho até esse nó que você está em não apontam para nós mais nada. Por que podemos fazer isso com um arquivo Huffman mas não o código Morse? Porque no código Morse há um pouco de ambigüidade. Nós poderíamos ser como, oh wait, nós batemos uma carta ao longo do caminho, talvez por isso esta é a nossa carta, enquanto que, se continuamos mais um pouco, então nós teria atingido outra carta. Mas isso não vai acontecer em codificação de Huffman, para que possamos ter certeza de que a única maneira que nós vamos bater um personagem é se as crianças esquerdo e direito que nós são NULL. 

Finalmente, queremos libertar toda a nossa memória. Queremos ambos perto o arquivo Huff que estamos lidando com bem como remover todas as árvores em nossa floresta. Com base na sua implementação, você provavelmente vai querer chamar remover floresta em vez de realmente passar por todas as árvores de si mesmo. Mas se você fez todas as árvores temporários, você vai querer liberar isso. Você sabe o seu código de melhor, para que você saiba onde você está alocando memória. E por isso, se você entrar, começar por até controlar f'ing para malloc, vendo sempre que malloc e certificando-se de que você libertar de tudo isso mas então apenas passando por seu código, entender onde você pode ter alocado memória. Normalmente você pode apenas dizer: "No final de um arquivo que eu estou indo só para remover floresta em minha floresta", Então, basicamente claro que a memória livre, que, "E então eu também estou indo para fechar o arquivo e então o meu programa vai sair." Mas é que a única vez que o programa é fechado? Não, porque, por vezes, pode ter havido um erro que aconteceu. Talvez a gente não pode abrir um arquivo ou nós não poderíamos fazer de outra árvore ou algum tipo de erro aconteceu no processo de alocação de memória e por isso retornou NULL. Um erro aconteceu e, depois, devolvido e saia. Então você quer ter certeza de que a qualquer momento possível que seu programa pode sair, você quer libertar toda a sua memória lá. Não só vai ser no final da função principal que você saia de seu código. Você quer olhar para trás a cada instância de que seu código potencialmente pode retornar prematuramente e memória qualquer livre faz sentido. Digamos que você tinha chamado fazer floresta e que retornou falso. Então você provavelmente não vai precisar remover a floresta porque você não tem uma floresta ainda. Mas em todos os pontos do código onde você pode retornar prematuramente você quer ter certeza de que você liberar qualquer memória possível. 

Então, quando estamos lidando com liberar memória e ter vazamentos potenciais, queremos não só usar nosso julgamento e nossa lógica mas também usar Valgrind para determinar se nós libertou toda a nossa memória corretamente ou não. Você pode executar Valgrind em Puff e então você também tem que passá-lo o número certo de linha de comando argumentos para Valgrind. Você pode executar isso, mas a saída é um pouco enigmática. Nós temos tido um pouco acostumado com Speller, mas ainda precisamos de ajuda um pouco mais, assim então executá-lo com algumas bandeiras, como o vazamento de mais-check = full, que provavelmente vai nos dar alguma saída mais útil em Valgrind. 

Em seguida, outra dica útil quando você está depurando é o comando diff. Você pode acessar a implementação do pessoal de Huff, que executar em um arquivo de texto, e depois a saída para um arquivo binário, um arquivo binário Huff, para ser específico. Então, se você executar o seu próprio sopro em que o arquivo binário, em seguida, idealmente, o seu arquivo de texto outputted vai ser idêntico ao original que você passou dentro Aqui eu estou usando hth.txt como exemplo, e isso é o que falou em sua especificação. Isso é literalmente apenas HTH e então uma nova linha. Mas, definitivamente, se sentir livre e você está definitivamente incentivados a usar exemplos mais para o seu arquivo de texto. 

Você pode até mesmo levar um tiro na talvez comprimir e depois descomprimir alguns dos arquivos que você usou na Speller como Guerra e Paz ou Jane Austen, ou algo assim - o que seria bem legal - ou Austin Powers, tipo de lidar com arquivos maiores porque nós não teríamos chegado até ele se usamos a ferramenta seguinte aqui, ls-l. Estamos acostumados a ls, que lista todos basicamente o conteúdo em nosso diretório atual. Passando o sinalizador-l realmente mostra o tamanho dos arquivos. Se você passar por a especificação pset, ele realmente percorre a criação do arquivo binário, de huffing-lo, e você vê que para arquivos muito pequenos o custo do espaço de comprimi-lo e traduzir toda essa informação de todas as freqüências e coisas assim supera o benefício real de comprimir o arquivo em primeiro lugar. Mas se você executá-lo em alguns arquivos de texto mais longos, então você pode ver que você começa a ter algum benefício em comprimir os arquivos. 

E então, finalmente, temos o nosso GDB velho amigo, que, certamente, vai vir a calhar também. 

Não temos qualquer dúvida em árvores Huff ou o processo talvez de fazer as árvores ou quaisquer outras perguntas sobre Puff Huff'n? Okay. Eu vou ficar em torno de um bit. 

Obrigado a todos. Este foi Walkthrough 6. E boa sorte. 

[CS50.TV]