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