Huffman coding: Difference between revisions

{{trans|Python}}

 

Int weight

[(Char, String)] symbols

print("Symbol\tWeight\tHuffman Code")

L(p) huff

 

{{out}}

 

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

{{incorrect|BBC BASIC|Huffman code can not contain another code as a prefix}}

{{works with|BBC BASIC for Windows}}

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

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

ENDIF

NEXT

{{out}}

<pre>

 

=={{header|Bracmat}}==

& 0:?chars

& 0:?p

| !arg

)

{{out}}

<pre>(L=

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;

 

}

}

[[File:CSharpHuffman.jpg]]

 

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

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

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

 

=={{header|Factor}}==

USING: kernel sequences combinators accessors assocs math hashtables math.order

sorting.slots classes formatting prettyprint ;

! u 1 { 1 0 0 1 1 }

! x 1 { 1 0 0 1 0 }

 

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

freq as uinteger

chars as string

print "'"+codelist(i).char+"'", codelist(i).code

next i

{{out}}

<pre>' ' 111

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

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

import Data.Ord (comparing)

 

main :: IO ()

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

 

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

abstract type HuffmanTree end

 

 

printencoding(huffmantree(makefreqdict(msg)), "")

Char Freq Huffman code

p 1 00000

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

 

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

 

=={{header|M2000 Interpreter}}==

Module Huffman {

comp=lambda (a, b) ->{

}

Huffman

 

{{out}}

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

 

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

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

 

 

=={{header|Nim}}==

 

 

type

 

for (key, value) in sortedByIt(toSeq(huffCodes.pairs), it[1]):

 

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

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

 

(return (reverse prefix))))))))

(map car table)))

{{Out}}

(print "weights: ---------------------------")

(for-each (lambda (ch)

(reverse (map car table))

(reverse codes))

<pre>

weights: ---------------------------

 

=={{header|Perl}}==

use strict;

 

print "$enc\n";

 

{{out}}

<pre>

=={{header|Phix}}==

{{trans|Lua}}

{{out}}

<pre>

'u' [1] 10001

'x' [1] 11110

"this is an example for huffman encoding"

</pre>

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

 

{{works with|rakudo|2015-12-17}}

my @queue = %frequencies.map({ [.value, .key] }).sort;

while @queue > 1 {

multi walk ($node, $prefix) { take $node => $prefix; }

multi walk ([$node1, $node2], $prefix) { walk $node1, $prefix ~ '0';

 

===Without building a tree===

 

{{works with|rakudo|2015-12-17}}

my @queue = %frequencies.map: { .value => (hash .key => '') };

while @queue > 1 {

my $decoded = $encoded .subst: /@codes/, { %decode-key{$_} }, :g;

 

 

{{out}}

 

=={{header|Red}}==

 

;; message to encode:

]

]

{{out}}

<pre> = 111

 

=={{header|REXX}}==

* 27.12.2013 Walter Pachl

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

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

End

{{out}}

<pre>We encode this string:

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

 

 

puts $str

{{out}}

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

=={{header|UNIX Shell}}==

{{works with|Bourne Again SHell}}

#!/bin/bash

 

awk -F: '{printf "%c\t%d\t%s\n", $2, $3, $1}' |

sort -k 2,2nr -k 3,3n

 

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

{{libheader|Wren-queue}}

Note that the results differ from Java because the PriorityQueue implementation is not the same.

 

class HuffmanTree {

var tree = buildTree.call(freqs)

System.print("SYMBOL\tWEIGHT\tHUFFMAN CODE")

 

{{out}}

x 1 11110

h 2 11111

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