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

g 11011

t 11010

</pre>

 

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]));

}

}

 

{{out}}

<pre>' ' 101

'c' 111110

'd' 111111</pre>

 

=={{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"

x -> 01011

</pre>

 

=={{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|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

this is an example for huffman encoding

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

 

=={{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;

}

@end

 

@implementation HuffmanTree

@synthesize freq; // the frequency of this tree

if (self = [super init]) {

freq = f;

 

const void *HuffmanRetain(CFAllocatorRef allocator, const void *ptr) {

}

void HuffmanRelease(CFAllocatorRef allocator, const void *ptr) {

}

CFComparisonResult HuffmanCompare(const void *ptr1, const void *ptr2, void *unused) {

if (f1 == f2)

return kCFCompareEqualTo;

}

@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]) {

}

return self;

}

@end

int freq = [chars countForObject:ch];

if (freq > 0)

}

while (CFBinaryHeapGetCount(trees) > 1) {

// two trees with least frequency

CFBinaryHeapRemoveMinimumValue(trees);

CFBinaryHeapRemoveMinimumValue(trees);

// put into new node and re-insert into queue

}

CFRelease(trees);

}

 

 

int main(int argc, const char * argv[]) {

 

NSString *test = @"this is an example for huffman encoding";

int n = [test length];

for (int i = 0; i < n; i++)

// build tree

HuffmanTree *tree = buildTree(chars);

// print out results

printCodes(tree, [NSMutableString string]);

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}}==

 

}

 

}

 

sub encode {

}

 

sub decode {

 

}

}

 

 

 

 

 

=={{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

h 2 11101

e 3 1111

</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].

 

 

 

 

 

 

 

;; node<=?: node node -> boolean

(define (node<=? x y)

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

(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)

min-1 min-2)))

(heap-min a-heap))

;; string->huffman-tree: string -> node

(define (string->huffman-tree str)

(define ht (make-hash))

(define n (sequence-length str))

(for ([ch str])

(make-huffman-tree

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

(define (make-encoder a-tree)

(define dict (huffman-tree->dictionary a-tree))

(lambda (a-str)

 

(define (make-decoder a-tree)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define msg "this is an example for huffman encoding")

 

;; We can print out the mapping for inspection:

(huffman-tree->dictionary tree)

(define encode (make-encoder tree))

(define encoded (encode msg))

 

(define decode (make-decoder tree))

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