Unicode Technical Report #6
A Standard Compression Scheme for Unicode®

This report presents the specifications of a compression scheme for Unicode and sample implementation. The design phase is completed with the publication of this technical report, but we still welcome information regarding implementation experience or corrigenda.

Status of this document

This document has been considered and approved by the Unicode Technical Committee for publication as a Technical Report. At the current time, the specifications in this technical report are provided as information and guidance to implementers of the Unicode Standard, but do not form part of the standard itself. The Unicode Technical Committee may decide to incorporate all or part of the material of this technical report into a future version of the Unicode Standard, either as informative, or as normative specification. Please mail corrigenda and other comments to unicore@unicode.org.

Compression Scheme for Unicode

Compressing Unicode text for transmission or storage, as mentioned in section 5.2 of The Unicode Standard, Version 2.0, is often useful. The traditional general-purpose data compression schemes (for example Huffman or LZW) are effective, but for best results they require considerable context. In the course of implementing Unicode, it became apparent that there is a need for a compression scheme that is efficient even for short strings. The compression scheme proposed here compresses Unicode text into a sequence of bytes by taking advantage of the characteristics of Unicode text. The resulting compressed sequence can be used on its own or as further input to a general-purpose file or disk-block based compression scheme. The latter achieves even better compression than either method alone.

Scope

The Standard Compression Scheme for Unicode will:

• express all code points in Unicode
• approximate the storage size of traditional character sets
• work well for short strings
• provide transparency for characters between U+0020-U+00FF, as well as CR, LF and TAB.
• support very simple decoders
• support simple as well as sophisticated encoders

It does not attempt to avoid the use of control bytes (including NUL) in the compressed stream.

The compression scheme is mainly intended for use with short to medium length Unicode strings.The resulting compressed format is intended for storage or transmission in bandwidth limited environments. It can be used stand-alone or as input to traditional general-purpose data compression schemes. It is not intended as processing format or as general purpose interchange format.

Description

Strings in languages using small alphabets contain runs of characters that are coded close together in Unicode. These runs are typically interrupted only by punctuation characters, which are themselves coded in proximity to each other in Unicode (usually in the Basic Latin range).

The basic concept of the compression scheme is to set up a so-called dynamically positioned window, which is region of 128 consecutive characters in Unicode. This window can be positioned to contain the alphabetic characters in question. Each character that fits this window is represented as a byte between 0x80 and 0xFF in the compressed data stream. A byte from 0x20 to 0x7F (as well as CR, LF, and TAB) always means a character from the Basic Latin range (or a control character).

Runs of characters from a selected window which are intermixed only with characters from the range U+0020--U+007F can be compressed without requiring tag bytes beyond the initial setup of the window.

Tag bytes are bytes in the range 0x00 to 0x1F (except CR, LF, TAB) that are used as commands to select, define and position windows, or to escape to an uncompressed stream of Unicode text. Strings from languages using large alphabets use this uncompressed mode.

There are scripts for which the characters ordinarily show larger fluctuation in code values than can be contained in a dynamically positioned window. For these areas of the Unicode code space, windows cannot be set. Instead, an escape to uncompressed Unicode can be used.

Encoders and Decoders

There is more than one possible encoding for a given Unicode string, and it is possible to trade off speed of encoding against the compression achieved.

It is possible to write a simple encoder for this scheme which uses a subset of the allowed tags. For example it could use only SCU, SD0, UQU and UC0 and still achieve respectable compression with typical text.

Definitions

All terms not defined here shall be as defined in the Unicode Standard.

 

Single Byte Mode - a mode where each character is represented in compressed form as a single byte.

 

Unicode Mode - a mode where each character is represented by a two byte sequence, corresponding to the Unicode character value with the most significant byte first.

 

Window - a range of 128 consecutive Unicode character values.

 

Locking Shift - a permanent shift to a new active window.

 

Non-locking Shift - a non-locking shift selects a window only for the immediately following character, before returning to the active window.

 

