2.3Dados Simbólicos

Todos os objetos de dados compostos que usamos até agora foram construídos, em última instância, a partir de números. Nesta seção, estendemos a capacidade de representação de nossa linguagem, introduzindo a capacidade de trabalhar com símbolos arbitrários como dados.

2.3.1Citação

Se pudermos formar dados compostos usando símbolos, podemos ter listas como:

(a b c d)
(23 45 17)
((Norah 12) 
 (Molly 9) 
 (Anna 7) 
 (Lauren 6) 
 (Charlotte 4))

Listas contendo símbolos podem parecer exatamente como as expressões de nossa linguagem:

(* (+ 23 45) (+ x 9))
(define (fact n) 
  (if (= n 1) 
      1 
      (* n (fact (- n 1)))))

Para manipular símbolos, precisamos de um novo elemento em nossa linguagem: a capacidade de citar um objeto de dados. Suponha que queremos construir a lista (a b). Não podemos fazer isso com (list a b), porque essa expressão constrói uma lista dos valores de a e b em vez dos próprios símbolos. Esse problema é bem conhecido no contexto de linguagens naturais, onde palavras e frases podem ser consideradas como entidades semânticas ou como cadeias de caracteres (entidades sintáticas). A prática comum em linguagens naturais é usar aspas para indicar que uma palavra ou frase deve ser tratada literalmente como uma cadeia de caracteres. Por exemplo, a primeira letra de "John" é claramente "J". Se dissermos a alguém "diga seu nome em voz alta", esperamos ouvir o nome dessa pessoa. No entanto, se dissermos "diga 'seu nome' em voz alta", esperamos ouvir as palavras "seu nome". Observe que somos forçados a aninhar aspas para descrever o que outra pessoa pode dizer.⁹⁸

