42 lines
854 B
Bash
42 lines
854 B
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
|