Encodings

Prefix codes

Encode and decode variable-length prefix codes with custom codebooks, truncated binary, unary and gamma
IDprefix18 / 20prefix · 2 characters
Encoding / Prefix codes

Prefix code

Short codewords for common symbols, no separators, and no codeword starts another.

Overhead
text only
Padding
none
Standard
Kraft-McMillan inequality; Elias, IEEE Trans. Inf. Theory 21 (1975)
Used by
Huffman tables, Golomb and Elias codes, bit puzzles
family 1 / 20

Sample

Out
01011001110011110101100
Back
"ABRACADABRA" · kraft 1

Options

codebookstring
optional
Codewords by symbol, such as A=0 B=10 C=11, or a JSON object such as {" ":"0"}
codestring
optional
In place of a codebook: truncated binary for n symbols from 0, unary from 0 or Elias gamma from 1
nnumber
optional
Truncated binary: how many symbols, from 2
separateboolean
default false
Put a space between codewords

Access

Importimport { prefix } from "@agntn/encodings/prefix"
CLIencodings encode prefix ABRACADABRA --codebook 'A=0 B=10 R=110 C=1110 D=1111'
Tryplayground with the sample above

prefix turns bits into symbols using variable-length codewords. Give it a codebook and let it read the stream.

ts
encode("prefix", "ABRACADABRA", { codebook: "A=0 B=10 R=110 C=1110 D=1111" });  // "01011001110011110101100"
decode("prefix", "01011001110011110101100", { codebook: "A=0 B=10 R=110 C=1110 D=1111" }).bytes;  // "ABRACADABRA"

That's the whole trick. No hand-written automaton next to your script, and no arguing with it about the last few bits. Algorithm textbooks feed this exact word to Huffman, so it gets to cast the first spell here too.

How do I use my own codebook?

Pass codebook as text. Each entry maps one character to one codeword. Separate entries with spaces or commas. Use = or : between each symbol and its bits.

Need a space, comma or = as a symbol? Pass a JSON object string instead.

ts
encode("prefix", "a b", { codebook: '{"a":"0"," ":"10","b":"11"}' });  // "01011"

Codebooks must be prefix-free. No codeword can start another. That means the decoder doesn't need separators between codewords. Each one can run up to 256 bits, which is plenty for any Huffman table you'd want to read by hand.

A conflicting pair is refused by name. Duplicate codewords are refused too.

ts
decode("prefix", "0", { codebook: "A=0 B=01" });  // throws: Invalid option codebook=A=0: is not prefix-free: "A" (U+0041) = 0 is a prefix of "B" (U+0042) = 01

An input symbol also needs its own entry. The error points at the missing one.

ts
encode("prefix", "ABZ", { codebook: "A=0 B=10 R=110 C=1110 D=1111" });  // throws: prefix: "Z" (U+005A) at index 2 has no codeword; add it to the codebook

What does the Kraft sum tell me?

The Kraft sum describes how much of the code tree is occupied. It's returned as an exact fraction.

ts
prefix.kraft({ codebook: "A=0 B=10" });  // "3/4"

A sum of 1 means the code is complete. A sum of 3/4 leaves free leaves on the tree. Decode details include kraft too.

What happens to bits at the end?

Decoding skips ASCII whitespace between bits. An unfinished codeword comes back in details, not padded or discarded.

ts
decode("prefix", "0101100111", { codebook: "A=0 B=10 R=110 C=1110 D=1111" }).details;  // { kraft: "1", leftover: "111", leftoverBits: 3 }

Here 111 starts a codeword but runs out of tape. leftoverBits tells you its length. Keep those bits if more input follows.

An incomplete code can also encounter bits that start no codeword. That's an error, with the index included.

ts
decode("prefix", "0 11", { codebook: "A=0 B=10" });  // throws: prefix: bits 11 at index 2 start no codeword

How do I use truncated binary?

Set code to truncated and supply n. It's the number of symbols and must be at least 2. For n: 5, the codewords are 00, 01, 10, 110 and 111.

ts
encode("prefix", "0 1 2 3 4", { code: "truncated", n: 5, separate: true });  // "00 01 10 110 111"
decode("prefix", "00110111", { code: "truncated", n: 5 }).bytes;  // "0 3 4"

Built-in codes use decimal numbers as symbols. Write them separated by spaces, or commas when reading. separate adds spaces between encoded codewords. It applies only to encoding and defaults to false.

You can inspect the generated table with prefix.codebook({ code: "truncated", n: 5 }). It returns { "0": "00", "1": "01", "2": "10", "3": "110", "4": "111" }.

How do unary and Elias gamma work?

Unary writes a number as that many ones followed by a zero. It accepts numbers from 0 through 255, so no codeword runs past 256 bits.

ts
encode("prefix", "0 1 2 5", { code: "unary", separate: true });  // "0 10 110 111110"
decode("prefix", "1110110", { code: "unary" }).bytes;  // "3 2"

Elias gamma starts at 1. Write the number in binary. Prefix it with a zero for each bit after its first.

ts
encode("prefix", "1 2 3 4 17", { code: "gamma", separate: true });  // "1 010 011 00100 000010001"
decode("prefix", "00100011010", { code: "gamma" }).bytes;  // "4 3 2"
encode("prefix", "0", { code: "gamma" });  // throws: prefix: the number 0 at index 0 has no codeword; Elias gamma starts at 1

Can identify find a prefix code?

identify never guesses prefix. Without a codebook, there's nothing to read. And unary would happily read any bits at all. Great at counting, lousy at guessing.

How do I use aliases and the CLI?

The registry name is prefix, in the prefix family. huffman and prefixcode are aliases.

ts
encode("huffman", "BAD", { codebook: "A=0 B=10 R=110 C=1110 D=1111" });  // "1001111"

The subpath @agntn/encodings/prefix exports prefix and PREFIX_CODES.

The CLI accepts --codebook, --code, --n and --separate. Decoded text goes to stdout. Details go to stderr.

shell
encodings decode prefix 0101100111 --codebook "A=0 B=10 R=110 C=1110 D=1111"

This prints ABRA on stdout. On stderr:

text
kraft: 1
leftover: 111
leftoverBits: 3