Podemos seguir a mesma prática para identificar listas e símbolos que devem ser tratados como objetos de dados, em vez de expressões a serem avaliadas. No entanto, nosso formato para citação difere daquele das linguagens naturais, pois colocamos uma marca de citação (tradicionalmente, o símbolo de aspas simples ') apenas no início do objeto a ser citado. Podemos fazer isso na sintaxe do Scheme porque dependemos de espaços e parênteses para delimitar objetos. Assim, o significado do caractere de aspas simples é citar o próximo objeto.⁹⁹

Agora podemos distinguir entre símbolos e seus valores:

(define a 1)
(define b 2)

(list a b)
(1 2)

(list 'a 'b)
(a b)

(list 'a b)
(a 2)

A citação também nos permite digitar objetos compostos, usando a representação impressa convencional para listas:¹⁰⁰

(car '(a b c))
a

(cdr '(a b c))
(b c)

De acordo com isso, podemos obter a lista vazia avaliando '(), e assim dispensar a variável nil.

Um primitivo adicional usado na manipulação de símbolos é eq?, que recebe dois símbolos como argumentos e testa se eles são iguais.¹⁰¹ Usando eq?, podemos implementar um procedimento útil chamado memq. Este procedimento recebe dois argumentos, um símbolo e uma lista. Se o símbolo não estiver contido na lista (ou seja, não for eq? a nenhum item da lista), então memq retorna falso. Caso contrário, ele retorna a sublista da lista começando com a primeira ocorrência do símbolo:

(define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))

Por exemplo, o valor de

(memq 'apple '(pear banana prune))

é falso, enquanto o valor de

(memq 'apple '(x (apple sauce) y apple pear))

é (apple pear).

Exercício 2.53: O que o interpretador imprimiria em resposta à avaliação de cada uma das seguintes expressões?

(list 'a 'b 'c)
(list (list 'george))
(cdr '((x1 x2) (y1 y2)))
(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))
(memq 'red '(red shoes blue socks))

Exercício 2.54: Duas listas são ditas equal? se contêm elementos iguais dispostos na mesma ordem. Por exemplo,

(equal? '(this is a list) 
        '(this is a list))

é verdadeiro, mas

(equal? '(this is a list) 
        '(this (is a) list))

é falso. Para ser mais preciso, podemos definir equal? recursivamente em termos da igualdade básica eq? de símbolos, dizendo que a e b são equal? se ambos são símbolos e os símbolos são eq?, ou se ambos são listas tais que (car a) é equal? a (car b) e (cdr a) é equal? a (cdr b). Usando essa ideia, implemente equal? como um procedimento.¹⁰²

Exercício 2.55: Eva Lu Ator digita no interpretador a expressão

(car ''abracadabra)

Para sua surpresa, o interpretador imprime quote. Explique.

2.3.2Exemplo: Diferenciação Simbólica

Como uma ilustração da manipulação de símbolos e uma nova ilustração da abstração de dados, considere o projeto de um procedimento que realiza a diferenciação simbólica de expressões algébricas. Gostaríamos que o procedimento recebesse como argumentos uma expressão algébrica e uma variável e retornasse a derivada da expressão em relação à variável. Por exemplo, se os argumentos para o procedimento forem $a{x}^2+bx+c$ e $x$, o procedimento deve retornar $2ax+b$. A diferenciação simbólica é de especial importância histórica em Lisp. Foi um dos exemplos motivadores por trás do desenvolvimento de uma linguagem de computador para manipulação de símbolos. Além disso, marcou o início de uma linha de pesquisa que levou ao desenvolvimento de sistemas poderosos para trabalhos matemáticos simbólicos, que atualmente são usados por um número crescente de matemáticos aplicados e físicos.

No desenvolvimento do programa de diferenciação simbólica, seguiremos a mesma estratégia de abstração de dados que seguimos no desenvolvimento do sistema de números racionais em 2.1.1. Ou seja, primeiro definiremos um algoritmo de diferenciação que opera em objetos abstratos como "somas", "produtos" e "variáveis" sem nos preocuparmos com como esses objetos são representados. Somente depois abordaremos o problema de representação.

O programa de diferenciação com dados abstratos

Para manter as coisas simples, consideraremos um programa de diferenciação simbólica muito simples que lida com expressões que são construídas usando apenas as operações de adição e multiplicação com dois argumentos. A diferenciação de qualquer expressão desse tipo pode ser realizada aplicando as seguintes regras de redução:

Observe que as duas últimas regras são recursivas por natureza. Ou seja, para obter a derivada de uma soma, primeiro encontramos as derivadas dos termos e as somamos. Cada um dos termos pode, por sua vez, ser uma expressão que precisa ser decomposta. A decomposição em partes cada vez menores eventualmente produzirá partes que são constantes ou variáveis, cujas derivadas serão 0 ou 1.

Para incorporar essas regras em um procedimento, nos permitimos um pouco de pensamento desejoso, como fizemos ao projetar a implementação de números racionais. Se tivéssemos uma maneira de representar expressões algébricas, deveríamos ser capazes de dizer se uma expressão é uma soma, um produto, uma constante ou uma variável. Deveríamos ser capazes de extrair as partes de uma expressão. Para uma soma, por exemplo, queremos ser capazes de extrair o adendo (primeiro termo) e o aumentando (segundo termo). Também deveríamos ser capazes de construir expressões a partir de partes. Vamos supor que já temos procedimentos para implementar os seguintes seletores, construtores e predicados:

(variable? e)          É e uma variável?
(same-variable? v1 v2) São v1 e v2 a mesma variável?
(sum? e)               É e uma soma?
(addend e)             Adendo da soma e.
(augend e)             Aumentando da soma e.
(make-sum a1 a2)       Constrói a soma de a1 e a2.
(product? e)           É e um produto?
(multiplier e)         Multiplicador do produto e.
(multiplicand e)       Multiplicando do produto e.
(make-product m1 m2)   Constrói o produto de m1 e m2.

Usando esses procedimentos e o predicado primitivo number?, que identifica números, podemos expressar as regras de diferenciação como o seguinte procedimento:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product 
           (multiplier exp)
           (deriv (multiplicand exp) var))
          (make-product 
           (deriv (multiplier exp) var)
           (multiplicand exp))))
        (else (error "unknown expression 
                      type: DERIV" exp))))

Este procedimento deriv incorpora o algoritmo completo de diferenciação. Como ele é expresso em termos de dados abstratos, ele funcionará independentemente de como escolhermos representar expressões algébricas, desde que projetemos um conjunto adequado de seletores e construtores. Este é o problema que devemos abordar a seguir.

Representando expressões algébricas

Podemos imaginar muitas maneiras de usar a estrutura de lista para representar expressões algébricas. Por exemplo, poderíamos usar listas de símbolos que espelham a notação algébrica usual, representando $ax+b$ como a lista (a * x + b). No entanto, uma escolha especialmente direta é usar a mesma notação prefixada entre parênteses que o Lisp usa para combinações; ou seja, representar $ax+b$ como (+ (* a x) b). Então, nossa representação de dados para o problema de diferenciação é a seguinte:

• As variáveis são símbolos. Elas são identificadas pelo predicado primitivo symbol?:

  (define (variable? x) (symbol? x))

• Duas variáveis são iguais se os símbolos que as representam são eq?:

  (define (same-variable? v1 v2)
    (and (variable? v1)
         (variable? v2)
         (eq? v1 v2)))

• Somas e produtos são construídos como listas:

  (define (make-sum a1 a2) (list '+ a1 a2))
  (define (make-product m1 m2) (list '* m1 m2))

• Uma soma é uma lista cujo primeiro elemento é o símbolo +:

  (define (sum? x)
    (and (pair? x) (eq? (car x) '+)))

• O adendo é o segundo item da lista de soma:

  (define (addend s) (cadr s))

• O aumentando é o terceiro item da lista de soma:

  (define (augend s) (caddr s))

• Um produto é uma lista cujo primeiro elemento é o símbolo *:

  (define (product? x)
    (and (pair? x) (eq? (car x) '*)))

• O multiplicador é o segundo item da lista de produto:

  (define (multiplier p) (cadr p))

• O multiplicando é o terceiro item da lista de produto:

  (define (multiplicand p) (caddr p))

Assim, precisamos apenas combinar esses procedimentos com o algoritmo incorporado em deriv para ter um programa de diferenciação simbólica funcional. Vamos ver alguns exemplos de seu comportamento:

(deriv '(+ x 3) 'x)
(+ 1 0)

(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
      (+  x 3)))

O programa produz respostas corretas; no entanto, elas não são simplificadas. É verdade que $$\frac{d(xy)}{dx}=x\cdot <!--\; \cdot \; -->0+1\cdot <!--\; \cdot \; -->y,$$ mas gostaríamos que o programa soubesse que $x\cdot <!--\; \cdot \; -->0=0$, $1\cdot <!--\; \cdot \; -->y=y$, e $0+y=y$. A resposta para o segundo exemplo deveria ter sido simplesmente y. Como o terceiro exemplo mostra, isso se torna um problema sério quando as expressões são complexas.

Nossa dificuldade é muito semelhante à que encontramos com a implementação de números racionais: não reduzimos as respostas à forma mais simples. Para realizar a redução de números racionais, precisamos mudar apenas os construtores e os seletores da implementação. Podemos adotar uma estratégia semelhante aqui. Não mudaremos deriv de forma alguma. Em vez disso, mudaremos make-sum para que, se ambos os somandos forem números, make-sum os some e retorne sua soma. Além disso, se um dos somandos for 0, então make-sum retornará o outro somando:

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) 
         (+ a1 a2))
        (else (list '+ a1 a2))))

Isso usa o procedimento =number?, que verifica se uma expressão é igual a um número dado:

(define (=number? exp num)
  (and (number? exp) (= exp num)))

Da mesma forma, mudaremos make-product para incorporar as regras de que 0 vezes qualquer coisa é 0 e 1 vezes qualquer coisa é a própria coisa:

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) 
             (=number? m2 0)) 
         0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) 
         (* m1 m2))
        (else (list '* m1 m2))))

Aqui está como esta versão funciona em nossos três exemplos:

(deriv '(+ x 3) 'x)
1

(deriv '(* x y) 'x)
y

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

Embora isso seja uma melhoria considerável, o terceiro exemplo mostra que ainda há um longo caminho a percorrer antes de obtermos um programa que coloque as expressões em uma forma que possamos concordar que é a "mais simples". O problema da simplificação algébrica é complexo porque, entre outras razões, uma forma que pode ser mais simples para um propósito pode não ser para outro.

Exercício 2.56: Mostre como estender o diferenciador básico para lidar com mais tipos de expressões. Por exemplo, implemente a regra de diferenciação $$\frac{d(u^n)}{dx}=n{u}^{n-<!--\; -\; -->1}\frac{du}{dx}$$ adicionando uma nova cláusula ao programa deriv e definindo os procedimentos apropriados exponentiation?, base, exponent e make-exponentiation. (Você pode usar o símbolo ** para denotar exponenciação.) Incorpore as regras de que qualquer coisa elevada à potência 0 é 1 e qualquer coisa elevada à potência 1 é a própria coisa.

Exercício 2.57: Estenda o programa de diferenciação para lidar com somas e produtos de um número arbitrário de (dois ou mais) termos. Então, o último exemplo acima poderia ser expresso como

(deriv '(* x y (+ x 3)) 'x)

Tente fazer isso mudando apenas a representação para somas e produtos, sem alterar o procedimento deriv. Por exemplo, o addend de uma soma seria o primeiro termo, e o augend seria a soma dos demais termos.

Exercício 2.58: Suponha que queiramos modificar o programa de diferenciação para que ele funcione com a notação matemática comum, na qual + e * são operadores infixos em vez de prefixos. Como o programa de diferenciação é definido em termos de dados abstratos, podemos modificá-lo para trabalhar com diferentes representações de expressões apenas alterando os predicados, seletores e construtores que definem a representação das expressões algébricas nas quais o diferenciador deve operar.

1. Mostre como fazer isso para diferenciar expressões algébricas apresentadas na forma infixa, como (x + (3 * (x + (y + 2)))). Para simplificar a tarefa, assuma que + e * sempre recebem dois argumentos e que as expressões são totalmente parentizadas.
2. O problema se torna substancialmente mais difícil se permitirmos a notação algébrica padrão, como (x + 3 * (x + y + 2)), que omite parênteses desnecessários e assume que a multiplicação é feita antes da adição. Você pode projetar predicados, seletores e construtores apropriados para essa notação de forma que nosso programa de derivada ainda funcione?

2.3.3Exemplo: Representando Conjuntos

Nos exemplos anteriores, construímos representações para dois tipos de objetos de dados compostos: números racionais e expressões algébricas. Em um desses exemplos, tivemos a escolha de simplificar (reduzir) as expressões no momento da construção ou no momento da seleção, mas, além disso, a escolha de uma representação para essas estruturas em termos de listas foi direta. Quando nos voltamos para a representação de conjuntos, a escolha de uma representação não é tão óbvia. De fato, há várias representações possíveis, e elas diferem significativamente umas das outras em vários aspectos.

Informalmente, um conjunto é simplesmente uma coleção de objetos distintos. Para dar uma definição mais precisa, podemos empregar o método de abstração de dados. Ou seja, definimos "conjunto" especificando as operações que devem ser usadas em conjuntos. Estas são union-set, intersection-set, element-of-set? e adjoin-set. Element-of-set? é um predicado que determina se um dado elemento é um membro de um conjunto. Adjoin-set recebe um objeto e um conjunto como argumentos e retorna um conjunto que contém os elementos do conjunto original e também o elemento adicionado. Union-set calcula a união de dois conjuntos, que é o conjunto contendo cada elemento que aparece em qualquer um dos argumentos. Intersection-set calcula a interseção de dois conjuntos, que é o conjunto contendo apenas elementos que aparecem em ambos os argumentos. Do ponto de vista da abstração de dados, somos livres para projetar qualquer representação que implemente essas operações de forma consistente com as interpretações dadas acima.¹⁰³

Conjuntos como listas não ordenadas

Uma maneira de representar um conjunto é como uma lista de seus elementos, na qual nenhum elemento aparece mais de uma vez. O conjunto vazio é representado pela lista vazia. Nessa representação, element-of-set? é semelhante ao procedimento memq de 2.3.1. Ele usa equal? em vez de eq? para que os elementos do conjunto não precisem ser símbolos:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

Usando isso, podemos escrever adjoin-set. Se o objeto a ser adicionado já estiver no conjunto, simplesmente retornamos o conjunto. Caso contrário, usamos cons para adicionar o objeto à lista que representa o conjunto:

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

Para intersection-set, podemos usar uma estratégia recursiva. Se soubermos como formar a interseção de set2 e o cdr de set1, só precisamos decidir se incluímos o car de set1 nisso. Mas isso depende de (car set1) também estar em set2. Aqui está o procedimento resultante:

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) 
         '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) 
                                 set2)))
        (else (intersection-set (cdr set1) 
                                set2))))

Em termos de eficiência, considere o número de passos necessários para nossas operações de conjunto. Como todas usam element-of-set?, a velocidade dessa operação tem um grande impacto na eficiência da implementação do conjunto como um todo. Agora, para verificar se um objeto é um membro de um conjunto, element-of-set? pode ter que percorrer todo o conjunto. (No pior caso, o objeto não está no conjunto.) Portanto, se o conjunto tiver $n$ elementos, element-of-set? pode levar até $n$ passos. Assim, o número de passos necessários cresce como $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. O número de passos necessários para adjoin-set, que usa essa operação, também cresce como $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Para intersection-set, que faz uma verificação element-of-set? para cada elemento de set1, o número de passos necessários cresce como o produto dos tamanhos dos conjuntos envolvidos, ou $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$ para dois conjuntos de tamanho $n$. O mesmo será verdadeiro para union-set.

Exercício 2.59: Implemente a operação union-set para a representação de conjuntos como listas não ordenadas.

Exercício 2.60: Especificamos que um conjunto seria representado como uma lista sem duplicatas. Agora, suponha que permitamos duplicatas. Por exemplo, o conjunto $\{1,2,3\}$ poderia ser representado como a lista (2 3 2 1 3 2 2). Projete procedimentos element-of-set?, adjoin-set, union-set e intersection-set que operem nessa representação. Como a eficiência de cada um se compara com o procedimento correspondente para a representação sem duplicatas? Existem aplicações para as quais você usaria essa representação em preferência à representação sem duplicatas?

Conjuntos como listas ordenadas

Uma maneira de acelerar nossas operações de conjunto é mudar a representação para que os elementos do conjunto sejam listados em ordem crescente. Para fazer isso, precisamos de alguma maneira de comparar dois objetos para dizer qual é maior. Por exemplo, poderíamos comparar símbolos lexicograficamente, ou poderíamos concordar em algum método para atribuir um número único a um objeto e então comparar os elementos comparando os números correspondentes. Para manter nossa discussão simples, consideraremos apenas o caso em que os elementos do conjunto são números, para que possamos comparar elementos usando > e <. Representaremos um conjunto de números listando seus elementos em ordem crescente. Enquanto nossa primeira representação acima nos permitia representar o conjunto $\{1,3,6,10\}$ listando os elementos em qualquer ordem, nossa nova representação permite apenas a lista (1 3 6 10).

Uma vantagem da ordenação aparece em element-of-set?: Ao verificar a presença de um item, não precisamos mais percorrer todo o conjunto. Se chegarmos a um elemento do conjunto que é maior que o item que estamos procurando, sabemos que o item não está no conjunto:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

Quantos passos isso economiza? No pior caso, o item que estamos procurando pode ser o maior do conjunto, então o número de passos é o mesmo que para a representação não ordenada. Por outro lado, se procurarmos itens de muitos tamanhos diferentes, podemos esperar que às vezes possamos parar a busca perto do início da lista e que outras vezes ainda precisaremos examinar a maior parte da lista. Em média, devemos esperar ter que examinar cerca de metade dos itens do conjunto. Assim, o número médio de passos necessários será cerca de $n/2$. Isso ainda é crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(n)$, mas nos economiza, em média, um fator de 2 no número de passos em relação à implementação anterior.

Obtemos uma aceleração mais impressionante com intersection-set. Na representação não ordenada, essa operação exigia $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$ passos, porque realizamos uma varredura completa de set2 para cada elemento de set1. Mas com a representação ordenada, podemos usar um método mais inteligente. Comece comparando os elementos iniciais, x1 e x2, dos dois conjuntos. Se x1 for igual a x2, isso dá um elemento da interseção, e o resto da interseção é a interseção dos cdr-s dos dois conjuntos. Suponha, no entanto, que x1 seja menor que x2. Como x2 é o menor elemento em set2, podemos concluir imediatamente que x1 não pode aparecer em set2 e, portanto, não está na interseção. Portanto, a interseção é igual à interseção de set2 com o cdr de set1. Da mesma forma, se x2 for menor que x1, a interseção é dada pela interseção de set1 com o cdr de set2. Aqui está o procedimento:

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1 (intersection-set 
                         (cdr set1)
                         (cdr set2))))
              ((< x1 x2) (intersection-set 
                          (cdr set1) 
                          set2))
              ((< x2 x1) (intersection-set 
                          set1 
                          (cdr set2)))))))

Para estimar o número de passos necessários por esse processo, observe que a cada passo reduzimos o problema de interseção ao cálculo de interseções de conjuntos menores—removendo o primeiro elemento de set1 ou set2 ou ambos. Assim, o número de passos necessários é no máximo a soma dos tamanhos de set1 e set2, em vez do produto dos tamanhos como na representação não ordenada. Isso é crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ em vez de $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$—uma aceleração considerável, mesmo para conjuntos de tamanho moderado.

Exercício 2.61: Dê uma implementação de adjoin-set usando a representação ordenada. Por analogia com element-of-set?, mostre como tirar vantagem da ordenação para produzir um procedimento que requer, em média, cerca de metade do número de passos em relação à representação não ordenada.

Exercício 2.62: Dê uma implementação $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ de union-set para conjuntos representados como listas ordenadas.

Conjuntos como árvores binárias

Podemos fazer melhor que a representação de lista ordenada, organizando os elementos do conjunto na forma de uma árvore. Cada nó da árvore contém um elemento do conjunto, chamado de "entrada" naquele nó, e um link para cada um de dois outros (possivelmente vazios) nós. O link "esquerdo" aponta para elementos menores que o do nó, e o link "direito" aponta para elementos maiores que o do nó. Figura 2.16 mostra algumas árvores que representam o conjunto $\{1,3,5,7,9,11\}$. O mesmo conjunto pode ser representado por uma árvore de várias maneiras diferentes. A única coisa que exigimos para uma representação válida é que todos os elementos na subárvore esquerda sejam menores que a entrada do nó e que todos os elementos na subárvore direita sejam maiores.

A vantagem da representação em árvore é a seguinte: Suponha que queremos verificar se um número $x$ está contido em um conjunto. Começamos comparando $x$ com a entrada no nó superior. Se $x$ for menor que isso, sabemos que precisamos apenas procurar na subárvore esquerda; se $x$ for maior, precisamos apenas procurar na subárvore direita. Agora, se a árvore estiver "balanceada", cada uma dessas subárvores terá cerca de metade do tamanho da árvore original. Assim, em um passo, reduzimos o problema de procurar em uma árvore de tamanho $n$ para procurar em uma árvore de tamanho $n/2$. Como o tamanho da árvore é reduzido à metade a cada passo, devemos esperar que o número de passos necessários para procurar em uma árvore de tamanho $n$ cresça como $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$.¹⁰⁴ Para grandes conjuntos, isso será uma aceleração significativa em relação às representações anteriores.

Podemos representar árvores usando listas. Cada nó será uma lista de três itens: a entrada no nó, a subárvore esquerda e a subárvore direita. Uma subárvore esquerda ou direita da lista vazia indicará que não há subárvore conectada lá. Podemos descrever essa representação pelos seguintes procedimentos:¹⁰⁵

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

Agora podemos escrever o procedimento element-of-set? usando a estratégia descrita acima:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? 
          x 
          (left-branch set)))
        ((> x (entry set))
         (element-of-set? 
          x 
          (right-branch set)))))

Adicionar um item a um conjunto é implementado de forma semelhante e também requer $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ passos. Para adicionar um item x, comparamos x com a entrada do nó para determinar se x deve ser adicionado ao ramo direito ou ao ramo esquerdo, e tendo adicionado x ao ramo apropriado, juntamos esse ramo recém-construído com a entrada original e o outro ramo. Se x for igual à entrada, simplesmente retornamos o nó. Se nos pedirem para adicionar x a uma árvore vazia, geramos uma árvore que tem x como entrada e ramos esquerdo e direito vazios. Aqui está o procedimento:

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree 
          (entry set)
          (adjoin-set x (left-branch set))
          (right-branch set)))
        ((> x (entry set))
         (make-tree
          (entry set)
          (left-branch set)
          (adjoin-set x (right-branch set))))))

A afirmação acima de que a procura na árvore pode ser realizada em um número logarítmico de passos depende da suposição de que a árvore está "balanceada", ou seja, que as subárvores esquerda e direita de cada árvore têm aproximadamente o mesmo número de elementos, de modo que cada subárvore contém cerca de metade dos elementos de seu pai. Mas como podemos ter certeza de que as árvores que construímos estarão balanceadas? Mesmo que comecemos com uma árvore balanceada, adicionar elementos com adjoin-set pode produzir um resultado desbalanceado. Como a posição de um elemento recém-adicionado depende de como o elemento se compara com os itens já no conjunto, podemos esperar que, se adicionarmos elementos "aleatoriamente", a árvore tenderá a ser balanceada em média. Mas isso não é uma garantia. Por exemplo, se começarmos com um conjunto vazio e adicionarmos os números de 1 a 7 em sequência, terminaremos com a árvore altamente desbalanceada mostrada em Figura 2.17. Nessa árvore, todas as subárvores esquerdas estão vazias, então ela não tem vantagem sobre uma simples lista ordenada. Uma maneira de resolver esse problema é definir uma operação que transforma uma árvore arbitrária em uma árvore balanceada com os mesmos elementos. Então, podemos realizar essa transformação após cada poucas operações adjoin-set para manter nosso conjunto em equilíbrio. Há também outras maneiras de resolver esse problema, a maioria das quais envolve projetar novas estruturas de dados para as quais a procura e a inserção podem ser feitas em $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ passos.¹⁰⁶

