Huffman codificando introdução
Huffman A codificação lida com o problema de emparelhamento de codificação de caracteres e binário correspondente a caracteres, que é dividido em codificação e decodificação, com o objetivo de comprimir o comprimento dos dados binários correspondentes aos caracteres. Sabemos que quando os caracteres são armazenados e transferidos, eles são binários (o computador conhece apenas 0/1), então há uma relação de mapeamento entre caracteres e binários. Os caracteres pertencem ao conjunto de caracteres (charset). Os caracteres precisam ser armazenados e transmitidos em binário por codificação. Quando exibidos, eles precisam ser decodificados de volta aos caracteres. O conjunto de caracteres e os métodos de codificação são relacionamentos individuais (o Unicode pode ser codificado com UTF-8, UTF-16, etc.). Depois de entender o conjunto de personagens, codificação e decodificação, o problema do código ilegal voando por todo o céu pode ser facilmente resolvido. Tomando a minúscula A da letra em inglês como exemplo, na codificação ASCII, o decimal é 97 e o binário é 01100001. Cada caractere no ASCII é codificado com 8 bits (1byte). Se houver 1000 caracteres a serem transmitidos, 8000 bits devem ser transmitidos. O problema é que a frequência do uso da letra E em inglês é de 12,702%, enquanto Z é de 0,074%. O primeiro é mais de 100 vezes o deste último, mas usa binário com os mesmos dígitos. Isso pode ser feito melhor, o método é a codificação de comprimento variável. O princípio orientador é codificar a frequência mais alta com dígitos mais curtos e aqueles com baixa frequência com dígitos mais longos. O algoritmo de codificação de Huffman lida com esses problemas.
Huffman codificando a implementação de Java
As estruturas de dados usadas principalmente pelo algoritmo de codificação Huffman são árvores binárias completas e filas prioritárias. Este último usa java.util.priorityQueue, e o primeiro se implementa (todos são classes internas). O código é o seguinte:
Árvore de classe estática {raiz privada do nó; public node getRoot () {return root; } public void setroot (nó root) {this.root = root; }} classe estática nó implementa comparável <Node> {private string chars = ""; private int frequência = 0; Pai privado do nó; nó privado LeftNode; nó privado RightNode; @Override public int compareto (nó n) {frequência de retorno - n.frequency; } public boolean isleaf () {return char.length () == 1; } public boolean isroot () {return parent == null; } public boolean IsLeftchild () {return pai! = null && this == Parent.LeftNode; } public int getfrequence () {frequência de retorno; } public void setFrequence (int frequência) {this.frequency = frequência; } public string getchars () {return chars; } public void setchars (string chars) {this.chars = chars; } public node getParent () {return parent; } public void setParent (nó pai) {this.parent = pai; } public node getLeftNode () {return leftNode; } public void SetLeftNode (nó leftNode) {this.leftnode = leftNode; } public node getRightNode () {return RightNode; } public void SetrightNode (nó RightNode) {this.rightNode = RightNode; }} Estatística
Como a tabela de codificação precisa ser organizada de acordo com a frequência, é claro que você deve obter as informações estatísticas da frequência. Eu implementei um método para lidar com esse problema. Se já houver estatísticas, converta -se para mapear <caractere, número inteiro>. Se as informações obtidas forem uma porcentagem, multiplique por 100 ou 1000 ou 10000. Eles sempre podem ser convertidos em um número inteiro. Por exemplo, 12,702% multiplicados por 1000 é 12702, e Huffman codifica apenas se importa com problemas de tamanho. O método estatístico é implementado da seguinte maneira:
mapa estático público <caractere, número inteiro> estatística (char [] chararray) {map <caractere, número inteiro> map = new Hashmap <caractere, número inteiro> (); for (charc c: chararray) {personagem personagem = novo caractere (c); if (map.containsKey (caractere)) {map.put (caractere, map.get (caractere) + 1); } else {map.put (caractere, 1); }} retornar mapa; } Construindo uma árvore
Construir uma árvore é uma etapa central no algoritmo de codificação de Huffman. A idéia é pendurar todos os caracteres em um nó foliar de uma árvore completamente binária, e a frequência do nó esquerdo de qualquer nó infantil que não seja de página não apareça mais do que o nó direito. O algoritmo converte estatísticas em nós e os armazena em uma fila de prioridade. Cada vez que dois nós com a frequência mínima aparecem da fila, um novo nó pai (nó não folhas) é construído. A soma dos dois nós cujo conteúdo de personagem aparece, e a frequência também é a soma deles. O primeiro pop-up é usado como o nó da criança esquerda, e o próximo é usado como o nó da criança direita, e o nó pai recém-construído é colocado na fila. Repita as ações acima n-1 vezes, n é o número de caracteres diferentes (o número na fila é reduzido em 1 de cada vez). Termine as etapas acima, resta um nó na fila e o nó raiz da árvore aparece. O código é o seguinte:
Buildtree de árvore estática privada (mapa <caractere, número inteiro> estatística, list <nó> folhas) {caractere [] keys = statistics.keyset (). ToArray (novo caractere [0]); PriorityQueue <Node> priorityQueue = new priorityQueue <Node> (); para (caractere de caractere: chaves) {nó nó = new Node (); node.chars = caractere.toString (); node.frequency = statistics.get (caractere); priorityqueue.add (nó); folhas.add (nó); } int size = priorityQueue.size (); for (int i = 1; i <= size - 1; i ++) {node node1 = priorityQueue.poll (); Nó nó2 = priorityQueue.poll (); Nó sumnode = new Node (); sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightNode = node2; node1.parent = sumnode; node2.parent = sumnode; priorityQueue.add (sumnode); } Árvore árvore = new Tree (); árvore.root = priorityQueue.poll (); árvore de retorno; } codificação
A codificação correspondente de um personagem é pesquisar no nó foliar onde o caractere está localizado. Se o nó do caractere for o nó esquerdo do nó pai, adicione 0 antes do caractere codificado; caso contrário, se for o nó direito, adicione 1 até o nó raiz. Enquanto a relação de mapeamento entre os caracteres e o código binário for obtido, a codificação é muito simples. O código é o seguinte:
public static string cody (string origalaltr, map <caractere, número inteiro> estatísticas) {if (origaltaltr == null || origaltaltr.equals ("")) {return ""; } char [] CharArray = OriginStr.ToCharArray (); List <Node> leafnodes = new ArrayList <Node> (); BuildTree (Estatística, Leafnodes); Mapa <caractere, string> codinfo = buildEncodingInfo (leafnodes); StringBuffer buffer = new StringBuffer (); for (char c: chararray) {personagem personagem = novo caractere (c); buffer.append (codinfo.get (caractere)); } retornar buffer.toString (); } mapa estático privado <caractere, string> BuildEncodingInfo (List <Node> leafnodes) {map <caractere, string> codords = new hashmap <caractere, string> (); para (folhas do nó: folhas) {caractere de caractere = novo caractere (leafnode.getchars (). charat (0)); String codeWord = ""; Nó currentNode = folha; do {if (currentNode.isleftchild ()) {codeWord = "0" + CodEdord; } else {codeWord = "1" + Codordord; } currentNode = currentNode.parent; } while (currentNode.parent! = null); CODEWORDS.PUT (caracteres, palavra de código); } retornar palavras de código; } decodificação
Como o algoritmo de codificação do Huffman pode garantir que qualquer código binário não seja o prefixo de outro código, a decodificação é muito simples. Retire cada bit do binário em sequência, procure na raiz da árvore, 1 para a direita, 0 à esquerda, alcance o nó da folha (acerto) e retorne ao nó raiz e continue repetindo as ações acima. O código é o seguinte:
public static string decody (string binarystr, mapa <caractere, número inteiro> estatística) {if (binarystr == null || binarystr.equals ("")) {return ""; } char [] binaryCharArray = binarystr.toCharArray (); LinkedList <Acfaracter> binaryList = new LinkedList <Acfaracter> (); int size = binarycharArray.length; for (int i = 0; i <tamanho; i ++) {binaryList.addlast (novo caractere (binaryCharArray [i])); } Lista <Node> leafnodes = new ArrayList <Node> (); Árvore da árvore = BuildTree (estatística, folhas); StringBuffer buffer = new StringBuffer (); while (binaryList.size ()> 0) {nó nó = árvore.root; do {caractere c = binaryList.removefirst (); if (c.charValue () == '0') {node = node.leftnode; } else {node = node.rightNode; }} while (! node.isisAf ()); buffer.append (node.chars); } retornar buffer.toString (); } Teste e comparação
Os seguintes testes sobre a correção da codificação de Huffman (codificados primeiro, depois decodificados, incluindo chineses) e comparação de Huffman que codifica com cordas comuns que codificam seqüências binárias. O código é o seguinte:
public static void main (string [] args) {string oristr = "Os códigos de huffman compactam dados de maneira muito eficaz: a economia de 20% a 90% é típica" + ", dependendo das características dos dados que estão sendo compactados. A ascensão da China"; Mapa <caractere, número inteiro> estatística = estatística (orist.toCharArray ()); String codedbinaristr = cody (orist, estatística); String decodedstr = decoding (codedbinaristr, estatísticas); System.out.println ("String original:" + oristr); System.out.println ("Huffman encheu String binária:" + codedbinaristr); System.out.println ("string decodificada da string binariy:" + decodedstr); System.out.println ("String binária de UTF-8:" + getStringofbyte (orist, charset.formoname ("utf-8"))); System.out.println ("String binária de UTF-16:" + getStringofbyte (orist, charset.formoname ("utf-16"))); System.out.println ("String binária de US-ASCII:" + getStringOfbyte (orist, charset.formoname ("US-ascii"))); System.out.println ("String binária de GB2312:" + getStringOfbyte (ORIST, charset.formoname ("gb2312"))); } public static string getStringofbyte (string str, charset charset) {if (str == null || str.equals ("" ") {return" "; } byte [] byteArray = str.getBytes (charset); int size = bytearray.length; StringBuffer buffer = new StringBuffer (); for (int i = 0; i <tamanho; i ++) {byte temp = bytearray [i]; buffer.append (getStringOfbyte (temp)); } retornar buffer.toString (); } public static string getStringofbyte (byte b) {stringbuffer buffer = new StringBuffer (); for (int i = 7; i> = 0; i--) {byte temp = (byte) ((b >> i) e 0x1); buffer.append (string.valueof (temp)); } retornar buffer.toString (); }O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.