Huffman coding: Difference between revisions

{{task|Compression}}

Huffman encoding is a way to assign binary codes to symbols that reduces the overall number of bits used to encode a typical string of those symbols.

 

# The remaining node is the root node and the tree is complete.

 

Traverse the constructed binary tree from root to leaves assigning and accumulating a '0' for one branch and a '1' for the other at each node. The accumulated zeros and ones at each leaf constitute a Huffman encoding for those symbols and weights:

 

 

=={{header|Ada}}==

 

huffman.ads:

with Ada.Containers.Ordered_Maps;

with Ada.Finalization;

-- free memory after finalization

overriding procedure Finalize (Object : in out Huffman_Tree);

 

huffman.adb:

with Ada.Unchecked_Deallocation;

with Ada.Containers.Vectors;

end loop;

end Dump_Encoding;

 

example main.adb:

with Huffman;

procedure Main is

(Char_Natural_Huffman_Tree.Decode (Tree => Tree, Code => Code));

end;

 

<pre> = 101

a = 1001

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

SortUp% = FN_sortSAinit(0,0) : REM Ascending

SortDn% = FN_sortSAinit(1,0) : REM Descending

ENDIF

NEXT

<pre>

101

t 11010

</pre>

=={{header|Bracmat}}==

& 0:?chars

& 0:?p

| !arg

)

<pre>(L=

(" ".101)

decoded: this is an example for huffman encoding

</pre>

=={{header|C}}==

 

This code lacks a lot of needed checkings, especially for memory allocation.

 

#include <stdlib.h>

#include <string.h>

 

return 0;

===Alternative===

Using a simple heap-based priority queue. Heap is an array, while ndoe tree is done by binary links.

#include <string.h>

 

{

int i;

 

init(str);

 

return 0;

'a': 1000

'c': 01101

'x': 01001

encoded: 0111111010011110000000111100000100010100001010100110001111100110100010101000001011101001000011010111000100010111110001010000101101011011110011000011101010000

=={{header|C sharp}}==

using System.Collections.Generic;

 

}

}

 

=={{header|C++}}==

This code builds a tree to generate huffman codes, then prints the codes.

 

#include <queue>

#include <map>

}

return 0;

 

<pre> 110

a 1001

 

=={{header|Clojure}}==

 

(into {} (map (fn [[k v]] [k (/ v sum)]) freqs))))

 

(defn huffman-tree [pq]

(while (> (.size pq) 1)

(.add pq new-node)))