Exercício 2.63: Cada um dos dois procedimentos a seguir converte uma árvore binária em uma lista.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append 
       (tree->list-1 
        (left-branch tree))
       (cons (entry tree)
             (tree->list-1 
              (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list 
         (left-branch tree)
         (cons (entry tree)
               (copy-to-list 
                (right-branch tree)
                result-list)))))
  (copy-to-list tree '()))

1. Os dois procedimentos produzem o mesmo resultado para toda árvore? Se não, como os resultados diferem? Que listas os dois procedimentos produzem para as árvores em Figura 2.16?
2. Os dois procedimentos têm a mesma ordem de crescimento no número de passos necessários para converter uma árvore balanceada com $n$ elementos em uma lista? Se não, qual cresce mais lentamente?

Exercício 2.64: O seguinte procedimento list->tree converte uma lista ordenada em uma árvore binária balanceada. O procedimento auxiliar partial-tree recebe como argumentos um inteiro $n$ e uma lista de pelo menos $n$ elementos e constrói uma árvore balanceada contendo os primeiros $n$ elementos da lista. O resultado retornado por partial-tree é um par (formado com cons) cujo car é a árvore construída e cujo cdr é a lista de elementos não incluídos na árvore.

(define (list->tree elements)
  (car (partial-tree 
        elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size 
             (quotient (- n 1) 2)))
        (let ((left-result 
               (partial-tree 
                elts left-size)))
          (let ((left-tree 
                 (car left-result))
                (non-left-elts 
                 (cdr left-result))
                (right-size 
                 (- n (+ left-size 1))))
            (let ((this-entry 
                   (car non-left-elts))
                  (right-result 
                   (partial-tree 
                    (cdr non-left-elts)
                    right-size)))
              (let ((right-tree 
                     (car right-result))
                    (remaining-elts 
                     (cdr right-result)))
                (cons (make-tree this-entry 
                                 left-tree 
                                 right-tree)
                      remaining-elts))))))))

