# US 2010/0169335 A1 · Detecting and Reordering Fixed-Length Records to Facilitate Compression

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

- Number: US 2010/0169335 A1
- Document ID: US20100169335A1
- Status: Published application
- Kind: A1
- Application number: 12/346,506
- Filed: 2008-12-30
- Published: 2010-07-01
- Earliest claimed: 2008-12-30
- Assignees: Microsoft Corporation
- Inventors: Hua Cai; Jiang Li
- Web page: https://patentgrep.com/patent/US20100169335A1

## CPC

- H04N 1/00472: {using a pop-up window}
- G06F 16/258: {Data format conversion from or to a database}
- 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
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- 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

Disclosed herein are one or more embodiments that facilitate compression of a source file having a fixed-length record therein. One or more of the disclosed embodiments detect the fixed-length records and determine a reordering plan for the source file, including determining a plurality of column groupings within the detected fixed-length records.

## Claims

### Claim 1

A method comprising:
detecting, by a computing device configured to facilitate compression of a source file, a plurality of fixed-length records within the source file;
determining, by the computing device, a reordering plan for the source file, including determining a plurality of column groupings within the detected fixed-length records; and
reordering, by the computing device, the fixed-length records based on the reordering plan to facilitate compression of the source file.

### Claim 2 (depends on 1)

The method of claim 1, wherein the detecting further comprises:
determining a plurality of candidate records based on a repeating string pattern detected within the source file;
determining a candidate record length based on a byte differential between repeated instances of the string pattern;
comparing first byte values occurring between the repeated instances of the string pattern with second byte values following the first byte values by the record length in order to calculate a score; and
if the score is less than or equal to a threshold value, determining that the candidate records are members of the set of fixed-length records.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the column groupings further comprises determining a dependency relationship between a first column and a second column based on a tendency of values repeating in the first column to appear together with values repeating in the second column.

### Claim 4 (depends on 1)

The method of claim 1, wherein determining the column groupings further comprises determining a partition plan of a set of partition plans partitioning the fixed-length records into candidate column groupings as an optimal partition plan based on coding bit sizes associated with each partition plan.

### Claim 5 (depends on 1)

The method of claim 1, further comprising evaluating the reordering plan to ensure that the source file will compress better after reordering than before reordering.

### Claim 6 (depends on 5)

The method of claim 5, wherein the evaluating further comprises determining an order-2 empirical entropy for both the source file and the reordered source file, the order-2 empirical entropy defined as
H
=
∑
i

∑
j

∑
k

p

(
x
i
,
y
j
,
z
k
)

log
2

p

(
z
k
|
x
i
,
y
j
)
wherein zk is a possible symbol in a file, xi and yj are the order-2 contexts of zk, p(zk|xi,yi) is the conditional probability of zk given xi and yj as the order-2 contexts, and p(xi, yj, zk) is the joint probability of xiyjzk.

### Claim 7 (depends on 1)

The method of claim 1, further comprising creating a reordering description file including the reordering plan, the reordering description file further including starting positions of the fixed-length records within the source file, record lengths of the fixed-length records, and a number of fixed-length records comprising a fixed-length table.

### Claim 8 (depends on 1)

The method of claim 1, wherein the reordering comprises raster scanning each column grouping separately.

### Claim 9 (depends on 1)

The method of claim 1, further comprising compressing the source file and the reordering description file, the column groupings and any non-record portions of the source file each compressed separately.

### Claim 10

A computing device comprising:
a processor; and
programming instructions configured to be executed by the processor to detect a set of fixed-length records within a source file, including:
determining a plurality of candidate records based on a repeating string pattern detected within the source file;
determining a candidate record length based on a byte differential between repeated instances of the string pattern;
comparing first byte values occurring between the repeated instances of the string pattern with second byte values following the first byte values by the record length in order to calculate a score; and
if the score is less than or equal to a threshold value, determining that the candidate records are members of the set of fixed-length records.

### Claim 11 (depends on 10)

The computing device of claim 10, wherein the score is calculated using a function defined as:
CalMatch

(
q
1
,
q
2
,
l
)
=
∑
i
=
0
l
-
1

