# US 2020/0401405 A1 · Advanced database decompression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401405 A1 - Document ID: US20200401405A1 - Status: Published application - Kind: A1 - Application number: 16/834,839 - Filed: 2020-03-30 - Published: 2020-12-24 - Earliest claimed: 2019-06-21 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Robert Lasch; Ismail Oukid; Norman May - Web page: https://patentgrep.com/patent/US20200401405A1 ## CPC - G06F 16/221: {Column-oriented storage; Management thereof} - H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes} - G06F 3/0604: {Improving or facilitating administration, e.g. storage management} - G06F 3/064: {Management of blocks} - G06F 16/9027: {Trees} - H03M 7/3095: {using variable length segments} - H03M 7/3097: {Grammar codes} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - 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 A method, a system, and a computer program product for decompressing data. One or more compressed blocks in a set of stored compressed blocks responsive to a request to access data in the set of stored compressed blocks are identified. String prefixes inside the identified compressed blocks are decompressed using front coding. String suffixes inside the identified compressed blocks are decompressed using a re-pair decompression. Uncompressed data is generated. ## Claims ### Claim 1 A computer-implemented method, comprising: identifying one or more compressed blocks in a set of stored compressed blocks responsive to a request to access data in the set of stored compressed blocks; and decompressing string prefixes inside the identified compressed blocks using front coding; decompressing string suffixes inside the identified compressed blocks using a re-pair decompression; and generating uncompressed data. ### Claim 2 (depends on 1) The method according to claim 1, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks; the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks. ### Claim 3 (depends on 2) The method according to claim 2, wherein the symbol tree includes a plurality of nodes, wherein the plurality of nodes includes at least one of the following: a terminal character, a non-terminal character, and any combination thereof. ### Claim 4 (depends on 3) The method according to claim 3, further comprising performing a plurality of re-pair decompressions in parallel. ### Claim 5 (depends on 4) The method according to claim 4, wherein the number of terminal characters is limited to a predetermined number, wherein the number of iterative expansions of each symbols is determined based on the predetermined number. ### Claim 6 (depends on 5) The method according to claim 5, wherein the re-pair decompression includes initializing a stack position in a memory corresponding to each symbol in the symbol tree; simultaneously loading, using vector instructions, each symbol in the symbol tree from storage into the memory; combining loaded symbols into the uncompressed data by evaluating one or more predicates associated with the symbols; and repeating, using the predetermined number, the simultaneously loading and the combining. ### Claim 7 (depends on 1) The method according to claim 1, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets. ### Claim 8 (depends on 1) The method according to claim 1, wherein the block size is at least one of the following: a fixed size and a variable size. ### Claim 9 (depends on 1) The method according to claim 1, wherein the one or more compressed blocks are compressed using re-pair compression. ### Claim 10 A system comprising: at least one programmable processor; and a non-transitory machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising: identifying one or more compressed blocks in a set of stored compressed blocks responsive to a request to access data in the set of stored compressed blocks; and decompressing string prefixes inside the identified compressed blocks using front coding; decompressing string suffixes inside the identified compressed blocks using a re-pair decompression; and generating uncompressed data. ### Claim 11 (depends on 10) The system according to claim 10, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks; the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks. ### Claim 12 (depends on 11) The system according to claim 11, wherein the symbol tree includes a plurality of nodes, wherein the plurality of nodes includes at least one of the following: a terminal character, a non-terminal character, and any combination thereof. ### Claim 13 (depends on 12) The system according to claim 12, wherein the operations further comprise performing a plurality of re-pair decompressions in parallel. ### Claim 14 (depends on 13) The system according to claim 13, wherein the number of terminal characters is limited to a predetermined number, wherein the number of iterative expansions of each symbols is determined based on the predetermined number. ### Claim 15 (depends on 14) The system according to claim 14, wherein the re-pair decompression includes initializing a stack position in a memory corresponding to each symbol in the symbol tree; simultaneously loading, using vector instructions, each symbol in the symbol tree from storage into the memory; combining loaded symbols into the uncompressed data by evaluating one or more predicates associated with the symbols; and repeating, using the predetermined number, the simultaneously loading and the combining. ### Claim 16 (depends on 10) The system according to claim 10, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets. ### Claim 17 (depends on 10) The system according to claim 10, wherein the block size is at least one of the following: a fixed size and a variable size. ### Claim 18 (depends on 10) The system according to claim 10, wherein the one or more compressed blocks are compressed using re-pair compression. ### Claim 19 A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising: identifying one or more compressed blocks in a set of stored compressed blocks responsive to a request to access data in the set of stored compressed blocks; and decompressing string prefixes inside the identified compressed blocks using front coding; decompressing string suffixes inside the identified compressed blocks using a re-pair decompression; and generating uncompressed data. ### Claim 20 (depends on 19) The computer program product according to claim 19, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks; the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks.