XDelta Compression Format

Overview

The XINA Delta (xd) compression format is a simple, high performance format for compression and decompression of a list of numeric values into a string. The compression is most efficient for data sets with frequently repeated values, or predictable value iterations.

The format consists of a few main features:

a comma separated list of plain text values
blank values indicating either repeating the previous value, or a static value
"XnY" indicates repeating value X exactly Y times
values may be a delta of the previous value (which can be applied recursively)
transformation of values (typically just to reduce their character length, since the format is plain-text)

Format Grammar

The version 1 (v1) format grammar is asdefined ~~follows:~~here. Note: whitespace is not permitted in the format.

string

version ':' all_values
version ',' parameters ':' all_values

version

'v' integer

parameters

parameter
parameter ',' parameters

parameter

delta
blank
scalar
offset

delta

'd0'
'd1'
'd2'
'd'
'dd'

blank

'br'
'bn'
'b' number

scalar

'*' number
'/' number

offset

'+' number
'-' number

all_values

""
nonblank_value
nonblank_value ',' values

values

value
value ',' values

value

blank_value
nonblank_value

blank_value

""
'n' integer

nonblank_value

'n'
number
number 'n' integer
'nn' integer

number

integer fraction exponent

integer

pos_integer
neg_integer

pos_integer

digit
onenine digits

neg_integer

'-' digit
'-' onenine digits

digits

digit
digit digits

digit

'0'
onenine

onenine

'1' . '9'

fraction

""
'.' digits

exponent

""
'E' sign digits
'e' sign digits

sign

""
'+'
'-'

Version

The version denotes the encoded format for backwards compatibility, in case of future updates or changes. If the string does not include the version, it is assumed to be version 0, which is detailed at the end of this document.

Blanks

The blank parameter indicates how blank (empty) values should be interpretted. 'br' (the default) repeats the previous value. 'b' number assigns a static numeric value. 'bn' assigns the null value. 'br' will be the most efficient in most cases, unless the data set contains almost entirely a single value.

Given the data set:

0, 0, 1, 1, 1, 2, 2

A br encoding would be:

v1,br,d0:0,,1,,,2,

A b0 encoding would be:

v1,b0,d0:0,,1,1,1,2,2

Which can be further reduced to:

v1,b0,d0:0,,1n3,2,2

Note, in this example, the first value must still be explicitly specified, per the first value non-blank rule.

Delta

The delta parameter defines the behavior for storing values as changing relative to the previous value. This can either be 'd0' (disabling the feature), 'd1' (the default, change from previous value), or 'd2' (change of change from previous value). Note, 'd' is an alias for 'd1', and 'dd' is an alias for 'd2', kept for backwards compatibility.

Given the simple data set:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

The d1 encoding would be:

0, 1, 1, 1, 1, 1, 1, 1, 1, 1

Which can be further reduced to

0,1n9

The d2 encoding would be:

0, 1, 0, 0, 0, 0, 0, 0, 0, 0

Which can be further reduced to

0,1,0n8

Note that in d1 encoding, the first value is not a delta but a static value. Likewise, in d2, the first value is static, and the second is the delta relative to the first.

When dealing with null values, the delta rules ignore any null values. For example, given the data set:

null, null, 0, 1, 2, 3, 4, null, 5, 6, 7, 8, 9

The d1 encoding would be:

n, n, 0, 1, 1, 1, 1, n, 1, 1, 1, 1, 1

Which can be further reduced to

nn2,0,1n4,n,1n5

Delta Considerations for Fractional Values

When using the delta feature with fractional values, errors may be introduced into the data, depending on the encoding and decoding environments and implementation, particularly with regard with how floating point data is handled. Because each value is computed based on the previous on, the potential for error increases across the data set. For this reason, when working with fractional values it is strongly recommended to used a fixed precision context, by chosing an adequate static precision at encode time and embedding it with the scalar value, described below. Alternatively, the file can be encoded with the d0 delta setting, disabling the feature. This can still provide significant compression benefit if the data set contains many repeated values.

Scalar / Offset

The scalar and offset parameters allow repetitive data to be further reduced. A single scalar value can be specified to either multiply ('*') or divide ('/') each value by, followed by a single positive ('+') or negative ('-') offset value. The scalar is always applied first, followed by the offset. The format is considered invalid if more than one scalar or more than one offset is present.

For example, given the data set:

50.0, 50.1, 50.3, 50.2, 49.9, 50.1

We can use a /10 scalar and +50 offset to encode as follows:

v1,d1,/10,+50:0,1,2,-1,-3,2

Note that each delta operation is relative to the previous untransformed value.

Values

There are six possible values:

"" (empty, blank)
'n' (null literal)
number
'n' integer (blank repeated integer times)
number 'n' integer (number repeated integer times)
'nn' integer (null repeated integer times)

Note that the first value of the full value set must not be blank (or repeated blanks), to preserve the ability to define an empty data set. That is, the ~~string:~~strings:

"v1:", "v1,b0:"

~~Denotes~~Both denote a data set with no values.

Decoding Order of Operations

Expansion (n repeated static values)

Blank resolution

Delta operations

Scalar transform

Offset transform

Implementation

We provide a reference encode / decode implementation in Java, TypeScript, and Python. Because the encoding process is very fast, multiple formats can usually be tested to find a reasonably optimal solution automatically.

General Recommendations

Print values as minimally as possible (ie, 1e3 instead of 1000 or 1e+3, 0 instead of 0.00)
When encoding fractional values with delta enabled, require an explicit scale input setting to inform the scalar parameter and prevent accumulated errors
Avoid use of regular expressions in decoders, they often add considerable overhead and are overkill for the simplicity of the format

Changelog

Version 1

Breaking change: In v0, 'n' integer repeats previous value integer times. In v1, 'n' integer repeats blank value integer times.

Breaking change: Added support for null values

Added version specification to header

Clarified parameter definition and limitations

Version 0

Initial release