System and method for intra-package delta compression of data

• US 20050022175A1
• Filed: 07/21/2003
• Published: 01/27/2005
• Est. Priority Date: 07/21/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McGuire, Thomas, Petrov, Alexander, Sliger, Michael V., Shende, Manojkumar
• Granted Patent: US 7,600,225 B2
• Time in Patent Office: Days
• US Class Current: 717/169
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A system and method for providing file data, such as a set of files for updating a computer system, in a self-contained package, in which the package size is significantly reduced via delta compression. A build mechanism examines files to be distributed, and generates a self-contained package containing files and deltas. To this end, a directed graph is built from the sizes of the various base file and delta file possibilities, and a minimum spanning tree computation selects the files that result in the smallest package. A base file may have multiple deltas applied to synthesize multiple files, and any base file may itself have been previously synthesized from another base file and a delta. A client extraction mechanism, optionally provided with the package, works with the contents of the package as directed by a manifest to synthesize target files from the base files and the contained deltas.

Claims

1. In a computing environment, a method comprising:

receiving information corresponding to a plurality of source files;

selecting a first source file as a base file;

generating a delta from the first source file and a second source file; and

packaging the base file and the delta into a self-contained package.

2. The method of claim 1 further comprising, packaging data for directing a client extractor to synthesize a target file corresponding to the second source file from the base file and the delta.

3. The method of claim 1 further comprising, setting at least one file name by which a client extractor may synthesize a target file corresponding to the second source file from the base file and the delta.

4. The method of claim 1 wherein the first source file and the second source file are not different versions of the same file.

5. The method of claim 1 wherein the first source file and the second source file are not different language translations of the same file.

6. The method of claim 1 wherein the first source file and the second source file are different language translations of the same file.

7. The method of claim 1 wherein selecting the first source file as the base file comprises selecting the source file based on package size considerations.

8. The method of claim 7 further comprising constructing a directed graph of file sizes based on multiple possible pairings of source files, and selecting the first source file based on information in the directed graph.

9. The method of claim 8 wherein selecting the first source file as the base file comprises applying a minimum spanning tree or like algorithm to the directed graph.

10. The method of claim 1 wherein selecting the first source file as the base file comprises computing sizes of possible deltas and selecting the first source file based on the sizes.

11. The method of claim 1 further comprising, providing the package to a recipient, the recipient applying the delta to the first source file to synthesize the second source file.

12. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

13. In a computing environment, a method comprising:

receiving a package comprising at least one base file and a plurality of deltas; and

applying a delta in the package to a base file to synthesize a target file.

14. The method of claim 13 wherein applying the delta to the base file comprises applying the delta to a base file included in the package.

15. The method of claim 13 wherein applying the delta to the base file comprises applying the delta to a base file synthesized from another delta and another base file.

16. The method of claim 13 further comprising interpreting a data file to determine to which base file each delta is to be applied.

17. The method of claim 14 wherein the data file comprises a set of instructions including instructions that identify a particular base file to which a particular delta file is to be applied.

18. The method of claim 13 further comprising, executing a setup program.

19. The method of claim 18 wherein the setup program is executed after each delta has been applied to a corresponding base file.

20. The method of claim 13 further comprising, deleting the deltas from a temporary directory.

21. The method of claim 13 further comprising, applying another delta to the synthesized target file to synthesize another target file.

22. The method of claim 13 further comprising, applying at least two deltas to a common base file to synthesize at least two target files.

23. A computer-readable medium having computer-executable instructions for performing the method of claim 13.

24. A computer-readable medium having stored thereon a data structure, comprising:

a first set of data comprising a base file; and

a second set of data comprising a delta file, the delta file packaged with the base file and configured to synthesize a target file when applied to the base file.

25. The data structure of claim 24 further comprising a third set of data comprising another delta file.

26. The data structure of claim 24 wherein the other delta is configured to synthesize another target file when applied to the base file.

27. The data structure of claim 24 wherein the other delta is configured to synthesize another target file when applied to the target file.

28. The data structure of claim 24 further comprising means for transmitting the data structure from a source to a client recipient.

29. The data structure of claim 24 further comprising a third set of data comprising data for directing an extraction program.

30. The data structure of claim 24 further comprising a third set of data comprising an extraction program.

31. The data structure of claim 30 further comprising a fourth set of data comprising data for directing the extraction program.

32. The data structure of claim 24 further comprising a third set of data comprising a file that is neither a base file nor a delta.

33. The data structure of claim 32 wherein the file that is neither a base file nor a delta is compressed.

34. In a computing environment, a system comprising:

means for selecting a first source file as a base file from which a second source file may be derived by applying a delta; and

means for packaging the base file and the delta into a self-contained package.