Optimal text segmentation for QR Codes
Introduction
The QR Code standard offers multiple ways to encode text. The text string is represented as a sequence of zero or more segments, where each segment can have a different mode. The primary 4 modes are numeric, alphanumeric, byte, and kanji. Each mode supports a different set of representable characters and has a different bit cost per character.
The demo here shows that we can find the optimal way to split any given string into QR Code segments with the best modes. The technique of dynamic programming is used to minimize the total number of bits to encode.
Live application (JavaScript)
User input
| Error correction level: | |
| (between 1 and 40) |
Program output
Optimal text split
Segment details
| Idx | Mode | Head bits | Data bits | Seg bits | Chars | Text string |
|---|
- Idx
The index of the segment, starting from 0.
- Mode
Either byte, alphanumeric, numeric, or kanji.
- Head bits
Number of bits in the segment used for header info.
- Data bits
Number of bits in the segment used for textual data.
- Seg bits
Number of bits in the whole segment, equal to header plus data bits.
- Chars
Number of Unicode code points for non-byte mode, or number of UTF-8 code units for byte mode, contained in the segment.
- Text string
The user text substring being represented by the segment.
Various statistics
| Property | Optimal | Byte-only | Savings |
|---|---|---|---|
| Text length (code points) | |||
| Number of segments | N/A | ||
| QR Code version | |||
| Total segment bits | |||
The “optimal” column represents the algorithm being demonstrated above.
The “byte-only” column represents the scenario where the entire text is always put into a single segment in byte mode. This works because any text can be encoded as UTF-8 bytes. Moreover, a segment is allowed to have zero bytes, so it’s unnecessary to special-case this to generate zero segments. Thus, an encoder that always uses a single byte-mode segment results in the simplest implementation that can handle unrestricted text.
For both the optimal and byte-only segmentations, the QR Code version is either the minimum version that fits all the segment bits, or the user-specified minimum version, whichever value is greater.
For both segmentations, the total segment bits includes all segment header and data bits. But this value excludes the terminator pseudo-segment, padding bits, padding bytes, and remainder bits.
If the list of segments requires more bits than what the largest possible QR Code (of version 40) at the user-specified error correction level can offer, then the message “Too long” is displayed.
Notes
For each segment, its number of header bits depends on the mode and the QR Code version. The header bits strictly increase when going from version 9 to version 10 and when going from 26 to 27 – except for the one case where a segment in byte mode has its header length stay the same from version 26 to 27. Because of this behavior, a text segmentation that is optimal for versions 1 to 9 might not be optimal for other versions.
The algorithm starts at the lowest version number, computes the optimal segmentation, and adds up all the segment bit lengths. If all the data and error correction code codewords fit in a QR Code of that version, then we’re done. Otherwise it increments the version number and repeats the process. This is why it’s necessary to specify the error correction level, because it influences the minimum version needed to contain a given text string. Also, the minimum version user input can be used to artificially force the version higher to see how it affects the segmentation.
This JavaScript demo only computes how a given text string should be split into optimal segments and what the final size is. However, it doesn’t actually encode the bits or generate QR Codes. The source TypeScript code and compiled JavaScript code are available for viewing. In the codebase, the most important function which performs the dynamic programming to compute the optimal segmentation is
computeCharacterModes().My Java QR Code library has a class (QrSegmentAdvanced) which performs the optimal segmentation and encodes the character bits. Then, the list of segments can be fed into the QR Code generator to make a barcode. This functionality is available exclusively in the Java language port, not the other languages.
The official QR Code specification document, in section annex J.2, tries to give an algorithm to split an input text string into different-mode segments to reduce the total bit length, having a similar goal as my algorithm. But that spec falls short in numerous ways. In the case (a)(2) for initial kanji, phrases like “subsequent data” and “the following n byte pairs” are ambiguous about what part of the input string they refer to. Also, case (a)(2) does not cover all subcases. Case (d)(3) for switching from numeric to alphanumeric mode is definitely suboptimal for some strings because after the algorithm would encode the first next character in alphanumeric mode and then switch to byte mode for the second next character. There doesn’t exist a hypothetical case (e) for what to do while in kanji mode. Overall, their algorithm in English prose is long and hard to read, and there is no obvious mathematical justification for why it should yield a minimal encoding. Meanwhile, my independently developed algorithm is complete and correct (minimal) for all possible inputs. Either way, note that length optimization is optional for the encoder, and it’s legal to use more bits than strictly necessary to encode a piece of text.
It’s possible to use Extended Channel Interpretation mode segments to switch to national character encodings and save space. For example, text with many accented Latin characters can be encoded in fewer bytes in ISO-8859-1 than in UTF-8. However, the meanings of ECIs are outside the QR Code specification, using any character encoding other than UTF-8 is generally a bad idea, and supporting tens of different character encodings would greatly complicate my optimization algorithm.
The dynamic programming algorithm for optimal segmentation runs in linear time and linear space. It requires scanning the entire string backward and then forward, hence it is not a streaming algorithm.
The algorithm
Basic info on how QR Code segments work:
Each segment has three fields: Mode (4 bits), character count (variable bits depending on mode and current version), and character data (variable bits depending on mode and character count).
For a given mode, the number of character count bits either stays the same or increases as the QR Code version increases. For example, a numeric mode segment’s character count field is 10 bits for versions 1 to 9, 12 bits for versions 10 to 26, and 14 bits for versions 27 to 40.
Numeric mode can encode the set of 10 characters ‹
0123456789›. It uses 31/3 bits per character, rounded up to an integer. For example, a numeric mode segment containing 0 characters uses 0 bits; 1 char is 4 bits; 2 chars is 7 bits; 3 chars is 10 bits; 4 chars is 14 bits.Alphanumeric mode can encode the set of 45 characters ‹
0123456789›. It uses 51/2 bits per character, rounded up to an integer. So 1 character uses 6 bits; 2 chars is 11 bits; 3 chars is 17 bits; 4 chars is 22 bits.ABCDEFGHIJKLM NOPQRSTUVWXYZ $%*+-./: Byte mode is conventionally interpreted as UTF-8 text. Hence any Unicode code point can be encoded, and each CP uses between 1 and 4 bytes. The mode uses 8 bits per byte (obviously), which means 8 to 32 bits per CP.
Kanji mode can encode most of the characters defined in Shift JIS. The encodable set includes kanji used in Japan, hiragana, katakana, East Asian punctuation, full-width ASCII, Greek, Cyrillic, and miscellaneous, but not ordinary ASCII. The mode uses 13 bits per character.
Let s be a text string we want to segment optimally, and let n be the length of s in code points. Let v be the QR Code version we are using.
First, define an overly powerful recursive function: Let f(i, m), requiring 0 ≤ i ≤ n, be the minimum number of bits to encode the suffix starting at character index i (0-based), such that the encoding starts with a segment of mode m. To satisfy the constraint of starting with a certain segment mode, it is permitted to make empty segments containing no characters. Also, this function uses fractional bit counts to match the observed behavior of numeric and alphanumeric segments. To ensure the numerator is always an integer, the smallest choice of denominator is 6. Numeric mode uses 20/6 bits per character; alphanumeric mode uses 33/6; byte mode uses 48/6 to 192/6; kanji mode uses 78/6.
Second, we reason about the base case. For each mode m, let f(n, m) = (bit length of empty segment of mode m) = 4 + (number of character count bits for a segment of mode m at version v). Note that index n is at the end of the string, which means taking a suffix of length 0.
Third, we reason about the inductive step when decrementing i:
For each index 0 ≤ i < n and each mode m, f(i, m) is computed from properties of the character c at index i and the values of f(i+1, m′) for all possible values of m′. In particular, f(i, m) minimizes a certain cost expression over all m′. If char c can be encoded in mode m′, then the subtotal cost equals the bit length of encoding c in m′ plus f(i+1, m′). Iff m ≠ m′, then the subtotal is rounded up to the nearest integer, and the bit length of a new empty segment header at the beginning of this string suffix is also added. Otherwise c is not encodable in m′, then the case is ignored in the minimization. And because byte mode can encode any character, there is a well-defined minimum value.
Furthermore, let g(i, m) be the mode m′ that was selected in the minimization to yield the final value of f(i, m). In other words, f(i, m) bits is achievable by choosing to encode the foremost character of that suffix in mode g(i, m).
Now we have computed a table of bit costs, which is f(i, m) for 0 ≤ i ≤ n and for m in all 4 possible modes. Initialize a blank array c of length n to store the best mode needed to encode each code point.
Fourth, we work forward in the cost table to figure out the best mode for each code point index:
Find a mode m0 that minimizes f(0, m0), and store c[0] = m0. This tells us the best mode to start in.
Update m1 = g(1, m0) so that m1 represents the best mode to encode the code point at index 1, and store c[1] = m1.
Update m2 = g(2, m1), and store c[2] = m2.
Repeat until we finish storing to c[n−1].
Finally, with the array c representing the best mode for each code point in the input string, we scan the array forward, starting a new segment whenever the mode changes, and putting each current code point into the current open segment. This can actually be combined with the previous step and the array c doesn’t need to be explicitly stored.