1. Escreva um parágrafo curto explicando o mais claramente possível como partial-tree funciona. Desenhe a árvore produzida por list->tree para a lista (1 3 5 7 9 11).
2. Qual é a ordem de crescimento no número de passos necessários para list->tree converter uma lista de $n$ elementos?

Exercício 2.65: Use os resultados de Exercício 2.63 e Exercício 2.64 para dar implementações $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ de union-set e intersection-set para conjuntos implementados como árvores binárias (balanceadas).¹⁰⁷

Conjuntos e recuperação de informação

Examinamos opções para usar listas para representar conjuntos e vimos como a escolha da representação para um objeto de dados pode ter um grande impacto no desempenho dos programas que usam os dados. Outra razão para nos concentrarmos em conjuntos é que as técnicas discutidas aqui aparecem repetidamente em aplicações envolvendo recuperação de informação.

Considere um banco de dados contendo um grande número de registros individuais, como os arquivos de pessoal de uma empresa ou as transações em um sistema de contabilidade. Um sistema típico de gerenciamento de dados passa uma grande quantidade de tempo acessando ou modificando os dados nos registros e, portanto, requer um método eficiente para acessar os registros. Isso é feito identificando uma parte de cada registro para servir como uma chave identificadora. Uma chave pode ser qualquer coisa que identifique exclusivamente o registro. Para um arquivo de pessoal, pode ser o número de identificação de um funcionário. Para um sistema de contabilidade, pode ser um número de transação. Seja qual for a chave, quando definimos o registro como uma estrutura de dados, devemos incluir um procedimento seletor key que recupera a chave associada a um determinado registro.

