# 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 one or two order delta of the previous value - 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 defined here. **Note: whitespace is not permitted in the format.** `string` - `version ':' all_values` - `version ',' parameters ':' all_values` `version` - `'v' pos_integer` `parameters` - `parameter` - `parameter ',' parameters` `parameter` - `delta` - `blank` - `scalar` - `offset` `delta` - `'d0'` - `'d1'` - `'d2'` `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' pos_integer` `nonblank_value` - `'n'` - `number` - `number 'n' pos_integer` - `'nn' pos_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 encoded literal value. `'b' number` assigns a static numeric value. `'bn'` assigns the `null` value. `'br'` will be the most efficient in most cases, unless the majority of a data set is a single value. The format is considered invalid if more than one blank parameter is specified. 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). The format is considered invalid if more than one delta parameter is specified. Given the simple data set: - `0, 1, 2, 3, 4, 5, 6, 7, 8, 9` The `d1` encoding would be: - `v1,br,d1:0,1,1,1,1,1,1,1,1,1` Which, with `br`, can be reduced to: - `v1,br,d1:0,1,,,,,,,,,` Which can be further reduced to - `v1,br,d1:0,1n9` The `d2` encoding would be: - `v1,br,d2:0,1,0,0,0,0,0,0,0,0` Which can be further reduced to: - `v1,br,d2: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 simply ignore any `null` values, carrying state from the previous non-`null` value. For example, given the data set: - `null, null, null, 0, 1, 2, 3, 4, null, 5, 6, 7, 8, 9` The `d1` encoding would be: - `v1,br,d1:n,n,n,0,1,1,1,1,n,1,1,1,1,1` Which can be further reduced to - `nn3,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. These represent the operations to perform at decode time, so they are inversed during encoding. Note that a `/0` scalar is invalid. 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' pos_integer` (`blank` repeated `integer` times) - `number 'n' pos_integer` (number repeated `integer` times) - `'nn' pos_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 strings: `"v1:"`, `"v1,b0:"` Both denote a data set with no values. ### Decoding Order of Operations - Blank resolution - Expansion (`n` repeated static values) - 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 - **Breaking change**: Added support for `d0` (disabled delta mode), changed names from `d` to `d1`, `dd` to `d2` - Added version specification to header - Clarified parameter definition and limitations ### Version 0 - Initial release For reference the v0 grammar (note, number, scalar, and offset formats remain unchanged from v1 grammar): `v0_string` - `v0_parameters ':' v0_all_values` `v0_parameters` - `v0_parameter` - `v0_parameter ',' v0_parameters` `v0_parameter` - `v0_delta` - `v0_blank` - `scalar` - `offset` `v0_delta` - `'d'` - `'dd'` `v0_blank` - `'br'` - `'b' number` `v0_all_values` - `""` - `number` - `number ',' v0_values` `v0_values` - `v0_value` - `v0_value ',' v0_values` `v0_value` - `""` - `number` - `v0_repeater` `v0_repeater` - `'n' pos_integer`