(defn symbol-map

 

(defn huffman-encode [items]

 

(defn display-huffman-encode [s]

 

 

 

=={{header|CoffeeScript}}==

huffman_encoding_table = (counts) ->

# counts is a hash where keys are characters and

console.log "#{rpad(code, 5)}: #{c} (#{counts[c]})"

console.log()

 

> coffee huffman.coffee

---- this is an example for huffman encoding

101 : c (4)

11 : d (8)

 

=={{header|Common Lisp}}==

 

 

(weight 0 :type number)

(element nil :type t)

(huffman-node-element node)

(huffman-node-weight node)

 

Example:

 

=={{header|D}}==

 

auto heap = sf.map!(s => tuple(s[1], [tuple(s[0], "")]))

.array.heapify!q{b < a};

auto lo = heap.front; heap.removeFront;

auto hi = heap.front; heap.removeFront;

heap.insert(tuple(lo[0] + hi[0], lo[1] ~ hi[1]));

}

}

 

writefln("'%s' %s", p[]);

{{out}}

<pre>' ' 101

'c' 111110

'd' 111111</pre>

 

=={{header|Erlang}}==

The main part of the code used here is extracted from [https://gist.github.com/rmies/2828351 Michel Rijnders' GitHubGist]. See also [http://codingpraxis.com/erlang/2012/10/23/huffman-coding-in-erlang.html his blog], for a complete description of the original module.

-export([encode/1, decode/2, main/0]).

print_bits(<<Bit:1, Rest/bitstring>>) ->

io:format("~w", [Bit]),

<pre> : 111

a: 1011

=={{header|F_Sharp|F#}}==

{{Trans|OCaml}}

| Leaf of int * 'a

| Node of int * 'a HuffmanTree * 'a HuffmanTree

let tree = charFreqs |> Map.toList |> buildTree

printfn "Symbol\tWeight\tHuffman code";

<pre>Symbol Weight Huffman code

p 1 00000

e 3 1101

6 111</pre>

 

=={{header|Fantom}}==

 

class Node

{

}

}

 

<pre>

From "this is an example for huffman encoding"

=={{header|Fortran}}==

 

! d-> 00000, t-> 00001, h-> 0001, s-> 0010,

! c-> 00110, x-> 00111, m-> 0100, o-> 0101,

print *

end program

 

=={{header|Go}}==

{{trans|Java}}

 

import (

fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")

printCodes(tree, []byte{})

<pre>

SYMBOL WEIGHT HUFFMAN CODE

</pre>

{{trans|Python}}

 

import (

fmt.Printf(" %c %d %s\n", c.sym, sym2freq[c.sym], c.code)

}

 

=={{header|Groovy}}==

Implemented and tested with Groovy 2.3.

 

import groovy.transform.*

 

: decoded

}

Usage:

def message = "this is an example for huffman encoding"

 

def decoded = decode(encoded, codeTable)

println decoded

<pre>

g: 00000

=={{header|Haskell}}==

Credits go to [http://www.haskell.org/haskellwiki/99_questions/46_to_50#Problem_50 huffman] where you'll also find a non-tree solution. Uses sorted list as a priority queue.

 

 

test :: String -> IO ()

 

serialize :: HTree a -> [(a, String)]

 

 

 

'r' : 00001

'g' : 00010

'a' : 1100

'e' : 1101

 

===Using <code>Set</code> as a priority queue===

(might be worth it for bigger alphabets):

 

htree :: (Ord t, Num t, Ord a) => S.Set (t, HTree a) -> HTree a

huffmanTree :: (Ord w, Num w, Ord a) => [(w, a)] -> HTree a

 

===A non-tree version===

import Control.Arrow (second, (&&&))

import Data.Ord (comparing)

 

main = do

 

=={{header|Icon}} and {{header|Unicon}}==

record huffcode(c,n,b,i) # encoding table char, freq, bitstring, bits (int)

 

}

return T

 

<pre>Input String : "this is an example for huffman encoding"

char freq encoding

and implements the algorithm given in the problem description.

The program produces Huffman codes based on each line of input.

 

procedure main(A)

else codeMap[node[1]] := prefix

return codeMap

 

A sample run:

'''Solution''' (drawn from [[J:Essays/Huffman_Coding|the J wiki]]):

 

if. 1=#x do. y

else. ((i{x),+/j{x) hc (i{y),<j{y [ i=. (i.#x) -. j=. 2{./:x end.

t=. 0 {:: x hc w NB. minimal weight binary tree

((< S: 0 t) i. w) { <@(1&=)@; S: 1 {:: t

 

t 0 1 0 1 0

h 1 1 1 1 1

c 1 0 0 0 0

d 1 0 0 0 1

 

=={{header|Java}}==

This implementation creates an actual tree structure, and then traverses the tree to recover the code.

 

abstract class HuffmanTree implements Comparable<HuffmanTree> {

printCodes(tree, new StringBuffer());

}

 

<pre>SYMBOL WEIGHT HUFFMAN CODE

d 1 00000

f 3 1101

6 111</pre>

 

=={{header|JavaScript}}==

 

The Huffman encoder

this.str = str;

 

}

return decoded;

 

And, using the Huffman encoder

print(s);

 

print(t);

 

 

<pre style='width: full; overflow: scroll'>this is an example for huffman encoding

'n': 000

is decoded string same as original? true</pre>

 

 

huffman[l_List] := Module[{merge, structure, rules},

rules = (# -> Flatten[Position[structure, #] - 1]) & /@ DeleteDuplicates[l];

 

 

=={{header|Objective-C}}==

 

This is not purely Objective-C. It uses Apple's Core Foundation library for its binary heap, which admittedly is very ugly. Thus, this only builds on Mac OS X, not GNUstep.

 

 

int freq;

}

@property (nonatomic, readonly) int freq;

@end

@implementation HuffmanTree

@synthesize freq; // the frequency of this tree

if (self = [super init]) {

freq = f;

}

@property (readonly) char value;

@end

 

@implementation HuffmanLeaf

@synthesize value;

if (self = [super initWithFreq:f]) {

value = c;

}

@property (readonly) HuffmanTree *left, *right;

@end

 

@implementation HuffmanNode

@synthesize left, right;

if (self = [super initWithFreq:l.freq+r.freq]) {

left = l;

}

return 0;

 

<pre>

SYMBOL WEIGHT HUFFMAN CODE

 

We use a Set (which is automatically sorted) as a priority queue.

| Leaf of 'a

| Node of 'a huffman_tree * 'a huffman_tree

 

let build_tree charFreqs =

let rec aux trees =

let f1, a = HSet.min_elt trees in

let tree = build_tree charFreqs in

print_string "Symbol\tHuffman code\n";

=={{header|Perl}}==

use strict;

 

print "$enc\n";

 

{{out}}

<pre>

</pre>

 

 

=={{header|PHP}}==

{{trans|Python}} (not exactly)

 

function encode($symb2freq) {

$heap = new SplPriorityQueue;

foreach ($huff as $sym => $code)

echo "$sym\t$symb2freq[$sym]\t$code\n";

 

<pre>

Symbol Weight Huffman Code

e 3 1111

</pre>

 

=={{header|PicoLisp}}==

Using a cons cells (freq . char) for leaves, and two cells (freq left . right)

for nodes.

(while (cadr Idx) (setq Idx @))

(car Idx) )

(prinl (cdr P) " " L)

(recurse (cadr P) (cons 0 L))

<pre>n 000

m 0100

 

=={{header|PL/I}}==

hencode: Proc Options(main);

/*--------------------------------------------------------------------

End;

 

<pre>The list of nodes:

id c oc l r f d t

input : this is an example for huffman encoding

result: this is an example for huffman encoding</pre>

=={{header|Prolog}}==

Works with SWI-Prolog

L = 'this is an example for huffman encoding',

atom_chars(L, LA),

N1 is N + 1.

run(V, [Other|RRest], [1,V], [Other|RRest]):-

<pre> ?- huffman.

Symbol Weight Code

=={{header|PureBasic}}==

{{works with|PureBasic|4.50}}

SampleString.s="this is an example for huffman encoding"

datalen=Len(SampleString)

Structure ztree

linked.c

EndStructure

 

Dim tree.ztree(255)

For i=0 To datalen-1

tree(memc(i))\char=memc(i)

tree(memc(i))\ischar=1

Next

For i=0 To 255

If tree(i)\number=0

EndIf

Next

dimsize=ArraySize(tree())

Repeat

EndIf

Next

If min1=0 Or min2=0

Break

EndIf

dimsize+1

ReDim tree(dimsize)

tree(hmin2)\linked=1

ForEver

i=0

While tree(i)\ischar=1

Wend

Input()

 

<pre> 110

n 000

The output is sorted first on length of the code, then on the symbols.

 

from collections import defaultdict

 

print "Symbol\tWeight\tHuffman Code"

for p in huff:

 

<pre>Symbol Weight Huffman Code

6 101

An extension to the method outlined above is given [http://paddy3118.blogspot.com/2009/04/abuse-of-pythons-in-built-data.html here].

 

 

=={{header|Racket}}==

#lang racket

(<= (node-freq x) (node-freq y)))

;; make-huffman-tree: (listof leaf) -> interior-node

(define (make-huffman-tree leaves)

(define a-heap (make-heap node<=?))

(heap-add-all! a-heap leaves)

(define min-1 (heap-min a-heap))

(heap-remove-min! a-heap)

(define n (sequence-length str))

(for ([ch str])

(make-huffman-tree

(for/list ([(k v) (in-hash ht)])

(loop (interior-right a-node) (cons #t path/rev))]

[(leaf? a-node)

(for/hash ([(k v) ht])

(values v k)))

(define decode (make-decoder tree))

;; Here's what the decoded message looks like:

 

=={{header|REXX}}==

* 27.12.2013 Walter Pachl

* 29.12.2013 -"- changed for test of s=xrange('00'x,'ff'x)

* Stem m contains eventually the following node data

* m.i.0id Node id

End

End

 

Exit

* show all lines representing node data

*--------------------------------------------------------------------*/

Do i=1 To m.0

End

Call dbg copies('-',21)

Say ' 'c '-->' code.c

End

<pre>We encode this string:

this is an example for huffman encoding

char --> code

--> 111

1011110111000000001110111000011011101101011101001111101000110011010001

00111110000110010

 

=={{header|Ruby}}==

Uses a {{libheader|RubyGems}} package [http://ruby.brian-amberg.de/priority-queue/ PriorityQueue]

 

def huffman_encoding(str)

enc = encode(str, encoding)

dec = decode(enc, encoding)

<pre>[" ", "111"]

["a", "1011"]

["x", "10100"]

success!

</pre>

 

=={{header|Scala}}==

{{works with|scala|2.8}}

import scala.collection.mutable.{Map, PriorityQueue}

}

}

 

<pre>

Char Weight Encoding

: 6/39 010

</pre>

=={{header|Scheme}}==

 

 

 

 

<pre>

</pre>

 

=={{header|SETL}}==

 

plaintext := 'this is an example for huffman encoding';

forest less:= [f, n];

return [f, n];

 

=={{header|Sidef}}==

}

 

func make_tree(text) {

var nodes = letters.keys.map { |l|

 

}

 

}

 

func encode(s, t) {

}

 

func decode (enc, tree) {

 

enc.each {|bit|

 

}

 

 

{{out}}

<pre>n: 000

=={{header|Standard ML}}==

{{works with|SML/NJ}}

Leaf of 'a

| Node of 'a huffman_tree * 'a huffman_tree

print "SYMBOL\tHUFFMAN CODE\n";

printCodes ([], tree)

 

=={{header|Tcl}}==

{{tcllib|struct::prioqueue}}

package require struct::prioqueue

 

set encoding [walkTree [$pq get]]

if {$opts(-dump)} {

}

}

return $encoding

 

puts $str

<pre style='width:full; overflow:scroll'>n 4 000

6 101

this is an example for huffman encoding

0101011111100100101011001001010111000001011101010111100001101100011011101101111001000111010111111011111110111000111100000101110100010000010010001100100011110</pre>

 

=={{header|Ursala}}==

following the algorithm given above

#import nat

#import flo

#cast %csAL

 

a quick walk through the code starting from the bottom:

* <code>*K2 ^/~&h float+ length</code> compute character frequencies by partitioning the input list of characters by equality, and transforming each equivalence class to a pair containing its member and its cardinality represented as a floating point number

* <code>~&plrDSLrnPlrmPCAS/'01'</code> otherwise there are two subtrees, hence two lists previously computed results propagating upward, so insert a zero into all of the bit strings in the results on the left, and a one into all the ones on the right, concatenate the left and right results, and propagate the contatenation upward

 

<pre><

`r: '00000',

`e: '1101',

` : '111'></pre>