Skip to main content

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
  • "n#" indicates repeating the previous value # 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 as follows:

string

  • version ':' values
  • version ',' parameters ':' 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

values

  • value
  • value ',' values

value

  • ""
  • 'n'
  • number
  • number 'n' integer
  • 'n' integer

number

  • integer fraction exponent

integer

  • digit
  • onenine digits
  • '-' 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:

  • 0,,1,,,2,

A b0 encoding would be:

  • ,,1,1,1,2,2

Which can be further reduced to

  • ,,1n3,2,2

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:

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

The d1 encoding would be:

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

Which can be further reduced to

  • 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 (note, whitespace added for clarity, not required):

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

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

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, 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
  • Avoid use of split functions, which generate copies of string data in many environments; better to iterate across the string in place
Back to top