Prefácio
Eu acho que amigos que aprenderam estruturas de dados devem conhecer Huffman. Este grande Deus inventou a famosa "árvore binária ideal". Para comemorá -lo, chamamos isso de "árvore de Huffman". A árvore do Huffman pode ser usada para a codificação de Huffman, e o conhecimento da codificação é muito grande, como compressão, criptografia, etc. Vamos dar uma olhada no que é a árvore do Huffman hoje.
conceito
Obviamente, uma das rotinas é que precisamos entender alguns conceitos básicos.
1. Comprimento do caminho: o caminho que forma os dois nós de um nó na árvore para outro nó. O número de ramificações no caminho é chamado de comprimento do caminho.
2. Comprimento do caminho da árvore: a soma dos comprimentos do caminho da raiz da árvore para cada nó. O que chamamos de árvore binária completa é o comprimento do caminho mais curto desse tipo.
3. O comprimento do caminho ponderado da árvore: se um valor ponderado for atribuído a cada nó foliar da árvore, o comprimento do caminho ponderado da árvore é igual à soma do produto do comprimento do caminho do nó raiz para todos os nós da folha e o peso do nó foliar.
Então, como determinamos se uma árvore é uma árvore binária ideal? Vamos dar uma olhada nas seguintes árvores:
Seus comprimentos de poder são:
WPL1: 7*2+5*2+2*2+4*2 = 36
WPL2: 7*3+5*3+2*1+4*2 = 46
WPL3: 7*1+5*2+2*3+4*3 = 35
É óbvio que a terceira árvore tem o caminho mais curto de peso (você não acredita, pode tentar. Se você encontrar um mais curto, provavelmente ganhará o prêmio Turing). É isso que chamamos de "Árvore Binária ideal (Hafman Tree)". Seu método de construção é muito simples. Você seleciona o nó com o menor peso e o coloca no fundo da árvore e coloca as duas menores conexões em um novo nó. Deve -se notar que o peso do novo nó formado deve ser igual à soma dos pesos desses dois nós. Em seguida, coloque este novo nó de volta no nó, onde precisamos formar a árvore para continuar classificando. Dessa forma, todos os nós com informações armazenadas na árvore Hafman estão nos nós da folha.
Depois de terminar o conceito, posso ser um pouco "pouco claro".
Vamos dar um exemplo para construí -lo claramente.
Há uma string: aaaaaaabbbbaaaaccccccccddddddfff
Na primeira etapa, contamos primeiro o número de vezes que cada caractere aparece e o chamamos de peso do personagem. A 15, B 5, C 8, D 6, F 3.
O segundo passo é encontrar os dois caracteres com o menor peso, B5 e F3, e construir o nó.
Em seguida, remova F3 e B5, agora A15, C8, D6, FB8.
Etapa 3, repita a segunda etapa até que apenas um nó seja restrito.
Agora é DFB14, A15, C8.
afinal,
OK, então nossa árvore de Huffman é construída.
Passos para construir
De acordo com a lógica acima, para resumir, existem algumas etapas:
1. Estatísticas o número de caracteres e caracteres que aparecem em uma string;
2. Crie nós de acordo com a estrutura da primeira etapa;
3. Classifique os pesos da ordem ascendente;
4. Retire os dois nós com o menor peso e gerar um novo nó pai;
5. Exclua os dois nós com o menor peso e armazene o nó pai na lista;
6. Repita a etapa 4 ou 5 até que haja um nó para a esquerda;
7. Atribua o último nó ao nó raiz.
Código Java
O princípio está concluído e a próxima etapa é implementar o código.
Primeiro, há uma classe de nó para armazenar dados.
pacote huffman;/** * classe de nó * @author yuxiu * */public class node {public string code; // codificação de hafman de nó public int codesize; // comprimento do nó Huffman codificando dados públicos de sequência; // dados do nó public int conting; // Nó o nó public node lcodild; nó público rchild; public node () {} public node (dados da string, int conting) {this.data = data; this.count = count; } nó público (int contagem, nó lchild, nó rchild) {this.count = count; this.lchild = lChild; this.rchild = rchild; } public node (dados da string, int conting, node lchild, node rchild) {this.data = data; this.count = count; this.lchild = lChild; this.rchild = rchild; }}Depois, há o processo de implementação.
pacote huffman; importar java.io.*; importar java.util.*; public class Huffman {private string str; // originalmente usado para string privada de compressão newstr = ""; // a string conectada por huffman codificando o nó privado raiz; // o nó raiz do huffman bininary binuss boble; Os caracteres são o mesmo caractere na mesma posição Private ArrayList <Node> Nodelist; // A fila para armazenar nós 15 16/ ** * Construa a árvore Huffman * * @param str */ public void Creathfmtree (String str) {this.str = str; Charlist = new ArrayList <String> (); Nodelist = new ArrayList <Node> (); // 1. Estatísticas O número de caracteres e caracteres que aparecem em uma string // A idéia básica é colocar uma corda não ordenada, como abababccdebed no charlist, que é aa, bbb, cc, dd, ee // e o comprimento da corda na lista é o peso correspondente para (int i = 0; i <str.l.lngth (); // Retire a bandeira do personagem = true; for (int j = 0; j <Charlist.size (); j ++) {if (charlist.get (j) .charat (0) == ch) {// se o mesmo caractere for encontrado string s = charlist.get (j)+ch; charlist.set (j, s); bandeira = false; quebrar; }} if (flag) {charlist.add (charlist.size (), ch + ""); }} // 2. Crie um nó de acordo com a estrutura da primeira etapa para (int i = 0; i <charlist.size (); i ++) {string data = charlist.get (i) .charat (0)+""; // Obtenha o primeiro caractere de cada string em Charlist int count = charlist.get (i) .Length (); // O comprimento da string na lista é o nó de peso correspondente = novo nó (dados, contagem); // crie o objeto nó nodelist.add (i, nó); // junte -se à fila do nó} // 3. Classificar (nodelista); enquanto (nodelist.size ()> 1) {// quando o número de nós é maior que um // 4. Retire os dois nós com o menor peso e gere um novo nó pai // 5. Exclua os dois nós com o menor peso e armazene o nó pai no nó da lista esquerda = nodelist.RemaVove (0); Nó direito = nodelist.remove (0); int parentweight = left.count + direito.count; // O peso do nó pai é igual à soma dos pesos do nó filho pai do nó = novo nó (peso -pai, esquerda, direita); Nodelist.add (0, pai); // Coloque o nó pai na primeira posição} // 6. Repita os quartos e quinto etapas para serem o loop while // 7. Atribua o último nó ao nó raiz raiz = nodelist.get (0); } / ** * Ordem ascendente * * @param nodelist * / public void Sort (ArrayList <Node> nodelist) {for (int i = 0; i <nodelist.size () - 1; i ++) {for (int j = i+1; j <nodelist.size (); j ++) {node; if (nodelist.get (i) .count> nodelist.get (j) .count) {temp = nodelist.get (i); Nodelist.set (i, nodelist.get (j)); Nodelist.set (J, Temp); }}}} / ** * Traversal * * @param node * node * / public void Output (nó nó) {if (node.lchild! = Null) {output (node.lchild); } System.out.print (node.count + ""); // travessal na ordem if (node.rchild! = Null) {output (node.rchild); }} public void output () {output (root); }/** * Método principal * * @param args */public static void main (string [] args) {huffman huff = new huffman (); // crie o objeto havalman huff.creathfmtree ("sdfassvvvdfgsfdfsdfs"); // construir a árvore}Resumir
O exposto acima tem tudo a ver com implementar a árvore Huffman baseada em Java. Espero que este artigo seja útil para que todos aprendam a usar o Java. Se você tiver alguma dúvida, deixe uma mensagem para discutir.