Huffman coding: Difference between revisions
Content added Content deleted
m (→{{header|Go}}) |
(added php) |
||
Line 2,406: | Line 2,406: | ||
x 01111 |
x 01111 |
||
h 11111</pre> |
h 11111</pre> |
||
=={{header|PHP}}== |
|||
{{works with|PHP|5.3+}} |
|||
{{trans|Python}} (not exactly) |
|||
<lang php><?php |
|||
function encode($symb2freq) { |
|||
$heap = new SplPriorityQueue; |
|||
$heap->setExtractFlags(SplPriorityQueue::EXTR_BOTH); |
|||
foreach ($symb2freq as $sym => $wt) |
|||
$heap->insert(array($sym => ''), -$wt); |
|||
while ($heap->count() > 1) { |
|||
$lo = $heap->extract(); |
|||
$hi = $heap->extract(); |
|||
foreach ($lo['data'] as &$x) |
|||
$x = '0'.$x; |
|||
foreach ($hi['data'] as &$x) |
|||
$x = '1'.$x; |
|||
$heap->insert($lo['data'] + $hi['data'], |
|||
$lo['priority'] + $hi['priority']); |
|||
} |
|||
$result = $heap->extract(); |
|||
return $result['data']; |
|||
} |
|||
$txt = 'this is an example for huffman encoding'; |
|||
$symb2freq = array_count_values(str_split($txt)); |
|||
$huff = encode($symb2freq); |
|||
echo "Symbol\tWeight\tHuffman Code\n"; |
|||
foreach ($huff as $sym => $code) |
|||
echo "$sym\t$symb2freq[$sym]\t$code\n"; |
|||
?></lang> |
|||
Example output: |
|||
<pre> |
|||
Symbol Weight Huffman Code |
|||
n 4 000 |
|||
m 2 0010 |
|||
o 2 0011 |
|||
t 1 01000 |
|||
g 1 01001 |
|||
x 1 01010 |
|||
u 1 01011 |
|||
s 2 0110 |
|||
c 1 01110 |
|||
d 1 01111 |
|||
p 1 10000 |
|||
l 1 10001 |
|||
a 3 1001 |
|||
6 101 |
|||
f 3 1100 |
|||
i 3 1101 |
|||
r 1 11100 |
|||
h 2 11101 |
|||
e 3 1111 |
|||
</pre> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |