Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

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}