# US 8,751,687 B2 · Efficient encoding of structured data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,687 B2 - Document ID: US8751687B2 - Status: Granted - Kind: B2 - Application number: 12/771,924 - Filed: 2010-04-30 - Published: 2011-11-03 - Granted: 2014-06-10 - Earliest claimed: 2010-04-30 - Assignees: Microsoft Corporation - Applicants: Alexander F. Nagy; Ashok Chandrasekaran; Kristof Roomp; Novia Rosalinda Wijaya - Inventors: Alexander F. Nagy; Ashok Chandrasekaran; Kristof Roomp; Novia Rosalinda Wijaya - Web page: https://patentgrep.com/patent/US8751687B2 ## CPC - H03M 7/3079: {Context modeling} - H03M 7/707: {Structured documents, e.g. XML} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract This document describes various techniques for efficiently sequencing structured data in a particular order to provide a sequence of data elements suitable for storage or communication. The sequence may contain values representing a number of default-value structured data elements omitted from the sequence and/or a byte length of the sequence. ## Claims ### Claim 1 A device-implemented method comprising: determining, via a data encoder of a device, a number of consecutive non-default-value structured data elements of a set of default-value structured data and non-default-value structured data elements forming at least a portion of a data structure and having a particular order; determining a number of consecutive default-value structured data elements of the particular order that precede or follow consecutive non-default-value structured data elements in the particular order; sequencing, based on the particular order, the consecutive non-default-value structured data elements; inserting, into the sequence and adjacent to the consecutive non-default-value structured data element that the consecutive default-value data elements precede or follow, a value representing the number of consecutive non-default-value structured data elements and the number of consecutive default-value structured data elements that precede or follow the consecutive non-default-value structured data elements, the consecutive default-value structured data elements not inserted into the sequence; and transmitting, via a data interface of the device, the sequence to an entity, the entity having access to information about the particular order, the sequence not including the consecutive default-value structured data elements. ### Claim 2 (depends on 1) The device-implemented method as recited in claim 1, wherein the information about the particular order includes information about only a portion of the particular order. ### Claim 3 (depends on 1) The device-implemented method as recited in claim 1, wherein the act of inserting the value inserts a bit-interleaved value, the bit interleaved value an interleaving of bits of the value representing the number of consecutive default-value structured data elements and the value representing the number of sequenced consecutive non-default-value structured data elements. ### Claim 4 (depends on 3) The device-implemented method as recited in claim 3, further comprising interleaving bits of the value representing the number of consecutive default-value structured data elements and bits of the value representing the number of sequenced consecutive non-default-value structured data elements to provide the bit interleaved value. ### Claim 5 (depends on 1) The device-implemented method as recited in claim 1, further comprising inserting a length value into the sequence, the length value representing a byte length of the sequence transmitted to the entity. ### Claim 6 (depends on 1) The method as recited in claim 1, wherein the data interface of the device is a network interface or an interface to a storage device. ### Claim 7 A device-implemented method comprising: receiving, via a data interface of a device, a sequence of data elements having a particular order and a value, the data elements being non-default-value data elements of the particular order, the value representing a number of consecutive default-value data elements and a number of consecutive non-default-value data elements, the value indicating the number of consecutive default-value data elements that precede or follow the consecutive non-default-value data element in the particular order, the default-value data elements not received with the sequence; inserting, via a data encoder of the device, default-value data elements into the sequence based on the value representing the number of consecutive default-value data elements and the number of consecutive non-default-value data elements and information about the particular order, the default-value data elements inserted adjacent to the consecutive non-default-value data elements that the consecutive default-value data elements precede or follow; and structuring the sequence of the consecutive non-default-value data elements and consecutive default-value data elements to provide structured data. ### Claim 8 (depends on 7) The device-implemented method as recited in claim 7, wherein the sequence of data elements does not include any default-value data elements and the value is located between the consecutive non-default-value data elements and another set of consecutive non-default-value data elements of the sequence of data elements. ### Claim 9 (depends on 7) The device-implemented method as recited in claim 7, further comprising structuring only a portion of the sequence of data elements to provide structured data. ### Claim 10 (depends on 7) The device-implemented method as recited in claim 7, wherein the sequence further comprises a length value representing a byte length of the sequence. ### Claim 11 (depends on 7) The device-implemented method as recited in claim 7, wherein the value is Morton encoded, the Morton-encoded value representing the number of consecutive default-value data elements and the number of consecutive non-default-value data elements. ### Claim 12 (depends on 7) The device-implemented method as recited in claim 7, wherein the data interface is a network interface or an interface to a storage device. ### Claim 13 A device-implemented method comprising: determining a number of non-default-value structured data elements of a data structure, the non-default-value data elements being consecutive data elements of a particular order; determining a number of consecutive default-value structured data elements of the data structure, the consecutive default-value data elements preceding or following the consecutive non-default-value structured data elements in the particular order; interleaving bits of a bit-value representing the number of consecutive non-default-value structured data elements and bits of a bit-value representing the number of consecutive default-value structured data elements to provide a bit interleaved value representing the number of consecutive non-default-value structured data elements and the number of consecutive default-value structured data elements; encoding, using 7-bit encoding, the bit-interleaved value to provide a 7-bit encoded value representing the number of consecutive non-default-value structured data elements and the number of consecutive default-value structured data elements; serializing the 7-bit encoded value; and serializing, based on the particular order, the non-default-value structured data elements to respectively precede or follow the 7-bit encoded value representing the number of consecutive non-default-value structured data elements and the number of consecutive default-value structured data elements, the default-value structured data elements not serialized into the serialized data elements. ### Claim 14 (depends on 13) The device-implemented method as recited in claim 13, further comprising inserting, into the serialized data elements, a length value representing a byte length of the serialized data elements. ### Claim 15 (depends on 13) The device-implemented method as recited in claim 13, further comprising transmitting the serialized data elements through a network interface. ### Claim 16 (depends on 13) The device-implemented method as recited in claim 13, further comprising storing the serialized data elements on a computer-readable storage medium. ### Claim 17 (depends on 13) The device-implemented method as recited in claim 13, further comprising encoding the serialized data elements. ### Claim 18 (depends on 17) The device-implemented method as recited in claim 17, further comprising decrementing serialized data elements having a default value of zero. ### Claim 19 (depends on 17) The device-implemented method as recited in claim 17, further comprising encoding, using Zig-Zag encoding, serialized data elements that include signed integers. ### Claim 20 (depends on 17) The device-implemented method as recited in claim 17, further comprising encoding, using 7-bit encoding, serialized data elements that include unsigned integers.