Agora representamos o banco de dados como um conjunto de registros. Para localizar o registro com uma determinada chave, usamos um procedimento lookup, que recebe como argumentos uma chave e um banco de dados e retorna o registro que tem essa chave, ou falso se não houver tal registro. Lookup é implementado de forma muito semelhante a element-of-set?. Por exemplo, se o conjunto de registros for implementado como uma lista não ordenada, poderíamos usar:

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key 
                 (key (car set-of-records)))
         (car set-of-records))
        (else 
         (lookup given-key 
                 (cdr set-of-records)))))

Claro, há maneiras melhores de representar grandes conjuntos do que como listas não ordenadas. Sistemas de recuperação de informação em que os registros precisam ser "acessados aleatoriamente" são tipicamente implementados por um método baseado em árvores, como a representação de árvore binária discutida anteriormente. Ao projetar tal sistema, a metodologia de abstração de dados pode ser de grande ajuda. O projetista pode criar uma implementação inicial usando uma representação simples e direta, como listas não ordenadas. Isso será inadequado para o sistema eventual, mas pode ser útil para fornecer um banco de dados "rápido e sujo" com o qual testar o resto do sistema. Posteriormente, a representação de dados pode ser modificada para ser mais sofisticada. Se o banco de dados for acessado em termos de seletores e construtores abstratos, essa mudança de representação não exigirá nenhuma alteração no resto do sistema.

Exercício 2.66: Implemente o procedimento lookup para o caso em que o conjunto de registros é estruturado como uma árvore binária, ordenada pelos valores numéricos das chaves.

2.3.4Exemplo: Árvores de Codificação de Huffman

Esta seção fornece prática no uso de estrutura de lista e abstração de dados para manipular conjuntos e árvores. A aplicação é a métodos para representar dados como sequências de uns e zeros (bits). Por exemplo, o código padrão ASCII usado para representar texto em computadores codifica cada caractere como uma sequência de sete bits. Usar sete bits nos permite distinguir $2^7$, ou 128, caracteres diferentes possíveis. Em geral, se quisermos distinguir $n$ símbolos diferentes, precisaremos usar ${\log }_2<!--\; \; -->n$ bits por símbolo. Se todas as nossas mensagens forem compostas pelos oito símbolos A, B, C, D, E, F, G e H, podemos escolher um código com três bits por caractere, por exemplo:

A 000  C 010  E 100  G 110
B 001  D 011  F 101  H 111

Com esse código, a mensagem

BACADAEAFABBAAAGAH

é codificada como a string de 54 bits

001000010000011000100000101
000001001000000000110000111

Códigos como ASCII e o código de A a H acima são conhecidos como códigos de comprimento fixo, porque representam cada símbolo na mensagem com o mesmo número de bits. Às vezes, é vantajoso usar códigos de comprimento variável, nos quais diferentes símbolos podem ser representados por diferentes números de bits. Por exemplo, o código Morse não usa o mesmo número de pontos e traços para cada letra do alfabeto. Em particular, E, a letra mais frequente, é representada por um único ponto. Em geral, se nossas mensagens forem tais que alguns símbolos apareçam muito frequentemente e outros muito raramente, podemos codificar os dados de forma mais eficiente (ou seja, usando menos bits por mensagem) se atribuirmos códigos mais curtos aos símbolos frequentes. Considere o seguinte código alternativo para as letras de A a H:

A 0    C 1010  E 1100  G 1110
B 100  D 1011  F 1101  H 1111

Com esse código, a mesma mensagem acima é codificada como a string

100010100101101100011
010100100000111001111

Essa string contém 42 bits, então economiza mais de 20% em espaço em comparação com o código de comprimento fixo mostrado acima.

Uma das dificuldades de usar um código de comprimento variável é saber quando chegamos ao final de um símbolo ao ler uma sequência de zeros e uns. O código Morse resolve esse problema usando um código separador especial (neste caso, uma pausa) após a sequência de pontos e traços para cada letra. Outra solução é projetar o código de forma que nenhum código completo para qualquer símbolo seja o início (ou prefixo) do código para outro símbolo. Esse código é chamado de código de prefixo. No exemplo acima, A é codificado por 0 e B é codificado por 100, então nenhum outro símbolo pode ter um código que comece com 0 ou com 100.

Em geral, podemos obter economias significativas se usarmos códigos de prefixo de comprimento variável que levem em consideração as frequências relativas dos símbolos nas mensagens a serem codificadas. Um esquema particular para fazer isso é chamado de método de codificação de Huffman, em homenagem ao seu descobridor, David Huffman. Um código de Huffman pode ser representado como uma árvore binária cujas folhas são os símbolos que são codificados. Em cada nó não folha da árvore há um conjunto contendo todos os símbolos nas folhas que estão abaixo do nó. Além disso, cada símbolo em uma folha é atribuído a um peso (que é sua frequência relativa), e cada nó não folha contém um peso que é a soma de todos os pesos das folhas abaixo dele. Os pesos não são usados no processo de codificação ou decodificação. Veremos abaixo como eles são usados para ajudar a construir a árvore.

Figura 2.18 mostra a árvore de Huffman para o código de A a H dado acima. Os pesos nas folhas indicam que a árvore foi projetada para mensagens em que A aparece com frequência relativa 8, B com frequência relativa 3, e as outras letras cada uma com frequência relativa 1.

