Anonymous user
Huffman coding: Difference between revisions
no edit summary
Alextretyak (talk | contribs) (Added 11l) |
No edit summary |
||
Line 6,867:
this is an example for huffman encoding
0101011111100100101011001001010111000001011101010111100001101100011011101101111001000111010111111011111110111000111100000101110100010000010010001100100011110</pre>
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
<lang bash>
#!/bin/bash
set -eu
# make scratch directory
t="$(mktemp -d)"
cd "${t:?mktemp failed}"
trap 'rm -r -- "$t"' EXIT
# get character frequencies
declare -a freq=()
while read addr line; do
for c in $line; do
: $((freq[8#$c]++))
done
done < <(od -b -v)
# convert freqs into a bucket queue
declare -i i=0
for c in ${!freq[@]}; do
fn="${freq[c]}.$((i++))"
echo "$c:${freq[c]}" >"$fn"
done
top2() { ls | sort -t. -k1,1n -k2,2n | sed 2q; }
set -- $(top2)
while [[ $# -gt 1 ]]; do
declare -i l="${1%%.*}" r="${2%%.*}" # combine weights into
fn="$((l + r)).$((i++))" # ... new node weight
mkdir "$fn"
mv "$1" "$fn/0"
mv "$2" "$fn/1"
set -- $(top2)
done
echo -e "Symbol\tWeight\tHuffman Code"
cd "$fn"
find . -type f -exec grep . {} + |
tr -d ./ |
awk -F: '{printf "%c\t%d\t%s\n", $2, $3, $1}' |
sort -k 2,2nr -k 3,3n
</lang>
=={{header|Ursala}}==
| |||