# US 8,280,850 B2 · Method for producing a size-optimized delta-file

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

- Number: US 8,280,850 B2
- Document ID: US8280850B2
- Status: Granted
- Kind: B2
- Application number: 12/310,538
- Filed: 2007-08-23
- Published: 2010-07-29
- Granted: 2012-10-02
- Earliest claimed: 2006-08-29
- Assignees: Siemens Aktiengesellschaft
- Inventors: Ulrich Lauther
- Web page: https://patentgrep.com/patent/US8280850B2

## CPC

- 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
- G06F 8/71: Version control (security arrangements therefor G06F21/57); Configuration management
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A delta file which encodes the difference between a first data file and a second data file is produced by determining a set of elemental data strings which are present in the two data files in a partial match in a graph being modeled. In the graph, each network node, representing data processing based on the first data file for producing a data byte of the second data file, is connected by network edges to all network nodes which are associated with a directly preceding data byte of the second data file. The network nodes and network edges are respectively assigned a cost value and a cost-optimized path in the graph is ascertained which, for all the day bytes of the second data file, contains only one network node per data byte. The cost-optimized path is taken as a basis for generating a delta file, containing a sequence of data processing operations and their data fields, which corresponds to the successive series of network nodes in the cost-optimized path.

## Claims

### Claim 1

A method for producing a delta-file encoding differences between a first data file and a second data file, each formed of data bytes, comprising:
determining a set of elemental data strings defined as pseudo-matches present in the two data files in a partial match;
modeling a graph of network nodes and network edges in which each network node represents a data processing operation based on the first data file for producing one of the data bytes of the second data file, and each related node, associated with a data byte of the second data file in the graph, is connected by related network edges to all preceding network nodes associated with a directly preceding data byte of the second data file;
assigning the network nodes and the network edges, respectively, a cost value;
ascertaining a cost-optimized path in the graph which, for all data bytes of the second data file, contains only one network node per data byte; and
generating a delta-file, based on the cost-optimized path, containing a series of data processing operations and data fields corresponding to a successive sequence of network nodes in the cost-optimized path.

### Claim 2 (depends on 1)

The method as claimed in claim 1, wherein the data processing operations based on the first data file for producing one of the data bytes of the second data file are respectively specific to a pseudo-match.

### Claim 3 (depends on 2)

The method as claimed in claim 2,
wherein the data processing operations based on the first data file for producing one of the data bytes of the second data file include ADD-operations and Diff-operations,
wherein reading of an ADD data field associated with an ADD-operation from the delta-file is effected by an ADD-operation, and storage thereof is effected at a first position in the second data file corresponding to a second position of the data byte with which the ADD-operation is associated, and
wherein said generating includes storing a data byte sum, totaled from a DIFF data field of a DIFF-operation and a corresponding data byte of the pseudo-match of the first data file, by a specific DIFF-operation for a specific pseudo-match at a third position in the second data file which corresponds to a fourth position of the data byte to which the specific DIFF-operation is assigned.

### Claim 4 (depends on 1)

The method as claimed in claim 1, wherein said modeling of the graph uses a matrix formed of lines and columns with successive columns of the graph assigned to successive data bytes of the second data file.

### Claim 5 (depends on 1)

The method as claimed in claim 1, wherein a non-zero cost value is assigned to each network node for which a state associated with the network node produces an associated data byte in the delta-file that is not equal to zero and a zero cost value is assigned to each network node for which the state associated with the network node produces the associated data byte in the delta-file that is equal to zero.

### Claim 6 (depends on 1)

The method as claimed in claim 1, wherein the zero cost value is assigned to each network edge for which the network nodes connected thereby belong to same or compatible pseudo-matches, and the non-zero value is assigned to each network edge for which the network nodes connected thereby belong to different pseudo-matches.

### Claim 7 (depends on 1)

The method as claimed in claim 1, further comprising producing pseudo-matches by
producing of a set of exactly matching maximum elemental data regions, defined as matches, present in the first and second data files;
ascertaining compatible matches with positions thereof respectively differing in the first and second data files by a same amount;
producing pseudo-matches by combining respectively compatible matches to form a combined data region.

### Claim 8 (depends on 1)

The method as claimed in claim 1, wherein said ascertaining the cost-optimized path includes reducing the pseudo-matches based on a cost comparison of costs, which occur if a match is used or not known within a gap of one of the pseudo-matches.

### Claim 9 (depends on 1)

The method as claimed in claim 1, further comprising selecting a set of non-overlapping pseudo-matches from the pseudo-matches to maximize overlapping of the second data file by exact matches.

### Claim 10 (depends on 1)

The method as claimed in claim 1, further comprising compressing the delta-file.

### Claim 11

A non-transitory computer-readable medium encoded with a computer program that when executed by an electronic data processing device causes the electronic data processing device to carry out a method comprising:
determining a set of elemental data strings defined as pseudo-matches present in the two data files in a partial match;
modeling a graph of network nodes and network edges in which each network node represents a data processing operation based on the first data file for producing one of the data bytes of the second data file, and each related node, associated with a data byte of the second data file in the graph, is connected by related network edges to all preceding network nodes associated with a directly preceding data byte of the second data file;
assigning the network nodes and the network edges, respectively, a cost value;
ascertaining a cost-optimized path in the graph which, for all data bytes of the second data file, contains only one network node per data byte; and
generating a delta-file, based on the cost-optimized path, containing a series of data processing operations and data fields corresponding to a successive sequence of network nodes in the cost-optimized path.

### Claim 12 (depends on 11)

The computer-readable medium as claimed in claim 11, wherein the data processing operations based on the first data file for producing one of the data bytes of the second data file are respectively specific to a pseudo-match.

### Claim 13 (depends on 12)

The computer-readable medium as claimed in claim 12,
wherein the data processing operations based on the first data file for producing one of the data bytes of the second data file include ADD-operations and Diff-operations,
wherein reading of an ADD data field associated with an ADD-operation from the delta-file is effected by an ADD-operation, and storage thereof is effected at a first position in the second data file corresponding to a second position of the data byte with which the ADD-operation is associated, and
wherein said generating includes storing a data byte sum, totaled from a DIFF data field of a DIFF-operation and a corresponding data byte of the pseudo-match of the first data file, by a specific DIFF-operation for a specific pseudo-match at a third position in the second data file which corresponds to a fourth position of the data byte to which the specific DIFF-operation is assigned.

### Claim 14 (depends on 11)

The computer-readable medium as claimed in claim 11, wherein said modeling of the graph uses a matrix formed of lines and columns with successive columns of the graph assigned to successive data bytes of the second data file.

### Claim 15 (depends on 11)

The computer-readable medium as claimed in claim 11, wherein a non-zero cost value is assigned to each network node for which a state associated with the network node produces an associated data byte in the delta-file that is not equal to zero and a zero cost value is assigned to each network node for which the state associated with the network node produces the associated data byte in the delta-file that is equal to zero.

### Claim 16 (depends on 11)

The computer-readable medium as claimed in claim 11, wherein the zero cost value is assigned to each network edge for which the network nodes connected thereby belong to same or compatible pseudo-matches, and the non-zero value is assigned to each network edge for which the network nodes connected thereby belong to different pseudo-matches.

### Claim 17 (depends on 11)

The computer-readable medium as claimed in claim 11, the method further comprising producing pseudo-matches by
producing of a set of exactly matching maximum elemental data regions, defined as matches, present in the first and second data files;
ascertaining compatible matches with positions thereof respectively differing in the first and second data files by a same amount;
producing pseudo-matches by combining respectively compatible matches to form a combined data region.

### Claim 18 (depends on 11)

The computer-readable medium as claimed in claim 11, wherein said ascertaining the cost-optimized path includes reducing the pseudo-matches based on a cost comparison of costs, which occur if a match is used or not known within a gap of one of the pseudo-matches.

### Claim 19 (depends on 11)

The computer-readable medium as claimed in claim 11, the method further comprising selecting a set of non-overlapping pseudo-matches from the pseudo-matches to maximize overlapping of the second data file by exact matches.

### Claim 20 (depends on 11)

The computer-readable medium as claimed in claim 11, the method further comprising compressing the delta-file.
