Libraryless. Click here for Pure Java version (15084L/89K).
1 | // Builds a HuffmanTree from a byte histogram |
2 | sclass HuffmanTreeMaker {
|
3 | delegate Node, Branch, Leaf to HuffmanTree. |
4 | |
5 | // output |
6 | gettable new HuffmanTree tree; |
7 | |
8 | // internal |
9 | new TreeSet<Head> pool; // combinable trees sorted by incidence (symbol frequency) |
10 | int indexCounter; // counter to keep order deterministic |
11 | |
12 | class Head is Comparable<Head> {
|
13 | int index = indexCounter++; |
14 | settable Node node; |
15 | settable double freq; // using floating point to keep things futureproof |
16 | |
17 | // sort by frequency first, then by index (order of creation) |
18 | public int compareTo(Head h) {
|
19 | if (this == h) ret 0; |
20 | var c = cmp(freq, h.freq); |
21 | if (c != 0) ret c; |
22 | ret cmp(index, h.index); |
23 | } |
24 | |
25 | toString { ret freq + "x " + node; }
|
26 | } |
27 | |
28 | // histogram[0] = incidence for byte 00 |
29 | // histogram[1] = incidence for byte 01 |
30 | // etc. up to 255 (or less) |
31 | selfType importByteHistogram(int[] histogram) {
|
32 | int n = l(histogram); |
33 | for i to n: {
|
34 | double freq = histogram[i]; |
35 | if (freq != 0) |
36 | pool.add(new Head().freq(freq).node(tree.new Leaf(i))); |
37 | } |
38 | this; |
39 | } |
40 | |
41 | run {
|
42 | while ping (l(pool) > 1) {
|
43 | var it = iterator(pool); |
44 | var a = it.next(); |
45 | it.remove(); |
46 | var b = it.next(); |
47 | it.remove(); |
48 | //print("Merging frequencies: " + commaCombine(a.freq, b.freq));
|
49 | var newHead = new Head() |
50 | .freq(a.freq+b.freq) |
51 | .node(tree.new Branch().zero(b.node).one(a.node)); |
52 | //print("Merging: " + commaCombine(a, b) + " to " + newHead);
|
53 | pool.add(newHead); |
54 | } |
55 | } |
56 | |
57 | HuffmanTree get() {
|
58 | run(); |
59 | if (nempty(pool)) |
60 | tree.root(popFirst(pool).node()); |
61 | ret tree; |
62 | } |
63 | } |
Began life as a copy of #1035665
download show line numbers debug dex old transpilations
Travelled to 2 computer(s): elmgxqgtpvxh, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1035667 |
| Snippet name: | HuffmanTreeMaker [OK] |
| Eternal ID of this version: | #1035667/14 |
| Text MD5: | 8c84c4a34cc09bee987f49d1537bba10 |
| Transpilation MD5: | 65da45965eaad1d64726fc9d9569fb12 |
| Author: | stefan |
| Category: | javax / huffman encoding |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2022-07-15 19:23:09 |
| Source code size: | 1756 bytes / 63 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 103 / 231 |
| Version history: | 13 change(s) |
| Referenced in: | [show references] |