Browse Prior Art Database

Compression of Updated Data by Extraction of Differences

IP.com Disclosure Number: IPCOM000102386D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 3 page(s) / 131K

Publishing Venue

IBM

Related People

Rindtorff, K: AUTHOR

Abstract

When a program update is prepared, it should be distributed to all registered users as quickly as possible and at minimum cost. Where distribution of the entire update is too expensive, at least a patch should be made available.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 47% of the total text.

Compression of Updated Data by Extraction of Differences

       When a program update is prepared, it should be
distributed to all registered users as quickly as possible and at
minimum cost. Where distribution of the entire update is too
expensive, at least a patch should be made available.

      The method presented here facilitates the preparation of a
patch in several ways.  A patch can be developed and tested in the
preferred programming language.  The newly compiled version is
compared with the original and differences are extracted and stored
in a compact form. This data is made available to all users as a
patch.  A copy of the new version is created by the user who is
provided with the original data and the extracted differences.
Extracting differences

      To determine differences between the original data (original)
and the modified data (update), a parallel scan is performed.  Each
time a difference is found, it is encoded, and the algorithm tries to
synchronize again.  This means finding a displacement between both
data versions so that they match as closely as possible.
Fundamental operations

      By sequentially processing the data of the original and the
update, the encoding of the positions is eliminated. All operations
cover the data at the actual position.  When the update is later
recreated, the original is again processed sequentially.  The
fundamental operations used to encode the extracted differences are:

      Command     Explanation
COPY           A sequence of data from the original is equal to the
data of the update and may later be copied from the original when the
update is reconstructed.  Only the number of characters must be
given.  No sequence data is appended to the command.
CHANGE         A sequence of data from the original is different from
the data of the update and must later be changed when the update is
reconstructed.  A copy of the changed data is appended to the
command.
SKIP           A sequence of data from the original does not appear
in the update and may later be skipped in the original when the
update is reconstructed.  Only the number of the skipped characters
is needed.  No sequence data must be appended to the command.
INSERT         A sequence of data from the update does not appear in
the data of the original and must later be inserted in the update for
reconstruction.  A copy of the data is appended to the command.
PASTE          A sequence of data from the update does appear at a
different position in the data of the original or the update and must
later be pasted into the update for reconstruction. Only the length
and the displacement of the data sequence must be given.  No further
data must be appended to the command.

      Example: The differences between the following two sentences
are to be encoded.
      Original: The brown lazy fox skips over the dog.
      Update:   The quic...