Huffman coding: Difference between revisions
m
syntax highlighting fixup automation
m (Python: pretty print Huffman table) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 33:
{{trans|Python}}
<
Int weight
[(Char, String)] symbols
Line 70:
print("Symbol\tWeight\tHuffman Code")
L(p) huff
print("#.\t#.\t#.".format(p[0], symb2freq[p[0]], p[1]))</
{{out}}
Line 100:
huffman.ads:
<
with Ada.Containers.Ordered_Maps;
with Ada.Finalization;
Line 182:
-- free memory after finalization
overriding procedure Finalize (Object : in out Huffman_Tree);
end Huffman;</
huffman.adb:
<
with Ada.Unchecked_Deallocation;
with Ada.Containers.Vectors;
Line 428:
end loop;
end Dump_Encoding;
end Huffman;</
example main.adb:
<
with Huffman;
procedure Main is
Line 479:
(Char_Natural_Huffman_Tree.Decode (Tree => Tree, Code => Code));
end;
end Main;</
{{out}}
Line 507:
{{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
Line 559:
ENDIF
NEXT
END</
{{out}}
<pre>
Line 584:
=={{header|Bracmat}}==
<
& 0:?chars
& 0:?p
Line 639:
| !arg
)
& out$("decoded:" str$(decode$(str$!encoded)));</
{{out}}
<pre>(L=
Line 669:
This code lacks a lot of needed checkings, especially for memory allocation.
<
#include <stdlib.h>
#include <string.h>
Line 842:
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>
Line 967:
return 0;
}</
{{out}}
<pre>' ': 000
Line 992:
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 1,305:
}
}
}</
[[File:CSharpHuffman.jpg]]
Line 1,312:
This code builds a tree to generate huffman codes, then prints the codes.
<
#include <queue>
#include <map>
Line 1,426:
}
return 0;
}</
{{out}}
Line 1,451:
=={{header|Clojure}}==
(Updated to 1.6 & includes pretty-printing). Uses Java PriorityQueue
<
(defn probs [s]
Line 1,484:
(->> s huffman-encode (sort-by :weight >) print-table))
(display-huffman-encode "this is an example for huffman encoding")</
{{out}}
Line 1,510:
===Alternate Version===
Uses c.d.priority-map. Creates a more shallow tree but appears to meet the requirements.
<
(require '[clojure.pprint :refer [print-table]])
Line 1,547:
(->> s huffman-encode (sort-by :weight >) print-table))
(display-huffman-encode "this is an example for huffman encoding")</
{{out}}
<pre>| :sym | :weight | :code |
Line 1,572:
=={{header|CoffeeScript}}==
<
huffman_encoding_table = (counts) ->
# counts is a hash where keys are characters and
Line 1,658:
console.log "#{rpad(code, 5)}: #{c} (#{counts[c]})"
console.log()
</
{{out}}
Line 1,705:
(For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)
<
(weight 0 :type number)
(element nil :type t)
Line 1,763:
(huffman-node-element node)
(huffman-node-weight node)
(huffman-node-encoding node))))</
Example:
Line 1,791:
=={{header|D}}==
<
auto encode(alias eq, R)(Group!(eq, R) sf) /*pure nothrow @safe*/ {
Line 1,811:
foreach (const p; s.dup.sort().group.encode)
writefln("'%s' %s", p[]);
}</
{{out}}
<pre>' ' 101
Line 1,835:
=={{header|Eiffel}}==
Adapted C# solution.
<
class HUFFMAN_NODE[T -> COMPARABLE]
inherit
Line 2,024:
end
end
</syntaxhighlight>
{{out}}
Line 2,050:
=={{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]).
Line 2,112:
print_bits(<<Bit:1, Rest/bitstring>>) ->
io:format("~w", [Bit]),
print_bits(Rest).</
{{out}}
<pre> : 111
Line 2,138:
=={{header|F_Sharp|F#}}==
{{Trans|OCaml}}
<
| Leaf of int * 'a
| Node of int * 'a HuffmanTree * 'a HuffmanTree
Line 2,172:
let tree = charFreqs |> Map.toList |> buildTree
printfn "Symbol\tWeight\tHuffman code";
printTree ([], tree)</
{{out}}
<pre>Symbol Weight Huffman code
Line 2,196:
=={{header|Factor}}==
<
USING: kernel sequences combinators accessors assocs math hashtables math.order
sorting.slots classes formatting prettyprint ;
Line 2,329:
! u 1 { 1 0 0 1 1 }
! x 1 { 1 0 0 1 0 }
</syntaxhighlight>
=={{header|Fantom}}==
<
class Node
{
Line 2,431:
}
}
</syntaxhighlight>
{{out}}
Line 2,460:
=={{header|Fortran}}==
<
! d-> 00000, t-> 00001, h-> 0001, s-> 0010,
! c-> 00110, x-> 00111, m-> 0100, o-> 0101,
Line 2,608:
print *
end program
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
freq as uinteger
chars as string
Line 2,696:
print "'"+codelist(i).char+"'", codelist(i).code
next i
</syntaxhighlight>
{{out}}
<pre>' ' 111
Line 2,720:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 2,816:
fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(tree, []byte{})
}</
{{out}}
<pre>
Line 2,841:
</pre>
{{trans|Python}}
<
import (
Line 2,905:
fmt.Printf(" %c %d %s\n", c.sym, sym2freq[c.sym], c.code)
}
}</
=={{header|Groovy}}==
Line 2,911:
Implemented and tested with Groovy 2.3.
<
import groovy.transform.*
Line 2,962:
: decoded
}
</syntaxhighlight>
Usage:
<
def message = "this is an example for huffman encoding"
Line 2,975:
def decoded = decode(encoded, codeTable)
println decoded
</syntaxhighlight>
{{out}}
<pre>
Line 3,004:
=={{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)
Line 3,043:
main :: IO ()
main = test "this is an example for huffman encoding"</
{{out}}
<
'r' : 00001
'g' : 00010
Line 3,063:
'a' : 1100
'e' : 1101
' ' : 111</
===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
Line 3,078:
huffmanTree :: (Ord w, Num w, Ord a) => [(w, a)] -> HTree a
huffmanTree = htree . S.fromList . map (second Leaf)</
===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)
Line 3,099:
main = do
test "this is an example for huffman encoding"</
=={{header|Icon}} and {{header|Unicon}}==
<
record huffcode(c,n,b,i) # encoding table char, freq, bitstring, bits (int)
Line 3,161:
}
return T
end</
{{out}}
Line 3,190:
and implements the algorithm given in the problem description.
The program produces Huffman codes based on each line of input.
<
procedure main(A)
Line 3,219:
else codeMap[node[1]] := prefix
return codeMap
end</
A sample run:
Line 3,265:
'''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.
Line 3,278:
t=. 0 {:: x hc w NB. minimal weight binary tree
((< S: 0 t) i. w) { <@(1&=)@; S: 1 {:: t
)</
'''Example''':<
t 0 1 0 1 0
h 1 1 1 1 1
Line 3,299:
c 1 0 0 0 0
d 1 0 0 0 1
g 1 1 1 1 0</
=={{header|Java}}==
This implementation creates an actual tree structure, and then traverses the tree to recover the code.
<
abstract class HuffmanTree implements Comparable<HuffmanTree> {
Line 3,397:
printCodes(tree, new StringBuffer());
}
}</
{{out}}
Line 3,429:
The Huffman encoder
<
this.str = str;
Line 3,491:
}
return decoded;
}</
And, using the Huffman encoder
<
print(s);
Line 3,506:
print(t);
print("is decoded string same as original? " + (s==t));</
{{out}}
Line 3,534:
=={{header|Julia}}==
<
abstract type HuffmanTree end
Line 3,588:
printencoding(huffmantree(makefreqdict(msg)), "")
</
Char Freq Huffman code
p 1 00000
Line 3,614:
{{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> {
Line 3,667:
println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(tree, StringBuffer())
}</
{{out}}
Line 3,695:
construct the Huffman tree, and finally fold the tree into the codes
while outputting them.
<
local freq = { }
Line 3,769:
return huffcode "this is an example for huffman encoding"
</syntaxhighlight>
<pre>
frequency word huffman code
Line 3,794:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Huffman {
comp=lambda (a, b) ->{
Line 3,879:
}
Huffman
</syntaxhighlight>
{{out}}
Line 3,911:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
huffman[l_List] := Module[{merge, structure, rules},
Line 3,923:
rules = (# -> Flatten[Position[structure, #] - 1]) & /@ DeleteDuplicates[l];
{Flatten[l /. rules], rules}];</
=={{header|Nim}}==
<
type
Line 4,022:
for (key, value) in sortedByIt(toSeq(huffCodes.pairs), it[1]):
echo &"'{key}' → {value}"</
{{out}}
Line 4,047:
=={{header|Oberon-2}}==
{{works with|oo2c}}
<
MODULE HuffmanEncoding;
IMPORT
Line 4,139:
END HuffmanEncoding.
</syntaxhighlight>
{{out}}
<pre>
Line 4,167:
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.
<
Line 4,316:
}
return 0;
}</
{{out}}
Line 4,347:
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
Line 4,396:
let tree = build_tree charFreqs in
print_string "Symbol\tHuffman code\n";
print_tree [] tree</
=={{header|Ol}}==
<
(define phrase "this is an example for huffman encoding")
Line 4,438:
(return (reverse prefix))))))))
(map car table)))
</syntaxhighlight>
{{Out}}
<
(print "weights: ---------------------------")
(for-each (lambda (ch)
Line 4,451:
(reverse (map car table))
(reverse codes))
</syntaxhighlight>
<pre>
weights: ---------------------------
Line 4,496:
=={{header|Perl}}==
<
use strict;
Line 4,552:
print "$enc\n";
print decode($enc, $rev_h), "\n";</
{{out}}
<pre>
Line 4,580:
=={{header|Phix}}==
{{trans|Lua}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">store_nodes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
Line 4,677:
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"this is an example for huffman encoding"</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 4,707:
{{trans|Python}} (not exactly)
<
function encode($symb2freq) {
$heap = new SplPriorityQueue;
Line 4,734:
foreach ($huff as $sym => $code)
echo "$sym\t$symb2freq[$sym]\t$code\n";
?></
{{out}}
Line 4,762:
=={{header|Picat}}==
{{trans|Prolog}}
<
huffman("this is an example for huffman encoding").
Line 4,810:
N1 = N + 1.
run(V, [Other|RRest], [1,V], [Other|RRest]) :-
different_terms(V, Other).</
{{out}}
Line 4,837:
Using a cons cells (freq . char) for leaves, and two cells (freq left . right)
for nodes.
<
(while (cadr Idx) (setq Idx @))
(car Idx) )
Line 4,854:
(prinl (cdr P) " " L)
(recurse (cadr P) (cons 0 L))
(recurse (cddr P) (cons 1 L)) ) ) )</
{{out}}
<pre>n 000
Line 4,877:
=={{header|PL/I}}==
<
hencode: Proc Options(main);
/*--------------------------------------------------------------------
Line 5,134:
End;
End;</
{{out}}
<pre>The list of nodes:
Line 5,204:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
function Get-HuffmanEncodingTable ( $String )
{
Line 5,266:
}
$EncodedString
</syntaxhighlight>
{{out}}
<pre>
Line 5,297:
=={{header|Prolog}}==
Works with SWI-Prolog
<
L = 'this is an example for huffman encoding',
atom_chars(L, LA),
Line 5,343:
N1 is N + 1.
run(V, [Other|RRest], [1,V], [Other|RRest]):-
dif(V, Other).</
{{out}}
<pre> ?- huffman.
Line 5,370:
=={{header|PureBasic}}==
{{works with|PureBasic|4.50}}
<syntaxhighlight lang="purebasic">
OpenConsole()
Line 5,454:
CloseConsole()
</syntaxhighlight>
{{out}}
Line 5,482:
The output is sorted first on length of the code, then on the symbols.
<
from collections import defaultdict
Line 5,508:
print "Symbol\tWeight\tHuffman Code"
for p in huff:
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])</
{{out}}
Line 5,538:
This implementation creates an explicit tree structure, which is used during decoding. We also make use of a "pseudo end of file" symbol and padding bits to facilitate reading and writing encoded data to from/to a file.
<
from __future__ import annotations
Line 5,724:
if __name__ == "__main__":
main()
</syntaxhighlight>
{{out}}
Line 5,762:
The word <code>huffmanlist</code> will turn the Huffman tree into a nest of nests, each containing an ascii character code and a nest containing a Huffman code. The nests are sorted by ascii character code to facilitate binary splitting.
<
[ [ 0 128 of ] constant
Line 5,829:
say " Huffman codes sorted by code length." cr
codesort echohuff
</syntaxhighlight>
{{out}}
Line 5,876:
=={{header|Racket}}==
<
#lang racket
Line 5,981:
(define decode (make-decoder tree))
;; Here's what the decoded message looks like:
(decode encoded)</
=={{header|Raku}}==
Line 5,991:
{{works with|rakudo|2015-12-17}}
<syntaxhighlight lang="raku"
my @queue = %frequencies.map({ [.value, .key] }).sort;
while @queue > 1 {
Line 6,003:
multi walk ($node, $prefix) { take $node => $prefix; }
multi walk ([$node1, $node2], $prefix) { walk $node1, $prefix ~ '0';
walk $node2, $prefix ~ '1'; }</
===Without building a tree===
Line 6,010:
{{works with|rakudo|2015-12-17}}
<syntaxhighlight lang="raku"
my @queue = %frequencies.map: { .value => (hash .key => '') };
while @queue > 1 {
Line 6,040:
my $decoded = $encoded .subst: /@codes/, { %decode-key{$_} }, :g;
.say for $original, $encoded, $decoded;</
{{out}}
Line 6,068:
=={{header|Red}}==
<
;; message to encode:
Line 6,159:
]
]
</syntaxhighlight>
{{out}}
<pre> = 111
Line 6,189:
=={{header|REXX}}==
<
* 27.12.2013 Walter Pachl
* 29.12.2013 -"- changed for test of s=xrange('00'x,'ff'x)
Line 6,446:
Say ' 'c '-->' code.c
End
Return</
{{out}}
<pre>We encode this string:
Line 6,517:
=={{header|Ruby}}==
Uses a {{libheader|RubyGems}} package [http://ruby.brian-amberg.de/priority-queue/ PriorityQueue]
<
def huffman_encoding(str)
Line 6,570:
enc = encode(str, encoding)
dec = decode(enc, encoding)
puts "success!" if str == dec</
<pre>[" ", "111"]
["a", "1011"]
Line 6,597:
Adapted C++ solution.
<
use std::collections::BTreeMap;
use std::collections::binary_heap::BinaryHeap;
Line 6,684:
}
}
</syntaxhighlight>
Output:
Line 6,711:
=={{header|Scala}}==
{{works with|scala|2.8}}
<
import scala.collection.mutable.{Map, PriorityQueue}
Line 6,759:
}
}
}</
{{out}}
Line 6,786:
==={{header|Scala (Alternate version)}}===
{{works with|scala|2.11.7}}
<
// this version uses immutable data only, recursive functions and pattern matching
object Huffman {
Line 6,829:
frequencies.foreach(x => println(x._1.value + "\t" + x._2 + s"/${text.length}" + s"\t${encodeChar(huffmanTree, x._1.value)}"))
}
}</
<pre>
Char Weight Code
Line 6,855:
=={{header|Scheme}}==
<
(if
(eof-object? (peek-char port))
Line 6,908:
(define freq-table (char-freq (open-input-string input) '()))
(define tree (huffman-tree (nodeify freq-table)))
(list-encodings tree (map car freq-table))</
{{out}}
Line 6,934:
=={{header|SETL}}==
<
plaintext := 'this is an example for huffman encoding';
Line 6,971:
forest less:= [f, n];
return [f, n];
end proc;</
=={{header|Sidef}}==
<
if (n.contains(:a)) {
h{n{:a}} = s
Line 7,027:
say enc
say decode(enc, tree)</
{{out}}
<pre>n: 000
Line 7,053:
=={{header|Standard ML}}==
{{works with|SML/NJ}}
<
Leaf of 'a
| Node of 'a huffman_tree * 'a huffman_tree
Line 7,109:
print "SYMBOL\tHUFFMAN CODE\n";
printCodes ([], tree)
end</
=={{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>)
Line 7,179:
let tree = buildTree(charFreqs)
print("Symbol\tHuffman code")
tree.printCodes("")</
{{out}}
<pre>
Line 7,206:
=={{header|Tcl}}==
{{tcllib|struct::prioqueue}}
<
package require struct::prioqueue
Line 7,258:
puts $str
puts [string map $encoding $str]</
{{out}}
<pre style='width:full; overflow:scroll'>n 4 000
Line 7,284:
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
<
#!/bin/bash
Line 7,326:
awk -F: '{printf "%c\t%d\t%s\n", $2, $3, $1}' |
sort -k 2,2nr -k 3,3n
</syntaxhighlight>
=={{header|Ursala}}==
following the algorithm given above
<
#import nat
#import flo
Line 7,343:
#cast %csAL
table = code_table 'this is an example for huffman encoding'</
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
Line 7,381:
{{libheader|Wren-queue}}
Note that the results differ from Java because the PriorityQueue implementation is not the same.
<
class HuffmanTree {
Line 7,452:
var tree = buildTree.call(freqs)
System.print("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes.call(tree, "")</
{{out}}
Line 7,480:
=={{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
Line 7,502:
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);
Line 7,510:
}}catch(TheEnd){}
sink.close();
}</
<
encodeTable,decodeTable := buildHuffman(text);
encodeTable.pump(Console.println,fcn(kv){"%s : %s".fmt(kv.xplode())});
Line 7,520:
println(e);
0'|Bits decoded to: "%s"|.fmt(decode(e,decodeTable)).println();</
{{out}}
<pre>
|