Dynamically positioned Window - a window with a position that can be selected starting at a multiple of 128 or at one of several predefined locations. Dynamically positioned windows can be accessed by locking or non-locking shifts.

They are only used in single byte mode with bytes in the range 0x80 to 0xFF.

 

Static Window - a window with fixed position which can be accessed by non-locking shift only. They are used in single byte mode with bytes in the range 0x00 to 0x7F.

 

Tag byte - any of the predefined single byte values that select compression functions in this scheme.

 

Index byte - a byte that is used as an index into the offset table (e.g.to select a window offset).

Conformance

Decoders are required to accept and interpret the full range of tags and arguments defined here. The action of a conformant decoder on illegal or reserved input is undefined.

Conformant Encoders must not emit illegal or reserved combinations of bytes. Encoders are not required to utilize (or be able to utilize) all the features of this compression scheme. Encoders must be able to encode strings containing any valid sequence of Unicode characters. The action of a conformant encoder on malformed input is undefined.

Encoders and decoders must always start in the initial state defined below.

Compression

The Unicode Compression Scheme compresses text by defining a set of windows into the Unicode code space and interpreting byte values relative to the position of the window currently in force. Thus characters from languages that use a small alphabet can be encoded with one byte per character. By switching to Unicode mode, non-alphabetic scripts can be encoded with two bytes per character.

The compression scheme is capable of compressing strings containing any Unicode character. Some control character and private use character values overlap with the tag byte values. They can still be encoded, though at a cost of an additional byte per character.

There are two compression modes:

• single byte mode, where each byte represents one character and is interpreted according to the current window setting.
• Unicode mode, where each character is represented by two bytes in the standard way with the most significant byte first.

(In the following text all byte values are given in hex.)

Single byte mode

Compressed text in single byte mode consists of a tag byte followed by zero, one, or two argument bytes followed by one or more text bytes. Single byte mode is in effect from initialization until the end of input or until an SCU tag.

An SCU tag indicates that all following bytes are interpreted in Unicode mode.

An SQU tag indicates that the following two bytes are interpreted as a Unicode character, most significant byte first.

In single byte mode, bytes between 00 and 1F are used as tags. The tags used in single mode are shown in Table X-1, their corresponding byte values are given in Table X-6.

Table X-1. Tags for use in Single-byte Mode

Unicode Mode

In Unicode mode, each character is encoded by two bytes in the standard way with the most significant byte first. This mode has its own set of reserved byte values which are used as tags, as shown in Table X-2. Their corresponding byte values are given in Table X-6. Once selected by SCU, Unicode mode is in effect until the end of input, or until any tag that selects an active window.

Quoting in Unicode mode

Note that in Unicode mode all tags are single bytes. Therefore all bytes which are not tag bytes are the most significant bytes (MSB) of a Unicode character. Each reserved tag value collides with 256 Unicode characters.

A quoting mechanism is defined for Unicode mode to enable a character to be encoded whose first byte would collide with a tag value. The two bytes following a UQU tag are taken as a Unicode character.

The tags values used in Unicode mode are chosen so that they correspond to the most significant bytes of Unicode character values from the private use area, since private use characters are not in frequent use.

Table X-2. Tags for use in Unicode mode

Windows

Windows are always 128 code positions in length. There are two kinds of windows, static (or fixed position) windows and dynamically positioned windows.

Dynamically Positioned Windows

There are 8 dynamically positioned windows that are used when compressing alphabetic text. Locking shift tags in the byte stream are used to select an active window, and other tags are used to redefine the position of any window. At initialization, the dynamically positioned windows are in their default positions given in table X-5.

Locking-Shifts (Dynamically positioned windows only)

An SCn tag (or UCn tag in Unicode mode) is used for a locking shift to dynamically positioned window n. Following such a tag, bytes in the range 80 to FF represent characters in the active dynamically positioned window. Therefore any byte xx between 80 and FF encodes the Unicode character

Unicode character = DynamicOffset[n] + (xx - 80)

The values for the starting offsets of dynamically positioned windows can change. Their initial values are specified in Table X-5.

Bytes in the range 20 to 7F always represent the corresponding character from the Basic Latin block (U+0020 to U+007F). In addition, LF, CR and HT represent U+000A, U+000D and U+0009 respectively.

Window Positioning

An SDn tag (or UDn tag) followed by an index byte repositions window n and makes it the active window.

In order to keep the encoding compact, the positions of the dynamically positioned windows are not set directly but defined via a lookup table. Each window definition tag in the byte stream is followed by one byte that is used as an index into this table. The set of legal positions is defined by the Window Offset Table given in Table X-3.

The first part of the Window Offset Table defines half blocks covering the alphabetic scripts, symbols and the private use area.

The individual entries from F9 onwards cover the scripts that cross a half-block boundary, plus one useful segment of European characters. Some collections of miscellaneous symbols and punctuation would also cross half-block boundaries, but these characters are likely to occur rarely, or in isolation. Therefore no special offsets for them are included here.

Table X-3. Window Offset Table

Extended Windows

An SDX tag (or UDX tag in Unicode mode) followed by two argument bytes (hbyte and lbyte) defines window n in the expansion space and makes it the active window. The window index n is given by the top 3 bits of hbyte. The window offset is calculated from the remaining thirteen bits of hbyte and lbyte as follows:

offset = 10000 + (80 * ((hbyte & 1F) * 100 + lbyte))

where & is the bitwise AND operator and all values are in hexadecimal notation. After an extended Window is defined each subsequent byte in the range 80 to FF represents a surrogate pair.

The following diagram shows how the bits in the two bytes following the SDX (or UDX) and a subsequent data byte map onto the bits in the resulting surrogate pair.

     hbyte         lbyte          data    nnnwwwww      zzzzzyyy      1xxxxxxx

     high-surrogate     low-surrogate    110110wwwwwzzzzz   110111yyyxxxxxxx

Non-locking Shifts and Static Windows

An SQn tag switches temporarily to a different window for just one character. The byte following the tag is interpreted relative to the window n, and then the window reverts to the previous value. This is called a non-locking shift.

If the byte following the SQn is in the range 80 to FF, dynamically positioned window n is used.

Static Windows

There are 8 static windows, seven of which are used only in conjunction with non-locking shifts. If any data byte following an SQn tag is in the range 00 to 7F, static window n is used. Therefore byte xx between 00 and 7F encodes the Unicode character

Unicode character = StartingOffset[n] + xx

The positions of static windows are as given in Table X-4 and cannot be changed. They cover character ranges which contain characters that tend to occur in isolation and therefore are suitable for access via non-locking shifts. Static window 0 is also used when bytes following an SCn or UCn are in the range 80 to FF.

Table X-4. Static Window Positions

Use of SQ0

SQ0 is used specifically to quote characters that would otherwise collide with tag bytes. It may not be used with bytes in the range 20 to 7F. These values are shall not be used by encoders. Decoders are not required to detect them as errors.

Note that this restriction applies only to SQ0, which maps to ASCII. SQ1 to SQ7 may be followed by any byte value.

As in the general case of SCn a following byte value in the range 80 to FF indicates use of dynamically positioned window 0.

Initial State

The initial state of encoder and decoder is as follows:

1. single byte mode
2. locking-shift
3. window 0 as the active window
4. all windows in their default positions

Note: It is expected that encoder and decoder are reinitialized at the beginning of each string.

Initial Window Settings

Encoder and Decoder are initialized with certain default settings for the windows. These allow use of the windows without predefining them, saving a few bytes for common cases.

Encoder and Decoder always start with dynamically-positioned window 0 active, so a string of characters that consists entirely of characters from the range U+0020--U+00FF plus CR, LF, TAB is effectively converted to ISO 8859-1.

Default positions are assigned based on the following criteria:

• Dynamically positioned windows: Frequently occurring ranges of character which commonly appear in runs containing characters in the selected range or intermixed with characters in the range U+0020--U+007F.
• Static windows: ranges of characters which commonly occur in isolation.

The choice of offsets is intended to enable handling most languages by requiring at most the definition of one extra window, at the cost of a single byte.

The default settings of the dynamically positioned windows are shown in Table X-5. The static window positions are fixed and are shown above in Table X-4.

Table X-5. Default Positions for Dynamically Positioned Windows

Notes

Surrogate Pairs

A surrogate pair can be encoded in any of these ways:

1. in Unicode mode, as a surrogate pair.
2. in Single byte mode, as a surrogate pair, with each value quoted: SQU hbyte1 lbyte1 SQU hbyte2 lbyte2.
3. in Single byte mode, as a single byte, by setting a dynamically positioned window to the appropriate position using an SDX or UDX tag.
4. or any otherwise legal combination of 1.) and 2.).

It is not possible to set a window to the surrogate range, such that one byte would represent one half of a surrogate pair.

Private Use Area

A character in the Private Use Area can be encoded in any of these ways:

• in Unicode mode, by quoting with UQU.
• in Unicode mode, if above F2FF, with no quoting.
• in Single byte mode, by quoting with SQU.
• in Single byte mode, as a single byte, by setting a dynamically positioned window to the required position in the Private Use Area using an SDn or UDn tag.

Tag Allocation

The tag byte values used in single mode are shown in Table X-6. In this table, "pass" means that the byte value (xx) represents the Unicode value U+00xx.

Table X-6. Single Mode Tag Values

The tag byte values used in Unicode mode are shown in Table X-7. In this table MSB means that the byte value is used as the most significant byte of a two byte sequence representing a Unicode value. There are no restrictions on the values of the byte immediately following an MSB. 

Table X-7. Unicode Mode Tag Values

Examples (informative)

German

German can be written using only Basic Latin and the Latin-1 supplement, so all characters above 0x0080 use the default position of dynamically positioned window 0.

Unicode values (9 characters):

00D6 006C 0020 0066 006C 0069 0065 00DF 0074

Compressed (9 bytes):

D6 6C 20 66 6C 69 65 DF 74

Russian

Russian can use the default position of window 2. The first byte of the compressed data is the tag SC2.

Unicode values (6 characters):

041C 043E 0441 043A 0432 0430

Compressed (7 bytes):

12 9C BE C1 BA B2 B0

Japanese

Japanese text profits almost always from the multiple predefined windows in SCSU. For more details on this sample click here.

Unicode values (116 characters)

3000 266a 30ea 30f3 30b4 53ef 611b
3044 3084 53ef 611b 3044 3084 30ea 30f3
30b4 3002 534a 4e16 7d00 3082 524d 306b
6d41 884c 3057 305f 300c 30ea 30f3 30b4
306e 6b4c 300d 304c 3074 3063 305f 308a
3059 308b 304b 3082 3057 308c 306a 3044
3002 7c73 30a2 30c3 30d7 30eb 30b3 30f3
30d4 30e5 30fc 30bf 793e 306e 30d1 30bd
30b3 30f3 300c 30de 30c3 30af ff08 30de
30c3 30ad 30f3 30c8 30c3 30b7 30e5 ff09
300d 3092 3001 3053 3088 306a 304f 611b
3059 308b 4eba 305f 3061 306e 3053 3068
3060 3002 300c 30a2 30c3 30d7 30eb 4fe1
8005 300d 306a 3093 3066 8a00 3044 65b9
307e 3067 3042 308b 3002

Compressed (178 bytes)

08 00 1b 4c ea 16 ca d3 94 0f 53 ef 61 1b e5 84
c4 0f 53 ef 61 1b e5 84 c4 16 ca d3 94 08 02 0f
53 4a 4e 16 7d 00 30 82 52 4d 30 6b 6d 41 88 4c
e5 97 9f 08 0c 16 ca d3 94 15 ae 0e 6b 4c 08 0d
8c b4 a3 9f ca 99 cb 8b c2 97 cc aa 84 08 02 0e
7c 73 e2 16 a3 b7 cb 93 d3 b4 c5 dc 9f 0e 79 3e
06 ae b1 9d 93 d3 08 0c be a3 8f 08 88 be a3 8d
d3 a8 a3 97 c5 17 89 08 0d 15 d2 08 01 93 c8 aa
8f 0e 61 1b 99 cb 0e 4e ba 9f a1 ae 93 a8 a0 08
02 08 0c e2 16 a3 b7 cb 0f 4f e1 80 05 ec 60 8d
ea 06 d3 e6 0f 8a 00 30 44 65 b9 e4 fe e7 c2 06
cb 82

All Features

The following sample compressed string contains all the features of the compression scheme, but limited to only representative instances of the eight SQn and the seventeen SCn/UCn, SDn/UDn, and SDX/UDX pairs. The text is repeated to demonstrate how the same substring can yield different compressed strings.

Unicode values (20 characters)

0041 00df 0401 015f 00df 01df f000 dbff dfff 000d 000a 0041 00df 0401 015f 00df 01df f000 dbff dfff

Compressed (35 bytes)

41 df 12 81 03 5f 10 df 1b 03 df 1c 88 80 0b bf ff ff 0d 0a 41 10 df 12 81 03 5f 10 df 13 df 14 80 15 ff

Possible Private Extensions (informative)

During the design and review phase of the compression scheme, extensions were repeatedly suggested to handle the two following situations. Since these extensions were not accepted as part of the compression scheme itself, it was felt useful to document them here.This will show how to solve certain problems by adding higher level protocols.

1. Avoiding (most) control byte values

After encoding, replace any control byte by DLE (0x10) followed by the same byte + 0x40. NUL becomes DLE followed by '@' (0x40). DLE is replaced by DLE followed by U+0050. Before decoding, perform the opposite transformation.

2. Handling runs of the same character

Before encoding, replace any run of 4 or more Unicode characters by '@' (U+0040), followed by the character to repeat, followed by a 16-bit count (packed into one Unicode character). The sequence ------------------------ becomes '@' '-' '!'. The @ sign itself is replaced by @@U+0001. After decoding, perform the reverse operation.

Acknowledgments

The authors would like to thank to Dr. Laura Wideburg for assistance in copy editing. Thanks to David Pope and Roman Czyborra for bug reports.

Authors

The original concept of a standard compression scheme for Unicode was implemented at Reuters and proposed by Misha Wolf and Charles Wicksteed. Extensions and refinements were proposed by Mark Davis, Ken Whistler and Martin Duerst. The final text for the Technical report and the sample implementations were created by Asmus Freytag.

Changes from previous revisions:

Note: none of the fixes imply a change to the specification.

Changes to the text

1. Russian uses SC2 instead of SC7 as claimed in the examples.

2. The 'All Features' example has been corrected.

3. A new Japanese example has been added.

4. Changed table X-3 from

to

to match the correct value used in the sample code.

5. Corrected 1FFF to 1F in the offset calculation equation for defining extended windows.

6. Corrected a few minor typographical errors (6/5/99).

Changes to the sample code (revision 005)

1. Corrected dynamic offset in for Window 1 in sample code to 0x00C0 to match table X-5 of specification (updated internal version number of SCSU.java to 005 and commented changed source line).

2. Changed methods in the expander from private to protected to support a minor update of the driver program. (Updated internal version number to 005 in Expand.java and added a comment).

3. Minor improvements to the driver program.(Updated internal version number to 005 in CompressMain.java)

Copyright

Copyright © 1996-1998 Unicode, Inc.. All Rights Reserved. The Unicode Consortium makes no expressed or implied warranty of any kind, and assumes no liability for errors or omissions. No liability is assumed for incidental and consequential damages in connection with or arising out of the use of the information or programs contained or accompanying this technical report.

The accompanying sample implementation is provided as is by Unicode, Inc. No claims are made as to fitness for any particular purpose. No warranties of any kind are expressed or implied. The recipient agrees to determine applicability of information provided.

Unicode and the Unicode logo are trademarks of Unicode, Inc., and are registered in some jurisdictions.

The Unicode Home Page: http://www.unicode.org

Unicode Technical Reports reside at: http://www.unicode/unicode/reports