---
title: "Prefix codes"
description: "Encode and decode variable-length prefix codes with custom codebooks, truncated binary, unary and gamma"
canonical_url: "https://encodings.agntn.dev/encodings/prefix"
---
# Prefix codes

> Encode and decode variable-length prefix codes with custom codebooks, truncated binary, unary and gamma

<encoding-facts name="prefix">



</encoding-facts>

`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.

```sh
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
```


## Sitemap

See the full [sitemap](https://encodings.agntn.dev/sitemap.md) for all pages.