Dada uma árvore de Huffman, podemos encontrar a codificação de qualquer símbolo começando na raiz e descendo até atingirmos a folha que contém o símbolo. Cada vez que descemos por um ramo esquerdo, adicionamos um 0 ao código, e cada vez que descemos por um ramo direito, adicionamos um 1. (Decidimos qual ramo seguir testando para ver qual ramo é o nó folha para o símbolo ou contém o símbolo em seu conjunto.) Por exemplo, começando na raiz da árvore em Figura 2.18, chegamos à folha para D seguindo um ramo direito, depois um ramo esquerdo, depois um ramo direito, depois um ramo direito; portanto, o código para D é 1011.

Para decodificar uma sequência de bits usando uma árvore de Huffman, começamos na raiz e usamos os zeros e uns sucessivos da sequência de bits para determinar se devemos descer pelo ramo esquerdo ou pelo ramo direito. Cada vez que chegamos a uma folha, geramos um novo símbolo na mensagem, momento em que começamos novamente na raiz da árvore para encontrar o próximo símbolo. Por exemplo, suponha que recebamos a árvore acima e a sequência 10001010. Começando na raiz, descemos pelo ramo direito (já que o primeiro bit da string é 1), depois pelo ramo esquerdo (já que o segundo bit é 0), depois pelo ramo esquerdo (já que o terceiro bit também é 0). Isso nos leva à folha para B, então o primeiro símbolo da mensagem decodificada é B. Agora começamos novamente na raiz, e fazemos um movimento para a esquerda porque o próximo bit na string é 0. Isso nos leva à folha para A. Então começamos novamente na raiz com o restante da string 1010, então movemos para a direita, esquerda, direita, esquerda e chegamos a C. Assim, a mensagem inteira é BAC.

Gerando árvores de Huffman

Dado um “alfabeto” de símbolos e suas frequências relativas, como podemos construir o “melhor” código? (Em outras palavras, qual árvore codificará mensagens com o menor número de bits?) Huffman forneceu um algoritmo para fazer isso e mostrou que o código resultante é de fato o melhor código de comprimento variável para mensagens onde a frequência relativa dos símbolos corresponde às frequências com as quais o código foi construído. Não vamos provar essa otimalidade dos códigos de Huffman aqui, mas vamos mostrar como as árvores de Huffman são construídas.¹⁰⁸

O algoritmo para gerar uma árvore de Huffman é muito simples. A ideia é organizar a árvore de forma que os símbolos com a menor frequência apareçam mais distantes da raiz. Comece com o conjunto de nós folha, contendo símbolos e suas frequências, conforme determinado pelos dados iniciais a partir dos quais o código será construído. Agora, encontre duas folhas com os menores pesos e una-as para produzir um nó que tenha esses dois nós como seus ramos esquerdo e direito. O peso do novo nó é a soma dos dois pesos. Remova as duas folhas do conjunto original e substitua-as por este novo nó. Agora, continue esse processo. A cada passo, una dois nós com os menores pesos, removendo-os do conjunto e substituindo-os por um nó que tenha esses dois como seus ramos esquerdo e direito. O processo para quando houver apenas um nó restante, que é a raiz de toda a árvore. Aqui está como a árvore de Huffman da Figura 2.18 foi gerada:

Inicial {(A 8) (B 3) (C 1) (D 1) 
folhas   (E 1) (F 1) (G 1) (H 1)}

União   {(A 8) (B 3) ({C D} 2) 
         (E 1) (F 1) (G 1) (H 1)}

União   {(A 8) (B 3) ({C D} 2) 
         ({E F} 2) (G 1) (H 1)}

União   {(A 8) (B 3) ({C D} 2) 
         ({E F} 2) ({G H} 2)}

União   {(A 8) (B 3) ({C D} 2) 
         ({E F G H} 4)}

União   {(A 8) ({B C D} 5) 
         ({E F G H} 4)}

União   {(A 8) ({B C D E F G H} 9)}

Final   {({A B C D E F G H} 17)}
união    

O algoritmo nem sempre especifica uma árvore única, porque pode não haver nós de menor peso únicos em cada passo. Além disso, a escolha da ordem em que os dois nós são unidos (ou seja, qual será o ramo direito e qual será o ramo esquerdo) é arbitrária.

Representando árvores de Huffman

Nos exercícios abaixo, trabalharemos com um sistema que usa árvores de Huffman para codificar e decodificar mensagens e gera árvores de Huffman de acordo com o algoritmo descrito acima. Começaremos discutindo como as árvores são representadas.

As folhas da árvore são representadas por uma lista consistindo do símbolo leaf, o símbolo na folha e o peso:

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

Uma árvore geral será uma lista de um ramo esquerdo, um ramo direito, um conjunto de símbolos e um peso. O conjunto de símbolos será simplesmente uma lista dos símbolos, em vez de uma representação de conjunto mais sofisticada. Quando fazemos uma árvore unindo dois nós, obtemos o peso da árvore como a soma dos pesos dos nós, e o conjunto de símbolos como a união dos conjuntos de símbolos para os nós. Como nossos conjuntos de símbolos são representados como listas, podemos formar a união usando o procedimento append que definimos em 2.2.1:

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) 
                (symbols right))
        (+ (weight left) (weight right))))

Se fizermos uma árvore dessa forma, teremos os seguintes seletores:

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))

(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

Os procedimentos symbols e weight devem fazer algo ligeiramente diferente dependendo de serem chamados com uma folha ou uma árvore geral. Estes são exemplos simples de procedimentos genéricos (procedimentos que podem lidar com mais de um tipo de dados), sobre os quais teremos muito mais a dizer em 2.4 e 2.5.

O procedimento de decodificação

O seguinte procedimento implementa o algoritmo de decodificação. Ele toma como argumentos uma lista de zeros e uns, junto com uma árvore de Huffman.

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch 
                (car bits) 
                current-branch)))
          (if (leaf? next-branch)
              (cons 
               (symbol-leaf next-branch)
               (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) 
                        next-branch)))))
  (decode-1 bits tree))

(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit: 
               CHOOSE-BRANCH" bit))))

O procedimento decode-1 toma dois argumentos: a lista de bits restantes e a posição atual na árvore. Ele continua se movendo “para baixo” na árvore, escolhendo um ramo esquerdo ou direito de acordo com se o próximo bit na lista é zero ou um. (Isso é feito com o procedimento choose-branch.) Quando ele atinge uma folha, retorna o símbolo naquela folha como o próximo símbolo na mensagem, colocando-o no resultado da decodificação do restante da mensagem, começando na raiz da árvore. Observe a verificação de erro na cláusula final de choose-branch, que reclama se o procedimento encontrar algo diferente de zero ou um nos dados de entrada.

Conjuntos de elementos ponderados

Em nossa representação de árvores, cada nó não folha contém um conjunto de símbolos, que representamos como uma lista simples. No entanto, o algoritmo de geração de árvores discutido acima requer que também trabalhemos com conjuntos de folhas e árvores, unindo sucessivamente os dois itens de menor peso. Como precisaremos repetidamente encontrar o item de menor peso em um conjunto, é conveniente usar uma representação ordenada para esse tipo de conjunto.

Representaremos um conjunto de folhas e árvores como uma lista de elementos, organizada em ordem crescente de peso. O seguinte procedimento adjoin-set para construir conjuntos é semelhante ao descrito em Exercício 2.61; no entanto, os itens são comparados por seus pesos, e o elemento sendo adicionado ao conjunto nunca está já nele.

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) 
         (cons x set))
        (else 
         (cons (car set)
               (adjoin-set x (cdr set))))))

O seguinte procedimento toma uma lista de pares símbolo-frequência, como ((A 4) (B 2) (C 1) (D 1)) e constrói um conjunto ordenado inicial de folhas, pronto para ser unido de acordo com o algoritmo de Huffman:

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set 
         (make-leaf (car pair)    ; símbolo
                    (cadr pair))  ; frequência
         (make-leaf-set (cdr pairs))))))

Exercício 2.67: Defina uma árvore de codificação e uma mensagem de exemplo:

(define sample-tree
  (make-code-tree 
   (make-leaf 'A 4)
   (make-code-tree
    (make-leaf 'B 2)
    (make-code-tree 
     (make-leaf 'D 1)
     (make-leaf 'C 1)))))

(define sample-message 
  '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Use o procedimento decode para decodificar a mensagem e dê o resultado.

Exercício 2.68: O procedimento encode toma como argumentos uma mensagem e uma árvore e produz a lista de bits que fornece a mensagem codificada.

(define (encode message tree)
  (if (null? message)
      '()
      (append 
       (encode-symbol (car message) 
                      tree)
       (encode (cdr message) tree))))

Encode-symbol é um procedimento, que você deve escrever, que retorna a lista de bits que codifica um determinado símbolo de acordo com uma determinada árvore. Você deve projetar encode-symbol de forma que ele sinalize um erro se o símbolo não estiver na árvore. Teste seu procedimento codificando o resultado que você obteve em Exercício 2.67 com a árvore de exemplo e veja se é o mesmo que a mensagem de exemplo original.

Exercício 2.69: O seguinte procedimento toma como seu argumento uma lista de pares símbolo-frequência (onde nenhum símbolo aparece em mais de um par) e gera uma árvore de codificação de Huffman de acordo com o algoritmo de Huffman.

(define (generate-huffman-tree pairs)
  (successive-merge 
   (make-leaf-set pairs)))

Make-leaf-set é o procedimento dado acima que transforma a lista de pares em um conjunto ordenado de folhas. Successive-merge é o procedimento que você deve escrever, usando make-code-tree para unir sucessivamente os elementos de menor peso do conjunto até que reste apenas um elemento, que é a árvore de Huffman desejada. (Este procedimento é um pouco complicado, mas não realmente complexo. Se você se encontrar projetando um procedimento complexo, então você está quase certamente fazendo algo errado. Você pode tirar vantagem significativa do fato de que estamos usando uma representação de conjunto ordenado.)

Exercício 2.70: O seguinte alfabeto de oito símbolos com frequências relativas associadas foi projetado para codificar eficientemente as letras das músicas de rock dos anos 1950. (Observe que os “símbolos” de um “alfabeto” não precisam ser letras individuais.)

A    2    NA  16
BOOM 1    SHA  3
GET  2    YIP  9
JOB  2    WAH  1

Use generate-huffman-tree (Exercício 2.69) para gerar uma árvore de Huffman correspondente, e use encode (Exercício 2.68) para codificar a seguinte mensagem:

Get a job
Sha na na na na na na na na

Get a job
Sha na na na na na na na na

Wah yip yip yip yip 
yip yip yip yip yip
Sha boom

Quantos bits são necessários para a codificação? Qual é o menor número de bits que seriam necessários para codificar essa música se usássemos um código de comprimento fixo para o alfabeto de oito símbolos?

Exercício 2.71: Suponha que temos uma árvore de Huffman para um alfabeto de $n$ símbolos, e que as frequências relativas dos símbolos são $1,2,4,\dots <!--\; \dots \; -->,2^{n-<!--\; -\; -->1}$. Esboce a árvore para $n=5$; para $n=10$. Em tal árvore (para geral $n$) quantos bits são necessários para codificar o símbolo mais frequente? O símbolo menos frequente?

Exercício 2.72: Considere o procedimento de codificação que você projetou em Exercício 2.68. Qual é a ordem de crescimento no número de passos necessários para codificar um símbolo? Certifique-se de incluir o número de passos necessários para pesquisar a lista de símbolos em cada nó encontrado. Responder a essa pergunta em geral é difícil. Considere o caso especial onde as frequências relativas dos $n$ símbolos são como descrito em Exercício 2.71, e dê a ordem de crescimento (como uma função de $n$) do número de passos necessários para codificar o símbolo mais frequente e o menos frequente no alfabeto.