How I Shrunk a QR Kanji Table by 36% Using Dynamic Programming

datalog — Sun, 25 Oct 2026 00:01:20 +0000

QR codes have a dedicated Kanji mode that encodes supported characters in 13 bits each. A character like 龍 takes 24 bits in UTF-8, so choosing Kanji mode can save useful space.

For my JavaScript implementation, I needed to ship a lookup table mapping Unicode values to QR Kanji indices. The challenge was to preserve every mapping while keeping the embedded data as small as possible.

The table is only 16,384 bytes as binary data. Encode those bytes as Base64, though, and it becomes a 21,848-character string. I reduced that to 13,984 characters by describing the table with a small command language and using dynamic programming to choose the commands.

That is a 35.99% reduction in Base64 size, or 28.84% after gzip, measured on the table data alone. Here is how it works—and what those numbers leave out.

What the table is for

The table maps 8,192 possible QR Kanji indices to 16-bit Unicode values. There are 6,879 occupied positions; the rest contain 0xFFFF, a marker for an unused slot.

The table includes kanji, hiragana, katakana, and symbols. Its order matters: moving a character would change its QR Kanji index.

For QR generation, the useful lookup goes in the other direction: given a Unicode value, find the corresponding 13-bit index. The project's decoder builds that reverse lookup at initialization.

The task here is to store this particular reference table compactly while preserving every value and every empty position.

Base64 is a representation, not compression

Each source position takes two bytes, including empty positions:

8,192 positions × 2 bytes = 16,384 bytes

Turning those bytes into source text adds overhead:

Representation	Size
Raw 16-bit values	16,384 bytes
Joined hexadecimal string	32,768 chars
Base64 of the raw bytes	21,848 chars

String sizes exclude quotes. Both textual representations use ASCII characters, so their character counts also equal their UTF-8 byte counts.

Base64 is convenient for embedding bytes in JavaScript, but it does not make the data smaller. To reduce the string, I first needed a smaller byte stream.

Store instructions instead of individual values

The table is irregular, but it has useful local structure: empty runs, sequences with a constant step, and small differences between neighboring nonempty values.

The format describes those patterns with five command types:

00 — A(value): Emit one explicit 16-bit value.
01 — E(count): Advance over empty positions, preserving the previous nonempty value.
02 — R(start, step, count): Emit at least three values from an explicit start.
03 — P(step, count): Emit at least two values, beginning at previous + step.
04 and above — D(delta): Emit the previous nonempty value plus a signed difference.

Tokens are shown in hexadecimal. Full values occupy two bytes, most significant byte first. Tokens, counts, and encoded steps use unsigned varints, with seven data bits per byte.

ZigZag encoding maps small signed numbers to small unsigned numbers:

Signed:   0  -1  +1  -2  +2
Unsigned: 0   1   2   3   4

A delta is stored directly in its token as zigzag(delta) + 4. There is no separate opcode byte for each delta: 06, for example, means D(+1).

Arithmetic wraps modulo 65,536. Deltas and steps use the range −32,768 through 32,767; 0xFFFF remains reserved for empty entries. Series never cross empty positions.

A sequence in five bytes

One part of the table contains these 20 consecutive Unicode values, from 0x3041 through 0x3054:

ぁあぃいぅうぇえぉおかがきぎくぐけげこご

Storing them directly takes 40 bytes. The Delta encoder stores the first value in full, followed by nineteen +1 deltas:

A(3041), D(+1), D(+1), ...
3 bytes + 19 bytes = 22 bytes

The Full encoder describes the same fragment with a five-byte series command:

R(3041, +1, 20)

02 30 41 02 14
│  └─┬─┘ │  └── count: 20
│    │   └───── ZigZag(+1): 2
│    └───────── start: 0x3041
└────────────── explicit-series token

As Base64, the original fragment takes 56 characters. The series takes eight: AjBBAhQ=.

This is an especially regular fragment, so it illustrates the format rather than predicting the compression ratio for the whole table.

Choosing commands with dynamic programming

Having a compact series command does not tell us where to use it. At a given position, the encoder may have several valid choices: one full value, one delta, or series of different lengths.

A series has setup costs. An explicit series costs five bytes when its step and count each fit in one byte. If its values can already be written as three one-byte deltas, using a series would make the stream larger.

The encoder compares the command's cost plus the best cost of everything after it.

Let cost[i] be the minimum number of bytes needed to encode the suffix starting at position i. The terminal cost is zero:

cost[n] = 0;

// Conceptual recurrence; candidate generation is omitted.
for (let i = n - 1; i >= 0; i--) {
    cost[i] = Infinity;

    for (const command of candidatesAt(i)) {
        const next = i + command.count;
        const total = command.byteLength + cost[next];

        if (total < cost[i]) {
            cost[i] = total;
            choice[i] = command;
        }
    }
}

The implementation works backward through the table, evaluates full values, deltas, and valid series lengths, and handles empty runs. It records the selected command at each position. A forward pass then writes the chosen stream.

There is an important reason one cost per position is enough: the previous nonempty value is determined by the source table, regardless of which commands encoded the prefix. A full value and a delta that emit the same value leave the same reference for the next command. The encoder precomputes that reference at each position.

This gives a shortest-path interpretation: positions are nodes, commands are edges, and encoded byte lengths are weights. The optimizer minimizes the binary stream size for this format. It does not optimize the eventual gzip size.

Results across the complete table

The Delta encoder is a simplified baseline: it uses one initial full value, individual deltas, and empty-run commands. The Full encoder also selects full values and series, using dynamic programming to minimize the complete binary stream.

Here are the results for all 8,192 positions:

Method	Binary stream	Base64	Gzip of Base64
Original	16,384 bytes	21,848 chars	14,033 bytes
Delta encoder	10,784 bytes	14,380 chars	10,094 bytes
Full encoder	10,488 bytes	13,984 chars	9,986 bytes
Full encoder savings vs. Original	35.99%	35.99%	28.84%

The Full encoder reduces Base64 size by 35.99% compared with the Original representation, or 28.84% after gzip.

Gzip sizes were measured on standalone Base64 strings at level 9, excluding decoder code and JavaScript wrappers. Results for a complete bundle may differ.

What happens at runtime

Only the encoded data and decoder need to ship to the client; the optimizer can run beforehand.

The scripts have no external dependencies. To use the pre-encoded table:

<script src="kanji-lookup-table-base64.min.js"></script>
<script src="lookup-table-decoder.js"></script>
<script>
const lookup = decodeKanjiTable(KANJI_LOOKUP_TABLE_BASE64);
console.log(lookup[0x9F8D]); // 4340: 龍
</script>

The decoder returns an Int16Array(65536) indexed by Unicode value, containing a QR Kanji index or -1 for an unsupported character. This reusable lookup occupies 128 KiB in memory; the compression savings apply to the embedded data.

What I took away

The useful step was finding a small vocabulary for the data: full values, deltas, empty runs, and arithmetic series. Dynamic programming then removed the guesswork from choosing between those representations.

General-purpose compression still helped after that transformation. Whether the same approach is worthwhile elsewhere depends on the data, the decoder, and the complete application bundle.

The source, format details, and demo are available at datalog/kanji-base64.

Have you used a small custom format to shrink static data in a JavaScript application? I'd be interested to hear which patterns made the difference.

DEV Community: datalog