[ Principal | ] |
MAC 323 - 2003 |
Esse texto é uma tradução, com algumas modificações, do texto extraido da
seguinte página da Universidade de Waterloo:
http://www.student.math.uwaterloo.ca/~cs240/slides/class/L17.pdf
Preparado por: Sérgio Haruo Nakanishi
DEFINIÇÕES profundidade(ni) - o tamanho do caminho do nó ni até a raiz da árvore. peso(ni) - se ni for uma folha, o peso de ni é a frequência com que aparece a informação (letra) da folha ni, caso não seja uma folha o peso de ni é a soma dos pesos dos seus filhos. WPL(T) = somatória de (peso(ni) * profundidade(ni)), para cada FOLHA ni de uma árovre binária T (weighted path length) WPL(T) = função custo dado em aula. Árvore binária completa (ou cheia) - árvore binária onde todos seus nós tem 2 filhos, exceto as folhas que não tem filho. LEMA Seja qualquer árvore binária completa (ou cheia) com seus pesos associados às suas folhas. Suponha que n1 e n2 sejam as folhas com os menores pesos. Então podemos construir uma árvore T´ a partir de T tal que: 1. T´ possue as mesmas folhas que T exceto por n1 e n2, e T´ tem uma nova folha n3. 2. O peso de n3 é a soma de n1 e n2. O peso das outras folhas não mudam. 3. WPL(T´) <= WPL(T) - peso(n3). 4. WPL(T´) = WPL(T) - peso(n3), se n1 e n2 são irmãos em T. Agora pra provar que Huffman é ótimo: Seja T a árvore codificadora construida pelo algoritmo de Huffman a partir de um conjunto de nós (folhas). Se X é qualquer outra árvore codificadora com os mesmos nós, então WPL(T) <= WPL(X). A prova é feita por indução sobre o número de folhas de T: Caso base: T tem apenas duas folhas. A prova é trivial. Caso geral: Seja n1 e n2 os dois primeiros nós escolhidos pelo algoritmo de Huffman na construção de T. Aplique o lema em T e X para produzir T´ e X´. Como T foi construida pelo algoritmo de Huffman, n1 e n2 são nescessariamente irmãos em T. Então: (1) WPL(T´) = WPL(T) - peso(n1) - peso(n2). O Lema também garante que: (2) WPL(X´) <= WPL(X) - peso(n1) - peso(n2). Usando a indução, podemos afirmar que: (3) WPL(T´) <= WPL(X´) Pois: . T´ e X´ tem um nó a menos que T. (Lembrando indução: supondo que para n elementos é verdadeiro, provar que para n+1 elementos é verdadeiro. T tem n+1 elementos.) . T´ é equivalente à árvore construida pelo algoritmo de Huffman usando as folhas de T´. . T´ e X´ tem o mesmo número de folhas. Essas três inequações (1, 2 e 3) combinadas nos permite concluir que: WPL(T) <= WPL(X) O que completa nossa prova. [] (substituir a igualdade (1) pela parte da esquerda da desigualdade (3) e substituir a parte direita da desigualdade (2) pela parte da direita da desigualdade 3 não afeta a desigualdade (3))
[ Página inicial | Panda2 | Lista MAC323 | Lista Java | Info ] |