# US 2014/0208053 A1 · Re-aligning a compressed data array

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0208053 A1
- Document ID: US20140208053A1
- Status: Published application
- Kind: A1
- Application number: 13/745,556
- Filed: 2013-01-18
- Published: 2014-07-24
- Earliest claimed: 2013-01-18
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Stuart E. Carney
- Web page: https://patentgrep.com/patent/US20140208053A1

## CPC

- G06F 12/023: {Free address space management}
- G06F 8/4434: {Reducing the memory space required by the program code}
- H03M 7/3068: {Precoding preceding compression, e.g. Burrows-Wheeler transformation}
- G06F 9/30178: {of compressed or encrypted instructions}
- G06F 2212/401: Compressed data
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/3059: {Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression}
- 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

Two-dimensional compressed data sets can be re-aligned while preserving compression of the data. A set of one or more shifts and a corresponding set of one or more first dimension indices into a two-dimensional compressed data set for re-aligning the two-dimensional compressed data set are determined. Impact of re-aligning upon each vector in the second dimension of the two-dimensional compressed data set is determined while the two-dimensional compressed data set remains compressed. New compressed vectors are created in the second dimension resulting from re-aligning. Compression information is modified for each of the original vectors of the two-dimensional compressed data set that remain after re-aligning based, at least in part, on the new compressed vectors. A re-aligned version of the two-dimensional compressed data set is created with the new compressed vectors, and the remaining original vectors with their modified compression information.

## Claims

### Claim 1

A method comprising:
determining a maximum shift value of a set of one or more shift values for re-aligning a two-dimensional data set, wherein each of the set of one or more shift values indicates shifts at a specified index into a first dimension of the two-dimensional data set, wherein the two-dimensional data set is compressed along the first dimension;
for each second dimension vector of the two-dimensional data set,
determining whether shifting for each of the set of one or more shift values at the specified index into the first dimension of the second dimension vector results in a different vector than either a previously created vector or the second dimension vector;
if shifting results in the different vector, adding the different vector to a re-aligned array;
if shifting does not result in the different vector, incorporating a compressed form of the second dimension vector into the re-aligned data set.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of the vectors comprises an ordered set of values.

### Claim 3 (depends on 1)

The method of claim 1, wherein sequential repeating instances of a set of values are represented with a single vector and compression information that indicates the repeating instances.

### Claim 4 (depends on 1)

The method of claim 1, wherein the different vector indicates no data values or null values at the specified index into the different vector when shifting beyond the two-dimensional data set.

### Claim 5 (depends on 1)

The method of claim 1 further comprising writing values into a buffer in accordance with the shifting.

### Claim 6 (depends on 5)

The method of claim 5, wherein said writing values into the buffer in accordance with the shifting comprises:
for each of the second dimension vectors of the two-dimensional data set,
for each position of the vector,
writing a null value or no data value into a position of the buffer that corresponds to the position of the vector if the position of the vector shifts beyond the two-dimensional data set,
writing a value at the position of the vector into the corresponding position of the buffer if the position of the vector is not shifted, and
writing a value at the position of a different vector of the two-dimensional data set into the corresponding position of the buffer if the position of the vector is shifted.

### Claim 7 (depends on 6)

The method of claim 6, wherein said adding the different vector to the re-aligned array comprises transferring contents of the buffer to the re-aligned array or creating a new vector for the re-aligned array with the contents of the buffer.

### Claim 8

A method comprising:
determining a set of one or more shifts and a corresponding set of one or more first dimension indices into a two-dimensional compressed data set for re-aligning the two-dimensional compressed data set;
determining impact of re-aligning upon each vector in the second dimension of the two-dimensional compressed data set while the two-dimensional compressed data set remains compressed; and
creating new compressed vectors in the second dimension resulting from re-aligning;
modifying compression information for each of the original vectors of the two-dimensional compressed data set that remain after re-aligning based, at least in part, on the new compressed vectors; and
creating a re-aligned version of the two-dimensional compressed data set with the new compressed vectors, and the remaining original vectors with their modified compression information.

### Claim 9 (depends on 8)

The method of claim 8, wherein each of the vectors comprise an ordered set of values.

### Claim 10

A computer program product for re-aligning a compressed two-dimensional data set, the computer program product comprising:
a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to:
determine a maximum shift value of a set of one or more shift values for re-aligning a two-dimensional data set, wherein each of the set of one or more shift values indicates shifts at a specified index into a first dimension of the two-dimensional data set, wherein the two-dimensional data set is compressed along the first dimension;
for each second dimension vector of the two-dimensional data set,
determine whether shifting for each of the set of one or more shift values at the specified index into the first dimension of the second dimension vector results in a different vector than either a previously created vector or the second dimension vector;
if shifting results in the different vector, add the different vector to a re-aligned array;
if shifting does not result in the different vector, incorporate a compressed form of the second dimension vector into the re-aligned data set.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein each of the vectors comprises an ordered set of values.

### Claim 12 (depends on 10)

The computer program product of claim 10, wherein sequential repeating instances of a set of values are represented with a single vector and compression information that indicates the repeating instances.

### Claim 13 (depends on 10)

The computer program product of claim 10, wherein the different vector indicates no data values or null values at the specified index into the different vector when shifting beyond the two-dimensional data set.

### Claim 14 (depends on 10)

The computer program product of claim 10 further comprising computer usable program code configured to write values into a buffer in accordance with the shifting.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein the computer usable program code configured to write values into the buffer in accordance with the shifting comprises the computer usable program code configured to:
for each of the second dimension vectors of the two-dimensional data set,
for each position of the vector,
write a null value or no data value into a position of the buffer that corresponds to the position of the vector if the position of the vector shifts beyond the two-dimensional data set,
write a value at the position of the vector into the corresponding position of the buffer if the position of the vector is not shifted, and
write a value at the position of a different vector of the two-dimensional data set into the corresponding position of the buffer if the position of the vector is shifted.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the computer usable program code configured to add the different vector to the re-aligned array comprises transferring contents of the buffer to the re-aligned array or creating a new vector for the re-aligned array with the contents of the buffer.

### Claim 17

An apparatus comprising:
a processor; and
a compressed data set re-alignment unit operable to,
determine a set of one or more shifts and a corresponding set of one or more first dimension indices into a two-dimensional compressed data set for re-aligning the two-dimensional compressed data set;
determine impact of re-aligning upon each vector in the second dimension of the two-dimensional compressed data set while the two-dimensional compressed data set remains compressed; and
create new compressed vectors in the second dimension resulting from re-aligning;
modify compression information for each of the original vectors of the two-dimensional compressed data set that remain after re-aligning based, at least in part, on the new compressed vectors; and
create a re-aligned version of the two-dimensional compressed data set with the new compressed vectors, and the remaining original vectors with their modified compression information.

### Claim 18 (depends on 17)

The apparatus of claim 17 further comprising a machine-readable storage medium having computer usable program code encoded therein, wherein the computer usable program code embodies the compressed data set re-alignment unit.
