Huffman coding: Difference between revisions

create a program to generate a Huffman encoding for each character as a table.

<br><br>

 

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

 

{{out}}

 

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

{{out}}

<pre>

t 11010

</pre>

=={{header|Bracmat}}==

& 0:?chars

& 0:?p

| !arg

)

{{out}}

<pre>(L=

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>

 

 

return 0;

{{out}}

<pre>' ': 000

 

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

 

{{out}}

=={{header|Clojure}}==

(Updated to 1.6 & includes pretty-printing). Uses Java PriorityQueue

 

(defn probs [s]

(->> s huffman-encode (sort-by :weight >) print-table))

 

 

{{out}}

===Alternate Version===

Uses c.d.priority-map. Creates a more shallow tree but appears to meet the requirements.

(require '[clojure.pprint :refer [print-table]])

 

(->> s huffman-encode (sort-by :weight >) print-table))

 

{{out}}

<pre>| :sym | :weight | :code |

 

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

 

{{out}}

101 : c (4)

11 : d (8)

 

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

(For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)

 

(weight 0 :type number)

(element nil :type t)

(huffman-node-element node)

(huffman-node-weight node)

 

Example:

 

=={{header|D}}==

 

auto encode(alias eq, R)(Group!(eq, R) sf) /*pure nothrow @safe*/ {

foreach (const p; s.dup.sort().group.encode)

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

{{out}}

<pre>' ' 101

=={{header|Eiffel}}==

Adapted C# solution.

class HUFFMAN_NODE[T -> COMPARABLE]

inherit

end

end

 

{{out}}

x: 01010

</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]),

{{out}}

<pre> : 111

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

{{out}}

<pre>Symbol Weight Huffman code

e 3 1101

6 111</pre>

 

=={{header|Fantom}}==

 

class Node

{

}

}

 

{{out}}

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

{{out}}

<pre>

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

{{out}}

<pre>

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

 

data HTree a

test :: String -> IO ()

test =

serialize . huffmanTree . freq

 

huffmanTree =

snd .

 

hstep

:: Ord a

=> [a] -> [(Int, a)]

{{out}}

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

This produces the output required without building the Huffman tree at all,

by building all the trace strings directly while reducing the histogram:

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

 

{{out}}

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

}

 

{{out}}

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

 

 

{{out}}

this is an example for huffman encoding

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

 

=={{header|Kotlin}}==

{{trans|Java}}

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

 

abstract class HuffmanTree(var freq: Int) : Comparable<HuffmanTree> {

println("SYMBOL\tWEIGHT\tHUFFMAN CODE")

printCodes(tree, StringBuffer())

 

{{out}}

f 3 1101

6 111</pre>

 

=={{header|Lua}}==

This implementation proceeds in three steps: determine word frequencies,

construct the Huffman tree, and finally fold the tree into the codes

while outputting them.

local freq = { }

 

return huffcode "this is an example for huffman encoding"

 

<pre>

frequency word huffman code

6 ‘ ’ “101”

</pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

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

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

 

 

=={{header|Nim}}==

 

 

type

 

 

 

 

 

 

 

root = tree.freeChildList[0]

 

{{out}}

 

=={{header|Oberon-2}}==

{{works with|oo2c}}

MODULE HuffmanEncoding;

IMPORT

 

END HuffmanEncoding.

{{out}}

<pre>

 

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.

 

 

}

return 0;

 

{{out}}

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

{{works with|OCaml|4.02+}}

| Leaf of 'a

| Node of 'a huffman_tree * 'a huffman_tree

let tree = build_tree charFreqs in

print_string "Symbol\tHuffman code\n";

 

=={{header|Perl}}==

use strict;

 

print "$enc\n";

 

{{out}}

<pre>

</pre>

 

{{out}}

 

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

 

{{out}}

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

{{out}}

<pre>n 000

 

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

hencode: Proc Options(main);

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

End;

 

{{out}}

<pre>The list of nodes:

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-HuffmanEncodingTable ( $String )

{

}

$EncodedString

{{out}}

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

{{out}}

<pre> ?- huffman.

=={{header|PureBasic}}==

{{works with|PureBasic|4.50}}

OpenConsole()

CloseConsole()

 

{{out}}

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:

 

{{out}}

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

(define decode (make-decoder tree))

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

 

=={{header|Red}}==

 

;; message to encode:

]

]

{{out}}

<pre> = 111

decoded: this is an example for huffman encoding

</pre>

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

{{out}}

<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"]

Adapted C++ solution.

 

use std::collections::BTreeMap;

use std::collections::binary_heap::BinaryHeap;

}

}

 

Output:

=={{header|Scala}}==

{{works with|scala|2.8}}

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

}

}

 

{{out}}

==={{header|Scala (Alternate version)}}===

{{works with|scala|2.11.7}}

// this version uses immutable data only, recursive functions and pattern matching

object Huffman {

frequencies.foreach(x => println(x._1.value + "\t" + x._2 + s"/${text.length}" + s"\t${encodeChar(huffmanTree, x._1.value)}"))

}

<pre>

Char Weight Code

=={{header|Scheme}}==

 

(if

(eof-object? (peek-char port))

(define freq-table (char-freq (open-input-string input) '()))

(define tree (huffman-tree (nodeify freq-table)))

 

{{out}}

 

=={{header|SETL}}==

 

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

forest less:= [f, n];

return [f, n];

 

=={{header|Sidef}}==

if (n.contains(:a)) {

h{n{:a}} = s

 

say enc

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

Rather than a priority queue of subtrees, we use the strategy of two sorted lists, one for leaves and one for nodes, and "merge" them as we iterate through them, taking advantage of the fact that any new nodes we create are bigger than any previously created nodes, so go at the end of the nodes list.

{{works with|Swift|2+}}

case Leaf(T)

indirect case Node(HuffmanTree<T>, HuffmanTree<T>)

let tree = buildTree(charFreqs)

print("Symbol\tHuffman code")

{{out}}

<pre>

=={{header|Tcl}}==

{{tcllib|struct::prioqueue}}

package require struct::prioqueue

 

set encoding [walkTree [$pq get]]

if {$opts(-dump)} {

}

}

return $encoding

 

puts $str

{{out}}

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

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

`e: '1101',

` : '111'></pre>

 

=={{header|zkl}}==

This code was adapted from Perl, Python and most of the other examples.

ft:=Dictionary();

foreach c in (text){ ft[c]=ft.find(c,0)+1 } // leafs w/count

decodeTable:=encodeTable.pump(Dictionary(),"reverse"); // code:symbol

return(encodeTable,decodeTable);

fcn decode(bits,table){ // this is a horrible decoder, for testing only

w:=bits.walker(); sink:=Sink(String);

}}catch(TheEnd){}

sink.close();

encodeTable,decodeTable := buildHuffman(text);

encodeTable.pump(Console.println,fcn(kv){"%s : %s".fmt(kv.xplode())});

println(e);

 

{{out}}

<pre>