s
i
where
S
i
=
{
0
if


q
1

[
i
]
=
q
2

[
i
]
1
otherwise
wherein q1 and q2 are start positions of two fixed-length records and l is a candidate record length.

### Claim 12 (depends on 10)

The computing device of claim 10, wherein the instructions are further configured to be executed by the processor to repeat the comparing and the determining that the candidate records are members until an end of the set of fixed-length records is reached.

### Claim 13 (depends on 12)

The computing device of claim 12, wherein the instructions are further configured to be executed by the processor to determine that the end of the set of fixed-length records has been reached if the score is larger than the threshold value.

### Claim 14 (depends on 10)

The computing device of claim 10, wherein the instructions are further configured to be executed by the processor to calculate the threshold value by dividing the candidate record length by a pre-defined value ranging from 2 to 4.

### Claim 15

An article of manufacture comprising:
a storage medium; and
a plurality of programming instructions stored on the storage medium and configured to program a computing device to, when executed:
detect one or more fixed-length records within a source file, the detecting including
determining a plurality of candidate records based on a repeating string pattern detected within the source file;
determining a candidate record length based on a byte differential between repeated instances of the string pattern;
comparing first byte values occurring between the repeated instances of the string pattern with second byte values following the first byte values by the record length in order to calculate a score; and
if the score is less than or equal to a threshold value, determining that the candidate records are members of the set of fixed-length records;
determine a plurality of column groupings within the fixed-length records, the determining including
determining a dependency relationship between a first column and a second column based on a tendency of values repeating in the first column to appear together with values repeating in the second column, or
determining a partition plan of a set of partition plans partitioning the fixed-length records into candidate column groupings as an optimal partition plan based on coding bit sizes associated with each partition plan; and
reorder the fixed-length records based on the plurality of column groupings to facilitate compression of the source file.

### Claim 16 (depends on 15)

The article of claim 15, wherein determining the dependency relationship includes:
calculating a probability that a repetition of values in the first column occurs together with a repetition of values in the second column;
comparing that probability to a threshold; and
if the probability is greater than the threshold, determine that the dependency relationship exists between the first and second columns.

### Claim 17 (depends on 16)

The article of claim 16, wherein the threshold is set to 0.95.

### Claim 18 (depends on 16)

The article of claim 16, wherein the programming instructions are further configured to program the computing device to, when executed, calculate the coding bit size for each partition plan using a Lempel-Ziv algorithm.

### Claim 19 (depends on 16)

The article of claim 16, wherein the Lempel-Ziv algorithm calculates a total number of coding bits over a string using a function R(S), where
R

(
S
)
=
∑
i
=
1
c

R
s

(
S
i
)
+
∑
j
=
1
d

R
m

(
M
j
)
wherein S represents the string, Si represents an unmatched symbol, c is the number of unmatched symbols, Mj represents a matched symbol, d is the number of matched symbols, Rs(Si) denotes the number of coding bits of an unmatched symbol Si, and Rm(Mi) denotes the number of coding bits of a matched symbol Mj, wherein Rs(Si) is further defined as
Rs(Si)=1+log2|A|
wherein log2|A| represents the number of coding bits of an unmatched symbol Si, and wherein Rm(Mi) is further defined as
Rm(Mj)=1+[2 log2(Δj+1)−1]+[2 log2(Lj+1)−1]
wherein Δj represents an offset of a matched symbol Mj and Lj represents a length of a matched symbol Mj.

### Claim 20 (depends on 16)

The article of claim 16, wherein the partition plan is determined as the optimal partition plan by comparing the coding bit sizes of the partition plans utilizing a function Q(i), where
Q

(
i
)
=
Min
-
1
≤
j
<
i

{
Q

(
j
)
+
R

(
{
C

[
j
+
1
]
,
…

,
C

[
i
]
}
)
}
or
Q

(
i
)
=
Min
μ
≤
j
<
i

{
Q

(
i
)
+
R

(
{
C

[
j
+
1
]
,
…

,
C

[
i
]
}
)
}
wherein Q(i) denotes the coding bit size of the optimal partition plan on a sub-table {C[0], . . . , C[i]}.
