render_example_test.gno
2.96 Kb · 82 lines
1package huffmandemo
2
3// ExampleRender pins the realm's Render output as a testable example. Every
4// figure in it is derived from the fixed strings in huffmandemo.gno, so a
5// change in the library's table or bit count fails here.
6func ExampleRender() {
7 print(Render(""))
8 // Output:
9 // # Huffman coding
10 //
11 // Frequency-based prefix codes, demoing the [`p/moul/x/daily/huffman`](/p/moul/x/daily/huffman/v0) library. Rare symbols get long codes, common ones get short codes, and no code is a prefix of another, so the stream needs no separators.
12 //
13 // ## `abracadabra`
14 //
15 // | symbol | count | code | bits |
16 // | --- | --- | --- | --- |
17 // | `a` | 5 | `0` | 1 |
18 // | `b` | 2 | `100` | 3 |
19 // | `c` | 1 | `101` | 3 |
20 // | `d` | 1 | `110` | 3 |
21 // | `r` | 2 | `111` | 3 |
22 //
23 // The table is sorted by (length, symbol) and the codes are assigned from the lengths alone. That is what canonical means: the decoder rebuilds every code from one small integer per symbol, and two runs over the same input can never disagree about the table.
24 //
25 // ### The stream
26 //
27 // ```
28 // 01001110101011001001110
29 // ```
30 //
31 // 23 bits against 88 raw, 65 saved (73%).
32 //
33 // `Decode()` returns `abracadabra`, the input it started from. ✅
34 //
35 // ## What the skew is worth
36 //
37 // | input | symbols | raw | coded | saved |
38 // | --- | --- | --- | --- | --- |
39 // | `abcdefgh` | 8 | 64 bits | 24 bits | 62% |
40 // | `the quick brown fox jumps over the lazy dog` | 27 | 344 bits | 192 bits | 44% |
41 // | `mississippi` | 4 | 88 bits | 21 bits | 76% |
42 // | `aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcd` | 4 | 264 bits | 38 bits | 85% |
43 //
44 // The floor is the alphabet, not the algorithm: eight distinct bytes used once each cost three bits apiece, which is what a fixed-width code over eight symbols would have spent anyway. Everything past that floor is bought with skew.
45 //
46 // ## The two inputs that break a naive implementation
47 //
48 // **One distinct symbol.** Its leaf has no sibling, so the tree walk gives it a zero-bit code and the stream comes out empty: here `aaaaa` is `00000`, five one-bit codes, and it is the only incomplete code the library emits.
49 //
50 // **A payload that was edited.** `Decode` rebuilds the canonical table from the lengths it was handed and refuses a payload whose own bits disagree with it, so a stored `Encoded` cannot be bent into decoding as a different string:
51 //
52 // ```
53 // huffman: corrupt payload
54 // ```
55 //
56 // ## Try your own
57 //
58 // ```
59 // /r/moul/x/daily/huffmandemo/v0:mississippi
60 // ```
61}
62
63// ExampleRender_input pins the caller-supplied path, which is the only part of
64// the page that is not fixed.
65func ExampleRender_input() {
66 print(Render("/hello"))
67 // Output:
68 // # Huffman coding
69 //
70 // Input: `hello`
71 //
72 // | symbol | count | code | bits |
73 // | --- | --- | --- | --- |
74 // | `e` | 1 | `00` | 2 |
75 // | `h` | 1 | `01` | 2 |
76 // | `l` | 2 | `10` | 2 |
77 // | `o` | 1 | `11` | 2 |
78 //
79 // 10 bits against 40 raw, 30 saved (75%).
80 //
81 // [back](/r/moul/x/daily/huffmandemo/v0)
82}